lib/CodeGen/MachineCopyPropagation.cpp

   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 #define DEBUG_TYPE "codegen-cp"
  15 #include "llvm/CodeGen/Passes.h"
  16 #include "llvm/Pass.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/Target/TargetRegisterInfo.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include "llvm/ADT/BitVector.h"
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/DenseSet.h"
  26 #include "llvm/ADT/SetVector.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include "llvm/ADT/Statistic.h"
  29 using namespace llvm;
  30
  31 STATISTIC(NumDeletes, "Number of dead copies deleted");
  32
  33 namespace {
  34   class MachineCopyPropagation : public MachineFunctionPass {
  35     const TargetRegisterInfo *TRI;
  36     BitVector ReservedRegs;
  37
  38   public:
  39     static char ID; // Pass identification, replacement for typeid
  40     MachineCopyPropagation() : MachineFunctionPass(ID) {
  41      initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
  42     }
  43
  44     virtual bool runOnMachineFunction(MachineFunction &MF);
  45
  46   private:
  47     void SourceNoLongerAvailable(unsigned Reg,
  48                                  DenseMap<unsigned, DenseSet<unsigned> > &SrcMap,
  49                                DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
  50     bool CopyPropagateBlock(MachineBasicBlock &MBB);
  51   };
  52 }
  53 char MachineCopyPropagation::ID = 0;
  54 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
  55
  56 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
  57                 "Machine Copy Propagation Pass", false, false)
  58
  59 void
  60 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
  61                               DenseMap<unsigned, DenseSet<unsigned> > &SrcMap,
  62                               DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
  63   DenseMap<unsigned, DenseSet<unsigned> >::iterator SI = SrcMap.find(Reg);
  64   if (SI != SrcMap.end()) {
  65     const DenseSet<unsigned>& Defs = SI->second;
  66     for (DenseSet<unsigned>::const_iterator I = Defs.begin(), E = Defs.end();
  67          I != E; ++I) {
  68       unsigned MappedDef = *I;
  69       // Source of copy is no longer available for propagation.
  70       if (AvailCopyMap.erase(MappedDef)) {
  71         for (const uint16_t *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
  72           AvailCopyMap.erase(*SR);
  73       }
  74     }
  75   }
  76   for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
  77     SI = SrcMap.find(*AS);
  78     if (SI != SrcMap.end()) {
  79       const DenseSet<unsigned>& Defs = SI->second;
  80       for (DenseSet<unsigned>::const_iterator I = Defs.begin(), E = Defs.end();
  81            I != E; ++I) {
  82         unsigned MappedDef = *I;
  83         if (AvailCopyMap.erase(MappedDef)) {
  84           for (const uint16_t *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
  85             AvailCopyMap.erase(*SR);
  86         }
  87       }
  88     }
  89   }
  90 }
  91
  92 static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
  93                                     const MachineInstr *MI) {
  94   const MachineBasicBlock *MBB = CopyMI->getParent();
  95   if (MI->getParent() != MBB)
  96     return false;
  97   MachineBasicBlock::const_iterator I = CopyMI;
  98   MachineBasicBlock::const_iterator E = MBB->end();
  99   MachineBasicBlock::const_iterator E2 = MI;
 100
 101   ++I;
 102   while (I != E && I != E2) {
 103     if (I->hasUnmodeledSideEffects() || I->isCall() ||
 104         I->isTerminator())
 105       return false;
 106     ++I;
 107   }
 108   return true;
 109 }
 110
 111 /// isNopCopy - Return true if the specified copy is really a nop. That is
 112 /// if the source of the copy is the same of the definition of the copy that
 113 /// supplied the source. If the source of the copy is a sub-register than it
 114 /// must check the sub-indices match. e.g.
 115 /// ecx = mov eax
 116 /// al  = mov cl
 117 /// But not
 118 /// ecx = mov eax
 119 /// al  = mov ch
 120 static bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src,
 121                       const TargetRegisterInfo *TRI) {
 122   unsigned SrcSrc = CopyMI->getOperand(1).getReg();
 123   if (Def == SrcSrc)
 124     return true;
 125   if (TRI->isSubRegister(SrcSrc, Def)) {
 126     unsigned SrcDef = CopyMI->getOperand(0).getReg();
 127     unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def);
 128     if (!SubIdx)
 129       return false;
 130     return SubIdx == TRI->getSubRegIndex(SrcDef, Src);
 131   }
 132
 133   return false;
 134 }
 135
 136 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
 137   SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;  // Candidates for deletion
 138   DenseMap<unsigned, MachineInstr*> AvailCopyMap;    // Def -> available copies map
 139   DenseMap<unsigned, MachineInstr*> CopyMap;         // Def -> copies map
 140   DenseMap<unsigned, DenseSet<unsigned> > SrcMap; // Src -> Def map
 141
 142   bool Changed = false;
 143   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
 144     MachineInstr *MI = &*I;
 145     ++I;
 146
 147     if (MI->isCopy()) {
 148       unsigned Def = MI->getOperand(0).getReg();
 149       unsigned Src = MI->getOperand(1).getReg();
 150
 151       if (TargetRegisterInfo::isVirtualRegister(Def) ||
 152           TargetRegisterInfo::isVirtualRegister(Src))
 153         report_fatal_error("MachineCopyPropagation should be run after"
 154                            " register allocation!");
 155
 156       DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
 157       if (CI != AvailCopyMap.end()) {
 158         MachineInstr *CopyMI = CI->second;
 159         if (!ReservedRegs.test(Def) &&
 160             (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
 161             isNopCopy(CopyMI, Def, Src, TRI)) {
 162           // The two copies cancel out and the source of the first copy
 163           // hasn't been overridden, eliminate the second one. e.g.
 164           //  %ECX<def> = COPY %EAX<kill>
 165           //  ... nothing clobbered EAX.
 166           //  %EAX<def> = COPY %ECX
 167           // =>
 168           //  %ECX<def> = COPY %EAX
 169           //
 170           // Also avoid eliminating a copy from reserved registers unless the
 171           // definition is proven not clobbered. e.g.
 172           // %RSP<def> = COPY %RAX
 173           // CALL
 174           // %RAX<def> = COPY %RSP
 175
 176           // Clear any kills of Def between CopyMI and MI. This extends the
 177           // live range.
 178           for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I)
 179             I->clearRegisterKills(Def, TRI);
 180
 181           MI->eraseFromParent();
 182           Changed = true;
 183           ++NumDeletes;
 184           continue;
 185         }
 186       }
 187
 188       // If Src is defined by a previous copy, it cannot be eliminated.
 189       CI = CopyMap.find(Src);
 190       if (CI != CopyMap.end())
 191         MaybeDeadCopies.remove(CI->second);
 192       for (const uint16_t *AS = TRI->getAliasSet(Src); *AS; ++AS) {
 193         CI = CopyMap.find(*AS);
 194         if (CI != CopyMap.end())
 195           MaybeDeadCopies.remove(CI->second);
 196       }
 197
 198       // Copy is now a candidate for deletion.
 199       MaybeDeadCopies.insert(MI);
 200
 201       // If 'Src' is previously source of another copy, then this earlier copy's
 202       // source is no longer available. e.g.
 203       // %xmm9<def> = copy %xmm2
 204       // ...
 205       // %xmm2<def> = copy %xmm0
 206       // ...
 207       // %xmm2<def> = copy %xmm9
 208       SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap);
 209
 210       // Remember Def is defined by the copy.
 211       // ... Make sure to clear the def maps of aliases first.
 212       for (const uint16_t *AS = TRI->getAliasSet(Def); *AS; ++AS) {
 213         CopyMap.erase(*AS);
 214         AvailCopyMap.erase(*AS);
 215       }
 216       CopyMap[Def] = MI;
 217       AvailCopyMap[Def] = MI;
 218       for (const uint16_t *SR = TRI->getSubRegisters(Def); *SR; ++SR) {
 219         CopyMap[*SR] = MI;
 220         AvailCopyMap[*SR] = MI;
 221       }
 222
 223       // Remember source that's copied to Def. Once it's clobbered, then
 224       // it's no longer available for copy propagation.
 225       SrcMap[Src].insert(Def);
 226
 227       continue;
 228     }
 229
 230     // Not a copy.
 231     SmallVector<unsigned, 2> Defs;
 232     int RegMaskOpNum = -1;
 233     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 234       MachineOperand &MO = MI->getOperand(i);
 235       if (MO.isRegMask())
 236         RegMaskOpNum = i;
 237       if (!MO.isReg())
 238         continue;
 239       unsigned Reg = MO.getReg();
 240       if (!Reg)
 241         continue;
 242
 243       if (TargetRegisterInfo::isVirtualRegister(Reg))
 244         report_fatal_error("MachineCopyPropagation should be run after"
 245                            " register allocation!");
 246
 247       if (MO.isDef()) {
 248         Defs.push_back(Reg);
 249         continue;
 250       }
 251
 252       // If 'Reg' is defined by a copy, the copy is no longer a candidate
 253       // for elimination.
 254       DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg);
 255       if (CI != CopyMap.end())
 256         MaybeDeadCopies.remove(CI->second);
 257       for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 258         CI = CopyMap.find(*AS);
 259         if (CI != CopyMap.end())
 260           MaybeDeadCopies.remove(CI->second);
 261       }
 262     }
 263
 264     // The instruction has a register mask operand which means that it clobbers
 265     // a large set of registers.  It is possible to use the register mask to
 266     // prune the available copies, but treat it like a basic block boundary for
 267     // now.
 268     if (RegMaskOpNum >= 0) {
 269       // Erase any MaybeDeadCopies whose destination register is clobbered.
 270       const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum);
 271       for (SmallSetVector<MachineInstr*, 8>::iterator
 272            DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
 273            DI != DE; ++DI) {
 274         unsigned Reg = (*DI)->getOperand(0).getReg();
 275         if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg))
 276           continue;
 277         (*DI)->eraseFromParent();
 278         Changed = true;
 279         ++NumDeletes;
 280       }
 281
 282       // Clear all data structures as if we were beginning a new basic block.
 283       MaybeDeadCopies.clear();
 284       AvailCopyMap.clear();
 285       CopyMap.clear();
 286       SrcMap.clear();
 287       continue;
 288     }
 289
 290     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
 291       unsigned Reg = Defs[i];
 292
 293       // No longer defined by a copy.
 294       CopyMap.erase(Reg);
 295       AvailCopyMap.erase(Reg);
 296       for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 297         CopyMap.erase(*AS);
 298         AvailCopyMap.erase(*AS);
 299       }
 300
 301       // If 'Reg' is previously source of a copy, it is no longer available for
 302       // copy propagation.
 303       SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap);
 304     }
 305   }
 306
 307   // If MBB doesn't have successors, delete the copies whose defs are not used.
 308   // If MBB does have successors, then conservative assume the defs are live-out
 309   // since we don't want to trust live-in lists.
 310   if (MBB.succ_empty()) {
 311     for (SmallSetVector<MachineInstr*, 8>::iterator
 312            DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
 313          DI != DE; ++DI) {
 314       if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) {
 315         (*DI)->eraseFromParent();
 316         Changed = true;
 317         ++NumDeletes;
 318       }
 319     }
 320   }
 321
 322   return Changed;
 323 }
 324
 325 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
 326   bool Changed = false;
 327
 328   TRI = MF.getTarget().getRegisterInfo();
 329   ReservedRegs = TRI->getReservedRegs(MF);
 330
 331   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 332     Changed |= CopyPropagateBlock(*I);
 333
 334   return Changed;
 335 }