1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
//===- Support/PostOrderIterator.h - Generic PostOrder iterator -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file builds on the Support/GraphTraits.h file to build a generic graph
// post order iterator. This should work over any graph type that has a
// GraphTraits specialization.
//
//===----------------------------------------------------------------------===//
#ifndef SUPPORT_POSTORDERITERATOR_H
#define SUPPORT_POSTORDERITERATOR_H
#include "Support/GraphTraits.h"
#include "Support/iterator"
#include <stack>
#include <set>
namespace llvm {
template<class GraphT, class GT = GraphTraits<GraphT> >
class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t> {
typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
typedef typename GT::NodeType NodeType;
typedef typename GT::ChildIteratorType ChildItTy;
std::set<NodeType *> 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
std::stack<std::pair<NodeType *, ChildItTy> > VisitStack;
void traverseChild() {
while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) {
NodeType *BB = *VisitStack.top().second++;
if (!Visited.count(BB)) { // If the block is not visited...
Visited.insert(BB);
VisitStack.push(make_pair(BB, GT::child_begin(BB)));
}
}
}
inline po_iterator(NodeType *BB) {
Visited.insert(BB);
VisitStack.push(make_pair(BB, GT::child_begin(BB)));
traverseChild();
}
inline po_iterator() { /* End is when stack is empty */ }
public:
typedef typename super::pointer pointer;
typedef po_iterator<GraphT, GT> _Self;
// Provide static "constructors"...
static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
static inline _Self end (GraphT G) { return _Self(); }
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 NodeType *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 global constructors that automatically figure out correct types...
//
template <class T>
po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
template <class T>
po_iterator<T> po_end (T G) { return po_iterator<T>::end(G); }
// Provide global definitions of inverse post order iterators...
template <class T>
struct ipo_iterator : public po_iterator<Inverse<T> > {
ipo_iterator(const po_iterator<Inverse<T> > &V) :po_iterator<Inverse<T> >(V){}
};
template <class T>
ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
return ipo_iterator<T>::begin(G, Reverse);
}
template <class T>
ipo_iterator<T> ipo_end(T G){
return ipo_iterator<T>::end(G);
}
//===--------------------------------------------------------------------===//
// 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 necessary.
//
// This class should be used like this:
// {
// ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
// ...
// }
// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
// ...
// }
// }
//
template<class GraphT, class GT = GraphTraits<GraphT> >
class ReversePostOrderTraversal {
typedef typename GT::NodeType NodeType;
std::vector<NodeType*> Blocks; // Block list in normal PO order
inline void Initialize(NodeType *BB) {
copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
}
public:
typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
inline ReversePostOrderTraversal(GraphT G) {
Initialize(GT::getEntryNode(G));
}
// 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 llvm namespace
#endif
|
