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

source code of llvm/include/llvm/Analysis/IntervalIterator.h