Mercurial > hg > CbC > CbC_llvm

comparison include/llvm/Analysis/RegionIterator.h @ 77:54457678186b LLVM3.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.6
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Mon, 08 Sep 2014 22:06:00 +0900
parents 95c75e76d11b
children afa8332a0e37
comparison
equal deleted inserted replaced
34:e874dbf0ad9d 77:54457678186b
13 13
14 #include "llvm/ADT/GraphTraits.h" 14 #include "llvm/ADT/GraphTraits.h"
15 #include "llvm/ADT/PointerIntPair.h" 15 #include "llvm/ADT/PointerIntPair.h"
16 #include "llvm/ADT/SmallPtrSet.h" 16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/Analysis/RegionInfo.h" 17 #include "llvm/Analysis/RegionInfo.h"
18 #include "llvm/Support/CFG.h" 18 #include "llvm/IR/CFG.h"
19 #include "llvm/Support/raw_ostream.h" 19 #include "llvm/Support/raw_ostream.h"
20 20
21 namespace llvm { 21 namespace llvm {
22 //===----------------------------------------------------------------------===// 22 //===----------------------------------------------------------------------===//
23 /// @brief Hierarchical RegionNode successor iterator. 23 /// @brief Hierarchical RegionNode successor iterator.
28 /// the parent Region. Furthermore for BasicBlocks that start a subregion, a 28 /// the parent Region. Furthermore for BasicBlocks that start a subregion, a
29 /// RegionNode representing the subregion is returned. 29 /// RegionNode representing the subregion is returned.
30 /// 30 ///
31 /// For a subregion RegionNode there is just one successor. The RegionNode 31 /// For a subregion RegionNode there is just one successor. The RegionNode
32 /// representing the exit of the subregion. 32 /// representing the exit of the subregion.
33 template<class NodeType> 33 template<class NodeType, class BlockT, class RegionT>
34 class RNSuccIterator : public std::iterator<std::forward_iterator_tag, 34 class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
35 NodeType, ptrdiff_t> 35 NodeType, ptrdiff_t> {
36 {
37 typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 36 typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
37
38 typedef GraphTraits<BlockT*> BlockTraits;
39 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
40
38 // The iterator works in two modes, bb mode or region mode. 41 // The iterator works in two modes, bb mode or region mode.
39 enum ItMode{ 42 enum ItMode {
40 // In BB mode it returns all successors of this BasicBlock as its 43 // In BB mode it returns all successors of this BasicBlock as its
41 // successors. 44 // successors.
42 ItBB, 45 ItBB,
43 // In region mode there is only one successor, thats the regionnode mapping 46 // In region mode there is only one successor, thats the regionnode mapping
44 // to the exit block of the regionnode 47 // to the exit block of the regionnode
45 ItRgBegin, // At the beginning of the regionnode successor. 48 ItRgBegin, // At the beginning of the regionnode successor.
46 ItRgEnd // At the end of the regionnode successor. 49 ItRgEnd // At the end of the regionnode successor.
47 }; 50 };
48 51
49 // Use two bit to represent the mode iterator. 52 // Use two bit to represent the mode iterator.
50 PointerIntPair<NodeType*, 2, enum ItMode> Node; 53 PointerIntPair<NodeType*, 2, ItMode> Node;
51 54
52 // The block successor iterator. 55 // The block successor iterator.
53 succ_iterator BItor; 56 SuccIterTy BItor;
54 57
55 // advanceRegionSucc - A region node has only one successor. It reaches end 58 // advanceRegionSucc - A region node has only one successor. It reaches end
56 // once we advance it. 59 // once we advance it.
57 void advanceRegionSucc() { 60 void advanceRegionSucc() {
58 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); 61 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
64 // isRegionMode - Is the current iterator in region mode? 67 // isRegionMode - Is the current iterator in region mode?
65 bool isRegionMode() const { return Node.getInt() != ItBB; } 68 bool isRegionMode() const { return Node.getInt() != ItBB; }
66 69
67 // Get the immediate successor. This function may return a Basic Block 70 // Get the immediate successor. This function may return a Basic Block
68 // RegionNode or a subregion RegionNode. 71 // RegionNode or a subregion RegionNode.
69 RegionNode* getISucc(BasicBlock* BB) const { 72 NodeType* getISucc(BlockT* BB) const {
70 RegionNode *succ; 73 NodeType *succ;
71 succ = getNode()->getParent()->getNode(BB); 74 succ = getNode()->getParent()->getNode(BB);
72 assert(succ && "BB not in Region or entered subregion!"); 75 assert(succ && "BB not in Region or entered subregion!");
73 return succ; 76 return succ;
74 } 77 }
75 78
76 // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. 79 // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
77 inline BasicBlock* getRegionSucc() const { 80 inline BlockT* getRegionSucc() const {
78 assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); 81 assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
79 return getNode()->template getNodeAs<Region>()->getExit(); 82 return getNode()->template getNodeAs<RegionT>()->getExit();
80 } 83 }
81 84
82 // isExit - Is this the exit BB of the Region? 85 // isExit - Is this the exit BB of the Region?
83 inline bool isExit(BasicBlock* BB) const { 86 inline bool isExit(BlockT* BB) const {
84 return getNode()->getParent()->getExit() == BB; 87 return getNode()->getParent()->getExit() == BB;
85 } 88 }
86 public: 89 public:
87 typedef RNSuccIterator<NodeType> Self; 90 typedef RNSuccIterator<NodeType, BlockT, RegionT> Self;
88 91
89 typedef typename super::pointer pointer; 92 typedef typename super::pointer pointer;
90 93
91 /// @brief Create begin iterator of a RegionNode. 94 /// @brief Create begin iterator of a RegionNode.
92 inline RNSuccIterator(NodeType* node) 95 inline RNSuccIterator(NodeType* node)
93 : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), 96 : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
94 BItor(succ_begin(node->getEntry())) { 97 BItor(BlockTraits::child_begin(node->getEntry())) {
95
96 98
97 // Skip the exit block 99 // Skip the exit block
98 if (!isRegionMode()) 100 if (!isRegionMode())
99 while (succ_end(node->getEntry()) != BItor && isExit(*BItor)) 101 while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
100 ++BItor; 102 ++BItor;
101 103
102 if (isRegionMode() && isExit(getRegionSucc())) 104 if (isRegionMode() && isExit(getRegionSucc()))
103 advanceRegionSucc(); 105 advanceRegionSucc();
104 } 106 }
105 107
106 /// @brief Create an end iterator. 108 /// @brief Create an end iterator.
107 inline RNSuccIterator(NodeType* node, bool) 109 inline RNSuccIterator(NodeType* node, bool)
108 : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), 110 : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
109 BItor(succ_end(node->getEntry())) {} 111 BItor(BlockTraits::child_end(node->getEntry())) {}
110 112
111 inline bool operator==(const Self& x) const { 113 inline bool operator==(const Self& x) const {
112 assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); 114 assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
113 if (isRegionMode()) 115 if (isRegionMode())
114 return Node.getInt() == x.Node.getInt(); 116 return Node.getInt() == x.Node.getInt();
117 } 119 }
118 120
119 inline bool operator!=(const Self& x) const { return !operator==(x); } 121 inline bool operator!=(const Self& x) const { return !operator==(x); }
120 122
121 inline pointer operator*() const { 123 inline pointer operator*() const {
122 BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor; 124 BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
123 assert(!isExit(BB) && "Iterator out of range!"); 125 assert(!isExit(BB) && "Iterator out of range!");
124 return getISucc(BB); 126 return getISucc(BB);
125 } 127 }
126 128
127 inline Self& operator++() { 129 inline Self& operator++() {
130 advanceRegionSucc(); 132 advanceRegionSucc();
131 } else { 133 } else {
132 // Skip the exit. 134 // Skip the exit.
133 do 135 do
134 ++BItor; 136 ++BItor;
135 while (BItor != succ_end(getNode()->getEntry()) 137 while (BItor != BlockTraits::child_end(getNode()->getEntry())
136 && isExit(*BItor)); 138 && isExit(*BItor));
137 } 139 }
138 return *this; 140 return *this;
139 } 141 }
140 142
160 /// @brief Flat RegionNode iterator. 162 /// @brief Flat RegionNode iterator.
161 /// 163 ///
162 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that 164 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
163 /// are contained in the Region and its subregions. This is close to a virtual 165 /// are contained in the Region and its subregions. This is close to a virtual
164 /// control flow graph of the Region. 166 /// control flow graph of the Region.
165 template<class NodeType> 167 template<class NodeType, class BlockT, class RegionT>
166 class RNSuccIterator<FlatIt<NodeType> > 168 class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
167 : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> 169 : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
168 {
169 typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super; 170 typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
171 typedef GraphTraits<BlockT*> BlockTraits;
172 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
173
170 NodeType* Node; 174 NodeType* Node;
171 succ_iterator Itor; 175 SuccIterTy Itor;
172 176
173 public: 177 public:
174 typedef RNSuccIterator<FlatIt<NodeType> > Self; 178 typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
175 typedef typename super::pointer pointer; 179 typedef typename super::pointer pointer;
176 180
177 /// @brief Create the iterator from a RegionNode. 181 /// @brief Create the iterator from a RegionNode.
178 /// 182 ///
179 /// Note that the incoming node must be a bb node, otherwise it will trigger 183 /// Note that the incoming node must be a bb node, otherwise it will trigger
180 /// an assertion when we try to get a BasicBlock. 184 /// an assertion when we try to get a BasicBlock.
181 inline RNSuccIterator(NodeType* node) : Node(node), 185 inline RNSuccIterator(NodeType* node) :
182 Itor(succ_begin(node->getEntry())) { 186 Node(node),
187 Itor(BlockTraits::child_begin(node->getEntry())) {
183 assert(!Node->isSubRegion() 188 assert(!Node->isSubRegion()
184 && "Subregion node not allowed in flat iterating mode!"); 189 && "Subregion node not allowed in flat iterating mode!");
185 assert(Node->getParent() && "A BB node must have a parent!"); 190 assert(Node->getParent() && "A BB node must have a parent!");
186 191
187 // Skip the exit block of the iterating region. 192 // Skip the exit block of the iterating region.
188 while (succ_end(Node->getEntry()) != Itor 193 while (BlockTraits::child_end(Node->getEntry()) != Itor
189 && Node->getParent()->getExit() == *Itor) 194 && Node->getParent()->getExit() == *Itor)
190 ++Itor; 195 ++Itor;
191 } 196 }
197
192 /// @brief Create an end iterator 198 /// @brief Create an end iterator
193 inline RNSuccIterator(NodeType* node, bool) : Node(node), 199 inline RNSuccIterator(NodeType* node, bool) :
194 Itor(succ_end(node->getEntry())) { 200 Node(node),
201 Itor(BlockTraits::child_end(node->getEntry())) {
195 assert(!Node->isSubRegion() 202 assert(!Node->isSubRegion()
196 && "Subregion node not allowed in flat iterating mode!"); 203 && "Subregion node not allowed in flat iterating mode!");
197 } 204 }
198 205
199 inline bool operator==(const Self& x) const { 206 inline bool operator==(const Self& x) const {
204 } 211 }
205 212
206 inline bool operator!=(const Self& x) const { return !operator==(x); } 213 inline bool operator!=(const Self& x) const { return !operator==(x); }
207 214
208 inline pointer operator*() const { 215 inline pointer operator*() const {
209 BasicBlock* BB = *Itor; 216 BlockT *BB = *Itor;
210 217
211 // Get the iterating region. 218 // Get the iterating region.
212 Region* Parent = Node->getParent(); 219 RegionT *Parent = Node->getParent();
213 220
214 // The only case that the successor reaches out of the region is it reaches 221 // The only case that the successor reaches out of the region is it reaches
215 // the exit of the region. 222 // the exit of the region.
216 assert(Parent->getExit() != BB && "iterator out of range!"); 223 assert(Parent->getExit() != BB && "iterator out of range!");
217 224
243 } 250 }
244 return *this; 251 return *this;
245 } 252 }
246 }; 253 };
247 254
248 template<class NodeType> 255 template<class NodeType, class BlockT, class RegionT>
249 inline RNSuccIterator<NodeType> succ_begin(NodeType* Node) { 256 inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
250 return RNSuccIterator<NodeType>(Node); 257 return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
251 } 258 }
252 259
253 template<class NodeType> 260 template<class NodeType, class BlockT, class RegionT>
254 inline RNSuccIterator<NodeType> succ_end(NodeType* Node) { 261 inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
255 return RNSuccIterator<NodeType>(Node, true); 262 return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
256 } 263 }
257 264
258 //===--------------------------------------------------------------------===// 265 //===--------------------------------------------------------------------===//
259 // RegionNode GraphTraits specialization so the bbs in the region can be 266 // RegionNode GraphTraits specialization so the bbs in the region can be
260 // iterate by generic graph iterators. 267 // iterate by generic graph iterators.
261 // 268 //
262 // NodeT can either be region node or const region node, otherwise child_begin 269 // NodeT can either be region node or const region node, otherwise child_begin
263 // and child_end fail. 270 // and child_end fail.
264 271
265 #define RegionNodeGraphTraits(NodeT) \ 272 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
266 template<> struct GraphTraits<NodeT*> { \ 273 template<> struct GraphTraits<NodeT*> { \
267 typedef NodeT NodeType; \ 274 typedef NodeT NodeType; \
268 typedef RNSuccIterator<NodeType> ChildIteratorType; \ 275 typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType; \
269 static NodeType *getEntryNode(NodeType* N) { return N; } \ 276 static NodeType *getEntryNode(NodeType* N) { return N; } \
270 static inline ChildIteratorType child_begin(NodeType *N) { \ 277 static inline ChildIteratorType child_begin(NodeType *N) { \
271 return RNSuccIterator<NodeType>(N); \ 278 return RNSuccIterator<NodeType, BlockT, RegionT>(N); \
272 } \ 279 } \
273 static inline ChildIteratorType child_end(NodeType *N) { \ 280 static inline ChildIteratorType child_end(NodeType *N) { \
274 return RNSuccIterator<NodeType>(N, true); \ 281 return RNSuccIterator<NodeType, BlockT, RegionT>(N, true); \
275 } \ 282 } \
276 }; \ 283 }; \
277 template<> struct GraphTraits<FlatIt<NodeT*> > { \ 284 template<> struct GraphTraits<FlatIt<NodeT*>> { \
278 typedef NodeT NodeType; \ 285 typedef NodeT NodeType; \
279 typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \ 286 typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType; \
280 static NodeType *getEntryNode(NodeType* N) { return N; } \ 287 static NodeType *getEntryNode(NodeType* N) { return N; } \
281 static inline ChildIteratorType child_begin(NodeType *N) { \ 288 static inline ChildIteratorType child_begin(NodeType *N) { \
282 return RNSuccIterator<FlatIt<NodeType> >(N); \ 289 return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
283 } \ 290 } \
284 static inline ChildIteratorType child_end(NodeType *N) { \ 291 static inline ChildIteratorType child_end(NodeType *N) { \
285 return RNSuccIterator<FlatIt<NodeType> >(N, true); \ 292 return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
286 } \ 293 } \
287 } 294 }
288 295
289 #define RegionGraphTraits(RegionT, NodeT) \ 296 #define RegionGraphTraits(RegionT, NodeT) \
290 template<> struct GraphTraits<RegionT*> \ 297 template<> struct GraphTraits<RegionT*> \
313 static nodes_iterator nodes_end(RegionT* R) { \ 320 static nodes_iterator nodes_end(RegionT* R) { \
314 return nodes_iterator::end(getEntryNode(R)); \ 321 return nodes_iterator::end(getEntryNode(R)); \
315 } \ 322 } \
316 } 323 }
317 324
318 RegionNodeGraphTraits(RegionNode); 325 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
319 RegionNodeGraphTraits(const RegionNode); 326 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
320 327
321 RegionGraphTraits(Region, RegionNode); 328 RegionGraphTraits(Region, RegionNode);
322 RegionGraphTraits(const Region, const RegionNode); 329 RegionGraphTraits(const Region, const RegionNode);
323 330
324 template <> struct GraphTraits<RegionInfo*> 331 template <> struct GraphTraits<RegionInfo*>
335 static nodes_iterator nodes_end(RegionInfo *RI) { 342 static nodes_iterator nodes_end(RegionInfo *RI) {
336 return nodes_iterator::end(getEntryNode(RI)); 343 return nodes_iterator::end(getEntryNode(RI));
337 } 344 }
338 }; 345 };
339 346
347 template <> struct GraphTraits<RegionInfoPass*>
348 : public GraphTraits<RegionInfo *> {
349 typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
350 GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
351
352 static NodeType *getEntryNode(RegionInfoPass *RI) {
353 return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
354 }
355 static nodes_iterator nodes_begin(RegionInfoPass* RI) {
356 return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
357 }
358 static nodes_iterator nodes_end(RegionInfoPass *RI) {
359 return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
360 }
361 };
362
340 } // End namespace llvm 363 } // End namespace llvm
341 364
342 #endif 365 #endif