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#include "llvm/CodeGen/Passes.h" 17#include "llvm/ADT/DenseMap.h" 18#include "llvm/ADT/ScopedHashTable.h" 19#include "llvm/ADT/SmallSet.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/CodeGen/MachineDominators.h" 23#include "llvm/CodeGen/MachineInstr.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/RecyclingAllocator.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetSubtargetInfo.h" 30using namespace llvm; 31 32#define DEBUG_TYPE "machine-cse" 33 34STATISTIC(NumCoalesces, "Number of copies coalesced"); 35STATISTIC(NumCSEs, "Number of common subexpression eliminated"); 36STATISTIC(NumPhysCSEs, 37 "Number of physreg referencing common subexpr eliminated"); 38STATISTIC(NumCrossBBCSEs, 39 "Number of cross-MBB physreg referencing CS eliminated"); 40STATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 41 42namespace { 43 class MachineCSE : public MachineFunctionPass { 44 const TargetInstrInfo *TII; 45 const TargetRegisterInfo *TRI; 46 AliasAnalysis *AA; 47 MachineDominatorTree *DT; 48 MachineRegisterInfo *MRI; 49 public: 50 static char ID; // Pass identification 51 MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(0), CurrVN(0) { 52 initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 53 } 54 55 bool runOnMachineFunction(MachineFunction &MF) override; 56 57 void getAnalysisUsage(AnalysisUsage &AU) const override { 58 AU.setPreservesCFG(); 59 MachineFunctionPass::getAnalysisUsage(AU); 60 AU.addRequired<AAResultsWrapperPass>(); 61 AU.addPreservedID(MachineLoopInfoID); 62 AU.addRequired<MachineDominatorTree>(); 63 AU.addPreserved<MachineDominatorTree>(); 64 } 65 66 void releaseMemory() override { 67 ScopeMap.clear(); 68 Exps.clear(); 69 } 70 71 private: 72 unsigned LookAheadLimit; 73 typedef RecyclingAllocator<BumpPtrAllocator, 74 ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 75 typedef ScopedHashTable<MachineInstr*, unsigned, 76 MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 77 typedef ScopedHTType::ScopeTy ScopeType; 78 DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 79 ScopedHTType VNT; 80 SmallVector<MachineInstr*, 64> Exps; 81 unsigned CurrVN; 82 83 bool PerformTrivialCopyPropagation(MachineInstr *MI, 84 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 SmallVectorImpl<unsigned> &PhysDefs, 92 bool &PhysUseDef) const; 93 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 94 SmallSet<unsigned,8> &PhysRefs, 95 SmallVectorImpl<unsigned> &PhysDefs, 96 bool &NonLocal) const; 97 bool isCSECandidate(MachineInstr *MI); 98 bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 99 MachineInstr *CSMI, MachineInstr *MI); 100 void EnterScope(MachineBasicBlock *MBB); 101 void ExitScope(MachineBasicBlock *MBB); 102 bool ProcessBlock(MachineBasicBlock *MBB); 103 void ExitScopeIfDone(MachineDomTreeNode *Node, 104 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); 105 bool PerformCSE(MachineDomTreeNode *Node); 106 }; 107} // end anonymous namespace 108 109char MachineCSE::ID = 0; 110char &llvm::MachineCSEID = MachineCSE::ID; 111INITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 112 "Machine Common Subexpression Elimination", false, false) 113INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 114INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 115INITIALIZE_PASS_END(MachineCSE, "machine-cse", 116 "Machine Common Subexpression Elimination", false, false) 117 118/// The source register of a COPY machine instruction can be propagated to all 119/// its users, and this propagation could increase the probability of finding 120/// common subexpressions. If the COPY has only one user, the COPY itself can 121/// be removed. 122bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, 123 MachineBasicBlock *MBB) { 124 bool Changed = false; 125 for (MachineOperand &MO : MI->operands()) { 126 if (!MO.isReg() || !MO.isUse()) 127 continue; 128 unsigned Reg = MO.getReg(); 129 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 130 continue; 131 bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg); 132 MachineInstr *DefMI = MRI->getVRegDef(Reg); 133 if (!DefMI->isCopy()) 134 continue; 135 unsigned SrcReg = DefMI->getOperand(1).getReg(); 136 if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 137 continue; 138 if (DefMI->getOperand(0).getSubReg()) 139 continue; 140 // FIXME: We should trivially coalesce subregister copies to expose CSE 141 // opportunities on instructions with truncated operands (see 142 // cse-add-with-overflow.ll). This can be done here as follows: 143 // if (SrcSubReg) 144 // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC, 145 // SrcSubReg); 146 // MO.substVirtReg(SrcReg, SrcSubReg, *TRI); 147 // 148 // The 2-addr pass has been updated to handle coalesced subregs. However, 149 // some machine-specific code still can't handle it. 150 // To handle it properly we also need a way find a constrained subregister 151 // class given a super-reg class and subreg index. 152 if (DefMI->getOperand(1).getSubReg()) 153 continue; 154 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 155 if (!MRI->constrainRegClass(SrcReg, RC)) 156 continue; 157 DEBUG(dbgs() << "Coalescing: " << *DefMI); 158 DEBUG(dbgs() << "*** to: " << *MI); 159 // Propagate SrcReg of copies to MI. 160 MO.setReg(SrcReg); 161 MRI->clearKillFlags(SrcReg); 162 // Coalesce single use copies. 163 if (OnlyOneUse) { 164 DefMI->eraseFromParent(); 165 ++NumCoalesces; 166 } 167 Changed = true; 168 } 169 170 return Changed; 171} 172 173bool 174MachineCSE::isPhysDefTriviallyDead(unsigned Reg, 175 MachineBasicBlock::const_iterator I, 176 MachineBasicBlock::const_iterator E) const { 177 unsigned LookAheadLeft = LookAheadLimit; 178 while (LookAheadLeft) { 179 // Skip over dbg_value's. 180 while (I != E && I->isDebugValue()) 181 ++I; 182 183 if (I == E) 184 // Reached end of block, register is obviously dead. 185 return true; 186 187 bool SeenDef = false; 188 for (const MachineOperand &MO : I->operands()) { 189 if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 190 SeenDef = true; 191 if (!MO.isReg() || !MO.getReg()) 192 continue; 193 if (!TRI->regsOverlap(MO.getReg(), Reg)) 194 continue; 195 if (MO.isUse()) 196 // Found a use! 197 return false; 198 SeenDef = true; 199 } 200 if (SeenDef) 201 // See a def of Reg (or an alias) before encountering any use, it's 202 // trivially dead. 203 return true; 204 205 --LookAheadLeft; 206 ++I; 207 } 208 return false; 209} 210 211/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 212/// physical registers (except for dead defs of physical registers). It also 213/// returns the physical register def by reference if it's the only one and the 214/// instruction does not uses a physical register. 215bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 216 const MachineBasicBlock *MBB, 217 SmallSet<unsigned,8> &PhysRefs, 218 SmallVectorImpl<unsigned> &PhysDefs, 219 bool &PhysUseDef) const{ 220 // First, add all uses to PhysRefs. 221 for (const MachineOperand &MO : MI->operands()) { 222 if (!MO.isReg() || MO.isDef()) 223 continue; 224 unsigned Reg = MO.getReg(); 225 if (!Reg) 226 continue; 227 if (TargetRegisterInfo::isVirtualRegister(Reg)) 228 continue; 229 // Reading constant physregs is ok. 230 if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 231 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 232 PhysRefs.insert(*AI); 233 } 234 235 // Next, collect all defs into PhysDefs. If any is already in PhysRefs 236 // (which currently contains only uses), set the PhysUseDef flag. 237 PhysUseDef = false; 238 MachineBasicBlock::const_iterator I = MI; I = std::next(I); 239 for (const MachineOperand &MO : MI->operands()) { 240 if (!MO.isReg() || !MO.isDef()) 241 continue; 242 unsigned Reg = MO.getReg(); 243 if (!Reg) 244 continue; 245 if (TargetRegisterInfo::isVirtualRegister(Reg)) 246 continue; 247 // Check against PhysRefs even if the def is "dead". 248 if (PhysRefs.count(Reg)) 249 PhysUseDef = true; 250 // If the def is dead, it's ok. But the def may not marked "dead". That's 251 // common since this pass is run before livevariables. We can scan 252 // forward a few instructions and check if it is obviously dead. 253 if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end())) 254 PhysDefs.push_back(Reg); 255 } 256 257 // Finally, add all defs to PhysRefs as well. 258 for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) 259 for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI) 260 PhysRefs.insert(*AI); 261 262 return !PhysRefs.empty(); 263} 264 265bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 266 SmallSet<unsigned,8> &PhysRefs, 267 SmallVectorImpl<unsigned> &PhysDefs, 268 bool &NonLocal) const { 269 // For now conservatively returns false if the common subexpression is 270 // not in the same basic block as the given instruction. The only exception 271 // is if the common subexpression is in the sole predecessor block. 272 const MachineBasicBlock *MBB = MI->getParent(); 273 const MachineBasicBlock *CSMBB = CSMI->getParent(); 274 275 bool CrossMBB = false; 276 if (CSMBB != MBB) { 277 if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) 278 return false; 279 280 for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 281 if (MRI->isAllocatable(PhysDefs[i]) || MRI->isReserved(PhysDefs[i])) 282 // Avoid extending live range of physical registers if they are 283 //allocatable or reserved. 284 return false; 285 } 286 CrossMBB = true; 287 } 288 MachineBasicBlock::const_iterator I = CSMI; I = std::next(I); 289 MachineBasicBlock::const_iterator E = MI; 290 MachineBasicBlock::const_iterator EE = CSMBB->end(); 291 unsigned LookAheadLeft = LookAheadLimit; 292 while (LookAheadLeft) { 293 // Skip over dbg_value's. 294 while (I != E && I != EE && I->isDebugValue()) 295 ++I; 296 297 if (I == EE) { 298 assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); 299 (void)CrossMBB; 300 CrossMBB = false; 301 NonLocal = true; 302 I = MBB->begin(); 303 EE = MBB->end(); 304 continue; 305 } 306 307 if (I == E) 308 return true; 309 310 for (const MachineOperand &MO : I->operands()) { 311 // RegMasks go on instructions like calls that clobber lots of physregs. 312 // Don't attempt to CSE across such an instruction. 313 if (MO.isRegMask()) 314 return false; 315 if (!MO.isReg() || !MO.isDef()) 316 continue; 317 unsigned MOReg = MO.getReg(); 318 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 319 continue; 320 if (PhysRefs.count(MOReg)) 321 return false; 322 } 323 324 --LookAheadLeft; 325 ++I; 326 } 327 328 return false; 329} 330 331bool MachineCSE::isCSECandidate(MachineInstr *MI) { 332 if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() || 333 MI->isInlineAsm() || MI->isDebugValue()) 334 return false; 335 336 // Ignore copies. 337 if (MI->isCopyLike()) 338 return false; 339 340 // Ignore stuff that we obviously can't move. 341 if (MI->mayStore() || MI->isCall() || MI->isTerminator() || 342 MI->hasUnmodeledSideEffects()) 343 return false; 344 345 if (MI->mayLoad()) { 346 // Okay, this instruction does a load. As a refinement, we allow the target 347 // to decide whether the loaded value is actually a constant. If so, we can 348 // actually use it as a load. 349 if (!MI->isInvariantLoad(AA)) 350 // FIXME: we should be able to hoist loads with no other side effects if 351 // there are no other instructions which can change memory in this loop. 352 // This is a trivial form of alias analysis. 353 return false; 354 } 355 356 // Ignore stack guard loads, otherwise the register that holds CSEed value may 357 // be spilled and get loaded back with corrupted data. 358 if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD) 359 return false; 360 361 return true; 362} 363 364/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 365/// common expression that defines Reg. 366bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 367 MachineInstr *CSMI, MachineInstr *MI) { 368 // FIXME: Heuristics that works around the lack the live range splitting. 369 370 // If CSReg is used at all uses of Reg, CSE should not increase register 371 // pressure of CSReg. 372 bool MayIncreasePressure = true; 373 if (TargetRegisterInfo::isVirtualRegister(CSReg) && 374 TargetRegisterInfo::isVirtualRegister(Reg)) { 375 MayIncreasePressure = false; 376 SmallPtrSet<MachineInstr*, 8> CSUses; 377 for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { 378 CSUses.insert(&MI); 379 } 380 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 381 if (!CSUses.count(&MI)) { 382 MayIncreasePressure = true; 383 break; 384 } 385 } 386 } 387 if (!MayIncreasePressure) return true; 388 389 // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 390 // an immediate predecessor. We don't want to increase register pressure and 391 // end up causing other computation to be spilled. 392 if (TII->isAsCheapAsAMove(*MI)) { 393 MachineBasicBlock *CSBB = CSMI->getParent(); 394 MachineBasicBlock *BB = MI->getParent(); 395 if (CSBB != BB && !CSBB->isSuccessor(BB)) 396 return false; 397 } 398 399 // Heuristics #2: If the expression doesn't not use a vr and the only use 400 // of the redundant computation are copies, do not cse. 401 bool HasVRegUse = false; 402 for (const MachineOperand &MO : MI->operands()) { 403 if (MO.isReg() && MO.isUse() && 404 TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 405 HasVRegUse = true; 406 break; 407 } 408 } 409 if (!HasVRegUse) { 410 bool HasNonCopyUse = false; 411 for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 412 // Ignore copies. 413 if (!MI.isCopyLike()) { 414 HasNonCopyUse = true; 415 break; 416 } 417 } 418 if (!HasNonCopyUse) 419 return false; 420 } 421 422 // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 423 // it unless the defined value is already used in the BB of the new use. 424 bool HasPHI = false; 425 SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 426 for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { 427 HasPHI |= MI.isPHI(); 428 CSBBs.insert(MI.getParent()); 429 } 430 431 if (!HasPHI) 432 return true; 433 return CSBBs.count(MI->getParent()); 434} 435 436void MachineCSE::EnterScope(MachineBasicBlock *MBB) { 437 DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 438 ScopeType *Scope = new ScopeType(VNT); 439 ScopeMap[MBB] = Scope; 440} 441 442void MachineCSE::ExitScope(MachineBasicBlock *MBB) { 443 DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 444 DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 445 assert(SI != ScopeMap.end()); 446 delete SI->second; 447 ScopeMap.erase(SI); 448} 449 450bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 451 bool Changed = false; 452 453 SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 454 SmallVector<unsigned, 2> ImplicitDefsToUpdate; 455 SmallVector<unsigned, 2> ImplicitDefs; 456 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 457 MachineInstr *MI = &*I; 458 ++I; 459 460 if (!isCSECandidate(MI)) 461 continue; 462 463 bool FoundCSE = VNT.count(MI); 464 if (!FoundCSE) { 465 // Using trivial copy propagation to find more CSE opportunities. 466 if (PerformTrivialCopyPropagation(MI, MBB)) { 467 Changed = true; 468 469 // After coalescing MI itself may become a copy. 470 if (MI->isCopyLike()) 471 continue; 472 473 // Try again to see if CSE is possible. 474 FoundCSE = VNT.count(MI); 475 } 476 } 477 478 // Commute commutable instructions. 479 bool Commuted = false; 480 if (!FoundCSE && MI->isCommutable()) { 481 if (MachineInstr *NewMI = TII->commuteInstruction(*MI)) { 482 Commuted = true; 483 FoundCSE = VNT.count(NewMI); 484 if (NewMI != MI) { 485 // New instruction. It doesn't need to be kept. 486 NewMI->eraseFromParent(); 487 Changed = true; 488 } else if (!FoundCSE) 489 // MI was changed but it didn't help, commute it back! 490 (void)TII->commuteInstruction(*MI); 491 } 492 } 493 494 // If the instruction defines physical registers and the values *may* be 495 // used, then it's not safe to replace it with a common subexpression. 496 // It's also not safe if the instruction uses physical registers. 497 bool CrossMBBPhysDef = false; 498 SmallSet<unsigned, 8> PhysRefs; 499 SmallVector<unsigned, 2> PhysDefs; 500 bool PhysUseDef = false; 501 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, 502 PhysDefs, PhysUseDef)) { 503 FoundCSE = false; 504 505 // ... Unless the CS is local or is in the sole predecessor block 506 // and it also defines the physical register which is not clobbered 507 // in between and the physical register uses were not clobbered. 508 // This can never be the case if the instruction both uses and 509 // defines the same physical register, which was detected above. 510 if (!PhysUseDef) { 511 unsigned CSVN = VNT.lookup(MI); 512 MachineInstr *CSMI = Exps[CSVN]; 513 if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) 514 FoundCSE = true; 515 } 516 } 517 518 if (!FoundCSE) { 519 VNT.insert(MI, CurrVN++); 520 Exps.push_back(MI); 521 continue; 522 } 523 524 // Found a common subexpression, eliminate it. 525 unsigned CSVN = VNT.lookup(MI); 526 MachineInstr *CSMI = Exps[CSVN]; 527 DEBUG(dbgs() << "Examining: " << *MI); 528 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 529 530 // Check if it's profitable to perform this CSE. 531 bool DoCSE = true; 532 unsigned NumDefs = MI->getDesc().getNumDefs() + 533 MI->getDesc().getNumImplicitDefs(); 534 535 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 536 MachineOperand &MO = MI->getOperand(i); 537 if (!MO.isReg() || !MO.isDef()) 538 continue; 539 unsigned OldReg = MO.getReg(); 540 unsigned NewReg = CSMI->getOperand(i).getReg(); 541 542 // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 543 // we should make sure it is not dead at CSMI. 544 if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) 545 ImplicitDefsToUpdate.push_back(i); 546 547 // Keep track of implicit defs of CSMI and MI, to clear possibly 548 // made-redundant kill flags. 549 if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg) 550 ImplicitDefs.push_back(OldReg); 551 552 if (OldReg == NewReg) { 553 --NumDefs; 554 continue; 555 } 556 557 assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 558 TargetRegisterInfo::isVirtualRegister(NewReg) && 559 "Do not CSE physical register defs!"); 560 561 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 562 DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 563 DoCSE = false; 564 break; 565 } 566 567 // Don't perform CSE if the result of the old instruction cannot exist 568 // within the register class of the new instruction. 569 const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg); 570 if (!MRI->constrainRegClass(NewReg, OldRC)) { 571 DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n"); 572 DoCSE = false; 573 break; 574 } 575 576 CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 577 --NumDefs; 578 } 579 580 // Actually perform the elimination. 581 if (DoCSE) { 582 for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) { 583 unsigned OldReg = CSEPair.first; 584 unsigned NewReg = CSEPair.second; 585 // OldReg may have been unused but is used now, clear the Dead flag 586 MachineInstr *Def = MRI->getUniqueVRegDef(NewReg); 587 assert(Def != nullptr && "CSEd register has no unique definition?"); 588 Def->clearRegisterDeads(NewReg); 589 // Replace with NewReg and clear kill flags which may be wrong now. 590 MRI->replaceRegWith(OldReg, NewReg); 591 MRI->clearKillFlags(NewReg); 592 } 593 594 // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 595 // we should make sure it is not dead at CSMI. 596 for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate) 597 CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false); 598 599 // Go through implicit defs of CSMI and MI, and clear the kill flags on 600 // their uses in all the instructions between CSMI and MI. 601 // We might have made some of the kill flags redundant, consider: 602 // subs ... %NZCV<imp-def> <- CSMI 603 // csinc ... %NZCV<imp-use,kill> <- this kill flag isn't valid anymore 604 // subs ... %NZCV<imp-def> <- MI, to be eliminated 605 // csinc ... %NZCV<imp-use,kill> 606 // Since we eliminated MI, and reused a register imp-def'd by CSMI 607 // (here %NZCV), that register, if it was killed before MI, should have 608 // that kill flag removed, because it's lifetime was extended. 609 if (CSMI->getParent() == MI->getParent()) { 610 for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II) 611 for (auto ImplicitDef : ImplicitDefs) 612 if (MachineOperand *MO = II->findRegisterUseOperand( 613 ImplicitDef, /*isKill=*/true, TRI)) 614 MO->setIsKill(false); 615 } else { 616 // If the instructions aren't in the same BB, bail out and clear the 617 // kill flag on all uses of the imp-def'd register. 618 for (auto ImplicitDef : ImplicitDefs) 619 MRI->clearKillFlags(ImplicitDef); 620 } 621 622 if (CrossMBBPhysDef) { 623 // Add physical register defs now coming in from a predecessor to MBB 624 // livein list. 625 while (!PhysDefs.empty()) { 626 unsigned LiveIn = PhysDefs.pop_back_val(); 627 if (!MBB->isLiveIn(LiveIn)) 628 MBB->addLiveIn(LiveIn); 629 } 630 ++NumCrossBBCSEs; 631 } 632 633 MI->eraseFromParent(); 634 ++NumCSEs; 635 if (!PhysRefs.empty()) 636 ++NumPhysCSEs; 637 if (Commuted) 638 ++NumCommutes; 639 Changed = true; 640 } else { 641 VNT.insert(MI, CurrVN++); 642 Exps.push_back(MI); 643 } 644 CSEPairs.clear(); 645 ImplicitDefsToUpdate.clear(); 646 ImplicitDefs.clear(); 647 } 648 649 return Changed; 650} 651 652/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 653/// dominator tree node if its a leaf or all of its children are done. Walk 654/// up the dominator tree to destroy ancestors which are now done. 655void 656MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 657 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { 658 if (OpenChildren[Node]) 659 return; 660 661 // Pop scope. 662 ExitScope(Node->getBlock()); 663 664 // Now traverse upwards to pop ancestors whose offsprings are all done. 665 while (MachineDomTreeNode *Parent = Node->getIDom()) { 666 unsigned Left = --OpenChildren[Parent]; 667 if (Left != 0) 668 break; 669 ExitScope(Parent->getBlock()); 670 Node = Parent; 671 } 672} 673 674bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 675 SmallVector<MachineDomTreeNode*, 32> Scopes; 676 SmallVector<MachineDomTreeNode*, 8> WorkList; 677 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 678 679 CurrVN = 0; 680 681 // Perform a DFS walk to determine the order of visit. 682 WorkList.push_back(Node); 683 do { 684 Node = WorkList.pop_back_val(); 685 Scopes.push_back(Node); 686 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 687 OpenChildren[Node] = Children.size(); 688 for (MachineDomTreeNode *Child : Children) 689 WorkList.push_back(Child); 690 } while (!WorkList.empty()); 691 692 // Now perform CSE. 693 bool Changed = false; 694 for (MachineDomTreeNode *Node : Scopes) { 695 MachineBasicBlock *MBB = Node->getBlock(); 696 EnterScope(MBB); 697 Changed |= ProcessBlock(MBB); 698 // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 699 ExitScopeIfDone(Node, OpenChildren); 700 } 701 702 return Changed; 703} 704 705bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 706 if (skipFunction(*MF.getFunction())) 707 return false; 708 709 TII = MF.getSubtarget().getInstrInfo(); 710 TRI = MF.getSubtarget().getRegisterInfo(); 711 MRI = &MF.getRegInfo(); 712 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 713 DT = &getAnalysis<MachineDominatorTree>(); 714 LookAheadLimit = TII->getMachineCSELookAheadLimit(); 715 return PerformCSE(DT->getRootNode()); 716} 717