X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineDominators.h;h=a69936f6e267ca339f2c6444e25bdf97be8eb69f;hb=fdd6e1b2e5e139a574f19788c71ae44dfaafa404;hp=7d1d9fe9ccf31b8a4a3db4f65d4ebe2588688f20;hpb=7ed47a13356daed2a34cd2209a31f92552e3bdd8;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 7d1d9fe9ccf..a69936f6e26 100644 --- a/include/llvm/CodeGen/MachineDominators.h +++ b/include/llvm/CodeGen/MachineDominators.h @@ -15,24 +15,22 @@ #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H #define LLVM_CODEGEN_MACHINEDOMINATORS_H -#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/DominatorInternals.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Support/GenericDomTree.h" +#include "llvm/Support/GenericDomTreeConstruction.h" namespace llvm { -inline void WriteAsOperand(std::ostream &, const MachineBasicBlock*, bool t) { } - template<> inline void DominatorTreeBase::addRoot(MachineBasicBlock* MBB) { this->Roots.push_back(MBB); } -EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); -EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); +extern template class DomTreeNodeBase; +extern template class DominatorTreeBase; typedef DomTreeNodeBase MachineDomTreeNode; @@ -41,65 +39,92 @@ typedef DomTreeNodeBase MachineDomTreeNode; /// compute a normal dominator tree. /// class MachineDominatorTree : public MachineFunctionPass { + /// \brief Helper structure used to hold all the basic blocks + /// involved in the split of a critical edge. + struct CriticalEdge { + MachineBasicBlock *FromBB; + MachineBasicBlock *ToBB; + MachineBasicBlock *NewBB; + }; + + /// \brief Pile up all the critical edges to be split. + /// The splitting of a critical edge is local and thus, it is possible + /// to apply several of those changes at the same time. + mutable SmallVector CriticalEdgesToSplit; + /// \brief Remember all the basic blocks that are inserted during + /// edge splitting. + /// Invariant: NewBBs == all the basic blocks contained in the NewBB + /// field of all the elements of CriticalEdgesToSplit. + /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs + /// such as BB == elt.NewBB. + mutable SmallSet NewBBs; + + /// \brief Apply all the recorded critical edges to the DT. + /// This updates the underlying DT information in a way that uses + /// the fast query path of DT as much as possible. + /// + /// \post CriticalEdgesToSplit.empty(). + void applySplitCriticalEdges() const; + public: static char ID; // Pass ID, replacement for typeid DominatorTreeBase* DT; - - MachineDominatorTree() : MachineFunctionPass(intptr_t(&ID)) { - DT = new DominatorTreeBase(false); - } - - ~MachineDominatorTree() { - DT->releaseMemory(); - delete DT; - } - - DominatorTreeBase& getBase() { return *DT; } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - MachineFunctionPass::getAnalysisUsage(AU); - } - + + MachineDominatorTree(); + + ~MachineDominatorTree() override; + + DominatorTreeBase &getBase() { + applySplitCriticalEdges(); + return *DT; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + /// getRoots - Return the root blocks of the current CFG. This may include /// multiple blocks if we are computing post dominators. For forward /// dominators, this will always be a single block (the entry node). /// inline const std::vector &getRoots() const { + applySplitCriticalEdges(); return DT->getRoots(); } - + inline MachineBasicBlock *getRoot() const { + applySplitCriticalEdges(); return DT->getRoot(); } - + inline MachineDomTreeNode *getRootNode() const { + applySplitCriticalEdges(); return DT->getRootNode(); } - - virtual bool runOnMachineFunction(MachineFunction &F) { - DT->recalculate(F); - - return false; - } - - inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { + + bool runOnMachineFunction(MachineFunction &F) override; + + inline bool dominates(const MachineDomTreeNode* A, + const MachineDomTreeNode* B) const { + applySplitCriticalEdges(); return DT->dominates(A, B); } - - inline bool dominates(MachineBasicBlock* A, MachineBasicBlock* B) const { + + inline bool dominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { + applySplitCriticalEdges(); return DT->dominates(A, B); } - + // dominates - Return true if A dominates B. This performs the // special checks necessary if A and B are in the same basic block. - bool dominates(MachineInstr *A, MachineInstr *B) const { - MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); + bool dominates(const MachineInstr *A, const MachineInstr *B) const { + applySplitCriticalEdges(); + const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); if (BBA != BBB) return DT->dominates(BBA, BBB); // Loop through the basic block until we find A or B. - MachineBasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; + MachineBasicBlock::const_iterator I = BBA->begin(); + for (; &*I != A && &*I != B; ++I) + /*empty*/ ; //if(!DT.IsPostDominators) { // A dominates B if it is found first in the basic block. @@ -109,76 +134,110 @@ public: // return &*I == B; //} } - + inline bool properlyDominates(const MachineDomTreeNode* A, - MachineDomTreeNode* B) const { + const MachineDomTreeNode* B) const { + applySplitCriticalEdges(); return DT->properlyDominates(A, B); } - - inline bool properlyDominates(MachineBasicBlock* A, - MachineBasicBlock* B) const { + + inline bool properlyDominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { + applySplitCriticalEdges(); return DT->properlyDominates(A, B); } - + /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) { + applySplitCriticalEdges(); return DT->findNearestCommonDominator(A, B); } - + inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { + applySplitCriticalEdges(); return DT->getNode(BB); } - + /// getNode - return the (Post)DominatorTree node for the specified basic /// block. This is the same as using operator[] on this class. /// inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { + applySplitCriticalEdges(); return DT->getNode(BB); } - + /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into + /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB) { + applySplitCriticalEdges(); return DT->addNewBlock(BB, DomBB); } - + /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// inline void changeImmediateDominator(MachineBasicBlock *N, MachineBasicBlock* NewIDom) { + applySplitCriticalEdges(); DT->changeImmediateDominator(N, NewIDom); } - + inline void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode* NewIDom) { + applySplitCriticalEdges(); DT->changeImmediateDominator(N, NewIDom); } - + /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(MachineBasicBlock *BB) { + applySplitCriticalEdges(); DT->eraseNode(BB); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. inline void splitBlock(MachineBasicBlock* NewBB) { + applySplitCriticalEdges(); DT->splitBlock(NewBB); } - - - virtual void releaseMemory() { - DT->releaseMemory(); + + /// isReachableFromEntry - Return true if A is dominated by the entry + /// block of the function containing it. + bool isReachableFromEntry(const MachineBasicBlock *A) { + applySplitCriticalEdges(); + return DT->isReachableFromEntry(A); } - - virtual void print(std::ostream &OS, const Module* M= 0) const { - DT->print(OS, M); + + void releaseMemory() override; + + void print(raw_ostream &OS, const Module*) const override; + + /// \brief Record that the critical edge (FromBB, ToBB) has been + /// split with NewBB. + /// This is best to use this method instead of directly update the + /// underlying information, because this helps mitigating the + /// number of time the DT information is invalidated. + /// + /// \note Do not use this method with regular edges. + /// + /// \note To benefit from the compile time improvement incurred by this + /// method, the users of this method have to limit the queries to the DT + /// interface between two edges splitting. In other words, they have to + /// pack the splitting of critical edges as much as possible. + void recordSplitCriticalEdge(MachineBasicBlock *FromBB, + MachineBasicBlock *ToBB, + MachineBasicBlock *NewBB) { + bool Inserted = NewBBs.insert(NewBB).second; + (void)Inserted; + assert(Inserted && + "A basic block inserted via edge splitting cannot appear twice"); + CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); } }; @@ -187,21 +246,29 @@ public: /// iterable by generic graph iterators. /// -template struct GraphTraits; +template +struct MachineDomTreeGraphTraitsBase { + typedef Node NodeType; + typedef ChildIterator ChildIteratorType; -template <> struct GraphTraits { - typedef MachineDomTreeNode NodeType; - typedef NodeType::iterator ChildIteratorType; - - static NodeType *getEntryNode(NodeType *N) { - return N; - } - static inline ChildIteratorType child_begin(NodeType* N) { + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { return N->begin(); } - static inline ChildIteratorType child_end(NodeType* N) { - return N->end(); - } + static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } +}; + +template struct GraphTraits; + +template <> +struct GraphTraits + : public MachineDomTreeGraphTraitsBase {}; + +template <> +struct GraphTraits + : public MachineDomTreeGraphTraitsBase { }; template <> struct GraphTraits