LLVM  6.0.0svn
IntervalIterator.h
Go to the documentation of this file.
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 
33 #ifndef LLVM_ANALYSIS_INTERVALITERATOR_H
34 #define LLVM_ANALYSIS_INTERVALITERATOR_H
35 
36 #include "llvm/ADT/GraphTraits.h"
37 #include "llvm/Analysis/Interval.h"
39 #include "llvm/IR/CFG.h"
40 #include "llvm/IR/Function.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <iterator>
45 #include <set>
46 #include <utility>
47 #include <vector>
48 
49 namespace llvm {
50 
51 class BasicBlock;
52 
53 // getNodeHeader - Given a source graph node and the source graph, return the
54 // BasicBlock that is the header node. This is the opposite of
55 // getSourceGraphNode.
56 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
57 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
58 
59 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
60 // source graph node that corresponds to the BasicBlock. This is the opposite
61 // of getNodeHeader.
63  return BB;
64 }
66  return IP->getBlockInterval(BB);
67 }
68 
69 // addNodeToInterval - This method exists to assist the generic ProcessNode
70 // with the task of adding a node to the new interval, depending on the
71 // type of the source node. In the case of a CFG source graph (BasicBlock
72 // case), the BasicBlock itself is added to the interval.
74  Int->Nodes.push_back(BB);
75 }
76 
77 // addNodeToInterval - This method exists to assist the generic ProcessNode
78 // with the task of adding a node to the new interval, depending on the
79 // type of the source node. In the case of a CFG source graph (BasicBlock
80 // case), the BasicBlock itself is added to the interval. In the case of
81 // an IntervalPartition source graph (Interval case), all of the member
82 // BasicBlocks are added to the interval.
84  // Add all of the nodes in I as new nodes in Int.
85  Int->Nodes.insert(Int->Nodes.end(), I->Nodes.begin(), I->Nodes.end());
86 }
87 
88 template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
89  class IGT = GraphTraits<Inverse<NodeTy *>>>
91  std::vector<std::pair<Interval *, typename Interval::succ_iterator>> IntStack;
92  std::set<BasicBlock *> Visited;
93  OrigContainer_t *OrigContainer;
94  bool IOwnMem; // If True, delete intervals when done with them
95  // See file header for conditions of use
96 
97 public:
98  using iterator_category = std::forward_iterator_tag;
99 
100  IntervalIterator() = default; // End iterator, empty stack
101 
102  IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
103  OrigContainer = M;
104  if (!ProcessInterval(&M->front())) {
105  llvm_unreachable("ProcessInterval should never fail for first interval!");
106  }
107  }
108 
110  : IntStack(std::move(x.IntStack)), Visited(std::move(x.Visited)),
111  OrigContainer(x.OrigContainer), IOwnMem(x.IOwnMem) {
112  x.IOwnMem = false;
113  }
114 
115  IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
116  OrigContainer = &IP;
117  if (!ProcessInterval(IP.getRootInterval())) {
118  llvm_unreachable("ProcessInterval should never fail for first interval!");
119  }
120  }
121 
123  if (IOwnMem)
124  while (!IntStack.empty()) {
125  delete operator*();
126  IntStack.pop_back();
127  }
128  }
129 
130  bool operator==(const IntervalIterator &x) const {
131  return IntStack == x.IntStack;
132  }
133  bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
134 
135  const Interval *operator*() const { return IntStack.back().first; }
136  Interval *operator*() { return IntStack.back().first; }
137  const Interval *operator->() const { return operator*(); }
138  Interval *operator->() { return operator*(); }
139 
140  IntervalIterator &operator++() { // Preincrement
141  assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
142  do {
143  // All of the intervals on the stack have been visited. Try visiting
144  // their successors now.
145  Interval::succ_iterator &SuccIt = IntStack.back().second,
146  EndIt = succ_end(IntStack.back().first);
147  while (SuccIt != EndIt) { // Loop over all interval succs
148  bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
149  ++SuccIt; // Increment iterator
150  if (Done) return *this; // Found a new interval! Use it!
151  }
152 
153  // Free interval memory... if necessary
154  if (IOwnMem) delete IntStack.back().first;
155 
156  // We ran out of successors for this interval... pop off the stack
157  IntStack.pop_back();
158  } while (!IntStack.empty());
159 
160  return *this;
161  }
162 
163  IntervalIterator operator++(int) { // Postincrement
164  IntervalIterator tmp = *this;
165  ++*this;
166  return tmp;
167  }
168 
169 private:
170  // ProcessInterval - This method is used during the construction of the
171  // interval graph. It walks through the source graph, recursively creating
172  // an interval per invocation until the entire graph is covered. This uses
173  // the ProcessNode method to add all of the nodes to the interval.
174  //
175  // This method is templated because it may operate on two different source
176  // graphs: a basic block graph, or a preexisting interval graph.
177  bool ProcessInterval(NodeTy *Node) {
178  BasicBlock *Header = getNodeHeader(Node);
179  if (!Visited.insert(Header).second)
180  return false;
181 
182  Interval *Int = new Interval(Header);
183 
184  // Check all of our successors to see if they are in the interval...
185  for (typename GT::ChildIteratorType I = GT::child_begin(Node),
186  E = GT::child_end(Node); I != E; ++I)
187  ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
188 
189  IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
190  return true;
191  }
192 
193  // ProcessNode - This method is called by ProcessInterval to add nodes to the
194  // interval being constructed, and it is also called recursively as it walks
195  // the source graph. A node is added to the current interval only if all of
196  // its predecessors are already in the graph. This also takes care of keeping
197  // the successor set of an interval up to date.
198  //
199  // This method is templated because it may operate on two different source
200  // graphs: a basic block graph, or a preexisting interval graph.
201  void ProcessNode(Interval *Int, NodeTy *Node) {
202  assert(Int && "Null interval == bad!");
203  assert(Node && "Null Node == bad!");
204 
205  BasicBlock *NodeHeader = getNodeHeader(Node);
206 
207  if (Visited.count(NodeHeader)) { // Node already been visited?
208  if (Int->contains(NodeHeader)) { // Already in this interval...
209  return;
210  } else { // In other interval, add as successor
211  if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
212  Int->Successors.push_back(NodeHeader);
213  }
214  } else { // Otherwise, not in interval yet
215  for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
216  E = IGT::child_end(Node); I != E; ++I) {
217  if (!Int->contains(*I)) { // If pred not in interval, we can't be
218  if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
219  Int->Successors.push_back(NodeHeader);
220  return; // See you later
221  }
222  }
223 
224  // If we get here, then all of the predecessors of BB are in the interval
225  // already. In this case, we must add BB to the interval!
226  addNodeToInterval(Int, Node);
227  Visited.insert(NodeHeader); // The node has now been visited!
228 
229  if (Int->isSuccessor(NodeHeader)) {
230  // If we were in the successor list from before... remove from succ list
231  Int->Successors.erase(std::remove(Int->Successors.begin(),
232  Int->Successors.end(), NodeHeader),
233  Int->Successors.end());
234  }
235 
236  // Now that we have discovered that Node is in the interval, perhaps some
237  // of its successors are as well?
238  for (typename GT::ChildIteratorType It = GT::child_begin(Node),
239  End = GT::child_end(Node); It != End; ++It)
240  ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
241  }
242  }
243 };
244 
248 
250  bool DeleteInts = true) {
251  return function_interval_iterator(F, DeleteInts);
252 }
255 }
256 
258  intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
259  return interval_part_interval_iterator(IP, DeleteIntervals);
260 }
261 
264 }
265 
266 } // end namespace llvm
267 
268 #endif // LLVM_ANALYSIS_INTERVALITERATOR_H
const Interval * operator*() const
function_interval_iterator intervals_end(Function *)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:37
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
BasicBlock * getNodeHeader(BasicBlock *BB)
F(f)
std::vector< BasicBlock * >::iterator succ_iterator
Definition: Interval.h:44
Definition: BitVector.h:920
std::pair< uint32_t, uint32_t > Interval
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
bool contains(BasicBlock *BB) const
contains - Find out if a basic block is in this interval
Definition: Interval.h:67
function_interval_iterator intervals_begin(Function *F, bool DeleteInts=true)
void addNodeToInterval(Interval *Int, BasicBlock *BB)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
BasicBlock * getHeaderNode() const
Definition: Interval.h:52
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isSuccessor(BasicBlock *BB) const
isSuccessor - find out if a basic block is a successor of this Interval
Definition: Interval.h:77
static const unsigned End
std::vector< BasicBlock * > Nodes
Nodes - The basic blocks in this interval.
Definition: Interval.h:55
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
IntervalIterator< Interval, IntervalPartition > interval_part_interval_iterator
BasicBlock * getSourceGraphNode(Function *, BasicBlock *BB)
IntervalIterator< BasicBlock, Function > function_interval_iterator
const Interval * operator->() const
IntervalIterator(Function *M, bool OwnMemory)
std::vector< BasicBlock * > Successors
Successors - List of BasicBlocks that are reachable directly from nodes in this interval, but are not in the interval themselves.
Definition: Interval.h:60
bool operator!=(const IntervalIterator &x) const
std::forward_iterator_tag iterator_category
#define I(x, y, z)
Definition: MD5.cpp:58
bool operator==(const IntervalIterator &x) const
IntervalIterator operator++(int)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
Definition: Function.h:595
IntervalIterator(IntervalIterator &&x)
IntervalIterator(IntervalPartition &IP, bool OwnMemory)
IntervalIterator & operator++()
Interval * getBlockInterval(BasicBlock *BB)