lib/CodeGen/MachineCSE.cpp

   1 //===-- MachineCSE.cpp - Machine Common Subexpression Elimination 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 pass performs global common subexpression elimination on machine
  11 // instructions using a scoped hash table based value numbering scheme. It
  12 // must be run while the machine function is still in SSA form.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "machine-cse"
  17 #include "llvm/CodeGen/Passes.h"
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Target/TargetInstrInfo.h"
  22 #include "llvm/ADT/ScopedHashTable.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Support/Debug.h"
  25
  26 using namespace llvm;
  27
  28 STATISTIC(NumCoalesces, "Number of copies coalesced");
  29 STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
  30
  31 namespace {
  32   class MachineCSE : public MachineFunctionPass {
  33     const TargetInstrInfo *TII;
  34     const TargetRegisterInfo *TRI;
  35     MachineRegisterInfo  *MRI;
  36     MachineDominatorTree *DT;
  37   public:
  38     static char ID; // Pass identification
  39     MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
  40
  41     virtual bool runOnMachineFunction(MachineFunction &MF);
  42
  43     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  44       AU.setPreservesCFG();
  45       MachineFunctionPass::getAnalysisUsage(AU);
  46       AU.addRequired<MachineDominatorTree>();
  47       AU.addPreserved<MachineDominatorTree>();
  48     }
  49
  50   private:
  51     unsigned CurrVN;
  52     ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT;
  53     SmallVector<MachineInstr*, 64> Exps;
  54
  55     bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB);
  56     bool isPhysDefTriviallyDead(unsigned Reg,
  57                                 MachineBasicBlock::const_iterator I,
  58                                 MachineBasicBlock::const_iterator E);
  59     bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
  60     bool ProcessBlock(MachineDomTreeNode *Node);
  61   };
  62 } // end anonymous namespace
  63
  64 char MachineCSE::ID = 0;
  65 static RegisterPass<MachineCSE>
  66 X("machine-cse", "Machine Common Subexpression Elimination");
  67
  68 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
  69
  70 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
  71                                           MachineBasicBlock *MBB) {
  72   bool Changed = false;
  73   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  74     MachineOperand &MO = MI->getOperand(i);
  75     if (!MO.isReg() || !MO.isUse())
  76       continue;
  77     unsigned Reg = MO.getReg();
  78     if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
  79       continue;
  80     if (!MRI->hasOneUse(Reg))
  81       // Only coalesce single use copies. This ensure the copy will be
  82       // deleted.
  83       continue;
  84     MachineInstr *DefMI = MRI->getVRegDef(Reg);
  85     if (DefMI->getParent() != MBB)
  86       continue;
  87     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
  88     if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
  89         TargetRegisterInfo::isVirtualRegister(SrcReg) &&
  90         !SrcSubIdx && !DstSubIdx) {
  91       MO.setReg(SrcReg);
  92       DefMI->eraseFromParent();
  93       ++NumCoalesces;
  94       Changed = true;
  95     }
  96   }
  97
  98   return Changed;
  99 }
 100
 101 bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
 102                                         MachineBasicBlock::const_iterator I,
 103                                         MachineBasicBlock::const_iterator E) {
 104   unsigned LookAheadLeft = 5;
 105   while (LookAheadLeft--) {
 106     if (I == E)
 107       // Reached end of block, register is obviously dead.
 108       return true;
 109
 110     if (I->isDebugValue())
 111       continue;
 112     bool SeenDef = false;
 113     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 114       const MachineOperand &MO = I->getOperand(i);
 115       if (!MO.isReg() || !MO.getReg())
 116         continue;
 117       if (!TRI->regsOverlap(MO.getReg(), Reg))
 118         continue;
 119       if (MO.isUse())
 120         return false;
 121       SeenDef = true;
 122     }
 123     if (SeenDef)
 124       // See a def of Reg (or an alias) before encountering any use, it's
 125       // trivially dead.
 126       return true;
 127     ++I;
 128   }
 129   return false;
 130 }
 131
 132 bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){
 133   unsigned PhysDef = 0;
 134   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 135     MachineOperand &MO = MI->getOperand(i);
 136     if (!MO.isReg())
 137       continue;
 138     unsigned Reg = MO.getReg();
 139     if (!Reg)
 140       continue;
 141     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 142       if (MO.isUse())
 143         // Can't touch anything to read a physical register.
 144         return true;
 145       if (MO.isDead())
 146         // If the def is dead, it's ok.
 147         continue;
 148       // Ok, this is a physical register def that's not marked "dead". That's
 149       // common since this pass is run before livevariables. We can scan
 150       // forward a few instructions and check if it is obviously dead.
 151       if (PhysDef)
 152         // Multiple physical register defs. These are rare, forget about it.
 153         return true;
 154       PhysDef = Reg;
 155     }
 156   }
 157
 158   if (PhysDef) {
 159     MachineBasicBlock::iterator I = MI; I = llvm::next(I);
 160     if (!isPhysDefTriviallyDead(PhysDef, I, MBB->end()))
 161       return true;
 162   }
 163   return false;
 164 }
 165
 166 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
 167   bool Changed = false;
 168
 169   ScopedHashTableScope<MachineInstr*, unsigned,
 170     MachineInstrExpressionTrait> VNTS(VNT);
 171   MachineBasicBlock *MBB = Node->getBlock();
 172   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
 173     MachineInstr *MI = &*I;
 174     ++I;
 175     bool SawStore = false;
 176     if (!MI->isSafeToMove(TII, 0, SawStore))
 177       continue;
 178     // Ignore copies or instructions that read / write physical registers
 179     // (except for dead defs of physical registers).
 180     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 181     if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
 182         MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
 183       continue;
 184
 185     bool FoundCSE = VNT.count(MI);
 186     if (!FoundCSE) {
 187       // Look for trivial copy coalescing opportunities.
 188       if (PerformTrivialCoalescing(MI, MBB))
 189         FoundCSE = VNT.count(MI);
 190     }
 191     // FIXME: commute commutable instructions?
 192
 193     // If the instruction defines a physical register and the value *may* be
 194     // used, then it's not safe to replace it with a common subexpression.
 195     if (FoundCSE && hasLivePhysRegDefUse(MI, MBB))
 196       FoundCSE = false;
 197
 198     if (!FoundCSE) {
 199       VNT.insert(MI, CurrVN++);
 200       Exps.push_back(MI);
 201       continue;
 202     }
 203
 204     // Found a common subexpression, eliminate it.
 205     unsigned CSVN = VNT.lookup(MI);
 206     MachineInstr *CSMI = Exps[CSVN];
 207     DEBUG(dbgs() << "Examining: " << *MI);
 208     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
 209     unsigned NumDefs = MI->getDesc().getNumDefs();
 210     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
 211       MachineOperand &MO = MI->getOperand(i);
 212       if (!MO.isReg() || !MO.isDef())
 213         continue;
 214       unsigned OldReg = MO.getReg();
 215       unsigned NewReg = CSMI->getOperand(i).getReg();
 216       assert(OldReg != NewReg &&
 217              TargetRegisterInfo::isVirtualRegister(OldReg) &&
 218              TargetRegisterInfo::isVirtualRegister(NewReg) &&
 219              "Do not CSE physical register defs!");
 220       MRI->replaceRegWith(OldReg, NewReg);
 221       --NumDefs;
 222     }
 223     MI->eraseFromParent();
 224     ++NumCSEs;
 225   }
 226
 227   // Recursively call ProcessBlock with childred.
 228   const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
 229   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 230     Changed |= ProcessBlock(Children[i]);
 231
 232   return Changed;
 233 }
 234
 235 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
 236   TII = MF.getTarget().getInstrInfo();
 237   TRI = MF.getTarget().getRegisterInfo();
 238   MRI = &MF.getRegInfo();
 239   DT = &getAnalysis<MachineDominatorTree>();
 240   return ProcessBlock(DT->getRootNode());
 241 }