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 | |
46 | namespace llvm { |
47 | |
48 | class BasicBlock; |
49 | class 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. |
54 | inline BasicBlock *(BasicBlock *BB) { return BB; } |
55 | inline BasicBlock *(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. |
60 | inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) { |
61 | return BB; |
62 | } |
63 | inline 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. |
71 | inline 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. |
81 | inline 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 | |
86 | template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>, |
87 | class IGT = GraphTraits<Inverse<NodeTy *>>> |
88 | class 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 | |
95 | public: |
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 | |
167 | private: |
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 * = 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 * = 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 | |
241 | using function_interval_iterator = IntervalIterator<BasicBlock, Function>; |
242 | using interval_part_interval_iterator = |
243 | IntervalIterator<Interval, IntervalPartition>; |
244 | |
245 | inline function_interval_iterator intervals_begin(Function *F, |
246 | bool DeleteInts = true) { |
247 | return function_interval_iterator(F, DeleteInts); |
248 | } |
249 | inline function_interval_iterator intervals_end(Function *) { |
250 | return function_interval_iterator(); |
251 | } |
252 | |
253 | inline interval_part_interval_iterator |
254 | intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) { |
255 | return interval_part_interval_iterator(IP, DeleteIntervals); |
256 | } |
257 | |
258 | inline 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 | |