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#include "llvm/CodeGen/Passes.h" 17311569861162c12b78b6c445793d4074aa4e4512Evan Cheng#include "llvm/ADT/DenseMap.h" 18c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/ADT/ScopedHashTable.h" 19189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng#include "llvm/ADT/SmallSet.h" 20c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/ADT/Statistic.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineDominators.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstr.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 25c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng#include "llvm/Support/Debug.h" 2653eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich#include "llvm/Support/RecyclingAllocator.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 28c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengusing namespace llvm; 29c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "machine-cse" 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan ChengSTATISTIC(NumCoalesces, "Number of copies coalesced"); 3316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan ChengSTATISTIC(NumCSEs, "Number of common subexpression eliminated"); 34189c1ec4c162ca3d36d9bca803b032eb19de434aEvan ChengSTATISTIC(NumPhysCSEs, 35189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng "Number of physreg referencing common subexpr eliminated"); 3697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan ChengSTATISTIC(NumCrossBBCSEs, 3797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng "Number of cross-MBB physreg referencing CS eliminated"); 38a63cde26ff698284ecdbec357966ca9d69e1d83aEvan ChengSTATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 393844173f6e5c2d3e309d71d8980e25cca1b9305dBob Wilson 40c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengnamespace { 41c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng class MachineCSE : public MachineFunctionPass { 426ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng const TargetInstrInfo *TII; 43b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const TargetRegisterInfo *TRI; 44a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AliasAnalysis *AA; 4531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineDominatorTree *DT; 4631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineRegisterInfo *MRI; 47c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng public: 48c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng static char ID; // Pass identification 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { 50081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 52c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 541df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 56c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.setPreservesCFG(); 57c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng MachineFunctionPass::getAnalysisUsage(AU); 58a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AU.addRequired<AliasAnalysis>(); 596542416560589c9cfa6298d2edc73f3350ccf56aEvan Cheng AU.addPreservedID(MachineLoopInfoID); 60c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addRequired<MachineDominatorTree>(); 61c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addPreserved<MachineDominatorTree>(); 62c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 63c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override { 65c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng ScopeMap.clear(); 66c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng Exps.clear(); 67c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng } 68c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 69c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng private: 70835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const unsigned LookAheadLimit; 7153eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef RecyclingAllocator<BumpPtrAllocator, 7253eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 7353eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHashTable<MachineInstr*, unsigned, 7453eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 7553eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHTType::ScopeTy ScopeType; 76311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 7753eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHTType VNT; 7816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng SmallVector<MachineInstr*, 64> Exps; 79311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned CurrVN; 8016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 81a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 82b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool isPhysDefTriviallyDead(unsigned Reg, 83b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng MachineBasicBlock::const_iterator I, 847a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky MachineBasicBlock::const_iterator E) const; 85189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool hasLivePhysRegDefUses(const MachineInstr *MI, 86189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 8797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 88a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<unsigned> &PhysDefs, 89b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand bool &PhysUseDef) const; 90189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 9197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 92a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<unsigned> &PhysDefs, 9397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool &NonLocal) const; 94a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool isCSECandidate(MachineInstr *MI); 952938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 962938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI); 97311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void EnterScope(MachineBasicBlock *MBB); 98311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScope(MachineBasicBlock *MBB); 99311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool ProcessBlock(MachineBasicBlock *MBB); 100311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScopeIfDone(MachineDomTreeNode *Node, 10196cb1128528a512f1ef9c28ae5e1b78a98dcc505Bill Wendling DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); 102311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool PerformCSE(MachineDomTreeNode *Node); 103c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng }; 104c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} // end anonymous namespace 105c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 106c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengchar MachineCSE::ID = 0; 1071dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineCSEID = MachineCSE::ID; 1082ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 1092ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine Common Subexpression Elimination", false, false) 1102ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1112ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1122ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineCSE, "machine-cse", 113ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine Common Subexpression Elimination", false, false) 114c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 1156ba9554988f2efe13c6556c6149aea4846cf415dEvan Chengbool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 1166ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineBasicBlock *MBB) { 1176ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 1186ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1196ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineOperand &MO = MI->getOperand(i); 12016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isUse()) 12116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 12216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned Reg = MO.getReg(); 123c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 12416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 125f437f733484169cf67f7c3e798908bbf27175580Evan Cheng if (!MRI->hasOneNonDBGUse(Reg)) 12616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Only coalesce single use copies. This ensure the copy will be 12716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // deleted. 12816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 12916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(Reg); 1300bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!DefMI->isCopy()) 1310bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 13204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned SrcReg = DefMI->getOperand(1).getReg(); 1330bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 1340bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DefMI->getOperand(0).getSubReg()) 1360bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: We should trivially coalesce subregister copies to expose CSE 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // opportunities on instructions with truncated operands (see 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // cse-add-with-overflow.ll). This can be done here as follows: 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // if (SrcSubReg) 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC, 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // SrcSubReg); 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // MO.substVirtReg(SrcReg, SrcSubReg, *TRI); 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The 2-addr pass has been updated to handle coalesced subregs. However, 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // some machine-specific code still can't handle it. 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // To handle it properly we also need a way find a constrained subregister 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // class given a super-reg class and subreg index. 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DefMI->getOperand(1).getSubReg()) 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const TargetRegisterClass *RC = MRI->getRegClass(Reg); 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!MRI->constrainRegClass(SrcReg, RC)) 1530bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 1540bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DEBUG(dbgs() << "Coalescing: " << *DefMI); 155bf4699c56100a0184bbe4fb53937c7204ca1ceb0Jakob Stoklund Olesen DEBUG(dbgs() << "*** to: " << *MI); 1560bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MO.setReg(SrcReg); 1570bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MRI->clearKillFlags(SrcReg); 1580bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DefMI->eraseFromParent(); 1590bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen ++NumCoalesces; 1600bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen Changed = true; 1616ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 1626ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 1636ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 1646ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 1656ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 166835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Chengbool 167835810bbf8cd8b5ed92df66127c5aed16d022c74Evan ChengMachineCSE::isPhysDefTriviallyDead(unsigned Reg, 168835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator I, 169835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator E) const { 170e81d0105894a7d0cdd9ffb788a10715ed073ac67Eric Christopher unsigned LookAheadLeft = LookAheadLimit; 171112e5e7eff408cb106386a0641db258048bcc836Evan Cheng while (LookAheadLeft) { 1722250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng // Skip over dbg_value's. 1732250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng while (I != E && I->isDebugValue()) 1742250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng ++I; 1752250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng 176b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (I == E) 177b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // Reached end of block, register is obviously dead. 178b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 179b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 180b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool SeenDef = false; 181b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 182b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const MachineOperand &MO = I->getOperand(i); 1832129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 1842129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen SeenDef = true; 185b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!MO.isReg() || !MO.getReg()) 186b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 187b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!TRI->regsOverlap(MO.getReg(), Reg)) 188b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 189b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (MO.isUse()) 190835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // Found a use! 191b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 192b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng SeenDef = true; 193b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 194b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (SeenDef) 1951df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick // See a def of Reg (or an alias) before encountering any use, it's 196b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // trivially dead. 197b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 198112e5e7eff408cb106386a0641db258048bcc836Evan Cheng 199112e5e7eff408cb106386a0641db258048bcc836Evan Cheng --LookAheadLeft; 200b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng ++I; 201b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 202b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 203b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng} 204b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 205189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 206835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng/// physical registers (except for dead defs of physical registers). It also 2072b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// returns the physical register def by reference if it's the only one and the 2082b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// instruction does not uses a physical register. 209189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 210189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 21197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 212a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<unsigned> &PhysDefs, 213b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand bool &PhysUseDef) const{ 214b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // First, add all uses to PhysRefs. 2156ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 216835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const MachineOperand &MO = MI->getOperand(i); 217b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (!MO.isReg() || MO.isDef()) 2186ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 2196ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng unsigned Reg = MO.getReg(); 2206ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!Reg) 2216ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 222835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 223835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng continue; 2245fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer // Reading constant physregs is ok. 2255fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 2265fa2d458af8522a0fc3c6c93227d8cb3c0dc2862Benjamin Kramer for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 227cfc0ad6e48fcbb5d9d7d97307e5b5df6bba53a97Benjamin Kramer PhysRefs.insert(*AI); 228b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand } 229b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand 230b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // Next, collect all defs into PhysDefs. If any is already in PhysRefs 231b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // (which currently contains only uses), set the PhysUseDef flag. 232b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand PhysUseDef = false; 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock::const_iterator I = MI; I = std::next(I); 234b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 235b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand const MachineOperand &MO = MI->getOperand(i); 236b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (!MO.isReg() || !MO.isDef()) 237b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand continue; 238b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand unsigned Reg = MO.getReg(); 239b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (!Reg) 240b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand continue; 241b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (TargetRegisterInfo::isVirtualRegister(Reg)) 242b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand continue; 243b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // Check against PhysRefs even if the def is "dead". 244b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (PhysRefs.count(Reg)) 245b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand PhysUseDef = true; 246b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // If the def is dead, it's ok. But the def may not marked "dead". That's 247b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // common since this pass is run before livevariables. We can scan 248b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // forward a few instructions and check if it is obviously dead. 249b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end())) 25097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng PhysDefs.push_back(Reg); 251b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 252b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 253b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // Finally, add all defs to PhysRefs as well. 254b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) 255b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI) 256b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand PhysRefs.insert(*AI); 257b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand 258189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng return !PhysRefs.empty(); 2596ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 2606ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 261189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 26297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallSet<unsigned,8> &PhysRefs, 263a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<unsigned> &PhysDefs, 26497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool &NonLocal) const { 2655e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman // For now conservatively returns false if the common subexpression is 26697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // not in the same basic block as the given instruction. The only exception 26797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // is if the common subexpression is in the sole predecessor block. 26897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng const MachineBasicBlock *MBB = MI->getParent(); 26997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng const MachineBasicBlock *CSMBB = CSMI->getParent(); 27097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 27197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool CrossMBB = false; 27297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (CSMBB != MBB) { 273f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) 27497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng return false; 275f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng 276f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 277fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (MRI->isAllocatable(PhysDefs[i]) || MRI->isReserved(PhysDefs[i])) 278c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames // Avoid extending live range of physical registers if they are 279c2e08db4e5a8e1b3c253fb07c6eb736dfb66fe59Lang Hames //allocatable or reserved. 280f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng return false; 281f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng } 282f96703e62f2302cfe2465fb0fddaf62259eee62cEvan Cheng CrossMBB = true; 28397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock::const_iterator I = CSMI; I = std::next(I); 2855e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman MachineBasicBlock::const_iterator E = MI; 28697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng MachineBasicBlock::const_iterator EE = CSMBB->end(); 287835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng unsigned LookAheadLeft = LookAheadLimit; 288835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng while (LookAheadLeft) { 2895e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman // Skip over dbg_value's. 29097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng while (I != E && I != EE && I->isDebugValue()) 2915e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman ++I; 29224d4c9911e7707eb0c35872f33c8ca01b3edcd7fEli Friedman 29397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (I == EE) { 29497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); 2955b8a1db7ea6510a2589f710d50754599da742de9Duncan Sands (void)CrossMBB; 29697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng CrossMBB = false; 29797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng NonLocal = true; 29897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng I = MBB->begin(); 29997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng EE = MBB->end(); 30097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng continue; 30197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 30297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 3035e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (I == E) 3045e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman return true; 305baf717a08a0bc8cb0a7931ea3ce51d063a8fe6f0Eli Friedman 3065e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 3075e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman const MachineOperand &MO = I->getOperand(i); 3082129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen // RegMasks go on instructions like calls that clobber lots of physregs. 3092129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen // Don't attempt to CSE across such an instruction. 3102129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen if (MO.isRegMask()) 3112129a0f6773b3625ddc5d541fe454a9a923cec2aJakob Stoklund Olesen return false; 3125e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (!MO.isReg() || !MO.isDef()) 3135e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman continue; 3145e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman unsigned MOReg = MO.getReg(); 3155e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (TargetRegisterInfo::isVirtualRegister(MOReg)) 3165e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman continue; 3175e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman if (PhysRefs.count(MOReg)) 3185e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman return false; 319baf717a08a0bc8cb0a7931ea3ce51d063a8fe6f0Eli Friedman } 3205e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman 3215e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman --LookAheadLeft; 3225e926ac651ac497ab782439a3a42840d0ef6f57cEli Friedman ++I; 323835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 324835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 325835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng return false; 326835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng} 327835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 328a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Chengbool MachineCSE::isCSECandidate(MachineInstr *MI) { 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() || 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MI->isInlineAsm() || MI->isDebugValue()) 3315196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng return false; 3325196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng 3332938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 33404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 335a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 336a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 337a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Ignore stuff that we obviously can't move. 3385a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->mayStore() || MI->isCall() || MI->isTerminator() || 339c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng MI->hasUnmodeledSideEffects()) 340a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 341a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 3425a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->mayLoad()) { 343a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Okay, this instruction does a load. As a refinement, we allow the target 344a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // to decide whether the loaded value is actually a constant. If so, we can 345a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // actually use it as a load. 346a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!MI->isInvariantLoad(AA)) 347a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // FIXME: we should be able to hoist loads with no other side effects if 348a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // there are no other instructions which can change memory in this loop. 349a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // This is a trivial form of alias analysis. 350a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 351a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng } 352a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return true; 353a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng} 354a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 35531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 35631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// common expression that defines Reg. 3572938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Chengbool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 3582938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI) { 3592938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // FIXME: Heuristics that works around the lack the live range splitting. 3602938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 361ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren // If CSReg is used at all uses of Reg, CSE should not increase register 362ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren // pressure of CSReg. 363ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren bool MayIncreasePressure = true; 364ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren if (TargetRegisterInfo::isVirtualRegister(CSReg) && 365ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren TargetRegisterInfo::isVirtualRegister(Reg)) { 366ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MayIncreasePressure = false; 367ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren SmallPtrSet<MachineInstr*, 8> CSUses; 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CSUses.insert(&MI); 370ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!CSUses.count(&MI)) { 373ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren MayIncreasePressure = true; 374ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren break; 375ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 376ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 377ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren } 378ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren if (!MayIncreasePressure) return true; 379ba86b13ad9cd6a9707a954598863da1e2a9f773bManman Ren 380622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 381622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // an immediate predecessor. We don't want to increase register pressure and 382622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // end up causing other computation to be spilled. 38322c310d78ce9630af15b0de94c18a409705b7496Tim Murray if (TII->isAsCheapAsAMove(MI)) { 3842938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *CSBB = CSMI->getParent(); 3852938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *BB = MI->getParent(); 386622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner if (CSBB != BB && !CSBB->isSuccessor(BB)) 3872938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 3882938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3892938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 3902938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #2: If the expression doesn't not use a vr and the only use 3912938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // of the redundant computation are copies, do not cse. 3922938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasVRegUse = false; 3932938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3942938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng const MachineOperand &MO = MI->getOperand(i); 395c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (MO.isReg() && MO.isUse() && 3962938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 3972938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasVRegUse = true; 3982938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 3992938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 4002938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 4012938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasVRegUse) { 4022938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasNonCopyUse = false; 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 4042938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!MI.isCopyLike()) { 4062938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasNonCopyUse = true; 4072938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 4082938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 4092938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 4102938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasNonCopyUse) 4112938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 4122938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 4132938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 4142938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 4152938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // it unless the defined value is already used in the BB of the new use. 41631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool HasPHI = false; 41731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 41836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { 41936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines HasPHI |= MI.isPHI(); 42036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CSBBs.insert(MI.getParent()); 42131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 42231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 42331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (!HasPHI) 42431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return true; 42531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return CSBBs.count(MI->getParent()); 42631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng} 42731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 428311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::EnterScope(MachineBasicBlock *MBB) { 429311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 430311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeType *Scope = new ScopeType(VNT); 431311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeMap[MBB] = Scope; 432311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 433311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 434311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::ExitScope(MachineBasicBlock *MBB) { 435311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 436311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 437311569861162c12b78b6c445793d4074aa4e4512Evan Cheng assert(SI != ScopeMap.end()); 438311569861162c12b78b6c445793d4074aa4e4512Evan Cheng delete SI->second; 439bb8ddc7e4ff1f06c7289865bbf9e1fa4632d1c8eJakub Staszak ScopeMap.erase(SI); 440311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 441311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 442311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 4436ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 4446ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 44531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 44639ad568c62f5120faec29f69d3d614303a1f992dManman Ren SmallVector<unsigned, 2> ImplicitDefsToUpdate; 44716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 4486ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineInstr *MI = &*I; 44916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng ++I; 450a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 451a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!isCSECandidate(MI)) 4526ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 4536ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 4546ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool FoundCSE = VNT.count(MI); 4556ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!FoundCSE) { 4566ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng // Look for trivial copy coalescing opportunities. 457db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng if (PerformTrivialCoalescing(MI, MBB)) { 458cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 459cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng 460db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng // After coalescing MI itself may become a copy. 46104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 462db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng continue; 4636ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng FoundCSE = VNT.count(MI); 464db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng } 4656ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 466a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng 467a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // Commute commutable instructions. 468a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng bool Commuted = false; 4695a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!FoundCSE && MI->isCommutable()) { 470a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng MachineInstr *NewMI = TII->commuteInstruction(MI); 471a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (NewMI) { 472a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng Commuted = true; 473a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng FoundCSE = VNT.count(NewMI); 474cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng if (NewMI != MI) { 475a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // New instruction. It doesn't need to be kept. 476a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng NewMI->eraseFromParent(); 477cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 478cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng } else if (!FoundCSE) 479a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // MI was changed but it didn't help, commute it back! 480a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng (void)TII->commuteInstruction(MI); 481a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 482a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 4836ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 484189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // If the instruction defines physical registers and the values *may* be 48567bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng // used, then it's not safe to replace it with a common subexpression. 486189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // It's also not safe if the instruction uses physical registers. 48797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng bool CrossMBBPhysDef = false; 4887a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky SmallSet<unsigned, 8> PhysRefs; 48997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng SmallVector<unsigned, 2> PhysDefs; 490b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand bool PhysUseDef = false; 491b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, 492b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand PhysDefs, PhysUseDef)) { 49367bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng FoundCSE = false; 49467bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng 49597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // ... Unless the CS is local or is in the sole predecessor block 49697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // and it also defines the physical register which is not clobbered 49797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // in between and the physical register uses were not clobbered. 498b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // This can never be the case if the instruction both uses and 499b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand // defines the same physical register, which was detected above. 500b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (!PhysUseDef) { 501b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand unsigned CSVN = VNT.lookup(MI); 502b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand MachineInstr *CSMI = Exps[CSVN]; 503b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) 504b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand FoundCSE = true; 505b64e2115de3b293ef706b75f040277477c949208Ulrich Weigand } 506835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 507835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 50816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!FoundCSE) { 50916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng VNT.insert(MI, CurrVN++); 51016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng Exps.push_back(MI); 51116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 51216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 51316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 51416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Found a common subexpression, eliminate it. 51516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned CSVN = VNT.lookup(MI); 51616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *CSMI = Exps[CSVN]; 51716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "Examining: " << *MI); 51816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 51931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 52031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Check if it's profitable to perform this CSE. 52131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool DoCSE = true; 52239ad568c62f5120faec29f69d3d614303a1f992dManman Ren unsigned NumDefs = MI->getDesc().getNumDefs() + 52339ad568c62f5120faec29f69d3d614303a1f992dManman Ren MI->getDesc().getNumImplicitDefs(); 52436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 52516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 52616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineOperand &MO = MI->getOperand(i); 52716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isDef()) 52816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 52916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned OldReg = MO.getReg(); 53016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned NewReg = CSMI->getOperand(i).getReg(); 53139ad568c62f5120faec29f69d3d614303a1f992dManman Ren 53239ad568c62f5120faec29f69d3d614303a1f992dManman Ren // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 53339ad568c62f5120faec29f69d3d614303a1f992dManman Ren // we should make sure it is not dead at CSMI. 53439ad568c62f5120faec29f69d3d614303a1f992dManman Ren if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) 53539ad568c62f5120faec29f69d3d614303a1f992dManman Ren ImplicitDefsToUpdate.push_back(i); 53639ad568c62f5120faec29f69d3d614303a1f992dManman Ren if (OldReg == NewReg) { 53739ad568c62f5120faec29f69d3d614303a1f992dManman Ren --NumDefs; 5386cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng continue; 53939ad568c62f5120faec29f69d3d614303a1f992dManman Ren } 540f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 5416cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 54216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng TargetRegisterInfo::isVirtualRegister(NewReg) && 54316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng "Do not CSE physical register defs!"); 544f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 5452938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 5467a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 54731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DoCSE = false; 54831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng break; 54931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 550f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 551f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling // Don't perform CSE if the result of the old instruction cannot exist 552f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling // within the register class of the new instruction. 553f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg); 554f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling if (!MRI->constrainRegClass(NewReg, OldRC)) { 5557a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n"); 556f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling DoCSE = false; 557f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling break; 558f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling } 559f6fb7ed53c786228445fc55e8d495ccead59b9aeBill Wendling 56031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 56116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng --NumDefs; 56216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 56331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 56431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Actually perform the elimination. 56531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (DoCSE) { 56649b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { 56731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 56849b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman MRI->clearKillFlags(CSEPairs[i].second); 56949b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman } 57097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 57139ad568c62f5120faec29f69d3d614303a1f992dManman Ren // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 57239ad568c62f5120faec29f69d3d614303a1f992dManman Ren // we should make sure it is not dead at CSMI. 57339ad568c62f5120faec29f69d3d614303a1f992dManman Ren for (unsigned i = 0, e = ImplicitDefsToUpdate.size(); i != e; ++i) 57439ad568c62f5120faec29f69d3d614303a1f992dManman Ren CSMI->getOperand(ImplicitDefsToUpdate[i]).setIsDead(false); 57539ad568c62f5120faec29f69d3d614303a1f992dManman Ren 57697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (CrossMBBPhysDef) { 57797b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // Add physical register defs now coming in from a predecessor to MBB 57897b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng // livein list. 57997b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng while (!PhysDefs.empty()) { 58097b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng unsigned LiveIn = PhysDefs.pop_back_val(); 58197b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng if (!MBB->isLiveIn(LiveIn)) 58297b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng MBB->addLiveIn(LiveIn); 58397b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 58497b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng ++NumCrossBBCSEs; 58597b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng } 58697b5beb7fe7bb776654b04ae6c18af6ea15c74f7Evan Cheng 58731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MI->eraseFromParent(); 58831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng ++NumCSEs; 589189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (!PhysRefs.empty()) 5902b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng ++NumPhysCSEs; 591a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (Commuted) 592a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng ++NumCommutes; 593cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 59431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } else { 59531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng VNT.insert(MI, CurrVN++); 59631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng Exps.push_back(MI); 59731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 59831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.clear(); 59939ad568c62f5120faec29f69d3d614303a1f992dManman Ren ImplicitDefsToUpdate.clear(); 600c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 6016ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 602311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return Changed; 603311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 604311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 605311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 606311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// dominator tree node if its a leaf or all of its children are done. Walk 607311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// up the dominator tree to destroy ancestors which are now done. 608311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid 609311569861162c12b78b6c445793d4074aa4e4512Evan ChengMachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 6107a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { 611311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (OpenChildren[Node]) 612311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return; 613311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 614311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Pop scope. 615311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Node->getBlock()); 616311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 617311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now traverse upwards to pop ancestors whose offsprings are all done. 6187a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky while (MachineDomTreeNode *Parent = Node->getIDom()) { 619311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned Left = --OpenChildren[Parent]; 620311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (Left != 0) 621311569861162c12b78b6c445793d4074aa4e4512Evan Cheng break; 622311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Parent->getBlock()); 623311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = Parent; 624311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 625311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 626311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 627311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 628311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 32> Scopes; 629311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 8> WorkList; 630311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 631311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 632c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng CurrVN = 0; 633c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 634311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Perform a DFS walk to determine the order of visit. 635311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Node); 636311569861162c12b78b6c445793d4074aa4e4512Evan Cheng do { 637311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = WorkList.pop_back_val(); 638311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Scopes.push_back(Node); 639311569861162c12b78b6c445793d4074aa4e4512Evan Cheng const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 640311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned NumChildren = Children.size(); 641311569861162c12b78b6c445793d4074aa4e4512Evan Cheng OpenChildren[Node] = NumChildren; 642311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0; i != NumChildren; ++i) { 643311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Child = Children[i]; 644311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Child); 645311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 646311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } while (!WorkList.empty()); 647311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 648311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now perform CSE. 649311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool Changed = false; 650311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 651311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Node = Scopes[i]; 652311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineBasicBlock *MBB = Node->getBlock(); 653311569861162c12b78b6c445793d4074aa4e4512Evan Cheng EnterScope(MBB); 654311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Changed |= ProcessBlock(MBB); 655311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 6567a7a6db6d79b53fdf01bbd9519e669424c3ea7a0Nick Lewycky ExitScopeIfDone(Node, OpenChildren); 657311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 6586ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 6596ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 660c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 661c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 662c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengbool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 66336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(*MF.getFunction())) 66436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 66536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6666ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng TII = MF.getTarget().getInstrInfo(); 667b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 6686ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MRI = &MF.getRegInfo(); 669a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AA = &getAnalysis<AliasAnalysis>(); 67031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DT = &getAnalysis<MachineDominatorTree>(); 671311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return PerformCSE(DT->getRootNode()); 672c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 673