#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;
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
#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 {
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
inline succ_iterator succ_end ( BasicBlock *BB);
inline succ_const_iterator succ_end (const BasicBlock *BB);
-
+#if 0
//===--------------------------------------------------------------------===//
// <Reverse> Depth First CFG iterator code
//===--------------------------------------------------------------------===//
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
#include "llvm/SymTabValue.h"
#include "llvm/BasicBlock.h"
-#include <list>
class Instruction;
class BasicBlock;
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
#define LLVM_TYPE_H
#include "llvm/Value.h"
+#include "llvm/Support/GraphTraits.h"
class DerivedType;
class MethodType;
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
#include "llvm/Analysis/Interval.h"
#include "llvm/BasicBlock.h"
-#include "llvm/CFG.h"
using namespace cfg;
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
-
+#include "llvm/Support/PostOrderIterator.h"
/************************** Constructor/Destructor ***************************/
{
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 ;
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];
#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>
//===----------------------------------------------------------------------===//
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);
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);
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
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
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,
}
} 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();
#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>
// 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);
}
#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
#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
// 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;
#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;
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 *****************************/
//**************************************************************************/
#include "SchedPriorities.h"
+#include "llvm/Support/PostOrderIterator.h"
SchedPriorities::SchedPriorities(const Method* method,
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;
#include "llvm/CodeGen/InstrScheduling.h"
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/Target/MachineSchedInfo.h"
+#include <list>
class Method;
class MachineInstr;
#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;
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 *****************************/
//**************************************************************************/
#include "SchedPriorities.h"
+#include "llvm/Support/PostOrderIterator.h"
SchedPriorities::SchedPriorities(const Method* method,
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;
#include "llvm/CodeGen/InstrScheduling.h"
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/Target/MachineSchedInfo.h"
+#include <list>
class Method;
class MachineInstr;
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
-
+#include "llvm/Support/PostOrderIterator.h"
/************************** Constructor/Destructor ***************************/
{
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 ;
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];
#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>
// 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; ) {
#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>
//===----------------------------------------------------------------------===//
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);
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);
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
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
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,
}
} 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();
#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
// 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;
#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 {
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;
#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 {
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;
#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 {
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;
projects / oota-llvm.git / commitdiff