1 //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // This file defines the iterators to iterate over the elements of a Region.
10 //===----------------------------------------------------------------------===//
11 #ifndef LLVM_ANALYSIS_REGIONITERATOR_H
12 #define LLVM_ANALYSIS_REGIONITERATOR_H
14 #include "llvm/ADT/GraphTraits.h"
15 #include "llvm/ADT/PointerIntPair.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/Analysis/RegionInfo.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/Support/raw_ostream.h"
22 //===----------------------------------------------------------------------===//
23 /// @brief Hierarchical RegionNode successor iterator.
25 /// This iterator iterates over all successors of a RegionNode.
27 /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
28 /// the parent Region. Furthermore for BasicBlocks that start a subregion, a
29 /// RegionNode representing the subregion is returned.
31 /// For a subregion RegionNode there is just one successor. The RegionNode
32 /// representing the exit of the subregion.
33 template <class NodeRef, class BlockT, class RegionT>
35 : public std::iterator<std::forward_iterator_tag, NodeRef> {
36 typedef std::iterator<std::forward_iterator_tag, NodeRef> super;
38 typedef GraphTraits<BlockT*> BlockTraits;
39 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
41 // The iterator works in two modes, bb mode or region mode.
43 // In BB mode it returns all successors of this BasicBlock as its
46 // In region mode there is only one successor, thats the regionnode mapping
47 // to the exit block of the regionnode
48 ItRgBegin, // At the beginning of the regionnode successor.
49 ItRgEnd // At the end of the regionnode successor.
52 static_assert(std::is_pointer<NodeRef>::value,
53 "FIXME: Currently RNSuccIterator only supports NodeRef as "
54 "pointers due to the use of pointer-specific data structures "
55 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
56 "it to support non-pointer types");
58 // Use two bit to represent the mode iterator.
59 PointerIntPair<NodeRef, 2, ItMode> Node;
61 // The block successor iterator.
64 // advanceRegionSucc - A region node has only one successor. It reaches end
65 // once we advance it.
66 void advanceRegionSucc() {
67 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
71 NodeRef getNode() const { return Node.getPointer(); }
73 // isRegionMode - Is the current iterator in region mode?
74 bool isRegionMode() const { return Node.getInt() != ItBB; }
76 // Get the immediate successor. This function may return a Basic Block
77 // RegionNode or a subregion RegionNode.
78 NodeRef getISucc(BlockT *BB) const {
80 succ = getNode()->getParent()->getNode(BB);
81 assert(succ && "BB not in Region or entered subregion!");
85 // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
86 inline BlockT* getRegionSucc() const {
87 assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
88 return getNode()->template getNodeAs<RegionT>()->getExit();
91 // isExit - Is this the exit BB of the Region?
92 inline bool isExit(BlockT* BB) const {
93 return getNode()->getParent()->getExit() == BB;
96 typedef RNSuccIterator<NodeRef, BlockT, RegionT> Self;
98 typedef typename super::value_type value_type;
100 /// @brief Create begin iterator of a RegionNode.
101 inline RNSuccIterator(NodeRef node)
102 : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
103 BItor(BlockTraits::child_begin(node->getEntry())) {
105 // Skip the exit block
107 while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
110 if (isRegionMode() && isExit(getRegionSucc()))
114 /// @brief Create an end iterator.
115 inline RNSuccIterator(NodeRef node, bool)
116 : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
117 BItor(BlockTraits::child_end(node->getEntry())) {}
119 inline bool operator==(const Self& x) const {
120 assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
122 return Node.getInt() == x.Node.getInt();
124 return BItor == x.BItor;
127 inline bool operator!=(const Self& x) const { return !operator==(x); }
129 inline value_type operator*() const {
130 BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
131 assert(!isExit(BB) && "Iterator out of range!");
135 inline Self& operator++() {
137 // The Region only has 1 successor.
143 while (BItor != BlockTraits::child_end(getNode()->getEntry())
149 inline Self operator++(int) {
157 //===----------------------------------------------------------------------===//
158 /// @brief Flat RegionNode iterator.
160 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
161 /// are contained in the Region and its subregions. This is close to a virtual
162 /// control flow graph of the Region.
163 template <class NodeRef, class BlockT, class RegionT>
164 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
165 : public std::iterator<std::forward_iterator_tag, NodeRef> {
166 typedef std::iterator<std::forward_iterator_tag, NodeRef> super;
167 typedef GraphTraits<BlockT*> BlockTraits;
168 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
174 typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> Self;
175 typedef typename super::value_type value_type;
177 /// @brief Create the iterator from a RegionNode.
179 /// Note that the incoming node must be a bb node, otherwise it will trigger
180 /// an assertion when we try to get a BasicBlock.
181 inline RNSuccIterator(NodeRef node)
182 : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
183 assert(!Node->isSubRegion() &&
184 "Subregion node not allowed in flat iterating mode!");
185 assert(Node->getParent() && "A BB node must have a parent!");
187 // Skip the exit block of the iterating region.
188 while (BlockTraits::child_end(Node->getEntry()) != Itor &&
189 Node->getParent()->getExit() == *Itor)
193 /// @brief Create an end iterator
194 inline RNSuccIterator(NodeRef node, bool)
195 : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
196 assert(!Node->isSubRegion() &&
197 "Subregion node not allowed in flat iterating mode!");
200 inline bool operator==(const Self& x) const {
201 assert(Node->getParent() == x.Node->getParent()
202 && "Cannot compare iterators of different regions!");
204 return Itor == x.Itor && Node == x.Node;
207 inline bool operator!=(const Self& x) const { return !operator==(x); }
209 inline value_type operator*() const {
212 // Get the iterating region.
213 RegionT *Parent = Node->getParent();
215 // The only case that the successor reaches out of the region is it reaches
216 // the exit of the region.
217 assert(Parent->getExit() != BB && "iterator out of range!");
219 return Parent->getBBNode(BB);
222 inline Self& operator++() {
223 // Skip the exit block of the iterating region.
226 while (Itor != succ_end(Node->getEntry())
227 && Node->getParent()->getExit() == *Itor);
232 inline Self operator++(int) {
239 template <class NodeRef, class BlockT, class RegionT>
240 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
241 return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
244 template <class NodeRef, class BlockT, class RegionT>
245 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
246 return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
249 //===--------------------------------------------------------------------===//
250 // RegionNode GraphTraits specialization so the bbs in the region can be
251 // iterate by generic graph iterators.
253 // NodeT can either be region node or const region node, otherwise child_begin
254 // and child_end fail.
256 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
257 template <> struct GraphTraits<NodeT *> { \
258 typedef NodeT *NodeRef; \
259 typedef RNSuccIterator<NodeRef, BlockT, RegionT> ChildIteratorType; \
260 static NodeRef getEntryNode(NodeRef N) { return N; } \
261 static inline ChildIteratorType child_begin(NodeRef N) { \
262 return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \
264 static inline ChildIteratorType child_end(NodeRef N) { \
265 return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \
268 template <> struct GraphTraits<FlatIt<NodeT *>> { \
269 typedef NodeT *NodeRef; \
270 typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> \
272 static NodeRef getEntryNode(NodeRef N) { return N; } \
273 static inline ChildIteratorType child_begin(NodeRef N) { \
274 return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \
276 static inline ChildIteratorType child_end(NodeRef N) { \
277 return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \
281 #define RegionGraphTraits(RegionT, NodeT) \
282 template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> { \
283 typedef df_iterator<NodeRef> nodes_iterator; \
284 static NodeRef getEntryNode(RegionT *R) { \
285 return R->getNode(R->getEntry()); \
287 static nodes_iterator nodes_begin(RegionT *R) { \
288 return nodes_iterator::begin(getEntryNode(R)); \
290 static nodes_iterator nodes_end(RegionT *R) { \
291 return nodes_iterator::end(getEntryNode(R)); \
295 struct GraphTraits<FlatIt<RegionT *>> \
296 : public GraphTraits<FlatIt<NodeT *>> { \
297 typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, \
298 GraphTraits<FlatIt<NodeRef>>> \
300 static NodeRef getEntryNode(RegionT *R) { \
301 return R->getBBNode(R->getEntry()); \
303 static nodes_iterator nodes_begin(RegionT *R) { \
304 return nodes_iterator::begin(getEntryNode(R)); \
306 static nodes_iterator nodes_end(RegionT *R) { \
307 return nodes_iterator::end(getEntryNode(R)); \
311 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
312 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
314 RegionGraphTraits(Region, RegionNode);
315 RegionGraphTraits(const Region, const RegionNode);
317 template <> struct GraphTraits<RegionInfo*>
318 : public GraphTraits<FlatIt<RegionNode*> > {
319 typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
320 GraphTraits<FlatIt<NodeRef>>>
323 static NodeRef getEntryNode(RegionInfo *RI) {
324 return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
326 static nodes_iterator nodes_begin(RegionInfo* RI) {
327 return nodes_iterator::begin(getEntryNode(RI));
329 static nodes_iterator nodes_end(RegionInfo *RI) {
330 return nodes_iterator::end(getEntryNode(RI));
334 template <> struct GraphTraits<RegionInfoPass*>
335 : public GraphTraits<RegionInfo *> {
336 typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
337 GraphTraits<FlatIt<NodeRef>>>
340 static NodeRef getEntryNode(RegionInfoPass *RI) {
341 return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
343 static nodes_iterator nodes_begin(RegionInfoPass* RI) {
344 return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
346 static nodes_iterator nodes_end(RegionInfoPass *RI) {
347 return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
351 } // End namespace llvm