1c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng//===-- MachineCSE.cpp - Machine Common Subexpression Elimination Pass ----===// 2c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// 3c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// The LLVM Compiler Infrastructure 4c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// 5c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// This file is distributed under the University of Illinois Open Source 6c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// License. See LICENSE.TXT for details. 7c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// 8c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng//===----------------------------------------------------------------------===// 9c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// 10c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// This pass performs global common subexpression elimination on machine 11c5bbba1e499d46f52364e76ea95d4a37adced676Evan Cheng// instructions using a scoped hash table based value numbering scheme. It 12c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// must be run while the machine function is still in SSA form. 13c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng// 14c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng//===----------------------------------------------------------------------===// 15c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 16c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#define DEBUG_TYPE "machine-cse" 17c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/CodeGen/Passes.h" 18c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/CodeGen/MachineDominators.h" 19c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/CodeGen/MachineInstr.h" 206ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 21a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng#include "llvm/Analysis/AliasAnalysis.h" 226ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng#include "llvm/Target/TargetInstrInfo.h" 23311569861162c12b78b6c445793d4074aa4e4512Evan Cheng#include "llvm/ADT/DenseMap.h" 24c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/ADT/ScopedHashTable.h" 25189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng#include "llvm/ADT/SmallSet.h" 26c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/ADT/Statistic.h" 27c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/Support/Debug.h" 2853eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich#include "llvm/Support/RecyclingAllocator.h" 29c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengusing namespace llvm; 30c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 3116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan ChengSTATISTIC(NumCoalesces, "Number of copies coalesced"); 3216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan ChengSTATISTIC(NumCSEs, "Number of common subexpression eliminated"); 33189c1ec4c162ca3d36d9bca803b032eb19de434aEvan ChengSTATISTIC(NumPhysCSEs, 34189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng "Number of physreg referencing common subexpr eliminated"); 3597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan ChengSTATISTIC(NumCrossBBCSEs, 3697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng "Number of cross-MBB physreg referencing CS eliminated"); 37a63cde26ff698284ecdbec357966ca9d69e1d83aEvan ChengSTATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 383844173f6e5c2d3e309d71d8980e25cca1b9305dBob Wilson 39c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengnamespace { 40c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng class MachineCSE : public MachineFunctionPass { 416ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng const TargetInstrInfo *TII; 42b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const TargetRegisterInfo *TRI; 43a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AliasAnalysis *AA; 4431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineDominatorTree *DT; 4531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineRegisterInfo *MRI; 46c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng public: 47c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng static char ID; // Pass identification 48081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 50081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 51c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 52c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 531df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 54c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.setPreservesCFG(); 56c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng MachineFunctionPass::getAnalysisUsage(AU); 57a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AU.addRequired<AliasAnalysis>(); 586542416560589c9cfa6298d2edc73f3350ccf56aEvan Cheng AU.addPreservedID(MachineLoopInfoID); 59c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addRequired<MachineDominatorTree>(); 60c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addPreserved<MachineDominatorTree>(); 61c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 62c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 63c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng virtual void releaseMemory() { 64c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng ScopeMap.clear(); 65c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng Exps.clear(); 66c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames AllocatableRegs.clear(); 67c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames ReservedRegs.clear(); 68c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng } 69c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 70c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng private: 71835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const unsigned LookAheadLimit; 7253eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef RecyclingAllocator<BumpPtrAllocator, 7353eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 7453eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHashTable<MachineInstr*, unsigned, 7553eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 7653eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHTType::ScopeTy ScopeType; 77311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 7853eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHTType VNT; 7916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng SmallVector<MachineInstr*, 64> Exps; 80311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned CurrVN; 81c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames BitVector AllocatableRegs; 82c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames BitVector ReservedRegs; 8316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 84a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 85b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool isPhysDefTriviallyDead(unsigned Reg, 86b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng MachineBasicBlock::const_iterator I, 877a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky MachineBasicBlock::const_iterator E) const; 88189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool hasLivePhysRegDefUses(const MachineInstr *MI, 89189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 9097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 9197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallVector<unsigned,2> &PhysDefs) const; 92189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 9397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 94f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng SmallVector<unsigned,2> &PhysDefs, 9597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool &NonLocal) const; 96a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool isCSECandidate(MachineInstr *MI); 972938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 982938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI); 99311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void EnterScope(MachineBasicBlock *MBB); 100311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScope(MachineBasicBlock *MBB); 101311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool ProcessBlock(MachineBasicBlock *MBB); 102311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScopeIfDone(MachineDomTreeNode *Node, 10396cb1128528a512f1ef9c28ae5e1b78a98dcc505Bill Wendling DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); 104311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool PerformCSE(MachineDomTreeNode *Node); 105c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng }; 106c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} // end anonymous namespace 107c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 108c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengchar MachineCSE::ID = 0; 1091dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineCSEID = MachineCSE::ID; 1102ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 1112ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine Common Subexpression Elimination", false, false) 1122ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1132ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1142ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineCSE, "machine-cse", 115ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine Common Subexpression Elimination", false, false) 116c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 1176ba9554988f2efe13c6556c6149aea4846cf415dEvan Chengbool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 1186ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineBasicBlock *MBB) { 1196ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 1206ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1216ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineOperand &MO = MI->getOperand(i); 12216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isUse()) 12316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 12416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned Reg = MO.getReg(); 125c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 12616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 127f437f733484169cf67f7c3e798908bbf27175580Evan Cheng if (!MRI->hasOneNonDBGUse(Reg)) 12816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Only coalesce single use copies. This ensure the copy will be 12916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // deleted. 13016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 13116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(Reg); 13216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (DefMI->getParent() != MBB) 13316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 1340bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!DefMI->isCopy()) 1350bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 13604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned SrcReg = DefMI->getOperand(1).getReg(); 1370bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 1380bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 1390bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (DefMI->getOperand(0).getSubReg() || DefMI->getOperand(1).getSubReg()) 1400bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 141bf4699c56100a0184bbe4fb53937c7204ca1ceb0Jakob Stoklund Olesen if (!MRI->constrainRegClass(SrcReg, MRI->getRegClass(Reg))) 1420bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 1430bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DEBUG(dbgs() << "Coalescing: " << *DefMI); 144bf4699c56100a0184bbe4fb53937c7204ca1ceb0Jakob Stoklund Olesen DEBUG(dbgs() << "*** to: " << *MI); 1450bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MO.setReg(SrcReg); 1460bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MRI->clearKillFlags(SrcReg); 1470bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DefMI->eraseFromParent(); 1480bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen ++NumCoalesces; 1490bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen Changed = true; 1506ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 1516ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 1526ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 1536ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 1546ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 155835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Chengbool 156835810bbf8cd8b5ed92df66127c5aed16d022c74Evan ChengMachineCSE::isPhysDefTriviallyDead(unsigned Reg, 157835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator I, 158835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator E) const { 159e81d0105894a7d0cdd9ffb788a10715ed073ac67Eric Christopher unsigned LookAheadLeft = LookAheadLimit; 160112e5e7eff408cb106386a0641db258048bcc836Evan Cheng while (LookAheadLeft) { 1612250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng // Skip over dbg_value's. 1622250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng while (I != E && I->isDebugValue()) 1632250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng ++I; 1642250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng 165b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (I == E) 166b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // Reached end of block, register is obviously dead. 167b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 168b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 169b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool SeenDef = false; 170b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 171b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const MachineOperand &MO = I->getOperand(i); 1722129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 1732129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen SeenDef = true; 174b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!MO.isReg() || !MO.getReg()) 175b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 176b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!TRI->regsOverlap(MO.getReg(), Reg)) 177b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 178b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (MO.isUse()) 179835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // Found a use! 180b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 181b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng SeenDef = true; 182b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 183b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (SeenDef) 1841df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick // See a def of Reg (or an alias) before encountering any use, it's 185b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // trivially dead. 186b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 187112e5e7eff408cb106386a0641db258048bcc836Evan Cheng 188112e5e7eff408cb106386a0641db258048bcc836Evan Cheng --LookAheadLeft; 189b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng ++I; 190b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 191b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 192b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng} 193b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 194189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 195835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng/// physical registers (except for dead defs of physical registers). It also 1962b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// returns the physical register def by reference if it's the only one and the 1972b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// instruction does not uses a physical register. 198189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 199189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 20097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 20197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallVector<unsigned,2> &PhysDefs) const{ 202189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng MachineBasicBlock::const_iterator I = MI; I = llvm::next(I); 2036ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 204835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const MachineOperand &MO = MI->getOperand(i); 2056ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!MO.isReg()) 2066ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 2076ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng unsigned Reg = MO.getReg(); 2086ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!Reg) 2096ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 210835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 211835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng continue; 212189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // If the def is dead, it's ok. But the def may not marked "dead". That's 213835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // common since this pass is run before livevariables. We can scan 214835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // forward a few instructions and check if it is obviously dead. 215189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (MO.isDef() && 216189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng (MO.isDead() || isPhysDefTriviallyDead(Reg, I, MBB->end()))) 217189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng continue; 2185fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer // Reading constant physregs is ok. 2195fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 2205fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 221cfc0ad6e48fcbb5d9d7d97307e5b5df6bba53a97Benjamin Kramer PhysRefs.insert(*AI); 22297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (MO.isDef()) 22397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng PhysDefs.push_back(Reg); 224b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 225b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 226189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng return !PhysRefs.empty(); 2276ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 2286ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 229189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 23097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 231f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng SmallVector<unsigned,2> &PhysDefs, 23297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool &NonLocal) const { 2335e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman // For now conservatively returns false if the common subexpression is 23497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // not in the same basic block as the given instruction. The only exception 23597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // is if the common subexpression is in the sole predecessor block. 23697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng const MachineBasicBlock *MBB = MI->getParent(); 23797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng const MachineBasicBlock *CSMBB = CSMI->getParent(); 23897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 23997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool CrossMBB = false; 24097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (CSMBB != MBB) { 241f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) 24297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng return false; 243f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng 244f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 245c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames if (AllocatableRegs.test(PhysDefs[i]) || ReservedRegs.test(PhysDefs[i])) 246c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames // Avoid extending live range of physical registers if they are 247c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames //allocatable or reserved. 248f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng return false; 249f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng } 250f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng CrossMBB = true; 25197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 2525e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I); 2535e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman MachineBasicBlock::const_iterator E = MI; 25497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng MachineBasicBlock::const_iterator EE = CSMBB->end(); 255835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng unsigned LookAheadLeft = LookAheadLimit; 256835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng while (LookAheadLeft) { 2575e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman // Skip over dbg_value's. 25897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng while (I != E && I != EE && I->isDebugValue()) 2595e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman ++I; 26024d4c9911e7707eb0c35872f33c8ca01b3edcd7fEli Friedman 26197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (I == EE) { 26297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); 2635b8a1db7ea6510a2589f710d50754599da742de9Duncan Sands (void)CrossMBB; 26497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng CrossMBB = false; 26597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng NonLocal = true; 26697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng I = MBB->begin(); 26797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng EE = MBB->end(); 26897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng continue; 26997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 27097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 2715e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (I == E) 2725e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman return true; 273baf717a08a0bc8cb0a7931ea3ce51d063a8fe6f0Eli Friedman 2745e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 2755e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman const MachineOperand &MO = I->getOperand(i); 2762129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen // RegMasks go on instructions like calls that clobber lots of physregs. 2772129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen // Don't attempt to CSE across such an instruction. 2782129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen if (MO.isRegMask()) 2792129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen return false; 2805e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (!MO.isReg() || !MO.isDef()) 2815e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman continue; 2825e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman unsigned MOReg = MO.getReg(); 2835e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (TargetRegisterInfo::isVirtualRegister(MOReg)) 2845e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman continue; 2855e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (PhysRefs.count(MOReg)) 2865e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman return false; 287baf717a08a0bc8cb0a7931ea3ce51d063a8fe6f0Eli Friedman } 2885e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman 2895e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman --LookAheadLeft; 2905e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman ++I; 291835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 292835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 293835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng return false; 294835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng} 295835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 296a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Chengbool MachineCSE::isCSECandidate(MachineInstr *MI) { 2975196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 298e68ea060c78356253d771e039747fbc06c623646Dale Johannesen MI->isKill() || MI->isInlineAsm() || MI->isDebugValue()) 2995196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng return false; 3005196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng 3012938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 30204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 303a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 304a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 305a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Ignore stuff that we obviously can't move. 3065a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->mayStore() || MI->isCall() || MI->isTerminator() || 307c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng MI->hasUnmodeledSideEffects()) 308a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 309a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 3105a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->mayLoad()) { 311a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Okay, this instruction does a load. As a refinement, we allow the target 312a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // to decide whether the loaded value is actually a constant. If so, we can 313a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // actually use it as a load. 314a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!MI->isInvariantLoad(AA)) 315a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // FIXME: we should be able to hoist loads with no other side effects if 316a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // there are no other instructions which can change memory in this loop. 317a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // This is a trivial form of alias analysis. 318a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 319a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng } 320a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return true; 321a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng} 322a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 32331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 32431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// common expression that defines Reg. 3252938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Chengbool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 3262938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI) { 3272938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // FIXME: Heuristics that works around the lack the live range splitting. 3282938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 329ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren // If CSReg is used at all uses of Reg, CSE should not increase register 330ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren // pressure of CSReg. 331ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren bool MayIncreasePressure = true; 332ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren if (TargetRegisterInfo::isVirtualRegister(CSReg) && 333ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren TargetRegisterInfo::isVirtualRegister(Reg)) { 334ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MayIncreasePressure = false; 335ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren SmallPtrSet<MachineInstr*, 8> CSUses; 336ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren for (MachineRegisterInfo::use_nodbg_iterator I =MRI->use_nodbg_begin(CSReg), 337ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren E = MRI->use_nodbg_end(); I != E; ++I) { 338ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MachineInstr *Use = &*I; 339ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren CSUses.insert(Use); 340ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 341ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 342ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren E = MRI->use_nodbg_end(); I != E; ++I) { 343ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MachineInstr *Use = &*I; 344ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren if (!CSUses.count(Use)) { 345ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MayIncreasePressure = true; 346ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren break; 347ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 348ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 349ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 350ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren if (!MayIncreasePressure) return true; 351ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren 352622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 353622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // an immediate predecessor. We don't want to increase register pressure and 354622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // end up causing other computation to be spilled. 3555a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->isAsCheapAsAMove()) { 3562938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *CSBB = CSMI->getParent(); 3572938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *BB = MI->getParent(); 358622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner if (CSBB != BB && !CSBB->isSuccessor(BB)) 3592938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 3602938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3612938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 3622938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #2: If the expression doesn't not use a vr and the only use 3632938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // of the redundant computation are copies, do not cse. 3642938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasVRegUse = false; 3652938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3662938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng const MachineOperand &MO = MI->getOperand(i); 367c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (MO.isReg() && MO.isUse() && 3682938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 3692938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasVRegUse = true; 3702938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 3712938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3722938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3732938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasVRegUse) { 3742938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasNonCopyUse = false; 3752938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 3762938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng E = MRI->use_nodbg_end(); I != E; ++I) { 3772938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *Use = &*I; 3782938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 37904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!Use->isCopyLike()) { 3802938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasNonCopyUse = true; 3812938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 3822938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3832938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3842938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasNonCopyUse) 3852938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 3862938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3872938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 3882938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 3892938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // it unless the defined value is already used in the BB of the new use. 39031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool HasPHI = false; 39131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 3922938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg), 39331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng E = MRI->use_nodbg_end(); I != E; ++I) { 39431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineInstr *Use = &*I; 39531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng HasPHI |= Use->isPHI(); 39631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSBBs.insert(Use->getParent()); 39731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 39831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 39931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (!HasPHI) 40031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return true; 40131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return CSBBs.count(MI->getParent()); 40231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng} 40331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 404311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::EnterScope(MachineBasicBlock *MBB) { 405311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 406311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeType *Scope = new ScopeType(VNT); 407311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeMap[MBB] = Scope; 408311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 409311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 410311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::ExitScope(MachineBasicBlock *MBB) { 411311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 412311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 413311569861162c12b78b6c445793d4074aa4e4512Evan Cheng assert(SI != ScopeMap.end()); 414311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeMap.erase(SI); 415311569861162c12b78b6c445793d4074aa4e4512Evan Cheng delete SI->second; 416311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 417311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 418311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 4196ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 4206ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 42131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 42239ad568c62f5120faec29f69d3d614303a1f992dManman Ren SmallVector<unsigned, 2> ImplicitDefsToUpdate; 42316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 4246ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineInstr *MI = &*I; 42516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng ++I; 426a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 427a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!isCSECandidate(MI)) 4286ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 4296ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 4306ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool FoundCSE = VNT.count(MI); 4316ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!FoundCSE) { 4326ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng // Look for trivial copy coalescing opportunities. 433db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng if (PerformTrivialCoalescing(MI, MBB)) { 434cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 435cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng 436db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng // After coalescing MI itself may become a copy. 43704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 438db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng continue; 4396ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng FoundCSE = VNT.count(MI); 440db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng } 4416ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 442a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng 443a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // Commute commutable instructions. 444a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng bool Commuted = false; 4455a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!FoundCSE && MI->isCommutable()) { 446a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng MachineInstr *NewMI = TII->commuteInstruction(MI); 447a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (NewMI) { 448a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng Commuted = true; 449a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng FoundCSE = VNT.count(NewMI); 450cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng if (NewMI != MI) { 451a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // New instruction. It doesn't need to be kept. 452a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng NewMI->eraseFromParent(); 453cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 454cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng } else if (!FoundCSE) 455a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // MI was changed but it didn't help, commute it back! 456a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng (void)TII->commuteInstruction(MI); 457a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 458a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 4596ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 460189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // If the instruction defines physical registers and the values *may* be 46167bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng // used, then it's not safe to replace it with a common subexpression. 462189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // It's also not safe if the instruction uses physical registers. 46397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool CrossMBBPhysDef = false; 4647a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky SmallSet<unsigned, 8> PhysRefs; 46597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallVector<unsigned, 2> PhysDefs; 46697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, PhysDefs)) { 46767bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng FoundCSE = false; 46867bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng 46997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // ... Unless the CS is local or is in the sole predecessor block 47097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // and it also defines the physical register which is not clobbered 47197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // in between and the physical register uses were not clobbered. 472189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng unsigned CSVN = VNT.lookup(MI); 473189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng MachineInstr *CSMI = Exps[CSVN]; 474f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) 475189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng FoundCSE = true; 476835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 477835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 47816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!FoundCSE) { 47916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng VNT.insert(MI, CurrVN++); 48016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng Exps.push_back(MI); 48116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 48216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 48316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 48416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Found a common subexpression, eliminate it. 48516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned CSVN = VNT.lookup(MI); 48616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *CSMI = Exps[CSVN]; 48716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "Examining: " << *MI); 48816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 48931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 49031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Check if it's profitable to perform this CSE. 49131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool DoCSE = true; 49239ad568c62f5120faec29f69d3d614303a1f992dManman Ren unsigned NumDefs = MI->getDesc().getNumDefs() + 49339ad568c62f5120faec29f69d3d614303a1f992dManman Ren MI->getDesc().getNumImplicitDefs(); 49439ad568c62f5120faec29f69d3d614303a1f992dManman Ren 49516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 49616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineOperand &MO = MI->getOperand(i); 49716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isDef()) 49816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 49916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned OldReg = MO.getReg(); 50016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned NewReg = CSMI->getOperand(i).getReg(); 50139ad568c62f5120faec29f69d3d614303a1f992dManman Ren 50239ad568c62f5120faec29f69d3d614303a1f992dManman Ren // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 50339ad568c62f5120faec29f69d3d614303a1f992dManman Ren // we should make sure it is not dead at CSMI. 50439ad568c62f5120faec29f69d3d614303a1f992dManman Ren if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) 50539ad568c62f5120faec29f69d3d614303a1f992dManman Ren ImplicitDefsToUpdate.push_back(i); 50639ad568c62f5120faec29f69d3d614303a1f992dManman Ren if (OldReg == NewReg) { 50739ad568c62f5120faec29f69d3d614303a1f992dManman Ren --NumDefs; 5086cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng continue; 50939ad568c62f5120faec29f69d3d614303a1f992dManman Ren } 510f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 5116cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 51216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng TargetRegisterInfo::isVirtualRegister(NewReg) && 51316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng "Do not CSE physical register defs!"); 514f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 5152938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 5167a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 51731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DoCSE = false; 51831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng break; 51931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 520f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 521f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling // Don't perform CSE if the result of the old instruction cannot exist 522f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling // within the register class of the new instruction. 523f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg); 524f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling if (!MRI->constrainRegClass(NewReg, OldRC)) { 5257a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n"); 526f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling DoCSE = false; 527f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling break; 528f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling } 529f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 53031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 53116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng --NumDefs; 53216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 53331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 53431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Actually perform the elimination. 53531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (DoCSE) { 53649b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { 53731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 53849b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman MRI->clearKillFlags(CSEPairs[i].second); 53949b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman } 54097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 54139ad568c62f5120faec29f69d3d614303a1f992dManman Ren // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 54239ad568c62f5120faec29f69d3d614303a1f992dManman Ren // we should make sure it is not dead at CSMI. 54339ad568c62f5120faec29f69d3d614303a1f992dManman Ren for (unsigned i = 0, e = ImplicitDefsToUpdate.size(); i != e; ++i) 54439ad568c62f5120faec29f69d3d614303a1f992dManman Ren CSMI->getOperand(ImplicitDefsToUpdate[i]).setIsDead(false); 54539ad568c62f5120faec29f69d3d614303a1f992dManman Ren 54697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (CrossMBBPhysDef) { 54797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // Add physical register defs now coming in from a predecessor to MBB 54897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // livein list. 54997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng while (!PhysDefs.empty()) { 55097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng unsigned LiveIn = PhysDefs.pop_back_val(); 55197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (!MBB->isLiveIn(LiveIn)) 55297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng MBB->addLiveIn(LiveIn); 55397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 55497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng ++NumCrossBBCSEs; 55597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 55697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 55731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MI->eraseFromParent(); 55831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng ++NumCSEs; 559189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (!PhysRefs.empty()) 5602b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng ++NumPhysCSEs; 561a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (Commuted) 562a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng ++NumCommutes; 563cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 56431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } else { 56531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng VNT.insert(MI, CurrVN++); 56631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng Exps.push_back(MI); 56731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 56831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.clear(); 56939ad568c62f5120faec29f69d3d614303a1f992dManman Ren ImplicitDefsToUpdate.clear(); 570c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 5716ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 572311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return Changed; 573311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 574311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 575311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 576311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// dominator tree node if its a leaf or all of its children are done. Walk 577311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// up the dominator tree to destroy ancestors which are now done. 578311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid 579311569861162c12b78b6c445793d4074aa4e4512Evan ChengMachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 5807a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { 581311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (OpenChildren[Node]) 582311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return; 583311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 584311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Pop scope. 585311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Node->getBlock()); 586311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 587311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now traverse upwards to pop ancestors whose offsprings are all done. 5887a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky while (MachineDomTreeNode *Parent = Node->getIDom()) { 589311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned Left = --OpenChildren[Parent]; 590311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (Left != 0) 591311569861162c12b78b6c445793d4074aa4e4512Evan Cheng break; 592311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Parent->getBlock()); 593311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = Parent; 594311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 595311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 596311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 597311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 598311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 32> Scopes; 599311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 8> WorkList; 600311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 601311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 602c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng CurrVN = 0; 603c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 604311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Perform a DFS walk to determine the order of visit. 605311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Node); 606311569861162c12b78b6c445793d4074aa4e4512Evan Cheng do { 607311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = WorkList.pop_back_val(); 608311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Scopes.push_back(Node); 609311569861162c12b78b6c445793d4074aa4e4512Evan Cheng const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 610311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned NumChildren = Children.size(); 611311569861162c12b78b6c445793d4074aa4e4512Evan Cheng OpenChildren[Node] = NumChildren; 612311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0; i != NumChildren; ++i) { 613311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Child = Children[i]; 614311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Child); 615311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 616311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } while (!WorkList.empty()); 617311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 618311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now perform CSE. 619311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool Changed = false; 620311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 621311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Node = Scopes[i]; 622311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineBasicBlock *MBB = Node->getBlock(); 623311569861162c12b78b6c445793d4074aa4e4512Evan Cheng EnterScope(MBB); 624311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Changed |= ProcessBlock(MBB); 625311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 6267a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky ExitScopeIfDone(Node, OpenChildren); 627311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 6286ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 6296ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 630c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 631c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 632c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengbool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 6336ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng TII = MF.getTarget().getInstrInfo(); 634b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 6356ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MRI = &MF.getRegInfo(); 636a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AA = &getAnalysis<AliasAnalysis>(); 63731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DT = &getAnalysis<MachineDominatorTree>(); 638c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames AllocatableRegs = TRI->getAllocatableSet(MF); 639c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames ReservedRegs = TRI->getReservedRegs(MF); 640311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return PerformCSE(DT->getRootNode()); 641c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 642