MachineCSE.cpp revision cfea985f5319991fcb1feac3e66f645da4a0b507
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 Cheng 30c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengusing namespace llvm; 31c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 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"); 36a63cde26ff698284ecdbec357966ca9d69e1d83aEvan ChengSTATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 373844173f6e5c2d3e309d71d8980e25cca1b9305dBob Wilson 38c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengnamespace { 39c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng class MachineCSE : public MachineFunctionPass { 406ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng const TargetInstrInfo *TII; 41b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const TargetRegisterInfo *TRI; 42a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AliasAnalysis *AA; 4331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineDominatorTree *DT; 4431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineRegisterInfo *MRI; 45c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng public: 46c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng static char ID; // Pass identification 47081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { 48081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 50c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 51c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 52c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 53c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &AU) const { 54c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.setPreservesCFG(); 55c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng MachineFunctionPass::getAnalysisUsage(AU); 56a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AU.addRequired<AliasAnalysis>(); 576542416560589c9cfa6298d2edc73f3350ccf56aEvan Cheng AU.addPreservedID(MachineLoopInfoID); 58c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addRequired<MachineDominatorTree>(); 59c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng AU.addPreserved<MachineDominatorTree>(); 60c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 61c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 62c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng virtual void releaseMemory() { 63c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng ScopeMap.clear(); 64c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng Exps.clear(); 65c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng } 66c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 67c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng private: 68835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const unsigned LookAheadLimit; 6953eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef RecyclingAllocator<BumpPtrAllocator, 7053eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; 7153eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHashTable<MachineInstr*, unsigned, 7253eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; 7353eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich typedef ScopedHTType::ScopeTy ScopeType; 74311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; 7553eeba586dac8a25db63fe02a00ef10feb8b3925Cameron Zwarich ScopedHTType VNT; 7616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng SmallVector<MachineInstr*, 64> Exps; 77311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned CurrVN; 7816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 79a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 80b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool isPhysDefTriviallyDead(unsigned Reg, 81b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng MachineBasicBlock::const_iterator I, 82835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator E) const ; 83189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool hasLivePhysRegDefUses(const MachineInstr *MI, 84189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 85189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng SmallSet<unsigned,8> &PhysRefs) const; 86189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 87189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng SmallSet<unsigned,8> &PhysRefs) const; 88a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng bool isCSECandidate(MachineInstr *MI); 892938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 902938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI); 91311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void EnterScope(MachineBasicBlock *MBB); 92311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScope(MachineBasicBlock *MBB); 93311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool ProcessBlock(MachineBasicBlock *MBB); 94311569861162c12b78b6c445793d4074aa4e4512Evan Cheng void ExitScopeIfDone(MachineDomTreeNode *Node, 95311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 96311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap); 97311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool PerformCSE(MachineDomTreeNode *Node); 98c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng }; 99c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} // end anonymous namespace 100c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 101c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengchar MachineCSE::ID = 0; 1022ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", 1032ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine Common Subexpression Elimination", false, false) 1042ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1052ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1062ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineCSE, "machine-cse", 107ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine Common Subexpression Elimination", false, false) 108c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 109c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan ChengFunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 110c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 1116ba9554988f2efe13c6556c6149aea4846cf415dEvan Chengbool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 1126ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineBasicBlock *MBB) { 1136ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 1146ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1156ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineOperand &MO = MI->getOperand(i); 11616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isUse()) 11716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 11816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned Reg = MO.getReg(); 119c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 12016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 121f437f733484169cf67f7c3e798908bbf27175580Evan Cheng if (!MRI->hasOneNonDBGUse(Reg)) 12216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Only coalesce single use copies. This ensure the copy will be 12316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // deleted. 12416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 12516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(Reg); 12616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (DefMI->getParent() != MBB) 12716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 1280bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!DefMI->isCopy()) 1290bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 13004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned SrcReg = DefMI->getOperand(1).getReg(); 1310bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 1320bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 1330bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen if (DefMI->getOperand(0).getSubReg() || DefMI->getOperand(1).getSubReg()) 1340bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 135bf4699c56100a0184bbe4fb53937c7204ca1ceb0Jakob Stoklund Olesen if (!MRI->constrainRegClass(SrcReg, MRI->getRegClass(Reg))) 1360bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen continue; 1370bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DEBUG(dbgs() << "Coalescing: " << *DefMI); 138bf4699c56100a0184bbe4fb53937c7204ca1ceb0Jakob Stoklund Olesen DEBUG(dbgs() << "*** to: " << *MI); 1390bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MO.setReg(SrcReg); 1400bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen MRI->clearKillFlags(SrcReg); 1410bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen DefMI->eraseFromParent(); 1420bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen ++NumCoalesces; 1430bc25f40402f48ba42fc45403f635b20d90fabb3Jakob Stoklund Olesen Changed = true; 1446ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 1456ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 1466ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 1476ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 1486ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 149835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Chengbool 150835810bbf8cd8b5ed92df66127c5aed16d022c74Evan ChengMachineCSE::isPhysDefTriviallyDead(unsigned Reg, 151835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator I, 152835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator E) const { 153e81d0105894a7d0cdd9ffb788a10715ed073ac67Eric Christopher unsigned LookAheadLeft = LookAheadLimit; 154112e5e7eff408cb106386a0641db258048bcc836Evan Cheng while (LookAheadLeft) { 1552250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng // Skip over dbg_value's. 1562250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng while (I != E && I->isDebugValue()) 1572250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng ++I; 1582250425d6e44558f9d333a5c7faef33744f561d6Evan Cheng 159b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (I == E) 160b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // Reached end of block, register is obviously dead. 161b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 162b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 163b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng bool SeenDef = false; 164b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 165b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng const MachineOperand &MO = I->getOperand(i); 166b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!MO.isReg() || !MO.getReg()) 167b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 168b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (!TRI->regsOverlap(MO.getReg(), Reg)) 169b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng continue; 170b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (MO.isUse()) 171835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // Found a use! 172b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 173b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng SeenDef = true; 174b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 175b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng if (SeenDef) 176b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // See a def of Reg (or an alias) before encountering any use, it's 177b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng // trivially dead. 178b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return true; 179112e5e7eff408cb106386a0641db258048bcc836Evan Cheng 180112e5e7eff408cb106386a0641db258048bcc836Evan Cheng --LookAheadLeft; 181b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng ++I; 182b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 183b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng return false; 184b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng} 185b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 186189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng/// hasLivePhysRegDefUses - Return true if the specified instruction read/write 187835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng/// physical registers (except for dead defs of physical registers). It also 1882b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// returns the physical register def by reference if it's the only one and the 1892b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng/// instruction does not uses a physical register. 190189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 191189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineBasicBlock *MBB, 192189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng SmallSet<unsigned,8> &PhysRefs) const { 193189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng MachineBasicBlock::const_iterator I = MI; I = llvm::next(I); 1946ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 195835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng const MachineOperand &MO = MI->getOperand(i); 1966ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!MO.isReg()) 1976ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 1986ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng unsigned Reg = MO.getReg(); 1996ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!Reg) 2006ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 201835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 202835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng continue; 203189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // If the def is dead, it's ok. But the def may not marked "dead". That's 204835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // common since this pass is run before livevariables. We can scan 205835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // forward a few instructions and check if it is obviously dead. 206189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (MO.isDef() && 207189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng (MO.isDead() || isPhysDefTriviallyDead(Reg, I, MBB->end()))) 208189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng continue; 209189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng PhysRefs.insert(Reg); 210189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) 211189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng PhysRefs.insert(*Alias); 212b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng } 213b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng 214189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng return !PhysRefs.empty(); 2156ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng} 2166ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 217189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Chengbool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 218189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng SmallSet<unsigned,8> &PhysRefs) const { 219835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // For now conservatively returns false if the common subexpression is 220835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // not in the same basic block as the given instruction. 221835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 222835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng if (CSMI->getParent() != MBB) 223835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng return false; 224835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I); 225835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng MachineBasicBlock::const_iterator E = MI; 226835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng unsigned LookAheadLeft = LookAheadLimit; 227835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng while (LookAheadLeft) { 228835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // Skip over dbg_value's. 229835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng while (I != E && I->isDebugValue()) 230835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng ++I; 231835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 232835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng if (I == E) 233835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng return true; 234189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng 235189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 236189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng const MachineOperand &MO = I->getOperand(i); 237189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (!MO.isReg() || !MO.isDef()) 238189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng continue; 239189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng unsigned MOReg = MO.getReg(); 240189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (TargetRegisterInfo::isVirtualRegister(MOReg)) 241189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng continue; 242189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (PhysRefs.count(MOReg)) 243189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng return false; 244189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng } 245835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 246835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng --LookAheadLeft; 247835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng ++I; 248835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 249835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 250835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng return false; 251835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng} 252835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 253a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Chengbool MachineCSE::isCSECandidate(MachineInstr *MI) { 2545196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 255e68ea060c78356253d771e039747fbc06c623646Dale Johannesen MI->isKill() || MI->isInlineAsm() || MI->isDebugValue()) 2565196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng return false; 2575196018d9cb80a1cc81b95c6365de24f33c5f6bbEvan Cheng 2582938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 25904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 260a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 261a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 262a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Ignore stuff that we obviously can't move. 263a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 264a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 265c36b7069b42bece963b7e6adf020353ce990ef76Evan Cheng MI->hasUnmodeledSideEffects()) 266a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 267a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 268a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (TID.mayLoad()) { 269a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // Okay, this instruction does a load. As a refinement, we allow the target 270a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // to decide whether the loaded value is actually a constant. If so, we can 271a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // actually use it as a load. 272a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!MI->isInvariantLoad(AA)) 273a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // FIXME: we should be able to hoist loads with no other side effects if 274a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // there are no other instructions which can change memory in this loop. 275a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng // This is a trivial form of alias analysis. 276a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return false; 277a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng } 278a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng return true; 279a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng} 280a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 28131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 28231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng/// common expression that defines Reg. 2832938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Chengbool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 2842938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *CSMI, MachineInstr *MI) { 2852938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // FIXME: Heuristics that works around the lack the live range splitting. 2862938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 287622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 288622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // an immediate predecessor. We don't want to increase register pressure and 289622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner // end up causing other computation to be spilled. 2902938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (MI->getDesc().isAsCheapAsAMove()) { 2912938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *CSBB = CSMI->getParent(); 2922938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineBasicBlock *BB = MI->getParent(); 293622a11bc0764897f6aaf80fe96b3abac6215f06bChris Lattner if (CSBB != BB && !CSBB->isSuccessor(BB)) 2942938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 2952938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 2962938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 2972938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #2: If the expression doesn't not use a vr and the only use 2982938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // of the redundant computation are copies, do not cse. 2992938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasVRegUse = false; 3002938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3012938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng const MachineOperand &MO = MI->getOperand(i); 302c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (MO.isReg() && MO.isUse() && 3032938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 3042938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasVRegUse = true; 3052938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 3062938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3072938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3082938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasVRegUse) { 3092938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng bool HasNonCopyUse = false; 3102938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 3112938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng E = MRI->use_nodbg_end(); I != E; ++I) { 3122938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng MachineInstr *Use = &*I; 3132938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Ignore copies. 31404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!Use->isCopyLike()) { 3152938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng HasNonCopyUse = true; 3162938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng break; 3172938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3182938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3192938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!HasNonCopyUse) 3202938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng return false; 3212938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng } 3222938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng 3232938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 3242938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng // it unless the defined value is already used in the BB of the new use. 32531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool HasPHI = false; 32631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> CSBBs; 3272938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg), 32831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng E = MRI->use_nodbg_end(); I != E; ++I) { 32931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MachineInstr *Use = &*I; 33031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng HasPHI |= Use->isPHI(); 33131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSBBs.insert(Use->getParent()); 33231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 33331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 33431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (!HasPHI) 33531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return true; 33631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng return CSBBs.count(MI->getParent()); 33731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng} 33831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 339311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::EnterScope(MachineBasicBlock *MBB) { 340311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 341311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeType *Scope = new ScopeType(VNT); 342311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeMap[MBB] = Scope; 343311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 344311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 345311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid MachineCSE::ExitScope(MachineBasicBlock *MBB) { 346311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 347311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 348311569861162c12b78b6c445793d4074aa4e4512Evan Cheng assert(SI != ScopeMap.end()); 349311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ScopeMap.erase(SI); 350311569861162c12b78b6c445793d4074aa4e4512Evan Cheng delete SI->second; 351311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 352311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 353311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { 3546ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool Changed = false; 3556ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 35631f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 35716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 3586ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MachineInstr *MI = &*I; 35916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng ++I; 360a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng 361a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng if (!isCSECandidate(MI)) 3626ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng continue; 3636ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 3646ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng bool FoundCSE = VNT.count(MI); 3656ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng if (!FoundCSE) { 3666ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng // Look for trivial copy coalescing opportunities. 367db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng if (PerformTrivialCoalescing(MI, MBB)) { 368cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 369cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng 370db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng // After coalescing MI itself may become a copy. 37104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 372db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng continue; 3736ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng FoundCSE = VNT.count(MI); 374db8771af286bc84267e7b5bd17eab51cd4ea552fEvan Cheng } 3756ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng } 376a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng 377a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // Commute commutable instructions. 378a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng bool Commuted = false; 379a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (!FoundCSE && MI->getDesc().isCommutable()) { 380a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng MachineInstr *NewMI = TII->commuteInstruction(MI); 381a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (NewMI) { 382a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng Commuted = true; 383a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng FoundCSE = VNT.count(NewMI); 384cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng if (NewMI != MI) { 385a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // New instruction. It doesn't need to be kept. 386a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng NewMI->eraseFromParent(); 387cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 388cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng } else if (!FoundCSE) 389a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng // MI was changed but it didn't help, commute it back! 390a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng (void)TII->commuteInstruction(MI); 391a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 392a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng } 3936ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 394189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // If the instruction defines physical registers and the values *may* be 39567bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng // used, then it's not safe to replace it with a common subexpression. 396189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // It's also not safe if the instruction uses physical registers. 397189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng SmallSet<unsigned,8> PhysRefs; 398189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs)) { 39967bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng FoundCSE = false; 40067bda7215b4bc1b3cc9dd80ef5785ac6dd26fb8cEvan Cheng 401835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng // ... Unless the CS is local and it also defines the physical register 402189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // which is not clobbered in between and the physical register uses 403189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng // were not clobbered. 404189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng unsigned CSVN = VNT.lookup(MI); 405189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng MachineInstr *CSMI = Exps[CSVN]; 406189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (PhysRegDefsReach(CSMI, MI, PhysRefs)) 407189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng FoundCSE = true; 408835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng } 409835810bbf8cd8b5ed92df66127c5aed16d022c74Evan Cheng 41016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!FoundCSE) { 41116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng VNT.insert(MI, CurrVN++); 41216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng Exps.push_back(MI); 41316b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 41416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 41516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng 41616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng // Found a common subexpression, eliminate it. 41716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned CSVN = VNT.lookup(MI); 41816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineInstr *CSMI = Exps[CSVN]; 41916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "Examining: " << *MI); 42016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 42131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 42231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Check if it's profitable to perform this CSE. 42331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng bool DoCSE = true; 42416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned NumDefs = MI->getDesc().getNumDefs(); 42516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 42616b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng MachineOperand &MO = MI->getOperand(i); 42716b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng if (!MO.isReg() || !MO.isDef()) 42816b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng continue; 42916b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned OldReg = MO.getReg(); 43016b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng unsigned NewReg = CSMI->getOperand(i).getReg(); 4316cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng if (OldReg == NewReg) 4326cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng continue; 4336cc1aeaad23b878fbf252efc3e45fb3a74a646ebEvan Cheng assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 43416b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng TargetRegisterInfo::isVirtualRegister(NewReg) && 43516b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng "Do not CSE physical register defs!"); 4362938a00f29dae82e47bf4939bcc8d0ff734ef582Evan Cheng if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { 43731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DoCSE = false; 43831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng break; 43931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 44031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 44116b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng --NumDefs; 44216b48b8a05d6881b575846fe42fad9a0c75b8a53Evan Cheng } 44331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng 44431f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng // Actually perform the elimination. 44531f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng if (DoCSE) { 44649b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { 44731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); 44849b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman MRI->clearKillFlags(CSEPairs[i].second); 44949b4589978ca181537c8ae694ac4c8d58d27a09aDan Gohman } 45031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng MI->eraseFromParent(); 45131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng ++NumCSEs; 452189c1ec4c162ca3d36d9bca803b032eb19de434aEvan Cheng if (!PhysRefs.empty()) 4532b4e727c6f55a4045a397250648227e2ded6c7d9Evan Cheng ++NumPhysCSEs; 454a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng if (Commuted) 455a63cde26ff698284ecdbec357966ca9d69e1d83aEvan Cheng ++NumCommutes; 456cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng Changed = true; 45731f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } else { 45831f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 45931f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng VNT.insert(MI, CurrVN++); 46031f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng Exps.push_back(MI); 46131f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng } 46231f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng CSEPairs.clear(); 463c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng } 4646ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 465311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return Changed; 466311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 467311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 468311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 469311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// dominator tree node if its a leaf or all of its children are done. Walk 470311569861162c12b78b6c445793d4074aa4e4512Evan Cheng/// up the dominator tree to destroy ancestors which are now done. 471311569861162c12b78b6c445793d4074aa4e4512Evan Chengvoid 472311569861162c12b78b6c445793d4074aa4e4512Evan ChengMachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 473311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 474311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { 475311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (OpenChildren[Node]) 476311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return; 477311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 478311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Pop scope. 479311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Node->getBlock()); 480311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 481311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now traverse upwards to pop ancestors whose offsprings are all done. 482311569861162c12b78b6c445793d4074aa4e4512Evan Cheng while (MachineDomTreeNode *Parent = ParentMap[Node]) { 483311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned Left = --OpenChildren[Parent]; 484311569861162c12b78b6c445793d4074aa4e4512Evan Cheng if (Left != 0) 485311569861162c12b78b6c445793d4074aa4e4512Evan Cheng break; 486311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScope(Parent->getBlock()); 487311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = Parent; 488311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 489311569861162c12b78b6c445793d4074aa4e4512Evan Cheng} 490311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 491311569861162c12b78b6c445793d4074aa4e4512Evan Chengbool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 492311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 32> Scopes; 493311569861162c12b78b6c445793d4074aa4e4512Evan Cheng SmallVector<MachineDomTreeNode*, 8> WorkList; 494311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; 495311569861162c12b78b6c445793d4074aa4e4512Evan Cheng DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 496311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 497c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng CurrVN = 0; 498c2b768f09e108b71348af58f3ab31d0fc6d15dd6Evan Cheng 499311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Perform a DFS walk to determine the order of visit. 500311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Node); 501311569861162c12b78b6c445793d4074aa4e4512Evan Cheng do { 502311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Node = WorkList.pop_back_val(); 503311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Scopes.push_back(Node); 504311569861162c12b78b6c445793d4074aa4e4512Evan Cheng const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 505311569861162c12b78b6c445793d4074aa4e4512Evan Cheng unsigned NumChildren = Children.size(); 506311569861162c12b78b6c445793d4074aa4e4512Evan Cheng OpenChildren[Node] = NumChildren; 507311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0; i != NumChildren; ++i) { 508311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Child = Children[i]; 509311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ParentMap[Child] = Node; 510311569861162c12b78b6c445793d4074aa4e4512Evan Cheng WorkList.push_back(Child); 511311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 512311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } while (!WorkList.empty()); 513311569861162c12b78b6c445793d4074aa4e4512Evan Cheng 514311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // Now perform CSE. 515311569861162c12b78b6c445793d4074aa4e4512Evan Cheng bool Changed = false; 516311569861162c12b78b6c445793d4074aa4e4512Evan Cheng for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { 517311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineDomTreeNode *Node = Scopes[i]; 518311569861162c12b78b6c445793d4074aa4e4512Evan Cheng MachineBasicBlock *MBB = Node->getBlock(); 519311569861162c12b78b6c445793d4074aa4e4512Evan Cheng EnterScope(MBB); 520311569861162c12b78b6c445793d4074aa4e4512Evan Cheng Changed |= ProcessBlock(MBB); 521311569861162c12b78b6c445793d4074aa4e4512Evan Cheng // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 522311569861162c12b78b6c445793d4074aa4e4512Evan Cheng ExitScopeIfDone(Node, OpenChildren, ParentMap); 523311569861162c12b78b6c445793d4074aa4e4512Evan Cheng } 5246ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng 5256ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng return Changed; 526c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 527c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng 528c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Chengbool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 5296ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng TII = MF.getTarget().getInstrInfo(); 530b3958e80324884e3d1c1e198a50f212bae0c3b77Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 5316ba9554988f2efe13c6556c6149aea4846cf415dEvan Cheng MRI = &MF.getRegInfo(); 532a5f32cb3d3cab0463c407cfd2c4153d5dea4498dEvan Cheng AA = &getAnalysis<AliasAnalysis>(); 53331f94c7c22cbf59753764bc17130dca6a73c0b4eEvan Cheng DT = &getAnalysis<MachineDominatorTree>(); 534311569861162c12b78b6c445793d4074aa4e4512Evan Cheng return PerformCSE(DT->getRootNode()); 535c6fe333688519c5a28d1e0f30ecdaa2ad8f1d410Evan Cheng} 536