summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/ADT/GraphTraits.h15
-rw-r--r--llvm/include/llvm/ADT/SCCIterator.h37
-rw-r--r--llvm/include/llvm/Analysis/CallGraph.h2
-rw-r--r--llvm/include/llvm/CodeGen/MachineBasicBlock.h4
-rw-r--r--llvm/include/llvm/IR/CFG.h4
-rw-r--r--llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp1
-rw-r--r--llvm/lib/Transforms/IPO/FunctionAttrs.cpp1
-rw-r--r--llvm/unittests/ADT/SCCIteratorTest.cpp1
8 files changed, 41 insertions, 24 deletions
diff --git a/llvm/include/llvm/ADT/GraphTraits.h b/llvm/include/llvm/ADT/GraphTraits.h
index 823caef7647..eb67b7c8365 100644
--- a/llvm/include/llvm/ADT/GraphTraits.h
+++ b/llvm/include/llvm/ADT/GraphTraits.h
@@ -27,19 +27,24 @@ template<class GraphType>
struct GraphTraits {
// Elements to provide:
+ // NOTICE: We are in a transition from migration interfaces that require
+ // NodeType *, to NodeRef. NodeRef is required to be cheap to copy, but does
+ // not have to be a raw pointer. In the transition, user should define
+ // NodeType, and NodeRef = NodeType *.
+ //
// typedef NodeType - Type of Node in the graph
+ // typedef NodeRef - NodeType *
// typedef ChildIteratorType - Type used to iterate over children in graph
- // static NodeType *getEntryNode(const GraphType &)
+ // static NodeRef getEntryNode(const GraphType &)
// Return the entry node of the graph
- // static ChildIteratorType child_begin(NodeType *)
- // static ChildIteratorType child_end (NodeType *)
+ // static ChildIteratorType child_begin(NodeRef)
+ // static ChildIteratorType child_end (NodeRef)
// Return iterators that point to the beginning and ending of the child
// node list for the specified node.
//
-
// typedef ...iterator nodes_iterator;
// static nodes_iterator nodes_begin(GraphType *G)
// static nodes_iterator nodes_end (GraphType *G)
@@ -57,7 +62,7 @@ struct GraphTraits {
// your argument to XXX_begin(...) is unknown or needs to have the proper .h
// file #include'd.
//
- typedef typename GraphType::UnknownGraphTypeError NodeType;
+ typedef typename GraphType::UnknownGraphTypeError NodeRef;
};
diff --git a/llvm/include/llvm/ADT/SCCIterator.h b/llvm/include/llvm/ADT/SCCIterator.h
index bc74416ac88..e89345c0f34 100644
--- a/llvm/include/llvm/ADT/SCCIterator.h
+++ b/llvm/include/llvm/ADT/SCCIterator.h
@@ -37,23 +37,22 @@ namespace llvm {
/// build up a vector of nodes in a particular SCC. Note that it is a forward
/// iterator and thus you cannot backtrack or re-visit nodes.
template <class GraphT, class GT = GraphTraits<GraphT>>
-class scc_iterator
- : public iterator_facade_base<
- scc_iterator<GraphT, GT>, std::forward_iterator_tag,
- const std::vector<typename GT::NodeType *>, ptrdiff_t> {
- typedef typename GT::NodeType NodeType;
+class scc_iterator : public iterator_facade_base<
+ scc_iterator<GraphT, GT>, std::forward_iterator_tag,
+ const std::vector<typename GT::NodeRef>, ptrdiff_t> {
+ typedef typename GT::NodeRef NodeRef;
typedef typename GT::ChildIteratorType ChildItTy;
- typedef std::vector<NodeType *> SccTy;
+ typedef std::vector<NodeRef> SccTy;
typedef typename scc_iterator::reference reference;
/// Element of VisitStack during DFS.
struct StackElement {
- NodeType *Node; ///< The current node pointer.
+ NodeRef Node; ///< The current node pointer.
ChildItTy NextChild; ///< The next child, modified inplace during DFS.
unsigned MinVisited; ///< Minimum uplink value of all children of Node.
- StackElement(NodeType *Node, const ChildItTy &Child, unsigned Min)
- : Node(Node), NextChild(Child), MinVisited(Min) {}
+ StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
+ : Node(Node), NextChild(Child), MinVisited(Min) {}
bool operator==(const StackElement &Other) const {
return Node == Other.Node &&
@@ -67,10 +66,10 @@ class scc_iterator
///
/// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
unsigned visitNum;
- DenseMap<NodeType *, unsigned> nodeVisitNumbers;
+ DenseMap<NodeRef, unsigned> nodeVisitNumbers;
/// Stack holding nodes of the SCC.
- std::vector<NodeType *> SCCNodeStack;
+ std::vector<NodeRef> SCCNodeStack;
/// The current SCC, retrieved using operator*().
SccTy CurrentSCC;
@@ -80,7 +79,7 @@ class scc_iterator
std::vector<StackElement> VisitStack;
/// A single "visit" within the non-recursive DFS traversal.
- void DFSVisitOne(NodeType *N);
+ void DFSVisitOne(NodeRef N);
/// The stack-based DFS traversal; defined below.
void DFSVisitChildren();
@@ -88,7 +87,7 @@ class scc_iterator
/// Compute the next SCC using the DFS traversal.
void GetNextSCC();
- scc_iterator(NodeType *entryN) : visitNum(0) {
+ scc_iterator(NodeRef entryN) : visitNum(0) {
DFSVisitOne(entryN);
GetNextSCC();
}
@@ -131,7 +130,7 @@ public:
/// This informs the \c scc_iterator that the specified \c Old node
/// has been deleted, and \c New is to be used in its place.
- void ReplaceNode(NodeType *Old, NodeType *New) {
+ void ReplaceNode(NodeRef Old, NodeRef New) {
assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
nodeVisitNumbers[New] = nodeVisitNumbers[Old];
nodeVisitNumbers.erase(Old);
@@ -139,7 +138,7 @@ public:
};
template <class GraphT, class GT>
-void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) {
+void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
++visitNum;
nodeVisitNumbers[N] = visitNum;
SCCNodeStack.push_back(N);
@@ -155,8 +154,8 @@ void scc_iterator<GraphT, GT>::DFSVisitChildren() {
assert(!VisitStack.empty());
while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
// TOS has at least one more child so continue DFS
- NodeType *childN = *VisitStack.back().NextChild++;
- typename DenseMap<NodeType *, unsigned>::iterator Visited =
+ NodeRef childN = *VisitStack.back().NextChild++;
+ typename DenseMap<NodeRef, unsigned>::iterator Visited =
nodeVisitNumbers.find(childN);
if (Visited == nodeVisitNumbers.end()) {
// this node has never been seen.
@@ -176,7 +175,7 @@ template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
DFSVisitChildren();
// Pop the leaf on top of the VisitStack.
- NodeType *visitingN = VisitStack.back().Node;
+ NodeRef visitingN = VisitStack.back().Node;
unsigned minVisitNum = VisitStack.back().MinVisited;
assert(VisitStack.back().NextChild == GT::child_end(visitingN));
VisitStack.pop_back();
@@ -212,7 +211,7 @@ bool scc_iterator<GraphT, GT>::hasLoop() const {
assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
if (CurrentSCC.size() > 1)
return true;
- NodeType *N = CurrentSCC.front();
+ NodeRef N = CurrentSCC.front();
for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
++CI)
if (*CI == N)
diff --git a/llvm/include/llvm/Analysis/CallGraph.h b/llvm/include/llvm/Analysis/CallGraph.h
index 4ecacb0f0be..f37e843fed5 100644
--- a/llvm/include/llvm/Analysis/CallGraph.h
+++ b/llvm/include/llvm/Analysis/CallGraph.h
@@ -410,6 +410,7 @@ public:
// traversals.
template <> struct GraphTraits<CallGraphNode *> {
typedef CallGraphNode NodeType;
+ typedef CallGraphNode *NodeRef;
typedef CallGraphNode::CallRecord CGNPairTy;
typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode *>
@@ -431,6 +432,7 @@ template <> struct GraphTraits<CallGraphNode *> {
template <> struct GraphTraits<const CallGraphNode *> {
typedef const CallGraphNode NodeType;
+ typedef const CallGraphNode *NodeRef;
typedef CallGraphNode::CallRecord CGNPairTy;
typedef std::pointer_to_unary_function<CGNPairTy, const CallGraphNode *>
diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
index d5f918eb2bb..2923371c100 100644
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -740,6 +740,7 @@ struct MBB2NumberFunctor :
template <> struct GraphTraits<MachineBasicBlock *> {
typedef MachineBasicBlock NodeType;
+ typedef MachineBasicBlock *NodeRef;
typedef MachineBasicBlock::succ_iterator ChildIteratorType;
static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
@@ -753,6 +754,7 @@ template <> struct GraphTraits<MachineBasicBlock *> {
template <> struct GraphTraits<const MachineBasicBlock *> {
typedef const MachineBasicBlock NodeType;
+ typedef const MachineBasicBlock *NodeRef;
typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
@@ -772,6 +774,7 @@ template <> struct GraphTraits<const MachineBasicBlock *> {
//
template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
typedef MachineBasicBlock NodeType;
+ typedef MachineBasicBlock *NodeRef;
typedef MachineBasicBlock::pred_iterator ChildIteratorType;
static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
return G.Graph;
@@ -786,6 +789,7 @@ template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
typedef const MachineBasicBlock NodeType;
+ typedef const MachineBasicBlock *NodeRef;
typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
return G.Graph;
diff --git a/llvm/include/llvm/IR/CFG.h b/llvm/include/llvm/IR/CFG.h
index e9bf09333a2..a256b5960bb 100644
--- a/llvm/include/llvm/IR/CFG.h
+++ b/llvm/include/llvm/IR/CFG.h
@@ -155,6 +155,7 @@ struct isPodLike<TerminatorInst::SuccIterator<T, U>> {
template <> struct GraphTraits<BasicBlock*> {
typedef BasicBlock NodeType;
+ typedef BasicBlock *NodeRef;
typedef succ_iterator ChildIteratorType;
static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
@@ -168,6 +169,7 @@ template <> struct GraphTraits<BasicBlock*> {
template <> struct GraphTraits<const BasicBlock*> {
typedef const BasicBlock NodeType;
+ typedef const BasicBlock *NodeRef;
typedef succ_const_iterator ChildIteratorType;
static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
@@ -187,6 +189,7 @@ template <> struct GraphTraits<const BasicBlock*> {
//
template <> struct GraphTraits<Inverse<BasicBlock*> > {
typedef BasicBlock NodeType;
+ typedef BasicBlock *NodeRef;
typedef pred_iterator ChildIteratorType;
static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
static inline ChildIteratorType child_begin(NodeType *N) {
@@ -199,6 +202,7 @@ template <> struct GraphTraits<Inverse<BasicBlock*> > {
template <> struct GraphTraits<Inverse<const BasicBlock*> > {
typedef const BasicBlock NodeType;
+ typedef const BasicBlock *NodeRef;
typedef const_pred_iterator ChildIteratorType;
static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
return G.Graph;
diff --git a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
index 90bc249bcb3..c2039e1dec2 100644
--- a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -623,6 +623,7 @@ template <> struct GraphTraits<IrreducibleGraph> {
typedef bfi_detail::IrreducibleGraph GraphT;
typedef const GraphT::IrrNode NodeType;
+ typedef const GraphT::IrrNode *NodeRef;
typedef GraphT::IrrNode::iterator ChildIteratorType;
static const NodeType *getEntryNode(const GraphT &G) {
diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
index b5d04a7f3a4..a68e8d8ef5d 100644
--- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -333,6 +333,7 @@ struct ArgumentUsesTracker : public CaptureTracker {
namespace llvm {
template <> struct GraphTraits<ArgumentGraphNode *> {
typedef ArgumentGraphNode NodeType;
+ typedef ArgumentGraphNode *NodeRef;
typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
static inline NodeType *getEntryNode(NodeType *A) { return A; }
diff --git a/llvm/unittests/ADT/SCCIteratorTest.cpp b/llvm/unittests/ADT/SCCIteratorTest.cpp
index da8c04483f9..597661fd8cc 100644
--- a/llvm/unittests/ADT/SCCIteratorTest.cpp
+++ b/llvm/unittests/ADT/SCCIteratorTest.cpp
@@ -230,6 +230,7 @@ public:
template <unsigned N>
struct GraphTraits<Graph<N> > {
typedef typename Graph<N>::NodeType NodeType;
+ typedef typename Graph<N>::NodeType *NodeRef;
typedef typename Graph<N>::ChildIterator ChildIteratorType;
static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
OpenPOWER on IntegriCloud