MachineCSE.cpp revision e68ea060c78356253d771e039747fbc06c623646
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 CSReg, unsigned Reg, 65 MachineInstr *CSMI, MachineInstr *MI); 66 bool ProcessBlock(MachineDomTreeNode *Node); 67 }; 68} // end anonymous namespace 69 70char MachineCSE::ID = 0; 71static RegisterPass<MachineCSE> 72X("machine-cse", "Machine Common Subexpression Elimination"); 73 74FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 75 76bool 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 116bool 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 // These must not count against the limit. 127 ++LookAheadLeft; 128 ++I; 129 continue; 130 } 131 bool SeenDef = false; 132 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 133 const MachineOperand &MO = I->getOperand(i); 134 if (!MO.isReg() || !MO.getReg()) 135 continue; 136 if (!TRI->regsOverlap(MO.getReg(), Reg)) 137 continue; 138 if (MO.isUse()) 139 return false; 140 SeenDef = true; 141 } 142 if (SeenDef) 143 // See a def of Reg (or an alias) before encountering any use, it's 144 // trivially dead. 145 return true; 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). 153bool 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 187static 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 193bool 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. 223bool 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 280bool 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 FoundCSE = VNT.count(MI); 299 } 300 // FIXME: commute commutable instructions? 301 302 // If the instruction defines a physical register and the value *may* be 303 // used, then it's not safe to replace it with a common subexpression. 304 if (FoundCSE && hasLivePhysRegDefUse(MI, MBB)) 305 FoundCSE = false; 306 307 if (!FoundCSE) { 308 VNT.insert(MI, CurrVN++); 309 Exps.push_back(MI); 310 continue; 311 } 312 313 // Found a common subexpression, eliminate it. 314 unsigned CSVN = VNT.lookup(MI); 315 MachineInstr *CSMI = Exps[CSVN]; 316 DEBUG(dbgs() << "Examining: " << *MI); 317 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 318 319 // Check if it's profitable to perform this CSE. 320 bool DoCSE = true; 321 unsigned NumDefs = MI->getDesc().getNumDefs(); 322 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 323 MachineOperand &MO = MI->getOperand(i); 324 if (!MO.isReg() || !MO.isDef()) 325 continue; 326 unsigned OldReg = MO.getReg(); 327 unsigned NewReg = CSMI->getOperand(i).getReg(); 328 if (OldReg == NewReg) 329 continue; 330 assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 331 TargetRegisterInfo::isVirtualRegister(NewReg) && 332 "Do not CSE physical register defs!"); 333 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 334 DoCSE = false; 335 break; 336 } 337 CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 338 --NumDefs; 339 } 340 341 // Actually perform the elimination. 342 if (DoCSE) { 343 for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) 344 MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 345 MI->eraseFromParent(); 346 ++NumCSEs; 347 } else { 348 DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 349 VNT.insert(MI, CurrVN++); 350 Exps.push_back(MI); 351 } 352 CSEPairs.clear(); 353 } 354 355 // Recursively call ProcessBlock with childred. 356 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 357 for (unsigned i = 0, e = Children.size(); i != e; ++i) 358 Changed |= ProcessBlock(Children[i]); 359 360 return Changed; 361} 362 363bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 364 TII = MF.getTarget().getInstrInfo(); 365 TRI = MF.getTarget().getRegisterInfo(); 366 MRI = &MF.getRegInfo(); 367 AA = &getAnalysis<AliasAnalysis>(); 368 DT = &getAnalysis<MachineDominatorTree>(); 369 return ProcessBlock(DT->getRootNode()); 370} 371