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