RegionIterator.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344
  1. //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  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
  13. #include "llvm/ADT/GraphTraits.h"
  14. #include "llvm/ADT/PointerIntPair.h"
  15. #include "llvm/ADT/SmallPtrSet.h"
  16. #include "llvm/Analysis/RegionInfo.h"
  17. #include "llvm/IR/CFG.h"
  18. #include "llvm/Support/raw_ostream.h"
  19. namespace llvm {
  20. //===----------------------------------------------------------------------===//
  21. /// @brief Hierarchical RegionNode successor iterator.
  22. ///
  23. /// This iterator iterates over all successors of a RegionNode.
  24. ///
  25. /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
  26. /// the parent Region. Furthermore for BasicBlocks that start a subregion, a
  27. /// RegionNode representing the subregion is returned.
  28. ///
  29. /// For a subregion RegionNode there is just one successor. The RegionNode
  30. /// representing the exit of the subregion.
  31. template<class NodeType, class BlockT, class RegionT>
  32. class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
  33. NodeType, ptrdiff_t> {
  34. typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
  35. typedef GraphTraits<BlockT*> BlockTraits;
  36. typedef typename BlockTraits::ChildIteratorType SuccIterTy;
  37. // The iterator works in two modes, bb mode or region mode.
  38. enum ItMode {
  39. // In BB mode it returns all successors of this BasicBlock as its
  40. // successors.
  41. ItBB,
  42. // In region mode there is only one successor, thats the regionnode mapping
  43. // to the exit block of the regionnode
  44. ItRgBegin, // At the beginning of the regionnode successor.
  45. ItRgEnd // At the end of the regionnode successor.
  46. };
  47. // Use two bit to represent the mode iterator.
  48. PointerIntPair<NodeType*, 2, ItMode> Node;
  49. // The block successor iterator.
  50. SuccIterTy BItor;
  51. // advanceRegionSucc - A region node has only one successor. It reaches end
  52. // once we advance it.
  53. void advanceRegionSucc() {
  54. assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
  55. Node.setInt(ItRgEnd);
  56. }
  57. NodeType* getNode() const{ return Node.getPointer(); }
  58. // isRegionMode - Is the current iterator in region mode?
  59. bool isRegionMode() const { return Node.getInt() != ItBB; }
  60. // Get the immediate successor. This function may return a Basic Block
  61. // RegionNode or a subregion RegionNode.
  62. NodeType* getISucc(BlockT* BB) const {
  63. NodeType *succ;
  64. succ = getNode()->getParent()->getNode(BB);
  65. assert(succ && "BB not in Region or entered subregion!");
  66. return succ;
  67. }
  68. // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
  69. inline BlockT* getRegionSucc() const {
  70. assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
  71. return getNode()->template getNodeAs<RegionT>()->getExit();
  72. }
  73. // isExit - Is this the exit BB of the Region?
  74. inline bool isExit(BlockT* BB) const {
  75. return getNode()->getParent()->getExit() == BB;
  76. }
  77. public:
  78. typedef RNSuccIterator<NodeType, BlockT, RegionT> Self;
  79. typedef typename super::pointer pointer;
  80. /// @brief Create begin iterator of a RegionNode.
  81. inline RNSuccIterator(NodeType* node)
  82. : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
  83. BItor(BlockTraits::child_begin(node->getEntry())) {
  84. // Skip the exit block
  85. if (!isRegionMode())
  86. while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
  87. ++BItor;
  88. if (isRegionMode() && isExit(getRegionSucc()))
  89. advanceRegionSucc();
  90. }
  91. /// @brief Create an end iterator.
  92. inline RNSuccIterator(NodeType* node, bool)
  93. : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
  94. BItor(BlockTraits::child_end(node->getEntry())) {}
  95. inline bool operator==(const Self& x) const {
  96. assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
  97. if (isRegionMode())
  98. return Node.getInt() == x.Node.getInt();
  99. else
  100. return BItor == x.BItor;
  101. }
  102. inline bool operator!=(const Self& x) const { return !operator==(x); }
  103. inline pointer operator*() const {
  104. BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
  105. assert(!isExit(BB) && "Iterator out of range!");
  106. return getISucc(BB);
  107. }
  108. inline Self& operator++() {
  109. if(isRegionMode()) {
  110. // The Region only has 1 successor.
  111. advanceRegionSucc();
  112. } else {
  113. // Skip the exit.
  114. do
  115. ++BItor;
  116. while (BItor != BlockTraits::child_end(getNode()->getEntry())
  117. && isExit(*BItor));
  118. }
  119. return *this;
  120. }
  121. inline Self operator++(int) {
  122. Self tmp = *this;
  123. ++*this;
  124. return tmp;
  125. }
  126. };
  127. // //
  128. ///////////////////////////////////////////////////////////////////////////////
  129. /// @brief Flat RegionNode iterator.
  130. ///
  131. /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
  132. /// are contained in the Region and its subregions. This is close to a virtual
  133. /// control flow graph of the Region.
  134. template<class NodeType, class BlockT, class RegionT>
  135. class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
  136. : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
  137. typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
  138. typedef GraphTraits<BlockT*> BlockTraits;
  139. typedef typename BlockTraits::ChildIteratorType SuccIterTy;
  140. NodeType* Node;
  141. SuccIterTy Itor;
  142. public:
  143. typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
  144. typedef typename super::pointer pointer;
  145. /// @brief Create the iterator from a RegionNode.
  146. ///
  147. /// Note that the incoming node must be a bb node, otherwise it will trigger
  148. /// an assertion when we try to get a BasicBlock.
  149. inline RNSuccIterator(NodeType* node) :
  150. Node(node),
  151. Itor(BlockTraits::child_begin(node->getEntry())) {
  152. assert(!Node->isSubRegion()
  153. && "Subregion node not allowed in flat iterating mode!");
  154. assert(Node->getParent() && "A BB node must have a parent!");
  155. // Skip the exit block of the iterating region.
  156. while (BlockTraits::child_end(Node->getEntry()) != Itor
  157. && Node->getParent()->getExit() == *Itor)
  158. ++Itor;
  159. }
  160. /// @brief Create an end iterator
  161. inline RNSuccIterator(NodeType* node, bool) :
  162. Node(node),
  163. Itor(BlockTraits::child_end(node->getEntry())) {
  164. assert(!Node->isSubRegion()
  165. && "Subregion node not allowed in flat iterating mode!");
  166. }
  167. inline bool operator==(const Self& x) const {
  168. assert(Node->getParent() == x.Node->getParent()
  169. && "Cannot compare iterators of different regions!");
  170. return Itor == x.Itor && Node == x.Node;
  171. }
  172. inline bool operator!=(const Self& x) const { return !operator==(x); }
  173. inline pointer operator*() const {
  174. BlockT *BB = *Itor;
  175. // Get the iterating region.
  176. RegionT *Parent = Node->getParent();
  177. // The only case that the successor reaches out of the region is it reaches
  178. // the exit of the region.
  179. assert(Parent->getExit() != BB && "iterator out of range!");
  180. return Parent->getBBNode(BB);
  181. }
  182. inline Self& operator++() {
  183. // Skip the exit block of the iterating region.
  184. do
  185. ++Itor;
  186. while (Itor != succ_end(Node->getEntry())
  187. && Node->getParent()->getExit() == *Itor);
  188. return *this;
  189. }
  190. inline Self operator++(int) {
  191. Self tmp = *this;
  192. ++*this;
  193. return tmp;
  194. }
  195. };
  196. template<class NodeType, class BlockT, class RegionT>
  197. inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
  198. return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
  199. }
  200. template<class NodeType, class BlockT, class RegionT>
  201. inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
  202. return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
  203. }
  204. //===--------------------------------------------------------------------===//
  205. // RegionNode GraphTraits specialization so the bbs in the region can be
  206. // iterate by generic graph iterators.
  207. //
  208. // NodeT can either be region node or const region node, otherwise child_begin
  209. // and child_end fail.
  210. #define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
  211. template<> struct GraphTraits<NodeT*> { \
  212. typedef NodeT NodeType; \
  213. typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType; \
  214. static NodeType *getEntryNode(NodeType* N) { return N; } \
  215. static inline ChildIteratorType child_begin(NodeType *N) { \
  216. return RNSuccIterator<NodeType, BlockT, RegionT>(N); \
  217. } \
  218. static inline ChildIteratorType child_end(NodeType *N) { \
  219. return RNSuccIterator<NodeType, BlockT, RegionT>(N, true); \
  220. } \
  221. }; \
  222. template<> struct GraphTraits<FlatIt<NodeT*>> { \
  223. typedef NodeT NodeType; \
  224. typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType; \
  225. static NodeType *getEntryNode(NodeType* N) { return N; } \
  226. static inline ChildIteratorType child_begin(NodeType *N) { \
  227. return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
  228. } \
  229. static inline ChildIteratorType child_end(NodeType *N) { \
  230. return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
  231. } \
  232. }
  233. #define RegionGraphTraits(RegionT, NodeT) \
  234. template<> struct GraphTraits<RegionT*> \
  235. : public GraphTraits<NodeT*> { \
  236. typedef df_iterator<NodeType*> nodes_iterator; \
  237. static NodeType *getEntryNode(RegionT* R) { \
  238. return R->getNode(R->getEntry()); \
  239. } \
  240. static nodes_iterator nodes_begin(RegionT* R) { \
  241. return nodes_iterator::begin(getEntryNode(R)); \
  242. } \
  243. static nodes_iterator nodes_end(RegionT* R) { \
  244. return nodes_iterator::end(getEntryNode(R)); \
  245. } \
  246. }; \
  247. template<> struct GraphTraits<FlatIt<RegionT*> > \
  248. : public GraphTraits<FlatIt<NodeT*> > { \
  249. typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \
  250. GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \
  251. static NodeType *getEntryNode(RegionT* R) { \
  252. return R->getBBNode(R->getEntry()); \
  253. } \
  254. static nodes_iterator nodes_begin(RegionT* R) { \
  255. return nodes_iterator::begin(getEntryNode(R)); \
  256. } \
  257. static nodes_iterator nodes_end(RegionT* R) { \
  258. return nodes_iterator::end(getEntryNode(R)); \
  259. } \
  260. }
  261. RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
  262. RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
  263. RegionGraphTraits(Region, RegionNode);
  264. RegionGraphTraits(const Region, const RegionNode);
  265. template <> struct GraphTraits<RegionInfo*>
  266. : public GraphTraits<FlatIt<RegionNode*> > {
  267. typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
  268. GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
  269. static NodeType *getEntryNode(RegionInfo *RI) {
  270. return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
  271. }
  272. static nodes_iterator nodes_begin(RegionInfo* RI) {
  273. return nodes_iterator::begin(getEntryNode(RI));
  274. }
  275. static nodes_iterator nodes_end(RegionInfo *RI) {
  276. return nodes_iterator::end(getEntryNode(RI));
  277. }
  278. };
  279. template <> struct GraphTraits<RegionInfoPass*>
  280. : public GraphTraits<RegionInfo *> {
  281. typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
  282. GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
  283. static NodeType *getEntryNode(RegionInfoPass *RI) {
  284. return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
  285. }
  286. static nodes_iterator nodes_begin(RegionInfoPass* RI) {
  287. return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
  288. }
  289. static nodes_iterator nodes_end(RegionInfoPass *RI) {
  290. return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
  291. }
  292. };
  293. } // End namespace llvm
  294. #endif