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