LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineCopyPropagation.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 146 148 98.6 %
Date: 2017-09-14 15:23:50 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/MC/MCRegisterInfo.h"
      27             : #include "llvm/Pass.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include "llvm/Target/TargetInstrInfo.h"
      31             : #include "llvm/Target/TargetRegisterInfo.h"
      32             : #include "llvm/Target/TargetSubtargetInfo.h"
      33             : #include <cassert>
      34             : #include <iterator>
      35             : 
      36             : using namespace llvm;
      37             : 
      38             : #define DEBUG_TYPE "machine-cp"
      39             : 
      40             : STATISTIC(NumDeletes, "Number of dead copies deleted");
      41             : 
      42             : namespace {
      43             : 
      44             : using RegList = SmallVector<unsigned, 4>;
      45             : using SourceMap = DenseMap<unsigned, RegList>;
      46             : using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
      47             : 
      48       91938 :   class MachineCopyPropagation : public MachineFunctionPass {
      49             :     const TargetRegisterInfo *TRI;
      50             :     const TargetInstrInfo *TII;
      51             :     const MachineRegisterInfo *MRI;
      52             : 
      53             :   public:
      54             :     static char ID; // Pass identification, replacement for typeid
      55             : 
      56       77070 :     MachineCopyPropagation() : MachineFunctionPass(ID) {
      57       15414 :       initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
      58       15414 :     }
      59             : 
      60       15359 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      61       15359 :       AU.setPreservesCFG();
      62       15359 :       MachineFunctionPass::getAnalysisUsage(AU);
      63       15359 :     }
      64             : 
      65             :     bool runOnMachineFunction(MachineFunction &MF) override;
      66             : 
      67       15363 :     MachineFunctionProperties getRequiredProperties() const override {
      68       46089 :       return MachineFunctionProperties().set(
      69       46089 :           MachineFunctionProperties::Property::NoVRegs);
      70             :     }
      71             : 
      72             :   private:
      73             :     void ClobberRegister(unsigned Reg);
      74             :     void ReadRegister(unsigned Reg);
      75             :     void CopyPropagateBlock(MachineBasicBlock &MBB);
      76             :     bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
      77             : 
      78             :     /// Candidates for deletion.
      79             :     SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
      80             : 
      81             :     /// Def -> available copies map.
      82             :     Reg2MIMap AvailCopyMap;
      83             : 
      84             :     /// Def -> copies map.
      85             :     Reg2MIMap CopyMap;
      86             : 
      87             :     /// Src -> Def map
      88             :     SourceMap SrcMap;
      89             : 
      90             :     bool Changed;
      91             :   };
      92             : 
      93             : } // end anonymous namespace
      94             : 
      95             : char MachineCopyPropagation::ID = 0;
      96             : 
      97             : char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
      98             : 
      99      197441 : INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
     100             :                 "Machine Copy Propagation Pass", false, false)
     101             : 
     102             : /// Remove any entry in \p Map where the register is a subregister or equal to
     103             : /// a register contained in \p Regs.
     104       54328 : static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs,
     105             :                               const TargetRegisterInfo &TRI) {
     106      220211 :   for (unsigned Reg : Regs) {
     107             :     // Source of copy is no longer available for propagation.
     108      282524 :     for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid(); ++SR)
     109      336140 :       Map.erase(*SR);
     110             :   }
     111       54328 : }
     112             : 
     113             : /// Remove any entry in \p Map that is marked clobbered in \p RegMask.
     114             : /// The map will typically have a lot fewer entries than the regmask clobbers,
     115             : /// so this is more efficient than iterating the clobbered registers and calling
     116             : /// ClobberRegister() on them.
     117      348798 : static void removeClobberedRegsFromMap(Reg2MIMap &Map,
     118             :                                        const MachineOperand &RegMask) {
     119     1520723 :   for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
     120             :        I = Next) {
     121      474329 :     Next = std::next(I);
     122      474329 :     unsigned Reg = I->first;
     123      474329 :     if (RegMask.clobbersPhysReg(Reg))
     124      302003 :       Map.erase(I);
     125             :   }
     126      348798 : }
     127             : 
     128     2455938 : void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
     129    30747624 :   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     130    25835748 :     CopyMap.erase(*AI);
     131    25835748 :     AvailCopyMap.erase(*AI);
     132             : 
     133    25835748 :     SourceMap::iterator SI = SrcMap.find(*AI);
     134    38753622 :     if (SI != SrcMap.end()) {
     135       34749 :       removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
     136       34749 :       SrcMap.erase(SI);
     137             :     }
     138             :   }
     139     2455938 : }
     140             : 
     141     3837602 : void MachineCopyPropagation::ReadRegister(unsigned Reg) {
     142             :   // If 'Reg' is defined by a copy, the copy is no longer a candidate
     143             :   // for elimination.
     144    51942540 :   for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
     145    44267336 :     Reg2MIMap::iterator CI = CopyMap.find(*AI);
     146    66401004 :     if (CI != CopyMap.end()) {
     147             :       DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump());
     148      488994 :       MaybeDeadCopies.remove(CI->second);
     149             :     }
     150             :   }
     151     3837602 : }
     152             : 
     153             : /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
     154             : /// This fact may have been obscured by sub register usage or may not be true at
     155             : /// all even though Src and Def are subregisters of the registers used in
     156             : /// PreviousCopy. e.g.
     157             : /// isNopCopy("ecx = COPY eax", AX, CX) == true
     158             : /// isNopCopy("ecx = COPY eax", AH, CL) == false
     159        8473 : static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
     160             :                       unsigned Def, const TargetRegisterInfo *TRI) {
     161        8473 :   unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
     162        8473 :   unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
     163        8473 :   if (Src == PreviousSrc) {
     164             :     assert(Def == PreviousDef);
     165             :     return true;
     166             :   }
     167       13078 :   if (!TRI->isSubRegister(PreviousSrc, Src))
     168             :     return false;
     169          29 :   unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
     170          29 :   return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
     171             : }
     172             : 
     173             : /// Remove instruction \p Copy if there exists a previous copy that copies the
     174             : /// register \p Src to the register \p Def; This may happen indirectly by
     175             : /// copying the super registers.
     176      325732 : bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
     177             :                                               unsigned Def) {
     178             :   // Avoid eliminating a copy from/to a reserved registers as we cannot predict
     179             :   // the value (Example: The sparc zero register is writable but stays zero).
     180      972990 :   if (MRI->isReserved(Src) || MRI->isReserved(Def))
     181             :     return false;
     182             : 
     183             :   // Search for an existing copy.
     184      317708 :   Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
     185      953124 :   if (CI == AvailCopyMap.end())
     186             :     return false;
     187             : 
     188             :   // Check that the existing copy uses the correct sub registers.
     189        8473 :   MachineInstr &PrevCopy = *CI->second;
     190        8473 :   if (!isNopCopy(PrevCopy, Src, Def, TRI))
     191             :     return false;
     192             : 
     193             :   DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
     194             : 
     195             :   // Copy was redundantly redefining either Src or Def. Remove earlier kill
     196             :   // flags between Copy and PrevCopy because the value will be reused now.
     197             :   assert(Copy.isCopy());
     198        1959 :   unsigned CopyDef = Copy.getOperand(0).getReg();
     199             :   assert(CopyDef == Src || CopyDef == Def);
     200             :   for (MachineInstr &MI :
     201       42213 :        make_range(PrevCopy.getIterator(), Copy.getIterator()))
     202       34377 :     MI.clearRegisterKills(CopyDef, TRI);
     203             : 
     204        1959 :   Copy.eraseFromParent();
     205        1959 :   Changed = true;
     206        1959 :   ++NumDeletes;
     207        1959 :   return true;
     208             : }
     209             : 
     210      277014 : void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
     211             :   DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
     212             : 
     213     3723396 :   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
     214     2892353 :     MachineInstr *MI = &*I;
     215     2892354 :     ++I;
     216             : 
     217     5784708 :     if (MI->isCopy()) {
     218      163341 :       unsigned Def = MI->getOperand(0).getReg();
     219      163341 :       unsigned Src = MI->getOperand(1).getReg();
     220             : 
     221             :       assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
     222             :              !TargetRegisterInfo::isVirtualRegister(Src) &&
     223             :              "MachineCopyPropagation should be run after register allocation!");
     224             : 
     225             :       // The two copies cancel out and the source of the first copy
     226             :       // hasn't been overridden, eliminate the second one. e.g.
     227             :       //  %ECX<def> = COPY %EAX
     228             :       //  ... nothing clobbered EAX.
     229             :       //  %EAX<def> = COPY %ECX
     230             :       // =>
     231             :       //  %ECX<def> = COPY %EAX
     232             :       //
     233             :       // or
     234             :       //
     235             :       //  %ECX<def> = COPY %EAX
     236             :       //  ... nothing clobbered EAX.
     237             :       //  %ECX<def> = COPY %EAX
     238             :       // =>
     239             :       //  %ECX<def> = COPY %EAX
     240      163341 :       if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def))
     241        1959 :         continue;
     242             : 
     243             :       // If Src is defined by a previous copy, the previous copy cannot be
     244             :       // eliminated.
     245      161382 :       ReadRegister(Src);
     246      353225 :       for (const MachineOperand &MO : MI->implicit_operands()) {
     247       31975 :         if (!MO.isReg() || !MO.readsReg())
     248        1514 :           continue;
     249       28947 :         unsigned Reg = MO.getReg();
     250       28947 :         if (!Reg)
     251           0 :           continue;
     252       28947 :         ReadRegister(Reg);
     253             :       }
     254             : 
     255             :       DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
     256             : 
     257             :       // Copy is now a candidate for deletion.
     258      322764 :       if (!MRI->isReserved(Def))
     259      160163 :         MaybeDeadCopies.insert(MI);
     260             : 
     261             :       // If 'Def' is previously source of another copy, then this earlier copy's
     262             :       // source is no longer available. e.g.
     263             :       // %xmm9<def> = copy %xmm2
     264             :       // ...
     265             :       // %xmm2<def> = copy %xmm0
     266             :       // ...
     267             :       // %xmm2<def> = copy %xmm9
     268      161382 :       ClobberRegister(Def);
     269      353225 :       for (const MachineOperand &MO : MI->implicit_operands()) {
     270       89869 :         if (!MO.isReg() || !MO.isDef())
     271       28947 :           continue;
     272        1514 :         unsigned Reg = MO.getReg();
     273        1514 :         if (!Reg)
     274           0 :           continue;
     275        1514 :         ClobberRegister(Reg);
     276             :       }
     277             : 
     278             :       // Remember Def is defined by the copy.
     279      752677 :       for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
     280             :            ++SR) {
     281     1289739 :         CopyMap[*SR] = MI;
     282      859826 :         AvailCopyMap[*SR] = MI;
     283             :       }
     284             : 
     285             :       // Remember source that's copied to Def. Once it's clobbered, then
     286             :       // it's no longer available for copy propagation.
     287      322764 :       RegList &DestList = SrcMap[Src];
     288      161382 :       if (!is_contained(DestList, Def))
     289      156091 :         DestList.push_back(Def);
     290             : 
     291      161382 :       continue;
     292             :     }
     293             : 
     294             :     // Not a copy.
     295     5458026 :     SmallVector<unsigned, 2> Defs;
     296     2729013 :     const MachineOperand *RegMask = nullptr;
     297    17434646 :     for (const MachineOperand &MO : MI->operands()) {
     298    11976620 :       if (MO.isRegMask())
     299      174399 :         RegMask = &MO;
     300    11976620 :       if (!MO.isReg())
     301    12664046 :         continue;
     302     7630501 :       unsigned Reg = MO.getReg();
     303     7630501 :       if (!Reg)
     304     1678766 :         continue;
     305             : 
     306             :       assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
     307             :              "MachineCopyPropagation should be run after register allocation!");
     308             : 
     309     8244777 :       if (MO.isDef()) {
     310     2293042 :         Defs.push_back(Reg);
     311     2293042 :         continue;
     312     3647273 :       } else if (MO.readsReg())
     313     3647273 :         ReadRegister(Reg);
     314             :     }
     315             : 
     316             :     // The instruction has a register mask operand which means that it clobbers
     317             :     // a large set of registers.  Treat clobbered registers the same way as
     318             :     // defined registers.
     319     2729013 :     if (RegMask) {
     320             :       // Erase any MaybeDeadCopies whose destination register is clobbered.
     321             :       for (SmallSetVector<MachineInstr *, 8>::iterator DI =
     322      348798 :                MaybeDeadCopies.begin();
     323      393710 :            DI != MaybeDeadCopies.end();) {
     324       22456 :         MachineInstr *MaybeDead = *DI;
     325       22456 :         unsigned Reg = MaybeDead->getOperand(0).getReg();
     326             :         assert(!MRI->isReserved(Reg));
     327             : 
     328       44870 :         if (!RegMask->clobbersPhysReg(Reg)) {
     329       22414 :           ++DI;
     330       22414 :           continue;
     331             :         }
     332             : 
     333             :         DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
     334             :               MaybeDead->dump());
     335             : 
     336             :         // erase() will return the next valid iterator pointing to the next
     337             :         // element after the erased one.
     338          42 :         DI = MaybeDeadCopies.erase(DI);
     339          42 :         MaybeDead->eraseFromParent();
     340          42 :         Changed = true;
     341             :         ++NumDeletes;
     342             :       }
     343             : 
     344      174399 :       removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
     345      174399 :       removeClobberedRegsFromMap(CopyMap, *RegMask);
     346      348798 :       for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
     347      251217 :            I != E; I = Next) {
     348       76818 :         Next = std::next(I);
     349      153636 :         if (RegMask->clobbersPhysReg(I->first)) {
     350       19579 :           removeRegsFromMap(AvailCopyMap, I->second, *TRI);
     351       19579 :           SrcMap.erase(I);
     352             :         }
     353             :       }
     354             :     }
     355             : 
     356             :     // Any previous copy definition or reading the Defs is no longer available.
     357    10480081 :     for (unsigned Reg : Defs)
     358     2293042 :       ClobberRegister(Reg);
     359             :   }
     360             : 
     361             :   // If MBB doesn't have successors, delete the copies whose defs are not used.
     362             :   // If MBB does have successors, then conservative assume the defs are live-out
     363             :   // since we don't want to trust live-in lists.
     364      277015 :   if (MBB.succ_empty()) {
     365      430262 :     for (MachineInstr *MaybeDead : MaybeDeadCopies) {
     366             :       assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
     367          44 :       MaybeDead->eraseFromParent();
     368          44 :       Changed = true;
     369          44 :       ++NumDeletes;
     370             :     }
     371             :   }
     372             : 
     373      554030 :   MaybeDeadCopies.clear();
     374      277015 :   AvailCopyMap.clear();
     375      277015 :   CopyMap.clear();
     376      277015 :   SrcMap.clear();
     377      277015 : }
     378             : 
     379      134794 : bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
     380      134794 :   if (skipFunction(*MF.getFunction()))
     381             :     return false;
     382             : 
     383      134737 :   Changed = false;
     384             : 
     385      134737 :   TRI = MF.getSubtarget().getRegisterInfo();
     386      134737 :   TII = MF.getSubtarget().getInstrInfo();
     387      134737 :   MRI = &MF.getRegInfo();
     388             : 
     389      681226 :   for (MachineBasicBlock &MBB : MF)
     390      277015 :     CopyPropagateBlock(MBB);
     391             : 
     392      134737 :   return Changed;
     393             : }

Generated by: LCOV version 1.13