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