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