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     void SourceNoLongerAvailable(unsigned Reg,
  47                                DenseMap<unsigned, unsigned> &SrcMap,
  48                                DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
  49     bool CopyPropagateBlock(MachineBasicBlock &MBB);
  50   };
  51 }
  52 char MachineCopyPropagation::ID = 0;
  53
  54 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
  55                 "Machine Copy Propagation Pass", false, false)
  56
  57 FunctionPass *llvm::createMachineCopyPropagationPass() {
  58   return new MachineCopyPropagation();
  59 }
  60
  61 void
  62 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
  63                               DenseMap<unsigned, unsigned> &SrcMap,
  64                               DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
  65   DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg);
  66   if (SI != SrcMap.end()) {
  67     unsigned MappedDef = SI->second;
  68     // Source of copy is no longer available for propagation.
  69     if (AvailCopyMap.erase(MappedDef)) {
  70       for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
  71         AvailCopyMap.erase(*SR);
  72     }
  73   }
  74   for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
  75     SI = SrcMap.find(*AS);
  76     if (SI != SrcMap.end()) {
  77       unsigned MappedDef = SI->second;
  78       if (AvailCopyMap.erase(MappedDef)) {
  79         for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
  80           AvailCopyMap.erase(*SR);
  81       }
  82     }
  83   }
  84 }
  85
  86 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
  87   SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion
  88   DenseMap<unsigned, MachineInstr*> AvailCopyMap;   // Def -> available copies map
  89   DenseMap<unsigned, MachineInstr*> CopyMap;        // Def -> copies map
  90   DenseMap<unsigned, unsigned> SrcMap;              // Src -> Def map
  91
  92   bool Changed = false;
  93   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
  94     MachineInstr *MI = &*I;
  95     ++I;
  96
  97     if (MI->isCopy()) {
  98       unsigned Def = MI->getOperand(0).getReg();
  99       unsigned Src = MI->getOperand(1).getReg();
 100
 101       if (TargetRegisterInfo::isVirtualRegister(Def) ||
 102           TargetRegisterInfo::isVirtualRegister(Src))
 103         report_fatal_error("MachineCopyPropagation should be run after"
 104                            " register allocation!");
 105
 106       DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
 107       if (CI != AvailCopyMap.end()) {
 108         MachineInstr *CopyMI = CI->second;
 109         unsigned SrcSrc = CopyMI->getOperand(1).getReg();
 110         if (!ReservedRegs.test(Def) &&
 111             (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) {
 112           // The two copies cancel out and the source of the first copy
 113           // hasn't been overridden, eliminate the second one. e.g.
 114           //  %ECX<def> = COPY %EAX<kill>
 115           //  ... nothing clobbered EAX.
 116           //  %EAX<def> = COPY %ECX
 117           // =>
 118           //  %ECX<def> = COPY %EAX
 119           CopyMI->getOperand(1).setIsKill(false);
 120           MI->eraseFromParent();
 121           Changed = true;
 122           ++NumDeletes;
 123           continue;
 124         }
 125       }
 126
 127       // If Src is defined by a previous copy, it cannot be eliminated.
 128       CI = CopyMap.find(Src);
 129       if (CI != CopyMap.end())
 130         MaybeDeadCopies.remove(CI->second);
 131       for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) {
 132         CI = CopyMap.find(*AS);
 133         if (CI != CopyMap.end())
 134           MaybeDeadCopies.remove(CI->second);
 135       }
 136
 137       // Copy is now a candidate for deletion.
 138       MaybeDeadCopies.insert(MI);
 139
 140       // If 'Src' is previously source of another copy, then this earlier copy's
 141       // source is no longer available. e.g.
 142       // %xmm9<def> = copy %xmm2
 143       // ...
 144       // %xmm2<def> = copy %xmm0
 145       // ...
 146       // %xmm2<def> = copy %xmm9
 147       SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap);
 148
 149       // Remember Def is defined by the copy.
 150       CopyMap[Def] = MI;
 151       AvailCopyMap[Def] = MI;
 152       for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) {
 153         CopyMap[*SR] = MI;
 154         AvailCopyMap[*SR] = MI;
 155       }
 156
 157       // Remember source that's copied to Def. Once it's clobbered, then
 158       // it's no longer available for copy propagation.
 159       SrcMap[Src] = Def;
 160
 161       continue;
 162     }
 163
 164     // Not a copy.
 165     SmallVector<unsigned, 2> Defs;
 166     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 167       MachineOperand &MO = MI->getOperand(i);
 168       if (!MO.isReg())
 169         continue;
 170       unsigned Reg = MO.getReg();
 171       if (!Reg)
 172         continue;
 173
 174       if (TargetRegisterInfo::isVirtualRegister(Reg))
 175         report_fatal_error("MachineCopyPropagation should be run after"
 176                            " register allocation!");
 177
 178       if (MO.isDef()) {
 179         Defs.push_back(Reg);
 180         continue;
 181       }
 182
 183       // If 'Reg' is defined by a copy, the copy is no longer a candidate
 184       // for elimination.
 185       DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg);
 186       if (CI != CopyMap.end())
 187         MaybeDeadCopies.remove(CI->second);
 188       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 189         CI = CopyMap.find(*AS);
 190         if (CI != CopyMap.end())
 191           MaybeDeadCopies.remove(CI->second);
 192       }
 193     }
 194
 195     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
 196       unsigned Reg = Defs[i];
 197
 198       // No longer defined by a copy.
 199       CopyMap.erase(Reg);
 200       AvailCopyMap.erase(Reg);
 201       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 202         CopyMap.erase(*AS);
 203         AvailCopyMap.erase(*AS);
 204       }
 205
 206       // If 'Reg' is previously source of a copy, it is no longer available for
 207       // copy propagation.
 208       SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap);
 209     }
 210   }
 211
 212   // If MBB doesn't have successors, delete the copies whose defs are not used.
 213   // If MBB does have successors, then conservative assume the defs are live-out
 214   // since we don't want to trust live-in lists.
 215   if (MBB.succ_empty()) {
 216     for (SmallSetVector<MachineInstr*, 8>::iterator
 217            DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
 218          DI != DE; ++DI) {
 219       if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) {
 220         (*DI)->eraseFromParent();
 221         Changed = true;
 222         ++NumDeletes;
 223       }
 224     }
 225   }
 226
 227   return Changed;
 228 }
 229
 230 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
 231   bool Changed = false;
 232
 233   TRI = MF.getTarget().getRegisterInfo();
 234   ReservedRegs = TRI->getReservedRegs(MF);
 235
 236   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 237     Changed |= CopyPropagateBlock(*I);
 238
 239   return Changed;
 240 }