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