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