X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCSE.cpp;h=cfe50408e6e316ebff326e278f04521de3724f1e;hb=343735288798bbd1cd2ed2750fa6cd323f12c26c;hp=e65d3bcaf2083da8f9d19ba716bd51cffa4b2c5b;hpb=bfc999956315ec0b29b4feb3780dd985e8e3f288;p=oota-llvm.git diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp index e65d3bcaf20..cfe50408e6e 100644 --- a/lib/CodeGen/MachineCSE.cpp +++ b/lib/CodeGen/MachineCSE.cpp @@ -20,6 +20,7 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Target/TargetInstrInfo.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ScopedHashTable.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Debug.h" @@ -51,9 +52,12 @@ namespace { } private: - unsigned CurrVN; + typedef ScopedHashTableScope ScopeType; + DenseMap ScopeMap; ScopedHashTable VNT; SmallVector Exps; + unsigned CurrVN; bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); bool isPhysDefTriviallyDead(unsigned Reg, @@ -61,8 +65,15 @@ namespace { MachineBasicBlock::const_iterator E); bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB); bool isCSECandidate(MachineInstr *MI); - bool isProfitableToCSE(unsigned Reg, MachineInstr *MI); - bool ProcessBlock(MachineDomTreeNode *Node); + bool isProfitableToCSE(unsigned CSReg, unsigned Reg, + MachineInstr *CSMI, MachineInstr *MI); + void EnterScope(MachineBasicBlock *MBB); + void ExitScope(MachineBasicBlock *MBB); + bool ProcessBlock(MachineBasicBlock *MBB); + void ExitScopeIfDone(MachineDomTreeNode *Node, + DenseMap &OpenChildren, + DenseMap &ParentMap); + bool PerformCSE(MachineDomTreeNode *Node); }; } // end anonymous namespace @@ -101,6 +112,7 @@ bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, DEBUG(dbgs() << "Coalescing: " << *DefMI); DEBUG(dbgs() << "*** to: " << *MI); MO.setReg(SrcReg); + MRI->clearKillFlags(SrcReg); if (NewRC != SRC) MRI->setRegClass(SrcReg, NewRC); DefMI->eraseFromParent(); @@ -116,13 +128,15 @@ bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg, MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator E) { unsigned LookAheadLeft = 5; - while (LookAheadLeft--) { + while (LookAheadLeft) { + // Skip over dbg_value's. + while (I != E && I->isDebugValue()) + ++I; + if (I == E) // Reached end of block, register is obviously dead. return true; - if (I->isDebugValue()) - continue; bool SeenDef = false; for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { const MachineOperand &MO = I->getOperand(i); @@ -138,11 +152,15 @@ bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg, // See a def of Reg (or an alias) before encountering any use, it's // trivially dead. return true; + + --LookAheadLeft; ++I; } return false; } +/// hasLivePhysRegDefUse - Return true if the specified instruction read / write +/// physical registers (except for dead defs of physical registers). bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){ unsigned PhysDef = 0; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -177,16 +195,19 @@ bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){ return false; } +static bool isCopy(const MachineInstr *MI, const TargetInstrInfo *TII) { + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + return TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || + MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg(); +} + bool MachineCSE::isCSECandidate(MachineInstr *MI) { if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || - MI->isKill() || MI->isInlineAsm()) + MI->isKill() || MI->isInlineAsm() || MI->isDebugValue()) return false; - // Ignore copies or instructions that read / write physical registers - // (except for dead defs of physical registers). - unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; - if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || - MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg()) + // Ignore copies. + if (isCopy(MI, TII)) return false; // Ignore stuff that we obviously can't move. @@ -210,14 +231,52 @@ bool MachineCSE::isCSECandidate(MachineInstr *MI) { /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a /// common expression that defines Reg. -bool MachineCSE::isProfitableToCSE(unsigned Reg, MachineInstr *MI) { - // FIXME: This "heuristic" works around the lack the live range splitting. - // If the common subexpression is used by PHIs, do not reuse it unless the - // defined value is already used in the BB of the new use. +bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, + MachineInstr *CSMI, MachineInstr *MI) { + // FIXME: Heuristics that works around the lack the live range splitting. + + // Heuristics #1: Don't cse "cheap" computating if the def is not local or in an + // immediate predecessor. We don't want to increase register pressure and end up + // causing other computation to be spilled. + if (MI->getDesc().isAsCheapAsAMove()) { + MachineBasicBlock *CSBB = CSMI->getParent(); + MachineBasicBlock *BB = MI->getParent(); + if (CSBB != BB && + find(CSBB->succ_begin(), CSBB->succ_end(), BB) == CSBB->succ_end()) + return false; + } + + // Heuristics #2: If the expression doesn't not use a vr and the only use + // of the redundant computation are copies, do not cse. + bool HasVRegUse = false; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg() && MO.isUse() && MO.getReg() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + HasVRegUse = true; + break; + } + } + if (!HasVRegUse) { + bool HasNonCopyUse = false; + for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), + E = MRI->use_nodbg_end(); I != E; ++I) { + MachineInstr *Use = &*I; + // Ignore copies. + if (!isCopy(Use, TII)) { + HasNonCopyUse = true; + break; + } + } + if (!HasNonCopyUse) + return false; + } + + // Heuristics #3: If the common subexpression is used by PHIs, do not reuse + // it unless the defined value is already used in the BB of the new use. bool HasPHI = false; SmallPtrSet CSBBs; - for (MachineRegisterInfo::use_nodbg_iterator I = - MRI->use_nodbg_begin(Reg), + for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg), E = MRI->use_nodbg_end(); I != E; ++I) { MachineInstr *Use = &*I; HasPHI |= Use->isPHI(); @@ -229,13 +288,24 @@ bool MachineCSE::isProfitableToCSE(unsigned Reg, MachineInstr *MI) { return CSBBs.count(MI->getParent()); } -bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { +void MachineCSE::EnterScope(MachineBasicBlock *MBB) { + DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); + ScopeType *Scope = new ScopeType(VNT); + ScopeMap[MBB] = Scope; +} + +void MachineCSE::ExitScope(MachineBasicBlock *MBB) { + DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); + DenseMap::iterator SI = ScopeMap.find(MBB); + assert(SI != ScopeMap.end()); + ScopeMap.erase(SI); + delete SI->second; +} + +bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { bool Changed = false; SmallVector, 8> CSEPairs; - ScopedHashTableScope VNTS(VNT); - MachineBasicBlock *MBB = Node->getBlock(); for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { MachineInstr *MI = &*I; ++I; @@ -246,8 +316,12 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { bool FoundCSE = VNT.count(MI); if (!FoundCSE) { // Look for trivial copy coalescing opportunities. - if (PerformTrivialCoalescing(MI, MBB)) + if (PerformTrivialCoalescing(MI, MBB)) { + // After coalescing MI itself may become a copy. + if (isCopy(MI, TII)) + continue; FoundCSE = VNT.count(MI); + } } // FIXME: commute commutable instructions? @@ -282,7 +356,7 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { assert(TargetRegisterInfo::isVirtualRegister(OldReg) && TargetRegisterInfo::isVirtualRegister(NewReg) && "Do not CSE physical register defs!"); - if (!isProfitableToCSE(NewReg, MI)) { + if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { DoCSE = false; break; } @@ -292,8 +366,10 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { // Actually perform the elimination. if (DoCSE) { - for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) + for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); + MRI->clearKillFlags(CSEPairs[i].second); + } MI->eraseFromParent(); ++NumCSEs; } else { @@ -304,10 +380,63 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { CSEPairs.clear(); } - // Recursively call ProcessBlock with childred. - const std::vector &Children = Node->getChildren(); - for (unsigned i = 0, e = Children.size(); i != e; ++i) - Changed |= ProcessBlock(Children[i]); + return Changed; +} + +/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given +/// dominator tree node if its a leaf or all of its children are done. Walk +/// up the dominator tree to destroy ancestors which are now done. +void +MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, + DenseMap &OpenChildren, + DenseMap &ParentMap) { + if (OpenChildren[Node]) + return; + + // Pop scope. + ExitScope(Node->getBlock()); + + // Now traverse upwards to pop ancestors whose offsprings are all done. + while (MachineDomTreeNode *Parent = ParentMap[Node]) { + unsigned Left = --OpenChildren[Parent]; + if (Left != 0) + break; + ExitScope(Parent->getBlock()); + Node = Parent; + } +} + +bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { + SmallVector Scopes; + SmallVector WorkList; + DenseMap ParentMap; + DenseMap OpenChildren; + + // Perform a DFS walk to determine the order of visit. + WorkList.push_back(Node); + do { + Node = WorkList.pop_back_val(); + Scopes.push_back(Node); + const std::vector &Children = Node->getChildren(); + unsigned NumChildren = Children.size(); + OpenChildren[Node] = NumChildren; + for (unsigned i = 0; i != NumChildren; ++i) { + MachineDomTreeNode *Child = Children[i]; + ParentMap[Child] = Node; + WorkList.push_back(Child); + } + } while (!WorkList.empty()); + + // Now perform CSE. + bool Changed = false; + for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { + MachineDomTreeNode *Node = Scopes[i]; + MachineBasicBlock *MBB = Node->getBlock(); + EnterScope(MBB); + Changed |= ProcessBlock(MBB); + // If it's a leaf node, it's done. Traverse upwards to pop ancestors. + ExitScopeIfDone(Node, OpenChildren, ParentMap); + } return Changed; } @@ -318,5 +447,5 @@ bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); AA = &getAnalysis(); DT = &getAnalysis(); - return ProcessBlock(DT->getRootNode()); + return PerformCSE(DT->getRootNode()); }