diff options
24 files changed, 284 insertions, 458 deletions
diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h index fc41a12..50ec4c0 100644 --- a/include/llvm/BasicBlock.h +++ b/include/llvm/BasicBlock.h @@ -24,7 +24,9 @@ #include "llvm/Value.h" // Get the definition of Value #include "llvm/ValueHolder.h" -#include "llvm/CFGdecls.h" +#include "llvm/Support/GraphTraits.h" + +#include "llvm/CFGdecls.h" // TODO FIXME: remove class Instruction; class Method; @@ -140,4 +142,68 @@ public: BasicBlock *splitBasicBlock(iterator I); }; +#include "llvm/CFG.h" // TODO FIXME when succ iterators are in BB.h + +// Provide specializations of GraphTraits to be able to treat a method as a +// graph of basic blocks... + +template <> struct GraphTraits<BasicBlock*> { + typedef BasicBlock NodeType; + typedef BasicBlock::succ_iterator ChildIteratorType; + + static NodeType *getEntryNode(BasicBlock *BB) { return BB; } + static inline ChildIteratorType child_begin(NodeType *N) { + return cfg::succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return cfg::succ_end(N); + } +}; + +template <> struct GraphTraits<const BasicBlock*> { + typedef const BasicBlock NodeType; + typedef BasicBlock::succ_const_iterator ChildIteratorType; + + static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } + + static inline ChildIteratorType child_begin(NodeType *N) { + return cfg::succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return cfg::succ_end(N); + } +}; + +// Provide specializations of GraphTraits to be able to treat a method as a +// graph of basic blocks... and to walk it in inverse order. Inverse order for +// a method is considered to be when traversing the predecessor edges of a BB +// instead of the successor edges. +// +template <> struct GraphTraits<Inverse<BasicBlock*> > { + typedef BasicBlock NodeType; + typedef BasicBlock::pred_iterator ChildIteratorType; + static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } + static inline ChildIteratorType child_begin(NodeType *N) { + return cfg::pred_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return cfg::pred_end(N); + } +}; + +template <> struct GraphTraits<Inverse<const BasicBlock*> > { + typedef const BasicBlock NodeType; + typedef BasicBlock::pred_const_iterator ChildIteratorType; + static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { + return G.Graph; + } + static inline ChildIteratorType child_begin(NodeType *N) { + return cfg::pred_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return cfg::pred_end(N); + } +}; + + #endif diff --git a/include/llvm/CFG.h b/include/llvm/CFG.h index 40de3a8..ad9cd94 100644 --- a/include/llvm/CFG.h +++ b/include/llvm/CFG.h @@ -21,13 +21,10 @@ #define LLVM_CFG_H #include "llvm/CFGdecls.h" // See this file for concise interface info -#include "llvm/Method.h" #include "llvm/BasicBlock.h" #include "llvm/InstrTypes.h" #include "llvm/Type.h" #include <iterator> -#include <stack> -#include <set> namespace cfg { @@ -147,362 +144,6 @@ inline succ_const_iterator succ_end(const BasicBlock *BB) { return succ_const_iterator(BB->getTerminator(),true); } - -//===----------------------------------------------------------------------===// -// Graph Type Declarations -// -// BasicBlockGraph - Represent a standard traversal of a CFG -// ConstBasicBlockGraph - Represent a standard traversal of a const CFG -// InverseBasicBlockGraph - Represent a inverse traversal of a CFG -// ConstInverseBasicBlockGraph - Represent a inverse traversal of a const CFG -// -// An Inverse traversal of a graph is where we chase predecessors, instead of -// successors. -// -struct BasicBlockGraph { - typedef BasicBlock NodeType; - typedef succ_iterator ChildIteratorType; - static inline ChildIteratorType child_begin(NodeType *N) { - return succ_begin(N); - } - static inline ChildIteratorType child_end(NodeType *N) { - return succ_end(N); - } -}; - -struct ConstBasicBlockGraph { - typedef const BasicBlock NodeType; - typedef succ_const_iterator ChildIteratorType; - static inline ChildIteratorType child_begin(NodeType *N) { - return succ_begin(N); - } - static inline ChildIteratorType child_end(NodeType *N) { - return succ_end(N); - } -}; - -struct InverseBasicBlockGraph { - typedef BasicBlock NodeType; - typedef pred_iterator ChildIteratorType; - static inline ChildIteratorType child_begin(NodeType *N) { - return pred_begin(N); - } - static inline ChildIteratorType child_end(NodeType *N) { - return pred_end(N); - } -}; - -struct ConstInverseBasicBlockGraph { - typedef const BasicBlock NodeType; - typedef pred_const_iterator ChildIteratorType; - static inline ChildIteratorType child_begin(NodeType *N) { - return pred_begin(N); - } - static inline ChildIteratorType child_end(NodeType *N) { - return pred_end(N); - } -}; - -struct TypeGraph { - typedef const ::Type NodeType; - typedef ::Type::subtype_iterator ChildIteratorType; - - static inline ChildIteratorType child_begin(NodeType *N) { - return N->subtype_begin(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->subtype_end(); - } -}; - - -//===----------------------------------------------------------------------===// -// Depth First Iterator -// - -// Generic Depth First Iterator -template<class GI> -class DFIterator : public std::forward_iterator<typename GI::NodeType, - ptrdiff_t> { - typedef typename GI::NodeType NodeType; - typedef typename GI::ChildIteratorType ChildItTy; - - set<NodeType *> Visited; // All of the blocks visited so far... - // VisitStack - Used to maintain the ordering. Top = current block - // First element is node pointer, second is the 'next child' to visit - stack<pair<NodeType *, ChildItTy> > VisitStack; - const bool Reverse; // Iterate over children before self? -private: - void reverseEnterNode() { - pair<NodeType *, ChildItTy> &Top = VisitStack.top(); - NodeType *Node = Top.first; - ChildItTy &It = Top.second; - for (; It != GI::child_end(Node); ++It) { - NodeType *Child = *It; - if (!Visited.count(Child)) { - Visited.insert(Child); - VisitStack.push(make_pair(Child, GI::child_begin(Child))); - reverseEnterNode(); - return; - } - } - } -public: - typedef DFIterator<GI> _Self; - - inline DFIterator(NodeType *Node, bool reverse) : Reverse(reverse) { - Visited.insert(Node); - VisitStack.push(make_pair(Node, GI::child_begin(Node))); - if (Reverse) reverseEnterNode(); - } - inline DFIterator() { /* End is when stack is empty */ } - - inline bool operator==(const _Self& x) const { - return VisitStack == x.VisitStack; - } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - - inline pointer operator*() const { - return VisitStack.top().first; - } - - // This is a nonstandard operator-> that dereferences the pointer an extra - // time... so that you can actually call methods ON the Node, because - // the contained type is a pointer. This allows BBIt->getTerminator() f.e. - // - inline NodeType *operator->() const { return operator*(); } - - inline _Self& operator++() { // Preincrement - if (Reverse) { // Reverse Depth First Iterator - if (VisitStack.top().second == GI::child_end(VisitStack.top().first)) - VisitStack.pop(); - if (!VisitStack.empty()) - reverseEnterNode(); - } else { // Normal Depth First Iterator - do { - pair<NodeType *, ChildItTy> &Top = VisitStack.top(); - NodeType *Node = Top.first; - ChildItTy &It = Top.second; - - while (It != GI::child_end(Node)) { - NodeType *Next = *It++; - if (!Visited.count(Next)) { // Has our next sibling been visited? - // No, do it now. - Visited.insert(Next); - VisitStack.push(make_pair(Next, GI::child_begin(Next))); - return *this; - } - } - - // Oops, ran out of successors... go up a level on the stack. - VisitStack.pop(); - } while (!VisitStack.empty()); - } - return *this; - } - - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; - } - - // nodeVisited - return true if this iterator has already visited the - // specified node. This is public, and will probably be used to iterate over - // nodes that a depth first iteration did not find: ie unreachable nodes. - // - inline bool nodeVisited(NodeType *Node) const { - return Visited.count(Node) != 0; - } -}; - -inline df_iterator df_begin(Method *M, bool Reverse = false) { - return df_iterator(M->front(), Reverse); -} - -inline df_const_iterator df_begin(const Method *M, bool Reverse = false) { - return df_const_iterator(M->front(), Reverse); -} -inline df_iterator df_end(Method*) { - return df_iterator(); -} -inline df_const_iterator df_end(const Method*) { - return df_const_iterator(); -} - -inline df_iterator df_begin(BasicBlock *BB, bool Reverse = false) { - return df_iterator(BB, Reverse); -} -inline df_const_iterator df_begin(const BasicBlock *BB, bool Reverse = false) { - return df_const_iterator(BB, Reverse); -} - -inline df_iterator df_end(BasicBlock*) { - return df_iterator(); -} -inline df_const_iterator df_end(const BasicBlock*) { - return df_const_iterator(); -} - - - -inline idf_iterator idf_begin(BasicBlock *BB, bool Reverse = false) { - return idf_iterator(BB, Reverse); -} -inline idf_const_iterator idf_begin(const BasicBlock *BB, bool Reverse = false) { - return idf_const_iterator(BB, Reverse); -} - -inline idf_iterator idf_end(BasicBlock*) { - return idf_iterator(); -} -inline idf_const_iterator idf_end(const BasicBlock*) { - return idf_const_iterator(); -} - - - - -inline tdf_iterator tdf_begin(const Type *T, bool Reverse = false) { - return tdf_iterator(T, Reverse); -} -inline tdf_iterator tdf_end (const Type *T) { - return tdf_iterator(); -} - - - - -//===----------------------------------------------------------------------===// -// Post Order CFG iterator code -// - -template<class BBType, class SuccItTy> -class POIterator : public std::forward_iterator<BBType, ptrdiff_t> { - set<BBType *> Visited; // All of the blocks visited so far... - // VisitStack - Used to maintain the ordering. Top = current block - // First element is basic block pointer, second is the 'next child' to visit - stack<pair<BBType *, SuccItTy> > VisitStack; - - void traverseChild() { - while (VisitStack.top().second != succ_end(VisitStack.top().first)) { - BBType *BB = *VisitStack.top().second++; - if (!Visited.count(BB)) { // If the block is not visited... - Visited.insert(BB); - VisitStack.push(make_pair(BB, succ_begin(BB))); - } - } - } - -public: - typedef POIterator<BBType, SuccItTy> _Self; - - inline POIterator(BBType *BB) { - Visited.insert(BB); - VisitStack.push(make_pair(BB, succ_begin(BB))); - traverseChild(); - } - inline POIterator() { /* End is when stack is empty */ } - - inline bool operator==(const _Self& x) const { - return VisitStack == x.VisitStack; - } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - - inline pointer operator*() const { - return VisitStack.top().first; - } - - // This is a nonstandard operator-> that dereferences the pointer an extra - // time... so that you can actually call methods ON the BasicBlock, because - // the contained type is a pointer. This allows BBIt->getTerminator() f.e. - // - inline BBType *operator->() const { return operator*(); } - - inline _Self& operator++() { // Preincrement - VisitStack.pop(); - if (!VisitStack.empty()) - traverseChild(); - return *this; - } - - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; - } - - // Provide default begin and end methods when nothing special is needed. - static inline _Self begin (BBType *BB) { return _Self(BB); } - static inline _Self end (BBType *BB) { return _Self(); } -}; - -inline po_iterator po_begin( Method *M) { - return po_iterator(M->front()); -} -inline po_const_iterator po_begin(const Method *M) { - return po_const_iterator(M->front()); -} -inline po_iterator po_end ( Method *M) { - return po_iterator(); -} -inline po_const_iterator po_end (const Method *M) { - return po_const_iterator(); -} - -inline po_iterator po_begin( BasicBlock *BB) { - return po_iterator(BB); -} -inline po_const_iterator po_begin(const BasicBlock *BB) { - return po_const_iterator(BB); -} -inline po_iterator po_end ( BasicBlock *BB) { - return po_iterator(); -} -inline po_const_iterator po_end (const BasicBlock *BB) { - return po_const_iterator(); -} - - -//===--------------------------------------------------------------------===// -// Reverse Post Order CFG iterator code -//===--------------------------------------------------------------------===// -// -// This is used to visit basic blocks in a method in reverse post order. This -// class is awkward to use because I don't know a good incremental algorithm to -// computer RPO from a graph. Because of this, the construction of the -// ReversePostOrderTraversal object is expensive (it must walk the entire graph -// with a postorder iterator to build the data structures). The moral of this -// story is: Don't create more ReversePostOrderTraversal classes than neccesary. -// -// This class should be used like this: -// { -// cfg::ReversePostOrderTraversal RPOT(MethodPtr); // Expensive to create -// for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { -// ... -// } -// for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { -// ... -// } -// } -// - -typedef reverse_iterator<vector<BasicBlock*>::iterator> rpo_iterator; - -class ReversePostOrderTraversal { - vector<BasicBlock*> Blocks; // Block list in normal PO order - inline void Initialize(BasicBlock *BB) { - copy(po_begin(BB), po_end(BB), back_inserter(Blocks)); - } -public: - inline ReversePostOrderTraversal(Method *M) { - Initialize(M->front()); - } - inline ReversePostOrderTraversal(BasicBlock *BB) { - Initialize(BB); - } - - // Because we want a reverse post order, use reverse iterators from the vector - inline rpo_iterator begin() { return Blocks.rbegin(); } - inline rpo_iterator end() { return Blocks.rend(); } -}; - } // End namespace cfg #endif diff --git a/include/llvm/CFGdecls.h b/include/llvm/CFGdecls.h index fa6d08f..4ffe256 100644 --- a/include/llvm/CFGdecls.h +++ b/include/llvm/CFGdecls.h @@ -60,7 +60,7 @@ inline succ_const_iterator succ_begin(const BasicBlock *BB); inline succ_iterator succ_end ( BasicBlock *BB); inline succ_const_iterator succ_end (const BasicBlock *BB); - +#if 0 //===--------------------------------------------------------------------===// // <Reverse> Depth First CFG iterator code //===--------------------------------------------------------------------===// @@ -137,6 +137,7 @@ inline po_iterator po_begin( BasicBlock *BB); inline po_const_iterator po_begin(const BasicBlock *BB); inline po_iterator po_end ( BasicBlock *BB); inline po_const_iterator po_end (const BasicBlock *BB); +#endif } // End namespace cfg diff --git a/include/llvm/Function.h b/include/llvm/Function.h index 6ec28a8..a7075af 100644 --- a/include/llvm/Function.h +++ b/include/llvm/Function.h @@ -13,7 +13,6 @@ #include "llvm/SymTabValue.h" #include "llvm/BasicBlock.h" -#include <list> class Instruction; class BasicBlock; @@ -201,4 +200,32 @@ public: inline inst_const_iterator inst_end() const { return inst_const_iterator(*this, true); } }; +// Provide specializations of GraphTraits to be able to treat a method as a +// graph of basic blocks... these are the same as the basic block iterators, +// except that the root node is implicitly the first node of the method. +// +template <> struct GraphTraits<Method*> : public GraphTraits<BasicBlock*> { + static NodeType *getEntryNode(Method *M) { return M->front(); } +}; +template <> struct GraphTraits<const Method*> : + public GraphTraits<const BasicBlock*> { + static NodeType *getEntryNode(const Method *M) { return M->front(); } +}; + +// Provide specializations of GraphTraits to be able to treat a method as a +// graph of basic blocks... and to walk it in inverse order. Inverse order for +// a method is considered to be when traversing the predecessor edges of a BB +// instead of the successor edges. +// +template <> struct GraphTraits<Inverse<Method*> > : + public GraphTraits<Inverse<BasicBlock*> > { + static NodeType *getEntryNode(Inverse<Method *> G) { return G.Graph->front();} +}; +template <> struct GraphTraits<Inverse<const Method*> > : + public GraphTraits<Inverse<const BasicBlock*> > { + static NodeType *getEntryNode(Inverse<const Method *> G) { + return G.Graph->front(); + } +}; + #endif diff --git a/include/llvm/Type.h b/include/llvm/Type.h index ed39d12..5854062 100644 --- a/include/llvm/Type.h +++ b/include/llvm/Type.h @@ -27,6 +27,7 @@ #define LLVM_TYPE_H #include "llvm/Value.h" +#include "llvm/Support/GraphTraits.h" class DerivedType; class MethodType; @@ -264,4 +265,34 @@ inline Type::TypeIterator Type::subtype_end() const { return TypeIterator(this, getNumContainedTypes()); } + +// Provide specializations of GraphTraits to be able to treat a type as a +// graph of sub types... + +template <> struct GraphTraits<Type*> { + typedef Type NodeType; + typedef Type::subtype_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(Type *T) { return T; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->subtype_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->subtype_end(); + } +}; + +template <> struct GraphTraits<const Type*> { + typedef const Type NodeType; + typedef Type::subtype_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(const Type *T) { return T; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->subtype_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->subtype_end(); + } +}; + #endif diff --git a/lib/Analysis/Interval.cpp b/lib/Analysis/Interval.cpp index a6567ec..97fa34e 100644 --- a/lib/Analysis/Interval.cpp +++ b/lib/Analysis/Interval.cpp @@ -7,7 +7,6 @@ #include "llvm/Analysis/Interval.h" #include "llvm/BasicBlock.h" -#include "llvm/CFG.h" using namespace cfg; diff --git a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp index e47c9d2..898dd28 100644 --- a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp +++ b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp @@ -11,7 +11,7 @@ #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" #include "llvm/CodeGen/MachineInstr.h" - +#include "llvm/Support/PostOrderIterator.h" /************************** Constructor/Destructor ***************************/ @@ -47,9 +47,9 @@ void MethodLiveVarInfo::constructBBs() { unsigned int POId = 0; // Reverse Depth-first Order ID - cfg::po_const_iterator BBI = cfg::po_begin(Meth); + po_iterator<const Method*> BBI = po_begin(Meth); - for( ; BBI != cfg::po_end(Meth) ; ++BBI, ++POId) + for( ; BBI != po_end(Meth) ; ++BBI, ++POId) { if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":" << endl ; @@ -77,9 +77,9 @@ bool MethodLiveVarInfo::doSingleBackwardPass() if(DEBUG_LV) cout << endl << " After Backward Pass ..." << endl; - cfg::po_const_iterator BBI = cfg::po_begin(Meth); + po_iterator<const Method*> BBI = po_begin(Meth); - for( ; BBI != cfg::po_end(Meth) ; ++BBI) + for( ; BBI != po_end(Meth) ; ++BBI) { BBLiveVar* LVBB = BB2BBLVMap[*BBI]; diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index d349314..0372141 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -6,8 +6,9 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/SimplifyCFG.h" // To get cfg::UnifyAllExitNodes -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" #include "llvm/Support/STLExtras.h" +#include "llvm/Method.h" #include <algorithm> //===----------------------------------------------------------------------===// @@ -59,7 +60,7 @@ void cfg::DominatorSet::calcForwardDominatorSet(const Method *M) { Changed = false; DomSetType WorkingSet; - df_const_iterator It = df_begin(M), End = df_end(M); + df_iterator<const Method*> It = df_begin(M), End = df_end(M); for ( ; It != End; ++It) { const BasicBlock *BB = *It; pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB); @@ -110,7 +111,7 @@ cfg::DominatorSet::DominatorSet(Method *M, bool PostDomSet) set<const BasicBlock*> Visited; DomSetType WorkingSet; - idf_const_iterator It = idf_begin(Root), End = idf_end(Root); + idf_iterator<const BasicBlock*> It = idf_begin(Root), End = idf_end(Root); for ( ; It != End; ++It) { const BasicBlock *BB = *It; succ_const_iterator PI = succ_begin(BB), PEnd = succ_end(BB); @@ -201,7 +202,7 @@ cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms) Nodes[Root] = new Node(Root, 0); // Add a node for the root... // Iterate over all nodes in depth first order... - for (df_const_iterator I = df_begin(M), E = df_end(M); I != E; ++I) { + for (df_iterator<const Method*> I = df_begin(M), E = df_end(M); I != E; ++I) { const BasicBlock *BB = *I, *IDom = IDoms[*I]; if (IDom != 0) { // Ignore the root node and other nasty nodes @@ -223,16 +224,17 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { if (!isPostDominator()) { // Iterate over all nodes in depth first order... - for (df_const_iterator I = df_begin(Root), E = df_end(Root); I != E; ++I) { + for (df_iterator<const BasicBlock*> I = df_begin(Root), E = df_end(Root); + I != E; ++I) { const BasicBlock *BB = *I; const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); unsigned DomSetSize = Dominators.size(); if (DomSetSize == 1) continue; // Root node... IDom = null - // Loop over all dominators of this node. This corresponds to looping over + // Loop over all dominators of this node. This corresponds to looping over // nodes in the dominator chain, looking for a node whose dominator set is // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the + // in it. This means that it is one level higher in the dom chain than the // current node, and it is our idom! We know that we have already added // a DominatorTree node for our idom, because the idom must be a // predecessor in the depth first order that we are iterating through the @@ -241,11 +243,11 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { DominatorSet::DomSetType::const_iterator I = Dominators.begin(); DominatorSet::DomSetType::const_iterator End = Dominators.end(); for (; I != End; ++I) { // Iterate over dominators... - // All of our dominators should form a chain, where the number of elements - // in the dominator set indicates what level the node is at in the chain. - // We want the node immediately above us, so it will have an identical - // dominator set, except that BB will not dominate it... therefore it's - // dominator set size will be one less than BB's... + // All of our dominators should form a chain, where the number of + // elements in the dominator set indicates what level the node is at in + // the chain. We want the node immediately above us, so it will have + // an identical dominator set, except that BB will not dominate it... + // therefore it's dominator set size will be one less than BB's... // if (DS.getDominators(*I).size() == DomSetSize - 1) { // We know that the immediate dominator should already have a node, @@ -263,20 +265,21 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { } } else if (Root) { // Iterate over all nodes in depth first order... - for (idf_const_iterator I = idf_begin(Root), E = idf_end(Root); I != E; ++I) { + for (idf_iterator<const BasicBlock*> I = idf_begin(Root), E = idf_end(Root); + I != E; ++I) { const BasicBlock *BB = *I; const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); unsigned DomSetSize = Dominators.size(); if (DomSetSize == 1) continue; // Root node... IDom = null - // Loop over all dominators of this node. This corresponds to looping over - // nodes in the dominator chain, looking for a node whose dominator set is - // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the - // current node, and it is our idom! We know that we have already added - // a DominatorTree node for our idom, because the idom must be a - // predecessor in the depth first order that we are iterating through the - // method. + // Loop over all dominators of this node. This corresponds to looping + // over nodes in the dominator chain, looking for a node whose dominator + // set is equal to the current nodes, except that the current node does + // not exist in it. This means that it is one level higher in the dom + // chain than the current node, and it is our idom! We know that we have + // already added a DominatorTree node for our idom, because the idom must + // be a predecessor in the depth first order that we are iterating through + // the method. // DominatorSet::DomSetType::const_iterator I = Dominators.begin(); DominatorSet::DomSetType::const_iterator End = Dominators.end(); diff --git a/lib/AsmParser/llvmAsmParser.y b/lib/AsmParser/llvmAsmParser.y index 591b8e8..33f46fc 100644 --- a/lib/AsmParser/llvmAsmParser.y +++ b/lib/AsmParser/llvmAsmParser.y @@ -21,8 +21,8 @@ #include "llvm/DerivedTypes.h" #include "llvm/iTerminators.h" #include "llvm/iMemory.h" -#include "llvm/CFG.h" // TODO: Change this when we have a DF.h #include "llvm/Support/STLExtras.h" +#include "llvm/Support/DepthFirstIterator.h" #include <list> #include <utility> // Get definition of pair class #include <algorithm> @@ -417,7 +417,7 @@ static void setValueName(Value *V, char *NameStr) { // TypeContains - Returns true if Ty contains E in it. // static bool TypeContains(const Type *Ty, const Type *E) { - return find(cfg::tdf_begin(Ty), cfg::tdf_end(Ty), E) != cfg::tdf_end(Ty); + return find(df_begin(Ty), df_end(Ty), E) != df_end(Ty); } diff --git a/lib/Bytecode/Reader/ReaderInternals.h b/lib/Bytecode/Reader/ReaderInternals.h index b94b791..ed4f1a4 100644 --- a/lib/Bytecode/Reader/ReaderInternals.h +++ b/lib/Bytecode/Reader/ReaderInternals.h @@ -13,6 +13,7 @@ #include "llvm/Instruction.h" #include <map> #include <utility> +#include <list> // Enable to trace to figure out what the heck is going on when parsing fails #define TRACE_LEVEL 0 diff --git a/lib/Bytecode/Writer/SlotCalculator.cpp b/lib/Bytecode/Writer/SlotCalculator.cpp index 0ac371c..cac8f2e 100644 --- a/lib/Bytecode/Writer/SlotCalculator.cpp +++ b/lib/Bytecode/Writer/SlotCalculator.cpp @@ -20,7 +20,7 @@ #include "llvm/DerivedTypes.h" #include "llvm/SymbolTable.h" #include "llvm/Support/STLExtras.h" -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" #include <algorithm> #if 0 @@ -264,8 +264,8 @@ int SlotCalculator::insertVal(const Value *D, bool dontIgnore = false) { // the type itself is. This also assures us that we will not hit infinite // recursion on recursive types... // - for (cfg::tdf_iterator I = cfg::tdf_begin(TheTy, true), - E = cfg::tdf_end(TheTy); I != E; ++I) + for (df_iterator<const Type*> I = df_begin(TheTy, true), + E = df_end(TheTy); I != E; ++I) if (*I != TheTy) { // If we haven't seen this sub type before, add it to our type table! const Type *SubTy = *I; diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h index 5c4a600..ef3b4df 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.h +++ b/lib/CodeGen/InstrSched/SchedGraph.h @@ -19,13 +19,14 @@ #ifndef LLVM_CODEGEN_SCHEDGRAPH_H #define LLVM_CODEGEN_SCHEDGRAPH_H -#include "llvm/CFGdecls.h" // just for graph iterators #include "llvm/Support/NonCopyable.h" #include "llvm/Support/HashExtras.h" +#include "llvm/Support/GraphTraits.h" #include <hash_map> class Value; class Instruction; +class TerminatorInst; class BasicBlock; class Method; class TargetMachine; @@ -480,13 +481,36 @@ inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) { return sg_succ_const_iterator(N->endOutEdges()); } -// -// po_iterator -// po_const_iterator +// Provide specializations of GraphTraits to be able to use graph iterators on +// the scheduling graph! // -typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator; -typedef cfg::POIterator<const SchedGraphNode, - sg_succ_const_iterator> sg_po_const_iterator; +template <> struct GraphTraits<SchedGraph*> { + typedef SchedGraphNode NodeType; + typedef sg_succ_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); } + static inline ChildIteratorType child_begin(NodeType *N) { + return succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return succ_end(N); + } +}; + +template <> struct GraphTraits<const SchedGraph*> { + typedef const SchedGraphNode NodeType; + typedef sg_succ_const_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(const SchedGraph *SG) { + return SG->getRoot(); + } + static inline ChildIteratorType child_begin(NodeType *N) { + return succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return succ_end(N); + } +}; //************************ External Functions *****************************/ diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp index 9e2053b..7840a25 100644 --- a/lib/CodeGen/InstrSched/SchedPriorities.cpp +++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp @@ -19,6 +19,7 @@ //**************************************************************************/ #include "SchedPriorities.h" +#include "llvm/Support/PostOrderIterator.h" SchedPriorities::SchedPriorities(const Method* method, @@ -50,8 +51,7 @@ SchedPriorities::initialize() void SchedPriorities::computeDelays(const SchedGraph* graph) { - sg_po_const_iterator poIter = sg_po_const_iterator::begin(graph->getRoot()); - sg_po_const_iterator poEnd = sg_po_const_iterator::end( graph->getRoot()); + po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph); for ( ; poIter != poEnd; ++poIter) { const SchedGraphNode* node = *poIter; diff --git a/lib/CodeGen/InstrSched/SchedPriorities.h b/lib/CodeGen/InstrSched/SchedPriorities.h index 909f4ed..81a2e6a 100644 --- a/lib/CodeGen/InstrSched/SchedPriorities.h +++ b/lib/CodeGen/InstrSched/SchedPriorities.h @@ -25,6 +25,7 @@ #include "llvm/CodeGen/InstrScheduling.h" #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" #include "llvm/Target/MachineSchedInfo.h" +#include <list> class Method; class MachineInstr; diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.h b/lib/Target/SparcV9/InstrSched/SchedGraph.h index 5c4a600..ef3b4df 100644 --- a/lib/Target/SparcV9/InstrSched/SchedGraph.h +++ b/lib/Target/SparcV9/InstrSched/SchedGraph.h @@ -19,13 +19,14 @@ #ifndef LLVM_CODEGEN_SCHEDGRAPH_H #define LLVM_CODEGEN_SCHEDGRAPH_H -#include "llvm/CFGdecls.h" // just for graph iterators #include "llvm/Support/NonCopyable.h" #include "llvm/Support/HashExtras.h" +#include "llvm/Support/GraphTraits.h" #include <hash_map> class Value; class Instruction; +class TerminatorInst; class BasicBlock; class Method; class TargetMachine; @@ -480,13 +481,36 @@ inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) { return sg_succ_const_iterator(N->endOutEdges()); } -// -// po_iterator -// po_const_iterator +// Provide specializations of GraphTraits to be able to use graph iterators on +// the scheduling graph! // -typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator; -typedef cfg::POIterator<const SchedGraphNode, - sg_succ_const_iterator> sg_po_const_iterator; +template <> struct GraphTraits<SchedGraph*> { + typedef SchedGraphNode NodeType; + typedef sg_succ_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); } + static inline ChildIteratorType child_begin(NodeType *N) { + return succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return succ_end(N); + } +}; + +template <> struct GraphTraits<const SchedGraph*> { + typedef const SchedGraphNode NodeType; + typedef sg_succ_const_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(const SchedGraph *SG) { + return SG->getRoot(); + } + static inline ChildIteratorType child_begin(NodeType *N) { + return succ_begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return succ_end(N); + } +}; //************************ External Functions *****************************/ diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp index 9e2053b..7840a25 100644 --- a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp @@ -19,6 +19,7 @@ //**************************************************************************/ #include "SchedPriorities.h" +#include "llvm/Support/PostOrderIterator.h" SchedPriorities::SchedPriorities(const Method* method, @@ -50,8 +51,7 @@ SchedPriorities::initialize() void SchedPriorities::computeDelays(const SchedGraph* graph) { - sg_po_const_iterator poIter = sg_po_const_iterator::begin(graph->getRoot()); - sg_po_const_iterator poEnd = sg_po_const_iterator::end( graph->getRoot()); + po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph); for ( ; poIter != poEnd; ++poIter) { const SchedGraphNode* node = *poIter; diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.h b/lib/Target/SparcV9/InstrSched/SchedPriorities.h index 909f4ed..81a2e6a 100644 --- a/lib/Target/SparcV9/InstrSched/SchedPriorities.h +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.h @@ -25,6 +25,7 @@ #include "llvm/CodeGen/InstrScheduling.h" #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" #include "llvm/Target/MachineSchedInfo.h" +#include <list> class Method; class MachineInstr; diff --git a/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp b/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp index e47c9d2..898dd28 100644 --- a/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp +++ b/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp @@ -11,7 +11,7 @@ #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" #include "llvm/CodeGen/MachineInstr.h" - +#include "llvm/Support/PostOrderIterator.h" /************************** Constructor/Destructor ***************************/ @@ -47,9 +47,9 @@ void MethodLiveVarInfo::constructBBs() { unsigned int POId = 0; // Reverse Depth-first Order ID - cfg::po_const_iterator BBI = cfg::po_begin(Meth); + po_iterator<const Method*> BBI = po_begin(Meth); - for( ; BBI != cfg::po_end(Meth) ; ++BBI, ++POId) + for( ; BBI != po_end(Meth) ; ++BBI, ++POId) { if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":" << endl ; @@ -77,9 +77,9 @@ bool MethodLiveVarInfo::doSingleBackwardPass() if(DEBUG_LV) cout << endl << " After Backward Pass ..." << endl; - cfg::po_const_iterator BBI = cfg::po_begin(Meth); + po_iterator<const Method*> BBI = po_begin(Meth); - for( ; BBI != cfg::po_end(Meth) ; ++BBI) + for( ; BBI != po_end(Meth) ; ++BBI) { BBLiveVar* LVBB = BB2BBLVMap[*BBI]; diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 631db2c..446b95a 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -11,8 +11,8 @@ #include "llvm/Type.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Support/STLExtras.h" +#include "llvm/Support/DepthFirstIterator.h" #include "llvm/Analysis/Writer.h" -#include "llvm/CFG.h" #include "llvm/iTerminators.h" #include <set> #include <algorithm> @@ -90,7 +90,8 @@ bool ADCE::doADCE() { // instructions live in basic blocks that are unreachable. These blocks will // be eliminated later, along with the instructions inside. // - for (cfg::df_iterator BBI = cfg::df_begin(M), BBE = cfg::df_end(M); + for (df_iterator<Method*> BBI = df_begin(M), + BBE = df_end(M); BBI != BBE; ++BBI) { BasicBlock *BB = *BBI; for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index d349314..0372141 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -6,8 +6,9 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/SimplifyCFG.h" // To get cfg::UnifyAllExitNodes -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" #include "llvm/Support/STLExtras.h" +#include "llvm/Method.h" #include <algorithm> //===----------------------------------------------------------------------===// @@ -59,7 +60,7 @@ void cfg::DominatorSet::calcForwardDominatorSet(const Method *M) { Changed = false; DomSetType WorkingSet; - df_const_iterator It = df_begin(M), End = df_end(M); + df_iterator<const Method*> It = df_begin(M), End = df_end(M); for ( ; It != End; ++It) { const BasicBlock *BB = *It; pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB); @@ -110,7 +111,7 @@ cfg::DominatorSet::DominatorSet(Method *M, bool PostDomSet) set<const BasicBlock*> Visited; DomSetType WorkingSet; - idf_const_iterator It = idf_begin(Root), End = idf_end(Root); + idf_iterator<const BasicBlock*> It = idf_begin(Root), End = idf_end(Root); for ( ; It != End; ++It) { const BasicBlock *BB = *It; succ_const_iterator PI = succ_begin(BB), PEnd = succ_end(BB); @@ -201,7 +202,7 @@ cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms) Nodes[Root] = new Node(Root, 0); // Add a node for the root... // Iterate over all nodes in depth first order... - for (df_const_iterator I = df_begin(M), E = df_end(M); I != E; ++I) { + for (df_iterator<const Method*> I = df_begin(M), E = df_end(M); I != E; ++I) { const BasicBlock *BB = *I, *IDom = IDoms[*I]; if (IDom != 0) { // Ignore the root node and other nasty nodes @@ -223,16 +224,17 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { if (!isPostDominator()) { // Iterate over all nodes in depth first order... - for (df_const_iterator I = df_begin(Root), E = df_end(Root); I != E; ++I) { + for (df_iterator<const BasicBlock*> I = df_begin(Root), E = df_end(Root); + I != E; ++I) { const BasicBlock *BB = *I; const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); unsigned DomSetSize = Dominators.size(); if (DomSetSize == 1) continue; // Root node... IDom = null - // Loop over all dominators of this node. This corresponds to looping over + // Loop over all dominators of this node. This corresponds to looping over // nodes in the dominator chain, looking for a node whose dominator set is // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the + // in it. This means that it is one level higher in the dom chain than the // current node, and it is our idom! We know that we have already added // a DominatorTree node for our idom, because the idom must be a // predecessor in the depth first order that we are iterating through the @@ -241,11 +243,11 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { DominatorSet::DomSetType::const_iterator I = Dominators.begin(); DominatorSet::DomSetType::const_iterator End = Dominators.end(); for (; I != End; ++I) { // Iterate over dominators... - // All of our dominators should form a chain, where the number of elements - // in the dominator set indicates what level the node is at in the chain. - // We want the node immediately above us, so it will have an identical - // dominator set, except that BB will not dominate it... therefore it's - // dominator set size will be one less than BB's... + // All of our dominators should form a chain, where the number of + // elements in the dominator set indicates what level the node is at in + // the chain. We want the node immediately above us, so it will have + // an identical dominator set, except that BB will not dominate it... + // therefore it's dominator set size will be one less than BB's... // if (DS.getDominators(*I).size() == DomSetSize - 1) { // We know that the immediate dominator should already have a node, @@ -263,20 +265,21 @@ void cfg::DominatorTree::calculate(const DominatorSet &DS) { } } else if (Root) { // Iterate over all nodes in depth first order... - for (idf_const_iterator I = idf_begin(Root), E = idf_end(Root); I != E; ++I) { + for (idf_iterator<const BasicBlock*> I = idf_begin(Root), E = idf_end(Root); + I != E; ++I) { const BasicBlock *BB = *I; const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); unsigned DomSetSize = Dominators.size(); if (DomSetSize == 1) continue; // Root node... IDom = null - // Loop over all dominators of this node. This corresponds to looping over - // nodes in the dominator chain, looking for a node whose dominator set is - // equal to the current nodes, except that the current node does not exist - // in it. This means that it is one level higher in the dom chain than the - // current node, and it is our idom! We know that we have already added - // a DominatorTree node for our idom, because the idom must be a - // predecessor in the depth first order that we are iterating through the - // method. + // Loop over all dominators of this node. This corresponds to looping + // over nodes in the dominator chain, looking for a node whose dominator + // set is equal to the current nodes, except that the current node does + // not exist in it. This means that it is one level higher in the dom + // chain than the current node, and it is our idom! We know that we have + // already added a DominatorTree node for our idom, because the idom must + // be a predecessor in the depth first order that we are iterating through + // the method. // DominatorSet::DomSetType::const_iterator I = Dominators.begin(); DominatorSet::DomSetType::const_iterator End = Dominators.end(); diff --git a/lib/VMCore/SlotCalculator.cpp b/lib/VMCore/SlotCalculator.cpp index 0ac371c..cac8f2e 100644 --- a/lib/VMCore/SlotCalculator.cpp +++ b/lib/VMCore/SlotCalculator.cpp @@ -20,7 +20,7 @@ #include "llvm/DerivedTypes.h" #include "llvm/SymbolTable.h" #include "llvm/Support/STLExtras.h" -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" #include <algorithm> #if 0 @@ -264,8 +264,8 @@ int SlotCalculator::insertVal(const Value *D, bool dontIgnore = false) { // the type itself is. This also assures us that we will not hit infinite // recursion on recursive types... // - for (cfg::tdf_iterator I = cfg::tdf_begin(TheTy, true), - E = cfg::tdf_end(TheTy); I != E; ++I) + for (df_iterator<const Type*> I = df_begin(TheTy, true), + E = df_end(TheTy); I != E; ++I) if (*I != TheTy) { // If we haven't seen this sub type before, add it to our type table! const Type *SubTy = *I; diff --git a/tools/dis/dis.cpp b/tools/dis/dis.cpp index 462ad7f..27a3c93 100644 --- a/tools/dis/dis.cpp +++ b/tools/dis/dis.cpp @@ -23,7 +23,8 @@ #include "llvm/Bytecode/Reader.h" #include "llvm/Support/CommandLine.h" #include "llvm/Method.h" -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" +#include "llvm/Support/PostOrderIterator.h" // OutputMode - The different orderings to print basic blocks in... enum OutputMode { @@ -99,19 +100,19 @@ int main(int argc, char **argv) { switch (WriteMode) { case dfo: // Depth First ordering - copy(cfg::df_begin(M), cfg::df_end(M), + copy(df_begin(M), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rdfo: // Reverse Depth First ordering - copy(cfg::df_begin(M, true), cfg::df_end(M), + copy(df_begin(M, true), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case po: // Post Order - copy(cfg::po_begin(M), cfg::po_end(M), + copy(po_begin(M), po_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rpo: { // Reverse Post Order - cfg::ReversePostOrderTraversal RPOT(M); + ReversePostOrderTraversal RPOT(M); copy(RPOT.begin(), RPOT.end(), ostream_iterator<BasicBlock*>(*Out, "\n")); break; diff --git a/tools/llvm-dis/dis.cpp b/tools/llvm-dis/dis.cpp index 462ad7f..27a3c93 100644 --- a/tools/llvm-dis/dis.cpp +++ b/tools/llvm-dis/dis.cpp @@ -23,7 +23,8 @@ #include "llvm/Bytecode/Reader.h" #include "llvm/Support/CommandLine.h" #include "llvm/Method.h" -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" +#include "llvm/Support/PostOrderIterator.h" // OutputMode - The different orderings to print basic blocks in... enum OutputMode { @@ -99,19 +100,19 @@ int main(int argc, char **argv) { switch (WriteMode) { case dfo: // Depth First ordering - copy(cfg::df_begin(M), cfg::df_end(M), + copy(df_begin(M), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rdfo: // Reverse Depth First ordering - copy(cfg::df_begin(M, true), cfg::df_end(M), + copy(df_begin(M, true), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case po: // Post Order - copy(cfg::po_begin(M), cfg::po_end(M), + copy(po_begin(M), po_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rpo: { // Reverse Post Order - cfg::ReversePostOrderTraversal RPOT(M); + ReversePostOrderTraversal RPOT(M); copy(RPOT.begin(), RPOT.end(), ostream_iterator<BasicBlock*>(*Out, "\n")); break; diff --git a/tools/llvm-dis/llvm-dis.cpp b/tools/llvm-dis/llvm-dis.cpp index 462ad7f..27a3c93 100644 --- a/tools/llvm-dis/llvm-dis.cpp +++ b/tools/llvm-dis/llvm-dis.cpp @@ -23,7 +23,8 @@ #include "llvm/Bytecode/Reader.h" #include "llvm/Support/CommandLine.h" #include "llvm/Method.h" -#include "llvm/CFG.h" +#include "llvm/Support/DepthFirstIterator.h" +#include "llvm/Support/PostOrderIterator.h" // OutputMode - The different orderings to print basic blocks in... enum OutputMode { @@ -99,19 +100,19 @@ int main(int argc, char **argv) { switch (WriteMode) { case dfo: // Depth First ordering - copy(cfg::df_begin(M), cfg::df_end(M), + copy(df_begin(M), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rdfo: // Reverse Depth First ordering - copy(cfg::df_begin(M, true), cfg::df_end(M), + copy(df_begin(M, true), df_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case po: // Post Order - copy(cfg::po_begin(M), cfg::po_end(M), + copy(po_begin(M), po_end(M), ostream_iterator<BasicBlock*>(*Out, "\n")); break; case rpo: { // Reverse Post Order - cfg::ReversePostOrderTraversal RPOT(M); + ReversePostOrderTraversal RPOT(M); copy(RPOT.begin(), RPOT.end(), ostream_iterator<BasicBlock*>(*Out, "\n")); break; |