1204642Srdivacky//===-- MachineCSE.cpp - Machine Common Subexpression Elimination Pass ----===// 2204642Srdivacky// 3204642Srdivacky// The LLVM Compiler Infrastructure 4204642Srdivacky// 5204642Srdivacky// This file is distributed under the University of Illinois Open Source 6204642Srdivacky// License. See LICENSE.TXT for details. 7204642Srdivacky// 8204642Srdivacky//===----------------------------------------------------------------------===// 9204642Srdivacky// 10204642Srdivacky// This pass performs global common subexpression elimination on machine 11204642Srdivacky// instructions using a scoped hash table based value numbering scheme. It 12204642Srdivacky// must be run while the machine function is still in SSA form. 13204642Srdivacky// 14204642Srdivacky//===----------------------------------------------------------------------===// 15204642Srdivacky 16204642Srdivacky#define DEBUG_TYPE "machine-cse" 17204642Srdivacky#include "llvm/CodeGen/Passes.h" 18207618Srdivacky#include "llvm/ADT/DenseMap.h" 19204642Srdivacky#include "llvm/ADT/ScopedHashTable.h" 20218893Sdim#include "llvm/ADT/SmallSet.h" 21204642Srdivacky#include "llvm/ADT/Statistic.h" 22249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 23249423Sdim#include "llvm/CodeGen/MachineDominators.h" 24249423Sdim#include "llvm/CodeGen/MachineInstr.h" 25249423Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 26204642Srdivacky#include "llvm/Support/Debug.h" 27218893Sdim#include "llvm/Support/RecyclingAllocator.h" 28249423Sdim#include "llvm/Target/TargetInstrInfo.h" 29204642Srdivackyusing namespace llvm; 30204642Srdivacky 31204792SrdivackySTATISTIC(NumCoalesces, "Number of copies coalesced"); 32204792SrdivackySTATISTIC(NumCSEs, "Number of common subexpression eliminated"); 33218893SdimSTATISTIC(NumPhysCSEs, 34218893Sdim "Number of physreg referencing common subexpr eliminated"); 35234353SdimSTATISTIC(NumCrossBBCSEs, 36234353Sdim "Number of cross-MBB physreg referencing CS eliminated"); 37218893SdimSTATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 38204642Srdivacky 39204642Srdivackynamespace { 40204642Srdivacky class MachineCSE : public MachineFunctionPass { 41204642Srdivacky const TargetInstrInfo *TII; 42204792Srdivacky const TargetRegisterInfo *TRI; 43204961Srdivacky AliasAnalysis *AA; 44204642Srdivacky MachineDominatorTree *DT; 45204961Srdivacky MachineRegisterInfo *MRI; 46204642Srdivacky public: 47204642Srdivacky static char ID; // Pass identification 48218893Sdim MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { 49218893Sdim initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 50218893Sdim } 51204642Srdivacky 52204642Srdivacky virtual bool runOnMachineFunction(MachineFunction &MF); 53234353Sdim 54204642Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55204642Srdivacky AU.setPreservesCFG(); 56204642Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 57204792Srdivacky AU.addRequired<AliasAnalysis>(); 58212904Sdim AU.addPreservedID(MachineLoopInfoID); 59204642Srdivacky AU.addRequired<MachineDominatorTree>(); 60204642Srdivacky AU.addPreserved<MachineDominatorTree>(); 61204642Srdivacky } 62204642Srdivacky 63213534Sdim virtual void releaseMemory() { 64213534Sdim ScopeMap.clear(); 65213534Sdim Exps.clear(); 66213534Sdim } 67213534Sdim 68204642Srdivacky private: 69208599Srdivacky const unsigned LookAheadLimit; 70218893Sdim typedef RecyclingAllocator<BumpPtrAllocator, 71218893Sdim ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 72218893Sdim typedef ScopedHashTable<MachineInstr*, unsigned, 73218893Sdim MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 74218893Sdim typedef ScopedHTType::ScopeTy ScopeType; 75207618Srdivacky DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 76218893Sdim ScopedHTType VNT; 77204792Srdivacky SmallVector<MachineInstr*, 64> Exps; 78207618Srdivacky unsigned CurrVN; 79204792Srdivacky 80204642Srdivacky bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 81204792Srdivacky bool isPhysDefTriviallyDead(unsigned Reg, 82204792Srdivacky MachineBasicBlock::const_iterator I, 83239462Sdim MachineBasicBlock::const_iterator E) const; 84218893Sdim bool hasLivePhysRegDefUses(const MachineInstr *MI, 85218893Sdim const MachineBasicBlock *MBB, 86234353Sdim SmallSet<unsigned,8> &PhysRefs, 87263508Sdim SmallVectorImpl<unsigned> &PhysDefs, 88243830Sdim bool &PhysUseDef) const; 89218893Sdim bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 90234353Sdim SmallSet<unsigned,8> &PhysRefs, 91263508Sdim SmallVectorImpl<unsigned> &PhysDefs, 92234353Sdim bool &NonLocal) const; 93204792Srdivacky bool isCSECandidate(MachineInstr *MI); 94204961Srdivacky bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 95204961Srdivacky MachineInstr *CSMI, MachineInstr *MI); 96207618Srdivacky void EnterScope(MachineBasicBlock *MBB); 97207618Srdivacky void ExitScope(MachineBasicBlock *MBB); 98207618Srdivacky bool ProcessBlock(MachineBasicBlock *MBB); 99207618Srdivacky void ExitScopeIfDone(MachineDomTreeNode *Node, 100239462Sdim DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); 101207618Srdivacky bool PerformCSE(MachineDomTreeNode *Node); 102204642Srdivacky }; 103204642Srdivacky} // end anonymous namespace 104204642Srdivacky 105204642Srdivackychar MachineCSE::ID = 0; 106234353Sdimchar &llvm::MachineCSEID = MachineCSE::ID; 107218893SdimINITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 108218893Sdim "Machine Common Subexpression Elimination", false, false) 109218893SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 110218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 111218893SdimINITIALIZE_PASS_END(MachineCSE, "machine-cse", 112218893Sdim "Machine Common Subexpression Elimination", false, false) 113204642Srdivacky 114204642Srdivackybool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 115204642Srdivacky MachineBasicBlock *MBB) { 116204642Srdivacky bool Changed = false; 117204642Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 118204642Srdivacky MachineOperand &MO = MI->getOperand(i); 119204792Srdivacky if (!MO.isReg() || !MO.isUse()) 120204792Srdivacky continue; 121204792Srdivacky unsigned Reg = MO.getReg(); 122218893Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 123204792Srdivacky continue; 124213534Sdim if (!MRI->hasOneNonDBGUse(Reg)) 125204792Srdivacky // Only coalesce single use copies. This ensure the copy will be 126204792Srdivacky // deleted. 127204792Srdivacky continue; 128204792Srdivacky MachineInstr *DefMI = MRI->getVRegDef(Reg); 129210299Sed if (!DefMI->isCopy()) 130210299Sed continue; 131212904Sdim unsigned SrcReg = DefMI->getOperand(1).getReg(); 132210299Sed if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 133210299Sed continue; 134210299Sed if (DefMI->getOperand(0).getSubReg() || DefMI->getOperand(1).getSubReg()) 135210299Sed continue; 136218893Sdim if (!MRI->constrainRegClass(SrcReg, MRI->getRegClass(Reg))) 137210299Sed continue; 138210299Sed DEBUG(dbgs() << "Coalescing: " << *DefMI); 139218893Sdim DEBUG(dbgs() << "*** to: " << *MI); 140210299Sed MO.setReg(SrcReg); 141210299Sed MRI->clearKillFlags(SrcReg); 142210299Sed DefMI->eraseFromParent(); 143210299Sed ++NumCoalesces; 144210299Sed Changed = true; 145204642Srdivacky } 146204642Srdivacky 147204642Srdivacky return Changed; 148204642Srdivacky} 149204642Srdivacky 150208599Srdivackybool 151208599SrdivackyMachineCSE::isPhysDefTriviallyDead(unsigned Reg, 152208599Srdivacky MachineBasicBlock::const_iterator I, 153208599Srdivacky MachineBasicBlock::const_iterator E) const { 154208599Srdivacky unsigned LookAheadLeft = LookAheadLimit; 155206083Srdivacky while (LookAheadLeft) { 156206083Srdivacky // Skip over dbg_value's. 157206083Srdivacky while (I != E && I->isDebugValue()) 158206083Srdivacky ++I; 159206083Srdivacky 160204792Srdivacky if (I == E) 161204792Srdivacky // Reached end of block, register is obviously dead. 162204792Srdivacky return true; 163204792Srdivacky 164204792Srdivacky bool SeenDef = false; 165204792Srdivacky for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 166204792Srdivacky const MachineOperand &MO = I->getOperand(i); 167234353Sdim if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 168234353Sdim SeenDef = true; 169204792Srdivacky if (!MO.isReg() || !MO.getReg()) 170204792Srdivacky continue; 171204792Srdivacky if (!TRI->regsOverlap(MO.getReg(), Reg)) 172204792Srdivacky continue; 173204792Srdivacky if (MO.isUse()) 174208599Srdivacky // Found a use! 175204792Srdivacky return false; 176204792Srdivacky SeenDef = true; 177204792Srdivacky } 178204792Srdivacky if (SeenDef) 179234353Sdim // See a def of Reg (or an alias) before encountering any use, it's 180204792Srdivacky // trivially dead. 181204792Srdivacky return true; 182206083Srdivacky 183206083Srdivacky --LookAheadLeft; 184204792Srdivacky ++I; 185204792Srdivacky } 186204792Srdivacky return false; 187204792Srdivacky} 188204792Srdivacky 189218893Sdim/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 190208599Srdivacky/// physical registers (except for dead defs of physical registers). It also 191210299Sed/// returns the physical register def by reference if it's the only one and the 192210299Sed/// instruction does not uses a physical register. 193218893Sdimbool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 194218893Sdim const MachineBasicBlock *MBB, 195234353Sdim SmallSet<unsigned,8> &PhysRefs, 196263508Sdim SmallVectorImpl<unsigned> &PhysDefs, 197243830Sdim bool &PhysUseDef) const{ 198243830Sdim // First, add all uses to PhysRefs. 199243830Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 200243830Sdim const MachineOperand &MO = MI->getOperand(i); 201243830Sdim if (!MO.isReg() || MO.isDef()) 202243830Sdim continue; 203243830Sdim unsigned Reg = MO.getReg(); 204243830Sdim if (!Reg) 205243830Sdim continue; 206243830Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) 207243830Sdim continue; 208243830Sdim // Reading constant physregs is ok. 209243830Sdim if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 210243830Sdim for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 211243830Sdim PhysRefs.insert(*AI); 212243830Sdim } 213243830Sdim 214243830Sdim // Next, collect all defs into PhysDefs. If any is already in PhysRefs 215243830Sdim // (which currently contains only uses), set the PhysUseDef flag. 216243830Sdim PhysUseDef = false; 217218893Sdim MachineBasicBlock::const_iterator I = MI; I = llvm::next(I); 218204642Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 219208599Srdivacky const MachineOperand &MO = MI->getOperand(i); 220243830Sdim if (!MO.isReg() || !MO.isDef()) 221204642Srdivacky continue; 222204642Srdivacky unsigned Reg = MO.getReg(); 223204642Srdivacky if (!Reg) 224204642Srdivacky continue; 225208599Srdivacky if (TargetRegisterInfo::isVirtualRegister(Reg)) 226208599Srdivacky continue; 227243830Sdim // Check against PhysRefs even if the def is "dead". 228243830Sdim if (PhysRefs.count(Reg)) 229243830Sdim PhysUseDef = true; 230218893Sdim // If the def is dead, it's ok. But the def may not marked "dead". That's 231208599Srdivacky // common since this pass is run before livevariables. We can scan 232208599Srdivacky // forward a few instructions and check if it is obviously dead. 233243830Sdim if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end())) 234234353Sdim PhysDefs.push_back(Reg); 235204792Srdivacky } 236204792Srdivacky 237243830Sdim // Finally, add all defs to PhysRefs as well. 238243830Sdim for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) 239243830Sdim for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI) 240243830Sdim PhysRefs.insert(*AI); 241243830Sdim 242218893Sdim return !PhysRefs.empty(); 243204642Srdivacky} 244204642Srdivacky 245218893Sdimbool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 246234353Sdim SmallSet<unsigned,8> &PhysRefs, 247263508Sdim SmallVectorImpl<unsigned> &PhysDefs, 248234353Sdim bool &NonLocal) const { 249208599Srdivacky // For now conservatively returns false if the common subexpression is 250234353Sdim // not in the same basic block as the given instruction. The only exception 251234353Sdim // is if the common subexpression is in the sole predecessor block. 252234353Sdim const MachineBasicBlock *MBB = MI->getParent(); 253234353Sdim const MachineBasicBlock *CSMBB = CSMI->getParent(); 254234353Sdim 255234353Sdim bool CrossMBB = false; 256234353Sdim if (CSMBB != MBB) { 257234353Sdim if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) 258234353Sdim return false; 259234353Sdim 260234353Sdim for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 261243830Sdim if (MRI->isAllocatable(PhysDefs[i]) || MRI->isReserved(PhysDefs[i])) 262234353Sdim // Avoid extending live range of physical registers if they are 263234353Sdim //allocatable or reserved. 264234353Sdim return false; 265234353Sdim } 266234353Sdim CrossMBB = true; 267234353Sdim } 268208599Srdivacky MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I); 269208599Srdivacky MachineBasicBlock::const_iterator E = MI; 270234353Sdim MachineBasicBlock::const_iterator EE = CSMBB->end(); 271208599Srdivacky unsigned LookAheadLeft = LookAheadLimit; 272208599Srdivacky while (LookAheadLeft) { 273208599Srdivacky // Skip over dbg_value's. 274234353Sdim while (I != E && I != EE && I->isDebugValue()) 275208599Srdivacky ++I; 276208599Srdivacky 277234353Sdim if (I == EE) { 278234353Sdim assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); 279234353Sdim (void)CrossMBB; 280234353Sdim CrossMBB = false; 281234353Sdim NonLocal = true; 282234353Sdim I = MBB->begin(); 283234353Sdim EE = MBB->end(); 284234353Sdim continue; 285234353Sdim } 286234353Sdim 287208599Srdivacky if (I == E) 288208599Srdivacky return true; 289208599Srdivacky 290218893Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 291218893Sdim const MachineOperand &MO = I->getOperand(i); 292234353Sdim // RegMasks go on instructions like calls that clobber lots of physregs. 293234353Sdim // Don't attempt to CSE across such an instruction. 294234353Sdim if (MO.isRegMask()) 295234353Sdim return false; 296218893Sdim if (!MO.isReg() || !MO.isDef()) 297218893Sdim continue; 298218893Sdim unsigned MOReg = MO.getReg(); 299218893Sdim if (TargetRegisterInfo::isVirtualRegister(MOReg)) 300218893Sdim continue; 301218893Sdim if (PhysRefs.count(MOReg)) 302218893Sdim return false; 303218893Sdim } 304218893Sdim 305208599Srdivacky --LookAheadLeft; 306208599Srdivacky ++I; 307208599Srdivacky } 308208599Srdivacky 309208599Srdivacky return false; 310208599Srdivacky} 311208599Srdivacky 312204792Srdivackybool MachineCSE::isCSECandidate(MachineInstr *MI) { 313204961Srdivacky if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 314205218Srdivacky MI->isKill() || MI->isInlineAsm() || MI->isDebugValue()) 315204792Srdivacky return false; 316204792Srdivacky 317204961Srdivacky // Ignore copies. 318212904Sdim if (MI->isCopyLike()) 319204961Srdivacky return false; 320204961Srdivacky 321204792Srdivacky // Ignore stuff that we obviously can't move. 322234353Sdim if (MI->mayStore() || MI->isCall() || MI->isTerminator() || 323218893Sdim MI->hasUnmodeledSideEffects()) 324204792Srdivacky return false; 325204792Srdivacky 326234353Sdim if (MI->mayLoad()) { 327204792Srdivacky // Okay, this instruction does a load. As a refinement, we allow the target 328204792Srdivacky // to decide whether the loaded value is actually a constant. If so, we can 329204792Srdivacky // actually use it as a load. 330204792Srdivacky if (!MI->isInvariantLoad(AA)) 331204792Srdivacky // FIXME: we should be able to hoist loads with no other side effects if 332204792Srdivacky // there are no other instructions which can change memory in this loop. 333204792Srdivacky // This is a trivial form of alias analysis. 334204792Srdivacky return false; 335204792Srdivacky } 336204792Srdivacky return true; 337204792Srdivacky} 338204792Srdivacky 339204961Srdivacky/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 340204961Srdivacky/// common expression that defines Reg. 341204961Srdivackybool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 342204961Srdivacky MachineInstr *CSMI, MachineInstr *MI) { 343204961Srdivacky // FIXME: Heuristics that works around the lack the live range splitting. 344204961Srdivacky 345239462Sdim // If CSReg is used at all uses of Reg, CSE should not increase register 346239462Sdim // pressure of CSReg. 347239462Sdim bool MayIncreasePressure = true; 348239462Sdim if (TargetRegisterInfo::isVirtualRegister(CSReg) && 349239462Sdim TargetRegisterInfo::isVirtualRegister(Reg)) { 350239462Sdim MayIncreasePressure = false; 351239462Sdim SmallPtrSet<MachineInstr*, 8> CSUses; 352239462Sdim for (MachineRegisterInfo::use_nodbg_iterator I =MRI->use_nodbg_begin(CSReg), 353239462Sdim E = MRI->use_nodbg_end(); I != E; ++I) { 354239462Sdim MachineInstr *Use = &*I; 355239462Sdim CSUses.insert(Use); 356239462Sdim } 357239462Sdim for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 358239462Sdim E = MRI->use_nodbg_end(); I != E; ++I) { 359239462Sdim MachineInstr *Use = &*I; 360239462Sdim if (!CSUses.count(Use)) { 361239462Sdim MayIncreasePressure = true; 362239462Sdim break; 363239462Sdim } 364239462Sdim } 365239462Sdim } 366239462Sdim if (!MayIncreasePressure) return true; 367239462Sdim 368218893Sdim // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 369218893Sdim // an immediate predecessor. We don't want to increase register pressure and 370218893Sdim // end up causing other computation to be spilled. 371234353Sdim if (MI->isAsCheapAsAMove()) { 372204961Srdivacky MachineBasicBlock *CSBB = CSMI->getParent(); 373204961Srdivacky MachineBasicBlock *BB = MI->getParent(); 374218893Sdim if (CSBB != BB && !CSBB->isSuccessor(BB)) 375204961Srdivacky return false; 376204961Srdivacky } 377204961Srdivacky 378204961Srdivacky // Heuristics #2: If the expression doesn't not use a vr and the only use 379204961Srdivacky // of the redundant computation are copies, do not cse. 380204961Srdivacky bool HasVRegUse = false; 381204961Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 382204961Srdivacky const MachineOperand &MO = MI->getOperand(i); 383218893Sdim if (MO.isReg() && MO.isUse() && 384204961Srdivacky TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 385204961Srdivacky HasVRegUse = true; 386204961Srdivacky break; 387204961Srdivacky } 388204961Srdivacky } 389204961Srdivacky if (!HasVRegUse) { 390204961Srdivacky bool HasNonCopyUse = false; 391204961Srdivacky for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 392204961Srdivacky E = MRI->use_nodbg_end(); I != E; ++I) { 393204961Srdivacky MachineInstr *Use = &*I; 394204961Srdivacky // Ignore copies. 395212904Sdim if (!Use->isCopyLike()) { 396204961Srdivacky HasNonCopyUse = true; 397204961Srdivacky break; 398204961Srdivacky } 399204961Srdivacky } 400204961Srdivacky if (!HasNonCopyUse) 401204961Srdivacky return false; 402204961Srdivacky } 403204961Srdivacky 404204961Srdivacky // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 405204961Srdivacky // it unless the defined value is already used in the BB of the new use. 406204961Srdivacky bool HasPHI = false; 407204961Srdivacky SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 408204961Srdivacky for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg), 409204961Srdivacky E = MRI->use_nodbg_end(); I != E; ++I) { 410204961Srdivacky MachineInstr *Use = &*I; 411204961Srdivacky HasPHI |= Use->isPHI(); 412204961Srdivacky CSBBs.insert(Use->getParent()); 413204961Srdivacky } 414204961Srdivacky 415204961Srdivacky if (!HasPHI) 416204961Srdivacky return true; 417204961Srdivacky return CSBBs.count(MI->getParent()); 418204961Srdivacky} 419204961Srdivacky 420207618Srdivackyvoid MachineCSE::EnterScope(MachineBasicBlock *MBB) { 421207618Srdivacky DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 422207618Srdivacky ScopeType *Scope = new ScopeType(VNT); 423207618Srdivacky ScopeMap[MBB] = Scope; 424207618Srdivacky} 425207618Srdivacky 426207618Srdivackyvoid MachineCSE::ExitScope(MachineBasicBlock *MBB) { 427207618Srdivacky DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 428207618Srdivacky DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 429207618Srdivacky assert(SI != ScopeMap.end()); 430243830Sdim delete SI->second; 431207618Srdivacky ScopeMap.erase(SI); 432207618Srdivacky} 433207618Srdivacky 434207618Srdivackybool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 435204642Srdivacky bool Changed = false; 436204642Srdivacky 437204961Srdivacky SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 438239462Sdim SmallVector<unsigned, 2> ImplicitDefsToUpdate; 439204792Srdivacky for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 440204642Srdivacky MachineInstr *MI = &*I; 441204792Srdivacky ++I; 442204792Srdivacky 443204792Srdivacky if (!isCSECandidate(MI)) 444204642Srdivacky continue; 445204642Srdivacky 446204642Srdivacky bool FoundCSE = VNT.count(MI); 447204642Srdivacky if (!FoundCSE) { 448204642Srdivacky // Look for trivial copy coalescing opportunities. 449206083Srdivacky if (PerformTrivialCoalescing(MI, MBB)) { 450221345Sdim Changed = true; 451221345Sdim 452206083Srdivacky // After coalescing MI itself may become a copy. 453212904Sdim if (MI->isCopyLike()) 454206083Srdivacky continue; 455204642Srdivacky FoundCSE = VNT.count(MI); 456206083Srdivacky } 457204642Srdivacky } 458204642Srdivacky 459218893Sdim // Commute commutable instructions. 460218893Sdim bool Commuted = false; 461234353Sdim if (!FoundCSE && MI->isCommutable()) { 462218893Sdim MachineInstr *NewMI = TII->commuteInstruction(MI); 463218893Sdim if (NewMI) { 464218893Sdim Commuted = true; 465218893Sdim FoundCSE = VNT.count(NewMI); 466221345Sdim if (NewMI != MI) { 467218893Sdim // New instruction. It doesn't need to be kept. 468218893Sdim NewMI->eraseFromParent(); 469221345Sdim Changed = true; 470221345Sdim } else if (!FoundCSE) 471218893Sdim // MI was changed but it didn't help, commute it back! 472218893Sdim (void)TII->commuteInstruction(MI); 473218893Sdim } 474218893Sdim } 475218893Sdim 476218893Sdim // If the instruction defines physical registers and the values *may* be 477204792Srdivacky // used, then it's not safe to replace it with a common subexpression. 478218893Sdim // It's also not safe if the instruction uses physical registers. 479234353Sdim bool CrossMBBPhysDef = false; 480239462Sdim SmallSet<unsigned, 8> PhysRefs; 481234353Sdim SmallVector<unsigned, 2> PhysDefs; 482243830Sdim bool PhysUseDef = false; 483243830Sdim if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, 484243830Sdim PhysDefs, PhysUseDef)) { 485204792Srdivacky FoundCSE = false; 486204792Srdivacky 487234353Sdim // ... Unless the CS is local or is in the sole predecessor block 488234353Sdim // and it also defines the physical register which is not clobbered 489234353Sdim // in between and the physical register uses were not clobbered. 490243830Sdim // This can never be the case if the instruction both uses and 491243830Sdim // defines the same physical register, which was detected above. 492243830Sdim if (!PhysUseDef) { 493243830Sdim unsigned CSVN = VNT.lookup(MI); 494243830Sdim MachineInstr *CSMI = Exps[CSVN]; 495243830Sdim if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) 496243830Sdim FoundCSE = true; 497243830Sdim } 498208599Srdivacky } 499208599Srdivacky 500204792Srdivacky if (!FoundCSE) { 501204792Srdivacky VNT.insert(MI, CurrVN++); 502204792Srdivacky Exps.push_back(MI); 503204792Srdivacky continue; 504204792Srdivacky } 505204792Srdivacky 506204792Srdivacky // Found a common subexpression, eliminate it. 507204792Srdivacky unsigned CSVN = VNT.lookup(MI); 508204792Srdivacky MachineInstr *CSMI = Exps[CSVN]; 509204792Srdivacky DEBUG(dbgs() << "Examining: " << *MI); 510204792Srdivacky DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 511204961Srdivacky 512204961Srdivacky // Check if it's profitable to perform this CSE. 513204961Srdivacky bool DoCSE = true; 514239462Sdim unsigned NumDefs = MI->getDesc().getNumDefs() + 515239462Sdim MI->getDesc().getNumImplicitDefs(); 516239462Sdim 517204792Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 518204792Srdivacky MachineOperand &MO = MI->getOperand(i); 519204792Srdivacky if (!MO.isReg() || !MO.isDef()) 520204792Srdivacky continue; 521204792Srdivacky unsigned OldReg = MO.getReg(); 522204792Srdivacky unsigned NewReg = CSMI->getOperand(i).getReg(); 523239462Sdim 524239462Sdim // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 525239462Sdim // we should make sure it is not dead at CSMI. 526239462Sdim if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) 527239462Sdim ImplicitDefsToUpdate.push_back(i); 528239462Sdim if (OldReg == NewReg) { 529239462Sdim --NumDefs; 530204792Srdivacky continue; 531239462Sdim } 532226633Sdim 533204792Srdivacky assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 534204792Srdivacky TargetRegisterInfo::isVirtualRegister(NewReg) && 535204792Srdivacky "Do not CSE physical register defs!"); 536226633Sdim 537204961Srdivacky if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 538239462Sdim DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 539204961Srdivacky DoCSE = false; 540204961Srdivacky break; 541204961Srdivacky } 542226633Sdim 543226633Sdim // Don't perform CSE if the result of the old instruction cannot exist 544226633Sdim // within the register class of the new instruction. 545226633Sdim const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg); 546226633Sdim if (!MRI->constrainRegClass(NewReg, OldRC)) { 547239462Sdim DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n"); 548226633Sdim DoCSE = false; 549226633Sdim break; 550226633Sdim } 551226633Sdim 552204961Srdivacky CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 553204792Srdivacky --NumDefs; 554204792Srdivacky } 555204961Srdivacky 556204961Srdivacky // Actually perform the elimination. 557204961Srdivacky if (DoCSE) { 558208599Srdivacky for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { 559204961Srdivacky MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 560208599Srdivacky MRI->clearKillFlags(CSEPairs[i].second); 561208599Srdivacky } 562234353Sdim 563239462Sdim // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 564239462Sdim // we should make sure it is not dead at CSMI. 565239462Sdim for (unsigned i = 0, e = ImplicitDefsToUpdate.size(); i != e; ++i) 566239462Sdim CSMI->getOperand(ImplicitDefsToUpdate[i]).setIsDead(false); 567239462Sdim 568234353Sdim if (CrossMBBPhysDef) { 569234353Sdim // Add physical register defs now coming in from a predecessor to MBB 570234353Sdim // livein list. 571234353Sdim while (!PhysDefs.empty()) { 572234353Sdim unsigned LiveIn = PhysDefs.pop_back_val(); 573234353Sdim if (!MBB->isLiveIn(LiveIn)) 574234353Sdim MBB->addLiveIn(LiveIn); 575234353Sdim } 576234353Sdim ++NumCrossBBCSEs; 577234353Sdim } 578234353Sdim 579204961Srdivacky MI->eraseFromParent(); 580204961Srdivacky ++NumCSEs; 581218893Sdim if (!PhysRefs.empty()) 582210299Sed ++NumPhysCSEs; 583218893Sdim if (Commuted) 584218893Sdim ++NumCommutes; 585221345Sdim Changed = true; 586204961Srdivacky } else { 587204961Srdivacky VNT.insert(MI, CurrVN++); 588204961Srdivacky Exps.push_back(MI); 589204961Srdivacky } 590204961Srdivacky CSEPairs.clear(); 591239462Sdim ImplicitDefsToUpdate.clear(); 592204642Srdivacky } 593204642Srdivacky 594207618Srdivacky return Changed; 595207618Srdivacky} 596204642Srdivacky 597207618Srdivacky/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 598207618Srdivacky/// dominator tree node if its a leaf or all of its children are done. Walk 599207618Srdivacky/// up the dominator tree to destroy ancestors which are now done. 600207618Srdivackyvoid 601207618SrdivackyMachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 602239462Sdim DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { 603207618Srdivacky if (OpenChildren[Node]) 604207618Srdivacky return; 605207618Srdivacky 606207618Srdivacky // Pop scope. 607207618Srdivacky ExitScope(Node->getBlock()); 608207618Srdivacky 609207618Srdivacky // Now traverse upwards to pop ancestors whose offsprings are all done. 610239462Sdim while (MachineDomTreeNode *Parent = Node->getIDom()) { 611207618Srdivacky unsigned Left = --OpenChildren[Parent]; 612207618Srdivacky if (Left != 0) 613207618Srdivacky break; 614207618Srdivacky ExitScope(Parent->getBlock()); 615207618Srdivacky Node = Parent; 616207618Srdivacky } 617207618Srdivacky} 618207618Srdivacky 619207618Srdivackybool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 620207618Srdivacky SmallVector<MachineDomTreeNode*, 32> Scopes; 621207618Srdivacky SmallVector<MachineDomTreeNode*, 8> WorkList; 622207618Srdivacky DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 623207618Srdivacky 624213534Sdim CurrVN = 0; 625213534Sdim 626207618Srdivacky // Perform a DFS walk to determine the order of visit. 627207618Srdivacky WorkList.push_back(Node); 628207618Srdivacky do { 629207618Srdivacky Node = WorkList.pop_back_val(); 630207618Srdivacky Scopes.push_back(Node); 631207618Srdivacky const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 632207618Srdivacky unsigned NumChildren = Children.size(); 633207618Srdivacky OpenChildren[Node] = NumChildren; 634207618Srdivacky for (unsigned i = 0; i != NumChildren; ++i) { 635207618Srdivacky MachineDomTreeNode *Child = Children[i]; 636207618Srdivacky WorkList.push_back(Child); 637207618Srdivacky } 638207618Srdivacky } while (!WorkList.empty()); 639207618Srdivacky 640207618Srdivacky // Now perform CSE. 641207618Srdivacky bool Changed = false; 642207618Srdivacky for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 643207618Srdivacky MachineDomTreeNode *Node = Scopes[i]; 644207618Srdivacky MachineBasicBlock *MBB = Node->getBlock(); 645207618Srdivacky EnterScope(MBB); 646207618Srdivacky Changed |= ProcessBlock(MBB); 647207618Srdivacky // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 648239462Sdim ExitScopeIfDone(Node, OpenChildren); 649207618Srdivacky } 650207618Srdivacky 651204642Srdivacky return Changed; 652204642Srdivacky} 653204642Srdivacky 654204642Srdivackybool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 655204642Srdivacky TII = MF.getTarget().getInstrInfo(); 656204792Srdivacky TRI = MF.getTarget().getRegisterInfo(); 657204642Srdivacky MRI = &MF.getRegInfo(); 658204961Srdivacky AA = &getAnalysis<AliasAnalysis>(); 659204642Srdivacky DT = &getAnalysis<MachineDominatorTree>(); 660207618Srdivacky return PerformCSE(DT->getRootNode()); 661204642Srdivacky} 662