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