MachineCSE.cpp revision 622a11bc0764897f6aaf80fe96b3abac6215f06b
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/DenseMap.h" 24#include "llvm/ADT/ScopedHashTable.h" 25#include "llvm/ADT/SmallSet.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/Support/Debug.h" 28#include "llvm/Support/RecyclingAllocator.h" 29 30using namespace llvm; 31 32STATISTIC(NumCoalesces, "Number of copies coalesced"); 33STATISTIC(NumCSEs, "Number of common subexpression eliminated"); 34STATISTIC(NumPhysCSEs, 35 "Number of physreg referencing common subexpr eliminated"); 36STATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 37 38namespace { 39 class MachineCSE : public MachineFunctionPass { 40 const TargetInstrInfo *TII; 41 const TargetRegisterInfo *TRI; 42 AliasAnalysis *AA; 43 MachineDominatorTree *DT; 44 MachineRegisterInfo *MRI; 45 public: 46 static char ID; // Pass identification 47 MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { 48 initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 49 } 50 51 virtual bool runOnMachineFunction(MachineFunction &MF); 52 53 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 54 AU.setPreservesCFG(); 55 MachineFunctionPass::getAnalysisUsage(AU); 56 AU.addRequired<AliasAnalysis>(); 57 AU.addPreservedID(MachineLoopInfoID); 58 AU.addRequired<MachineDominatorTree>(); 59 AU.addPreserved<MachineDominatorTree>(); 60 } 61 62 virtual void releaseMemory() { 63 ScopeMap.clear(); 64 Exps.clear(); 65 } 66 67 private: 68 const unsigned LookAheadLimit; 69 typedef RecyclingAllocator<BumpPtrAllocator, 70 ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 71 typedef ScopedHashTable<MachineInstr*, unsigned, 72 MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 73 typedef ScopedHTType::ScopeTy ScopeType; 74 DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 75 ScopedHTType VNT; 76 SmallVector<MachineInstr*, 64> Exps; 77 unsigned CurrVN; 78 79 bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 80 bool isPhysDefTriviallyDead(unsigned Reg, 81 MachineBasicBlock::const_iterator I, 82 MachineBasicBlock::const_iterator E) const ; 83 bool hasLivePhysRegDefUses(const MachineInstr *MI, 84 const MachineBasicBlock *MBB, 85 SmallSet<unsigned,8> &PhysRefs) const; 86 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 87 SmallSet<unsigned,8> &PhysRefs) const; 88 bool isCSECandidate(MachineInstr *MI); 89 bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 90 MachineInstr *CSMI, MachineInstr *MI); 91 void EnterScope(MachineBasicBlock *MBB); 92 void ExitScope(MachineBasicBlock *MBB); 93 bool ProcessBlock(MachineBasicBlock *MBB); 94 void ExitScopeIfDone(MachineDomTreeNode *Node, 95 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 96 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap); 97 bool PerformCSE(MachineDomTreeNode *Node); 98 }; 99} // end anonymous namespace 100 101char MachineCSE::ID = 0; 102INITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 103 "Machine Common Subexpression Elimination", false, false) 104INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 105INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 106INITIALIZE_PASS_END(MachineCSE, "machine-cse", 107 "Machine Common Subexpression Elimination", false, false) 108 109FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 110 111bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 112 MachineBasicBlock *MBB) { 113 bool Changed = false; 114 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 115 MachineOperand &MO = MI->getOperand(i); 116 if (!MO.isReg() || !MO.isUse()) 117 continue; 118 unsigned Reg = MO.getReg(); 119 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 120 continue; 121 if (!MRI->hasOneNonDBGUse(Reg)) 122 // Only coalesce single use copies. This ensure the copy will be 123 // deleted. 124 continue; 125 MachineInstr *DefMI = MRI->getVRegDef(Reg); 126 if (DefMI->getParent() != MBB) 127 continue; 128 if (!DefMI->isCopy()) 129 continue; 130 unsigned SrcReg = DefMI->getOperand(1).getReg(); 131 if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 132 continue; 133 if (DefMI->getOperand(0).getSubReg() || DefMI->getOperand(1).getSubReg()) 134 continue; 135 if (!MRI->constrainRegClass(SrcReg, MRI->getRegClass(Reg))) 136 continue; 137 DEBUG(dbgs() << "Coalescing: " << *DefMI); 138 DEBUG(dbgs() << "*** to: " << *MI); 139 MO.setReg(SrcReg); 140 MRI->clearKillFlags(SrcReg); 141 DefMI->eraseFromParent(); 142 ++NumCoalesces; 143 Changed = true; 144 } 145 146 return Changed; 147} 148 149bool 150MachineCSE::isPhysDefTriviallyDead(unsigned Reg, 151 MachineBasicBlock::const_iterator I, 152 MachineBasicBlock::const_iterator E) const { 153 unsigned LookAheadLeft = LookAheadLimit; 154 while (LookAheadLeft) { 155 // Skip over dbg_value's. 156 while (I != E && I->isDebugValue()) 157 ++I; 158 159 if (I == E) 160 // Reached end of block, register is obviously dead. 161 return true; 162 163 bool SeenDef = false; 164 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 165 const MachineOperand &MO = I->getOperand(i); 166 if (!MO.isReg() || !MO.getReg()) 167 continue; 168 if (!TRI->regsOverlap(MO.getReg(), Reg)) 169 continue; 170 if (MO.isUse()) 171 // Found a use! 172 return false; 173 SeenDef = true; 174 } 175 if (SeenDef) 176 // See a def of Reg (or an alias) before encountering any use, it's 177 // trivially dead. 178 return true; 179 180 --LookAheadLeft; 181 ++I; 182 } 183 return false; 184} 185 186/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 187/// physical registers (except for dead defs of physical registers). It also 188/// returns the physical register def by reference if it's the only one and the 189/// instruction does not uses a physical register. 190bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 191 const MachineBasicBlock *MBB, 192 SmallSet<unsigned,8> &PhysRefs) const { 193 MachineBasicBlock::const_iterator I = MI; I = llvm::next(I); 194 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 195 const MachineOperand &MO = MI->getOperand(i); 196 if (!MO.isReg()) 197 continue; 198 unsigned Reg = MO.getReg(); 199 if (!Reg) 200 continue; 201 if (TargetRegisterInfo::isVirtualRegister(Reg)) 202 continue; 203 // If the def is dead, it's ok. But the def may not marked "dead". That's 204 // common since this pass is run before livevariables. We can scan 205 // forward a few instructions and check if it is obviously dead. 206 if (MO.isDef() && 207 (MO.isDead() || isPhysDefTriviallyDead(Reg, I, MBB->end()))) 208 continue; 209 PhysRefs.insert(Reg); 210 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) 211 PhysRefs.insert(*Alias); 212 } 213 214 return !PhysRefs.empty(); 215} 216 217bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 218 SmallSet<unsigned,8> &PhysRefs) const { 219 // For now conservatively returns false if the common subexpression is 220 // not in the same basic block as the given instruction. 221 MachineBasicBlock *MBB = MI->getParent(); 222 if (CSMI->getParent() != MBB) 223 return false; 224 MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I); 225 MachineBasicBlock::const_iterator E = MI; 226 unsigned LookAheadLeft = LookAheadLimit; 227 while (LookAheadLeft) { 228 // Skip over dbg_value's. 229 while (I != E && I->isDebugValue()) 230 ++I; 231 232 if (I == E) 233 return true; 234 235 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 236 const MachineOperand &MO = I->getOperand(i); 237 if (!MO.isReg() || !MO.isDef()) 238 continue; 239 unsigned MOReg = MO.getReg(); 240 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 241 continue; 242 if (PhysRefs.count(MOReg)) 243 return false; 244 } 245 246 --LookAheadLeft; 247 ++I; 248 } 249 250 return false; 251} 252 253bool MachineCSE::isCSECandidate(MachineInstr *MI) { 254 if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 255 MI->isKill() || MI->isInlineAsm() || MI->isDebugValue()) 256 return false; 257 258 // Ignore copies. 259 if (MI->isCopyLike()) 260 return false; 261 262 // Ignore stuff that we obviously can't move. 263 const TargetInstrDesc &TID = MI->getDesc(); 264 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 265 MI->hasUnmodeledSideEffects()) 266 return false; 267 268 if (TID.mayLoad()) { 269 // Okay, this instruction does a load. As a refinement, we allow the target 270 // to decide whether the loaded value is actually a constant. If so, we can 271 // actually use it as a load. 272 if (!MI->isInvariantLoad(AA)) 273 // FIXME: we should be able to hoist loads with no other side effects if 274 // there are no other instructions which can change memory in this loop. 275 // This is a trivial form of alias analysis. 276 return false; 277 } 278 return true; 279} 280 281/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 282/// common expression that defines Reg. 283bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 284 MachineInstr *CSMI, MachineInstr *MI) { 285 // FIXME: Heuristics that works around the lack the live range splitting. 286 287 // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 288 // an immediate predecessor. We don't want to increase register pressure and 289 // end up causing other computation to be spilled. 290 if (MI->getDesc().isAsCheapAsAMove()) { 291 MachineBasicBlock *CSBB = CSMI->getParent(); 292 MachineBasicBlock *BB = MI->getParent(); 293 if (CSBB != BB && !CSBB->isSuccessor(BB)) 294 return false; 295 } 296 297 // Heuristics #2: If the expression doesn't not use a vr and the only use 298 // of the redundant computation are copies, do not cse. 299 bool HasVRegUse = false; 300 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 301 const MachineOperand &MO = MI->getOperand(i); 302 if (MO.isReg() && MO.isUse() && 303 TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 304 HasVRegUse = true; 305 break; 306 } 307 } 308 if (!HasVRegUse) { 309 bool HasNonCopyUse = false; 310 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 311 E = MRI->use_nodbg_end(); I != E; ++I) { 312 MachineInstr *Use = &*I; 313 // Ignore copies. 314 if (!Use->isCopyLike()) { 315 HasNonCopyUse = true; 316 break; 317 } 318 } 319 if (!HasNonCopyUse) 320 return false; 321 } 322 323 // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 324 // it unless the defined value is already used in the BB of the new use. 325 bool HasPHI = false; 326 SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 327 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg), 328 E = MRI->use_nodbg_end(); I != E; ++I) { 329 MachineInstr *Use = &*I; 330 HasPHI |= Use->isPHI(); 331 CSBBs.insert(Use->getParent()); 332 } 333 334 if (!HasPHI) 335 return true; 336 return CSBBs.count(MI->getParent()); 337} 338 339void MachineCSE::EnterScope(MachineBasicBlock *MBB) { 340 DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 341 ScopeType *Scope = new ScopeType(VNT); 342 ScopeMap[MBB] = Scope; 343} 344 345void MachineCSE::ExitScope(MachineBasicBlock *MBB) { 346 DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 347 DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 348 assert(SI != ScopeMap.end()); 349 ScopeMap.erase(SI); 350 delete SI->second; 351} 352 353bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 354 bool Changed = false; 355 356 SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 357 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 358 MachineInstr *MI = &*I; 359 ++I; 360 361 if (!isCSECandidate(MI)) 362 continue; 363 364 bool FoundCSE = VNT.count(MI); 365 if (!FoundCSE) { 366 // Look for trivial copy coalescing opportunities. 367 if (PerformTrivialCoalescing(MI, MBB)) { 368 // After coalescing MI itself may become a copy. 369 if (MI->isCopyLike()) 370 continue; 371 FoundCSE = VNT.count(MI); 372 } 373 } 374 375 // Commute commutable instructions. 376 bool Commuted = false; 377 if (!FoundCSE && MI->getDesc().isCommutable()) { 378 MachineInstr *NewMI = TII->commuteInstruction(MI); 379 if (NewMI) { 380 Commuted = true; 381 FoundCSE = VNT.count(NewMI); 382 if (NewMI != MI) 383 // New instruction. It doesn't need to be kept. 384 NewMI->eraseFromParent(); 385 else if (!FoundCSE) 386 // MI was changed but it didn't help, commute it back! 387 (void)TII->commuteInstruction(MI); 388 } 389 } 390 391 // If the instruction defines physical registers and the values *may* be 392 // used, then it's not safe to replace it with a common subexpression. 393 // It's also not safe if the instruction uses physical registers. 394 SmallSet<unsigned,8> PhysRefs; 395 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs)) { 396 FoundCSE = false; 397 398 // ... Unless the CS is local and it also defines the physical register 399 // which is not clobbered in between and the physical register uses 400 // were not clobbered. 401 unsigned CSVN = VNT.lookup(MI); 402 MachineInstr *CSMI = Exps[CSVN]; 403 if (PhysRegDefsReach(CSMI, MI, PhysRefs)) 404 FoundCSE = true; 405 } 406 407 if (!FoundCSE) { 408 VNT.insert(MI, CurrVN++); 409 Exps.push_back(MI); 410 continue; 411 } 412 413 // Found a common subexpression, eliminate it. 414 unsigned CSVN = VNT.lookup(MI); 415 MachineInstr *CSMI = Exps[CSVN]; 416 DEBUG(dbgs() << "Examining: " << *MI); 417 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 418 419 // Check if it's profitable to perform this CSE. 420 bool DoCSE = true; 421 unsigned NumDefs = MI->getDesc().getNumDefs(); 422 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 423 MachineOperand &MO = MI->getOperand(i); 424 if (!MO.isReg() || !MO.isDef()) 425 continue; 426 unsigned OldReg = MO.getReg(); 427 unsigned NewReg = CSMI->getOperand(i).getReg(); 428 if (OldReg == NewReg) 429 continue; 430 assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 431 TargetRegisterInfo::isVirtualRegister(NewReg) && 432 "Do not CSE physical register defs!"); 433 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 434 DoCSE = false; 435 break; 436 } 437 CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 438 --NumDefs; 439 } 440 441 // Actually perform the elimination. 442 if (DoCSE) { 443 for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { 444 MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 445 MRI->clearKillFlags(CSEPairs[i].second); 446 } 447 MI->eraseFromParent(); 448 ++NumCSEs; 449 if (!PhysRefs.empty()) 450 ++NumPhysCSEs; 451 if (Commuted) 452 ++NumCommutes; 453 } else { 454 DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 455 VNT.insert(MI, CurrVN++); 456 Exps.push_back(MI); 457 } 458 CSEPairs.clear(); 459 } 460 461 return Changed; 462} 463 464/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 465/// dominator tree node if its a leaf or all of its children are done. Walk 466/// up the dominator tree to destroy ancestors which are now done. 467void 468MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 469 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 470 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { 471 if (OpenChildren[Node]) 472 return; 473 474 // Pop scope. 475 ExitScope(Node->getBlock()); 476 477 // Now traverse upwards to pop ancestors whose offsprings are all done. 478 while (MachineDomTreeNode *Parent = ParentMap[Node]) { 479 unsigned Left = --OpenChildren[Parent]; 480 if (Left != 0) 481 break; 482 ExitScope(Parent->getBlock()); 483 Node = Parent; 484 } 485} 486 487bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 488 SmallVector<MachineDomTreeNode*, 32> Scopes; 489 SmallVector<MachineDomTreeNode*, 8> WorkList; 490 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; 491 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 492 493 CurrVN = 0; 494 495 // Perform a DFS walk to determine the order of visit. 496 WorkList.push_back(Node); 497 do { 498 Node = WorkList.pop_back_val(); 499 Scopes.push_back(Node); 500 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 501 unsigned NumChildren = Children.size(); 502 OpenChildren[Node] = NumChildren; 503 for (unsigned i = 0; i != NumChildren; ++i) { 504 MachineDomTreeNode *Child = Children[i]; 505 ParentMap[Child] = Node; 506 WorkList.push_back(Child); 507 } 508 } while (!WorkList.empty()); 509 510 // Now perform CSE. 511 bool Changed = false; 512 for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 513 MachineDomTreeNode *Node = Scopes[i]; 514 MachineBasicBlock *MBB = Node->getBlock(); 515 EnterScope(MBB); 516 Changed |= ProcessBlock(MBB); 517 // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 518 ExitScopeIfDone(Node, OpenChildren, ParentMap); 519 } 520 521 return Changed; 522} 523 524bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 525 TII = MF.getTarget().getInstrInfo(); 526 TRI = MF.getTarget().getRegisterInfo(); 527 MRI = &MF.getRegInfo(); 528 AA = &getAnalysis<AliasAnalysis>(); 529 DT = &getAnalysis<MachineDominatorTree>(); 530 return PerformCSE(DT->getRootNode()); 531} 532