LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineCopyPropagation.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 133 135 98.5 %
Date: 2018-02-23 15:42:53 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This is an extremely simple MachineInstr-level copy propagation pass.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/ADT/DenseMap.h"
      15             : #include "llvm/ADT/STLExtras.h"
      16             : #include "llvm/ADT/SetVector.h"
      17             : #include "llvm/ADT/SmallVector.h"
      18             : #include "llvm/ADT/Statistic.h"
      19             : #include "llvm/ADT/iterator_range.h"
      20             : #include "llvm/CodeGen/MachineBasicBlock.h"
      21             : #include "llvm/CodeGen/MachineFunction.h"
      22             : #include "llvm/CodeGen/MachineFunctionPass.h"
      23             : #include "llvm/CodeGen/MachineInstr.h"
      24             : #include "llvm/CodeGen/MachineOperand.h"
      25             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      26             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      27             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      28             : #include "llvm/MC/MCRegisterInfo.h"
      29             : #include "llvm/Pass.h"
      30             : #include "llvm/Support/Debug.h"
      31             : #include "llvm/Support/raw_ostream.h"
      32             : #include <cassert>
      33             : #include <iterator>
      34             : 
      35             : using namespace llvm;
      36             : 
      37             : #define DEBUG_TYPE "machine-cp"
      38             : 
      39             : STATISTIC(NumDeletes, "Number of dead copies deleted");
      40             : 
      41             : namespace {
      42             : 
      43             : using RegList = SmallVector<unsigned, 4>;
      44             : using SourceMap = DenseMap<unsigned, RegList>;
      45             : using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
      46             : 
      47       51303 :   class MachineCopyPropagation : public MachineFunctionPass {
      48             :     const TargetRegisterInfo *TRI;
      49             :     const TargetInstrInfo *TII;
      50             :     const MachineRegisterInfo *MRI;
      51             : 
      52             :   public:
      53             :     static char ID; // Pass identification, replacement for typeid
      54             : 
      55       51588 :     MachineCopyPropagation() : MachineFunctionPass(ID) {
      56       17196 :       initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
      57       17196 :     }
      58             : 
      59       17088 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      60       17088 :       AU.setPreservesCFG();
      61       17088 :       MachineFunctionPass::getAnalysisUsage(AU);
      62       17088 :     }
      63             : 
      64             :     bool runOnMachineFunction(MachineFunction &MF) override;
      65             : 
      66       17092 :     MachineFunctionProperties getRequiredProperties() const override {
      67       34184 :       return MachineFunctionProperties().set(
      68       17092 :           MachineFunctionProperties::Property::NoVRegs);
      69             :     }
      70             : 
      71             :   private:
      72             :     void ClobberRegister(unsigned Reg);
      73             :     void ReadRegister(unsigned Reg);
      74             :     void CopyPropagateBlock(MachineBasicBlock &MBB);
      75             :     bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
      76             : 
      77             :     /// Candidates for deletion.
      78             :     SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
      79             : 
      80             :     /// Def -> available copies map.
      81             :     Reg2MIMap AvailCopyMap;
      82             : 
      83             :     /// Def -> copies map.
      84             :     Reg2MIMap CopyMap;
      85             : 
      86             :     /// Src -> Def map
      87             :     SourceMap SrcMap;
      88             : 
      89             :     bool Changed;
      90             :   };
      91             : 
      92             : } // end anonymous namespace
      93             : 
      94             : char MachineCopyPropagation::ID = 0;
      95             : 
      96             : char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
      97             : 
      98      160848 : INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
      99             :                 "Machine Copy Propagation Pass", false, false)
     100             : 
     101             : /// Remove any entry in \p Map where the register is a subregister or equal to
     102             : /// a register contained in \p Regs.
     103       53133 : static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs,
     104             :                               const TargetRegisterInfo &TRI) {
     105      164953 :   for (unsigned Reg : Regs) {
     106             :     // Source of copy is no longer available for propagation.
     107      218606 :     for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid(); ++SR)
     108      162696 :       Map.erase(*SR);
     109             :   }
     110       53133 : }
     111             : 
     112             : /// Remove any entry in \p Map that is marked clobbered in \p RegMask.
     113             : /// The map will typically have a lot fewer entries than the regmask clobbers,
     114             : /// so this is more efficient than iterating the clobbered registers and calling
     115             : /// ClobberRegister() on them.
     116      361512 : static void removeClobberedRegsFromMap(Reg2MIMap &Map,
     117             :                                        const MachineOperand &RegMask) {
     118     1215087 :   for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
     119             :        I = Next) {
     120             :     Next = std::next(I);
     121      492063 :     unsigned Reg = I->first;
     122      492063 :     if (RegMask.clobbersPhysReg(Reg))
     123             :       Map.erase(I);
     124             :   }
     125      361512 : }
     126             : 
     127     2736307 : void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
     128    33006492 :   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     129    27533878 :     CopyMap.erase(*AI);
     130    27533878 :     AvailCopyMap.erase(*AI);
     131             : 
     132    27533878 :     SourceMap::iterator SI = SrcMap.find(*AI);
     133    13766939 :     if (SI != SrcMap.end()) {
     134       32876 :       removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
     135             :       SrcMap.erase(SI);
     136             :     }
     137             :   }
     138     2736307 : }
     139             : 
     140     4214101 : void MachineCopyPropagation::ReadRegister(unsigned Reg) {
     141             :   // If 'Reg' is defined by a copy, the copy is no longer a candidate
     142             :   // for elimination.
     143    55212326 :   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     144    46784124 :     Reg2MIMap::iterator CI = CopyMap.find(*AI);
     145    23392062 :     if (CI != CopyMap.end()) {
     146             :       DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump());
     147      507354 :       MaybeDeadCopies.remove(CI->second);
     148             :     }
     149             :   }
     150     4214101 : }
     151             : 
     152             : /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
     153             : /// This fact may have been obscured by sub register usage or may not be true at
     154             : /// all even though Src and Def are subregisters of the registers used in
     155             : /// PreviousCopy. e.g.
     156             : /// isNopCopy("ecx = COPY eax", AX, CX) == true
     157             : /// isNopCopy("ecx = COPY eax", AH, CL) == false
     158        8220 : static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
     159             :                       unsigned Def, const TargetRegisterInfo *TRI) {
     160        8220 :   unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
     161        8220 :   unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
     162        8220 :   if (Src == PreviousSrc) {
     163             :     assert(Def == PreviousDef);
     164             :     return true;
     165             :   }
     166       12118 :   if (!TRI->isSubRegister(PreviousSrc, Src))
     167             :     return false;
     168          28 :   unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
     169          28 :   return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
     170             : }
     171             : 
     172             : /// Remove instruction \p Copy if there exists a previous copy that copies the
     173             : /// register \p Src to the register \p Def; This may happen indirectly by
     174             : /// copying the super registers.
     175      329286 : bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
     176             :                                               unsigned Def) {
     177             :   // Avoid eliminating a copy from/to a reserved registers as we cannot predict
     178             :   // the value (Example: The sparc zero register is writable but stays zero).
     179      983462 :   if (MRI->isReserved(Src) || MRI->isReserved(Def))
     180             :     return false;
     181             : 
     182             :   // Search for an existing copy.
     183      320990 :   Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
     184      320990 :   if (CI == AvailCopyMap.end())
     185             :     return false;
     186             : 
     187             :   // Check that the existing copy uses the correct sub registers.
     188        8223 :   MachineInstr &PrevCopy = *CI->second;
     189       16446 :   if (PrevCopy.getOperand(0).isDead())
     190             :     return false;
     191        8220 :   if (!isNopCopy(PrevCopy, Src, Def, TRI))
     192             :     return false;
     193             : 
     194             :   DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
     195             : 
     196             :   // Copy was redundantly redefining either Src or Def. Remove earlier kill
     197             :   // flags between Copy and PrevCopy because the value will be reused now.
     198             :   assert(Copy.isCopy());
     199        2186 :   unsigned CopyDef = Copy.getOperand(0).getReg();
     200             :   assert(CopyDef == Src || CopyDef == Def);
     201             :   for (MachineInstr &MI :
     202        2186 :        make_range(PrevCopy.getIterator(), Copy.getIterator()))
     203       35689 :     MI.clearRegisterKills(CopyDef, TRI);
     204             : 
     205        2186 :   Copy.eraseFromParent();
     206        2186 :   Changed = true;
     207             :   ++NumDeletes;
     208        2186 :   return true;
     209             : }
     210             : 
     211      306623 : void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
     212             :   DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
     213             : 
     214     3656567 :   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
     215     3043321 :     MachineInstr *MI = &*I;
     216             :     ++I;
     217             : 
     218     6086642 :     if (MI->isCopy()) {
     219      165156 :       unsigned Def = MI->getOperand(0).getReg();
     220      165156 :       unsigned Src = MI->getOperand(1).getReg();
     221             : 
     222             :       assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
     223             :              !TargetRegisterInfo::isVirtualRegister(Src) &&
     224             :              "MachineCopyPropagation should be run after register allocation!");
     225             : 
     226             :       // The two copies cancel out and the source of the first copy
     227             :       // hasn't been overridden, eliminate the second one. e.g.
     228             :       //  %ecx = COPY %eax
     229             :       //  ... nothing clobbered eax.
     230             :       //  %eax = COPY %ecx
     231             :       // =>
     232             :       //  %ecx = COPY %eax
     233             :       //
     234             :       // or
     235             :       //
     236             :       //  %ecx = COPY %eax
     237             :       //  ... nothing clobbered eax.
     238             :       //  %ecx = COPY %eax
     239             :       // =>
     240             :       //  %ecx = COPY %eax
     241      165156 :       if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
     242        2186 :         continue;
     243             : 
     244             :       // If Src is defined by a previous copy, the previous copy cannot be
     245             :       // eliminated.
     246      162970 :       ReadRegister(Src);
     247      388346 :       for (const MachineOperand &MO : MI->implicit_operands()) {
     248       32738 :         if (!MO.isReg() || !MO.readsReg())
     249        1535 :           continue;
     250       29668 :         unsigned Reg = MO.getReg();
     251       29668 :         if (!Reg)
     252           0 :           continue;
     253       29668 :         ReadRegister(Reg);
     254             :       }
     255             : 
     256             :       DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
     257             : 
     258             :       // Copy is now a candidate for deletion.
     259      325940 :       if (!MRI->isReserved(Def))
     260      161678 :         MaybeDeadCopies.insert(MI);
     261             : 
     262             :       // If 'Def' is previously source of another copy, then this earlier copy's
     263             :       // source is no longer available. e.g.
     264             :       // %xmm9 = copy %xmm2
     265             :       // ...
     266             :       // %xmm2 = copy %xmm0
     267             :       // ...
     268             :       // %xmm2 = copy %xmm9
     269      162970 :       ClobberRegister(Def);
     270      388346 :       for (const MachineOperand &MO : MI->implicit_operands()) {
     271       92074 :         if (!MO.isReg() || !MO.isDef())
     272       29668 :           continue;
     273        1535 :         unsigned Reg = MO.getReg();
     274        1535 :         if (!Reg)
     275           0 :           continue;
     276        1535 :         ClobberRegister(Reg);
     277             :       }
     278             : 
     279             :       // Remember Def is defined by the copy.
     280      763551 :       for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
     281             :            ++SR) {
     282      875222 :         CopyMap[*SR] = MI;
     283      875222 :         AvailCopyMap[*SR] = MI;
     284             :       }
     285             : 
     286             :       // Remember source that's copied to Def. Once it's clobbered, then
     287             :       // it's no longer available for copy propagation.
     288      162970 :       RegList &DestList = SrcMap[Src];
     289      162970 :       if (!is_contained(DestList, Def))
     290      158482 :           DestList.push_back(Def);
     291             : 
     292      162970 :       continue;
     293             :     }
     294             : 
     295             :     // Not a copy.
     296             :     SmallVector<unsigned, 2> Defs;
     297             :     const MachineOperand *RegMask = nullptr;
     298    28713849 :     for (const MachineOperand &MO : MI->operands()) {
     299    12917842 :       if (MO.isRegMask())
     300             :         RegMask = &MO;
     301    12917842 :       if (!MO.isReg())
     302    13432516 :         continue;
     303     8368945 :       unsigned Reg = MO.getReg();
     304     8368945 :       if (!Reg)
     305     1762920 :         continue;
     306             : 
     307             :       assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
     308             :              "MachineCopyPropagation should be run after register allocation!");
     309             : 
     310     9177827 :       if (MO.isDef()) {
     311     2571802 :         Defs.push_back(Reg);
     312     2571802 :         continue;
     313             :       } else if (MO.readsReg())
     314     4021463 :         ReadRegister(Reg);
     315             :     }
     316             : 
     317             :     // The instruction has a register mask operand which means that it clobbers
     318             :     // a large set of registers.  Treat clobbered registers the same way as
     319             :     // defined registers.
     320     2878165 :     if (RegMask) {
     321             :       // Erase any MaybeDeadCopies whose destination register is clobbered.
     322             :       for (SmallSetVector<MachineInstr *, 8>::iterator DI =
     323             :                MaybeDeadCopies.begin();
     324      204230 :            DI != MaybeDeadCopies.end();) {
     325       23474 :         MachineInstr *MaybeDead = *DI;
     326       23474 :         unsigned Reg = MaybeDead->getOperand(0).getReg();
     327             :         assert(!MRI->isReserved(Reg));
     328             : 
     329       46905 :         if (!RegMask->clobbersPhysReg(Reg)) {
     330       23431 :           ++DI;
     331       23431 :           continue;
     332             :         }
     333             : 
     334             :         DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
     335             :               MaybeDead->dump());
     336             : 
     337             :         // erase() will return the next valid iterator pointing to the next
     338             :         // element after the erased one.
     339          43 :         DI = MaybeDeadCopies.erase(DI);
     340          43 :         MaybeDead->eraseFromParent();
     341          43 :         Changed = true;
     342             :         ++NumDeletes;
     343             :       }
     344             : 
     345      180756 :       removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
     346      180756 :       removeClobberedRegsFromMap(CopyMap, *RegMask);
     347      180756 :       for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
     348      259991 :            I != E; I = Next) {
     349             :         Next = std::next(I);
     350      158470 :         if (RegMask->clobbersPhysReg(I->first)) {
     351       20257 :           removeRegsFromMap(AvailCopyMap, I->second, *TRI);
     352             :           SrcMap.erase(I);
     353             :         }
     354             :       }
     355             :     }
     356             : 
     357             :     // Any previous copy definition or reading the Defs is no longer available.
     358     8021769 :     for (unsigned Reg : Defs)
     359     2571802 :       ClobberRegister(Reg);
     360             :   }
     361             : 
     362             :   // If MBB doesn't have successors, delete the copies whose defs are not used.
     363             :   // If MBB does have successors, then conservative assume the defs are live-out
     364             :   // since we don't want to trust live-in lists.
     365      306623 :   if (MBB.succ_empty()) {
     366      167738 :     for (MachineInstr *MaybeDead : MaybeDeadCopies) {
     367             :       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
     368          50 :       MaybeDead->eraseFromParent();
     369          50 :       Changed = true;
     370             :       ++NumDeletes;
     371             :     }
     372             :   }
     373             : 
     374             :   MaybeDeadCopies.clear();
     375      306623 :   AvailCopyMap.clear();
     376      306623 :   CopyMap.clear();
     377      306623 :   SrcMap.clear();
     378      306623 : }
     379             : 
     380      158698 : bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
     381      158698 :   if (skipFunction(MF.getFunction()))
     382             :     return false;
     383             : 
     384      158605 :   Changed = false;
     385             : 
     386      158605 :   TRI = MF.getSubtarget().getRegisterInfo();
     387      158605 :   TII = MF.getSubtarget().getInstrInfo();
     388      158605 :   MRI = &MF.getRegInfo();
     389             : 
     390      465228 :   for (MachineBasicBlock &MBB : MF)
     391      306623 :     CopyPropagateBlock(MBB);
     392             : 
     393      158605 :   return Changed;
     394             : }

Generated by: LCOV version 1.13