X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineDominators.h;h=608833305f9679531c6867afe96ac332435c4b67;hb=f3474549ba401c05a6d3db3dc6b2cfe3a7f73314;hp=621ba2f7a1bc25a0d762871a8da936299095196e;hpb=08895f886655d7d8368d2fdb513dcc963b681a74;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 621ba2f7a1b..608833305f9 100644 --- a/include/llvm/CodeGen/MachineDominators.h +++ b/include/llvm/CodeGen/MachineDominators.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Owen Anderson and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -15,16 +15,23 @@ #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H #define LLVM_CODEGEN_MACHINEDOMINATORS_H -#include "llvm/CodeGen/MachineFunctionPass.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/GenericDomTreeConstruction.h" +#include "llvm/Support/GenericDomTree.h" namespace llvm { -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); + +typedef DomTreeNodeBase MachineDomTreeNode; //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to @@ -34,16 +41,15 @@ class MachineDominatorTree : public MachineFunctionPass { 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; - } - + + MachineDominatorTree(); + + ~MachineDominatorTree(); + + DominatorTreeBase& getBase() { return *DT; } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + /// 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). @@ -51,38 +57,37 @@ public: inline const std::vector &getRoots() const { return DT->getRoots(); } - + inline MachineBasicBlock *getRoot() const { return DT->getRoot(); } - + inline MachineDomTreeNode *getRootNode() const { return DT->getRootNode(); } - - virtual bool runOnFunction(Function &F); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - - inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { + + virtual bool runOnMachineFunction(MachineFunction &F); + + inline bool dominates(const MachineDomTreeNode* A, + const MachineDomTreeNode* B) const { return DT->dominates(A, B); } - - inline bool dominates(MachineBasicBlock* A, MachineBasicBlock* B) const { + + inline bool dominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { 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 { + 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. @@ -92,43 +97,43 @@ public: // return &*I == B; //} } - + inline bool properlyDominates(const MachineDomTreeNode* A, - MachineDomTreeNode* B) const { + const MachineDomTreeNode* B) const { return DT->properlyDominates(A, B); } - - inline bool properlyDominates(MachineBasicBlock* A, - MachineBasicBlock* B) const { + + inline bool properlyDominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { 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) { return DT->findNearestCommonDominator(A, B); } - + inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { 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 { 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) { return DT->addNewBlock(BB, DomBB); } - + /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// @@ -136,35 +141,65 @@ public: MachineBasicBlock* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + inline void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode* NewIDom) { 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) { 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) { 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) { + return DT->isReachableFromEntry(A); + } + + virtual void releaseMemory(); + + virtual void print(raw_ostream &OS, const Module*) const; +}; + +//===------------------------------------- +/// DominatorTree GraphTraits specialization so the DominatorTree can be +/// iterable by generic graph iterators. +/// + +template struct GraphTraits; + +template <> struct GraphTraits { + typedef MachineDomTreeNode NodeType; + typedef NodeType::iterator ChildIteratorType; + + 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(); } - - virtual void print(std::ostream &OS, const Module* M= 0) const { - DT->print(OS, M); +}; + +template <> struct GraphTraits + : public GraphTraits { + static NodeType *getEntryNode(MachineDominatorTree *DT) { + return DT->getRootNode(); } }; } -#endif \ No newline at end of file +#endif