LLVM 19.0.0git
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
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.
61 return BB;
62}
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.
72 Int->Nodes.push_back(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.
82 // Add all of the nodes in I as new nodes in Int.
83 llvm::append_range(Int->Nodes, I->Nodes);
84}
85
86template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
87 class IGT = GraphTraits<Inverse<NodeTy *>>>
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(&M->front())) {
103 llvm_unreachable("ProcessInterval should never fail for first interval!");
104 }
105 }
106
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(IP.getRootInterval())) {
116 llvm_unreachable("ProcessInterval should never fail for first interval!");
117 }
118 }
119
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*(); }
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(IntStack.back().first);
145 while (SuccIt != EndIt) { // Loop over all interval succs
146 bool Done = ProcessInterval(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(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, getSourceGraphNode(OrigContainer, *I));
186
187 IntStack.push_back(std::make_pair(Int, succ_begin(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(NodeHeader)) { // Node already been visited?
206 if (Int->contains(NodeHeader)) { // Already in this interval...
207 return;
208 } else { // In other interval, add as successor
209 if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
210 Int->Successors.push_back(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(*I)) { // If pred not in interval, we can't be
216 if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
217 Int->Successors.push_back(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!
225 Visited.insert(NodeHeader); // The node has now been visited!
226
227 if (Int->isSuccessor(NodeHeader)) {
228 // If we were in the successor list from before... remove from succ list
229 llvm::erase(Int->Successors, 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, getSourceGraphNode(OrigContainer, *It));
237 }
238 }
239};
240
244
246 bool DeleteInts = true) {
247 return function_interval_iterator(F, DeleteInts);
248}
251}
252
254 intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
255 return interval_part_interval_iterator(IP, DeleteIntervals);
256}
257
260}
261
262} // end namespace llvm
263
264#endif // LLVM_ANALYSIS_INTERVALITERATOR_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool End
Definition: ELF_riscv.cpp:480
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
std::pair< uint64_t, uint64_t > Interval
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Interval * operator->() const
IntervalIterator & operator++()
std::forward_iterator_tag iterator_category
IntervalIterator(IntervalIterator &&x)
IntervalIterator(Function *M, bool OwnMemory)
IntervalIterator(IntervalPartition &IP, bool OwnMemory)
IntervalIterator operator++(int)
const Interval * operator*() const
bool operator!=(const IntervalIterator &x) const
bool operator==(const IntervalIterator &x) const
Interval * getBlockInterval(BasicBlock *BB)
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
BasicBlock * getNodeHeader(BasicBlock *BB)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
function_interval_iterator intervals_end(Function *)
IntervalIterator< Interval, IntervalPartition > interval_part_interval_iterator
@ Done
Definition: Threading.h:61
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:99
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2053
BasicBlock * getSourceGraphNode(Function *, BasicBlock *BB)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2039
function_interval_iterator intervals_begin(Function *F, bool DeleteInts=true)
void addNodeToInterval(Interval *Int, BasicBlock *BB)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
IntervalIterator< BasicBlock, Function > function_interval_iterator
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858