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