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     AliasAnalysis *AA;
  37     MachineDominatorTree *DT;
  38     MachineRegisterInfo *MRI;
  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 isProfitableToCSE(unsigned Reg, MachineInstr *MI);
  65     bool ProcessBlock(MachineDomTreeNode *Node);
  66   };
  67 } // end anonymous namespace
  68
  69 char MachineCSE::ID = 0;
  70 static RegisterPass<MachineCSE>
  71 X("machine-cse", "Machine Common Subexpression Elimination");
  72
  73 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
  74
  75 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
  76                                           MachineBasicBlock *MBB) {
  77   bool Changed = false;
  78   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  79     MachineOperand &MO = MI->getOperand(i);
  80     if (!MO.isReg() || !MO.isUse())
  81       continue;
  82     unsigned Reg = MO.getReg();
  83     if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
  84       continue;
  85     if (!MRI->hasOneUse(Reg))
  86       // Only coalesce single use copies. This ensure the copy will be
  87       // deleted.
  88       continue;
  89     MachineInstr *DefMI = MRI->getVRegDef(Reg);
  90     if (DefMI->getParent() != MBB)
  91       continue;
  92     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
  93     if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
  94         TargetRegisterInfo::isVirtualRegister(SrcReg) &&
  95         !SrcSubIdx && !DstSubIdx) {
  96       const TargetRegisterClass *SRC   = MRI->getRegClass(SrcReg);
  97       const TargetRegisterClass *RC    = MRI->getRegClass(Reg);
  98       const TargetRegisterClass *NewRC = getCommonSubClass(RC, SRC);
  99       if (!NewRC)
 100         continue;
 101       DEBUG(dbgs() << "Coalescing: " << *DefMI);
 102       DEBUG(dbgs() << "*** to: " << *MI);
 103       MO.setReg(SrcReg);
 104       if (NewRC != SRC)
 105         MRI->setRegClass(SrcReg, NewRC);
 106       DefMI->eraseFromParent();
 107       ++NumCoalesces;
 108       Changed = true;
 109     }
 110   }
 111
 112   return Changed;
 113 }
 114
 115 bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
 116                                         MachineBasicBlock::const_iterator I,
 117                                         MachineBasicBlock::const_iterator E) {
 118   unsigned LookAheadLeft = 5;
 119   while (LookAheadLeft--) {
 120     if (I == E)
 121       // Reached end of block, register is obviously dead.
 122       return true;
 123
 124     if (I->isDebugValue())
 125       continue;
 126     bool SeenDef = false;
 127     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 128       const MachineOperand &MO = I->getOperand(i);
 129       if (!MO.isReg() || !MO.getReg())
 130         continue;
 131       if (!TRI->regsOverlap(MO.getReg(), Reg))
 132         continue;
 133       if (MO.isUse())
 134         return false;
 135       SeenDef = true;
 136     }
 137     if (SeenDef)
 138       // See a def of Reg (or an alias) before encountering any use, it's
 139       // trivially dead.
 140       return true;
 141     ++I;
 142   }
 143   return false;
 144 }
 145
 146 bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){
 147   unsigned PhysDef = 0;
 148   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 149     MachineOperand &MO = MI->getOperand(i);
 150     if (!MO.isReg())
 151       continue;
 152     unsigned Reg = MO.getReg();
 153     if (!Reg)
 154       continue;
 155     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 156       if (MO.isUse())
 157         // Can't touch anything to read a physical register.
 158         return true;
 159       if (MO.isDead())
 160         // If the def is dead, it's ok.
 161         continue;
 162       // Ok, this is a physical register def that's not marked "dead". That's
 163       // common since this pass is run before livevariables. We can scan
 164       // forward a few instructions and check if it is obviously dead.
 165       if (PhysDef)
 166         // Multiple physical register defs. These are rare, forget about it.
 167         return true;
 168       PhysDef = Reg;
 169     }
 170   }
 171
 172   if (PhysDef) {
 173     MachineBasicBlock::iterator I = MI; I = llvm::next(I);
 174     if (!isPhysDefTriviallyDead(PhysDef, I, MBB->end()))
 175       return true;
 176   }
 177   return false;
 178 }
 179
 180 bool MachineCSE::isCSECandidate(MachineInstr *MI) {
 181   if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
 182       MI->isKill() || MI->isInlineAsm())
 183     return false;
 184
 185   // Ignore copies or instructions that read / write physical registers
 186   // (except for dead defs of physical registers).
 187   unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 188   if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
 189       MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
 190     return false;
 191
 192   // Ignore stuff that we obviously can't move.
 193   const TargetInstrDesc &TID = MI->getDesc();
 194   if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
 195       TID.hasUnmodeledSideEffects())
 196     return false;
 197
 198   if (TID.mayLoad()) {
 199     // Okay, this instruction does a load. As a refinement, we allow the target
 200     // to decide whether the loaded value is actually a constant. If so, we can
 201     // actually use it as a load.
 202     if (!MI->isInvariantLoad(AA))
 203       // FIXME: we should be able to hoist loads with no other side effects if
 204       // there are no other instructions which can change memory in this loop.
 205       // This is a trivial form of alias analysis.
 206       return false;
 207   }
 208   return true;
 209 }
 210
 211 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
 212 /// common expression that defines Reg.
 213 bool MachineCSE::isProfitableToCSE(unsigned Reg, MachineInstr *MI) {
 214   // FIXME: This "heuristic" works around the lack the live range splitting.
 215   // If the common subexpression is used by PHIs, do not reuse it unless the
 216   // defined value is already used in the BB of the new use.
 217   bool HasPHI = false;
 218   SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
 219   for (MachineRegisterInfo::use_nodbg_iterator I =
 220        MRI->use_nodbg_begin(Reg),
 221        E = MRI->use_nodbg_end(); I != E; ++I) {
 222     MachineInstr *Use = &*I;
 223     HasPHI |= Use->isPHI();
 224     CSBBs.insert(Use->getParent());
 225   }
 226
 227   if (!HasPHI)
 228     return true;
 229   return CSBBs.count(MI->getParent());
 230 }
 231
 232 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
 233   bool Changed = false;
 234
 235   SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
 236   ScopedHashTableScope<MachineInstr*, unsigned,
 237     MachineInstrExpressionTrait> VNTS(VNT);
 238   MachineBasicBlock *MBB = Node->getBlock();
 239   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
 240     MachineInstr *MI = &*I;
 241     ++I;
 242
 243     if (!isCSECandidate(MI))
 244       continue;
 245
 246     bool FoundCSE = VNT.count(MI);
 247     if (!FoundCSE) {
 248       // Look for trivial copy coalescing opportunities.
 249       if (PerformTrivialCoalescing(MI, MBB))
 250         FoundCSE = VNT.count(MI);
 251     }
 252     // FIXME: commute commutable instructions?
 253
 254     // If the instruction defines a physical register and the value *may* be
 255     // used, then it's not safe to replace it with a common subexpression.
 256     if (FoundCSE && hasLivePhysRegDefUse(MI, MBB))
 257       FoundCSE = false;
 258
 259     if (!FoundCSE) {
 260       VNT.insert(MI, CurrVN++);
 261       Exps.push_back(MI);
 262       continue;
 263     }
 264
 265     // Found a common subexpression, eliminate it.
 266     unsigned CSVN = VNT.lookup(MI);
 267     MachineInstr *CSMI = Exps[CSVN];
 268     DEBUG(dbgs() << "Examining: " << *MI);
 269     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
 270
 271     // Check if it's profitable to perform this CSE.
 272     bool DoCSE = true;
 273     unsigned NumDefs = MI->getDesc().getNumDefs();
 274     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
 275       MachineOperand &MO = MI->getOperand(i);
 276       if (!MO.isReg() || !MO.isDef())
 277         continue;
 278       unsigned OldReg = MO.getReg();
 279       unsigned NewReg = CSMI->getOperand(i).getReg();
 280       if (OldReg == NewReg)
 281         continue;
 282       assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
 283              TargetRegisterInfo::isVirtualRegister(NewReg) &&
 284              "Do not CSE physical register defs!");
 285       if (!isProfitableToCSE(NewReg, MI)) {
 286         DoCSE = false;
 287         break;
 288       }
 289       CSEPairs.push_back(std::make_pair(OldReg, NewReg));
 290       --NumDefs;
 291     }
 292
 293     // Actually perform the elimination.
 294     if (DoCSE) {
 295       for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i)
 296         MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
 297       MI->eraseFromParent();
 298       ++NumCSEs;
 299     } else {
 300       DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
 301       VNT.insert(MI, CurrVN++);
 302       Exps.push_back(MI);
 303     }
 304     CSEPairs.clear();
 305   }
 306
 307   // Recursively call ProcessBlock with childred.
 308   const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
 309   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 310     Changed |= ProcessBlock(Children[i]);
 311
 312   return Changed;
 313 }
 314
 315 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
 316   TII = MF.getTarget().getInstrInfo();
 317   TRI = MF.getTarget().getRegisterInfo();
 318   MRI = &MF.getRegInfo();
 319   AA = &getAnalysis<AliasAnalysis>();
 320   DT = &getAnalysis<MachineDominatorTree>();
 321   return ProcessBlock(DT->getRootNode());
 322 }