IntervalIterator.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268
  1. //===- IntervalIterator.h - Interval Iterator Declaration -------*- 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. //
  10. // This file defines an iterator that enumerates the intervals in a control flow
  11. // graph of some sort. This iterator is parametric, allowing iterator over the
  12. // following types of graphs:
  13. //
  14. // 1. A Function* object, composed of BasicBlock nodes.
  15. // 2. An IntervalPartition& object, composed of Interval nodes.
  16. //
  17. // This iterator is defined to walk the control flow graph, returning intervals
  18. // in depth first order. These intervals are completely filled in except for
  19. // the predecessor fields (the successor information is filled in however).
  20. //
  21. // By default, the intervals created by this iterator are deleted after they
  22. // are no longer any use to the iterator. This behavior can be changed by
  23. // passing a false value into the intervals_begin() function. This causes the
  24. // IOwnMem member to be set, and the intervals to not be deleted.
  25. //
  26. // It is only safe to use this if all of the intervals are deleted by the caller
  27. // and all of the intervals are processed. However, the user of the iterator is
  28. // not allowed to modify or delete the intervals until after the iterator has
  29. // been used completely. The IntervalPartition class uses this functionality.
  30. //
  31. //===----------------------------------------------------------------------===//
  32. #ifndef LLVM_ANALYSIS_INTERVALITERATOR_H
  33. #define LLVM_ANALYSIS_INTERVALITERATOR_H
  34. #include "llvm/Analysis/IntervalPartition.h"
  35. #include "llvm/IR/CFG.h"
  36. #include "llvm/IR/Function.h"
  37. #include <algorithm>
  38. #include <set>
  39. #include <vector>
  40. namespace llvm {
  41. // getNodeHeader - Given a source graph node and the source graph, return the
  42. // BasicBlock that is the header node. This is the opposite of
  43. // getSourceGraphNode.
  44. //
  45. inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
  46. inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
  47. // getSourceGraphNode - Given a BasicBlock and the source graph, return the
  48. // source graph node that corresponds to the BasicBlock. This is the opposite
  49. // of getNodeHeader.
  50. //
  51. inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
  52. return BB;
  53. }
  54. inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
  55. return IP->getBlockInterval(BB);
  56. }
  57. // addNodeToInterval - This method exists to assist the generic ProcessNode
  58. // with the task of adding a node to the new interval, depending on the
  59. // type of the source node. In the case of a CFG source graph (BasicBlock
  60. // case), the BasicBlock itself is added to the interval.
  61. //
  62. inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
  63. Int->Nodes.push_back(BB);
  64. }
  65. // addNodeToInterval - This method exists to assist the generic ProcessNode
  66. // with the task of adding a node to the new interval, depending on the
  67. // type of the source node. In the case of a CFG source graph (BasicBlock
  68. // case), the BasicBlock itself is added to the interval. In the case of
  69. // an IntervalPartition source graph (Interval case), all of the member
  70. // BasicBlocks are added to the interval.
  71. //
  72. inline void addNodeToInterval(Interval *Int, Interval *I) {
  73. // Add all of the nodes in I as new nodes in Int.
  74. Int->Nodes.insert(Int->Nodes.end(), I->Nodes.begin(), I->Nodes.end());
  75. }
  76. template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>,
  77. class IGT = GraphTraits<Inverse<NodeTy*> > >
  78. class IntervalIterator {
  79. std::vector<std::pair<Interval*, typename Interval::succ_iterator> > IntStack;
  80. std::set<BasicBlock*> Visited;
  81. OrigContainer_t *OrigContainer;
  82. bool IOwnMem; // If True, delete intervals when done with them
  83. // See file header for conditions of use
  84. public:
  85. typedef std::forward_iterator_tag iterator_category;
  86. IntervalIterator() {} // End iterator, empty stack
  87. IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
  88. OrigContainer = M;
  89. if (!ProcessInterval(&M->front())) {
  90. llvm_unreachable("ProcessInterval should never fail for first interval!");
  91. }
  92. }
  93. IntervalIterator(IntervalIterator &&x)
  94. : IntStack(std::move(x.IntStack)), Visited(std::move(x.Visited)),
  95. OrigContainer(x.OrigContainer), IOwnMem(x.IOwnMem) {
  96. x.IOwnMem = false;
  97. }
  98. IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
  99. OrigContainer = &IP;
  100. if (!ProcessInterval(IP.getRootInterval())) {
  101. llvm_unreachable("ProcessInterval should never fail for first interval!");
  102. }
  103. }
  104. ~IntervalIterator() {
  105. if (IOwnMem)
  106. while (!IntStack.empty()) {
  107. delete operator*();
  108. IntStack.pop_back();
  109. }
  110. }
  111. bool operator==(const IntervalIterator &x) const {
  112. return IntStack == x.IntStack;
  113. }
  114. bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
  115. const Interval *operator*() const { return IntStack.back().first; }
  116. Interval *operator*() { return IntStack.back().first; }
  117. const Interval *operator->() const { return operator*(); }
  118. Interval *operator->() { return operator*(); }
  119. IntervalIterator &operator++() { // Preincrement
  120. assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
  121. do {
  122. // All of the intervals on the stack have been visited. Try visiting
  123. // their successors now.
  124. Interval::succ_iterator &SuccIt = IntStack.back().second,
  125. EndIt = succ_end(IntStack.back().first);
  126. while (SuccIt != EndIt) { // Loop over all interval succs
  127. bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
  128. ++SuccIt; // Increment iterator
  129. if (Done) return *this; // Found a new interval! Use it!
  130. }
  131. // Free interval memory... if necessary
  132. if (IOwnMem) delete IntStack.back().first;
  133. // We ran out of successors for this interval... pop off the stack
  134. IntStack.pop_back();
  135. } while (!IntStack.empty());
  136. return *this;
  137. }
  138. IntervalIterator operator++(int) { // Postincrement
  139. IntervalIterator tmp = *this;
  140. ++*this;
  141. return tmp;
  142. }
  143. private:
  144. // ProcessInterval - This method is used during the construction of the
  145. // interval graph. It walks through the source graph, recursively creating
  146. // an interval per invocation until the entire graph is covered. This uses
  147. // the ProcessNode method to add all of the nodes to the interval.
  148. //
  149. // This method is templated because it may operate on two different source
  150. // graphs: a basic block graph, or a preexisting interval graph.
  151. //
  152. bool ProcessInterval(NodeTy *Node) {
  153. BasicBlock *Header = getNodeHeader(Node);
  154. if (!Visited.insert(Header).second)
  155. return false;
  156. Interval *Int = new Interval(Header);
  157. // Check all of our successors to see if they are in the interval...
  158. for (typename GT::ChildIteratorType I = GT::child_begin(Node),
  159. E = GT::child_end(Node); I != E; ++I)
  160. ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
  161. IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
  162. return true;
  163. }
  164. // ProcessNode - This method is called by ProcessInterval to add nodes to the
  165. // interval being constructed, and it is also called recursively as it walks
  166. // the source graph. A node is added to the current interval only if all of
  167. // its predecessors are already in the graph. This also takes care of keeping
  168. // the successor set of an interval up to date.
  169. //
  170. // This method is templated because it may operate on two different source
  171. // graphs: a basic block graph, or a preexisting interval graph.
  172. //
  173. void ProcessNode(Interval *Int, NodeTy *Node) {
  174. assert(Int && "Null interval == bad!");
  175. assert(Node && "Null Node == bad!");
  176. BasicBlock *NodeHeader = getNodeHeader(Node);
  177. if (Visited.count(NodeHeader)) { // Node already been visited?
  178. if (Int->contains(NodeHeader)) { // Already in this interval...
  179. return;
  180. } else { // In other interval, add as successor
  181. if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
  182. Int->Successors.push_back(NodeHeader);
  183. }
  184. } else { // Otherwise, not in interval yet
  185. for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
  186. E = IGT::child_end(Node); I != E; ++I) {
  187. if (!Int->contains(*I)) { // If pred not in interval, we can't be
  188. if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
  189. Int->Successors.push_back(NodeHeader);
  190. return; // See you later
  191. }
  192. }
  193. // If we get here, then all of the predecessors of BB are in the interval
  194. // already. In this case, we must add BB to the interval!
  195. addNodeToInterval(Int, Node);
  196. Visited.insert(NodeHeader); // The node has now been visited!
  197. if (Int->isSuccessor(NodeHeader)) {
  198. // If we were in the successor list from before... remove from succ list
  199. Int->Successors.erase(std::remove(Int->Successors.begin(),
  200. Int->Successors.end(), NodeHeader),
  201. Int->Successors.end());
  202. }
  203. // Now that we have discovered that Node is in the interval, perhaps some
  204. // of its successors are as well?
  205. for (typename GT::ChildIteratorType It = GT::child_begin(Node),
  206. End = GT::child_end(Node); It != End; ++It)
  207. ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
  208. }
  209. }
  210. };
  211. typedef IntervalIterator<BasicBlock, Function> function_interval_iterator;
  212. typedef IntervalIterator<Interval, IntervalPartition>
  213. interval_part_interval_iterator;
  214. inline function_interval_iterator intervals_begin(Function *F,
  215. bool DeleteInts = true) {
  216. return function_interval_iterator(F, DeleteInts);
  217. }
  218. inline function_interval_iterator intervals_end(Function *) {
  219. return function_interval_iterator();
  220. }
  221. inline interval_part_interval_iterator
  222. intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
  223. return interval_part_interval_iterator(IP, DeleteIntervals);
  224. }
  225. inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
  226. return interval_part_interval_iterator();
  227. }
  228. } // End llvm namespace
  229. #endif