Line data Source code
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"
38 : #include "llvm/Analysis/IntervalPartition.h"
39 : #include "llvm/IR/CFG.h"
40 : #include "llvm/IR/Function.h"
41 : #include "llvm/Support/ErrorHandling.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 0 : 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.
62 0 : inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
63 0 : return BB;
64 : }
65 : inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
66 0 : 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.
73 : inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
74 0 : 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.
83 0 : inline void addNodeToInterval(Interval *Int, Interval *I) {
84 : // Add all of the nodes in I as new nodes in Int.
85 0 : Int->Nodes.insert(Int->Nodes.end(), I->Nodes.begin(), I->Nodes.end());
86 0 : }
87 :
88 : template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
89 : class IGT = GraphTraits<Inverse<NodeTy *>>>
90 : class IntervalIterator {
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 0 : IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
103 0 : OrigContainer = M;
104 0 : if (!ProcessInterval(&M->front())) {
105 0 : llvm_unreachable("ProcessInterval should never fail for first interval!");
106 : }
107 0 : }
108 :
109 : IntervalIterator(IntervalIterator &&x)
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 0 : IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
116 0 : OrigContainer = &IP;
117 0 : if (!ProcessInterval(IP.getRootInterval())) {
118 0 : llvm_unreachable("ProcessInterval should never fail for first interval!");
119 : }
120 0 : }
121 :
122 0 : ~IntervalIterator() {
123 0 : if (IOwnMem)
124 0 : while (!IntStack.empty()) {
125 0 : delete operator*();
126 : IntStack.pop_back();
127 : }
128 0 : }
129 0 :
130 0 : bool operator==(const IntervalIterator &x) const {
131 0 : return IntStack == x.IntStack;
132 0 : }
133 : bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
134 :
135 0 : const Interval *operator*() const { return IntStack.back().first; }
136 0 : Interval *operator*() { return IntStack.back().first; }
137 0 : const Interval *operator->() const { return operator*(); }
138 0 : Interval *operator->() { return operator*(); }
139 0 :
140 : IntervalIterator &operator++() { // Preincrement
141 : assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
142 0 : do {
143 : // All of the intervals on the stack have been visited. Try visiting
144 : // their successors now.
145 0 : 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 0 : if (Done) return *this; // Found a new interval! Use it!
151 : }
152 :
153 : // Free interval memory... if necessary
154 0 : 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 0 : return *this;
161 0 : }
162 0 :
163 : IntervalIterator operator++(int) { // Postincrement
164 0 : IntervalIterator tmp = *this;
165 : ++*this;
166 : return tmp;
167 : }
168 0 :
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 0 : // 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 0 : // 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 0 : Interval *Int = new Interval(Header);
183 0 :
184 0 : // Check all of our successors to see if they are in the interval...
185 : for (typename GT::ChildIteratorType I = GT::child_begin(Node),
186 0 : 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 0 : return true;
191 : }
192 :
193 : // ProcessNode - This method is called by ProcessInterval to add nodes to the
194 0 : // 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 0 : //
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 0 :
205 0 : BasicBlock *NodeHeader = getNodeHeader(Node);
206 0 :
207 : if (Visited.count(NodeHeader)) { // Node already been visited?
208 0 : 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 0 : Int->Successors.push_back(NodeHeader);
213 : }
214 : } else { // Otherwise, not in interval yet
215 : for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
216 0 : 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 0 :
236 0 : // Now that we have discovered that Node is in the interval, perhaps some
237 0 : // 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 0 : ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
241 : }
242 : }
243 : };
244 0 :
245 0 : using function_interval_iterator = IntervalIterator<BasicBlock, Function>;
246 : using interval_part_interval_iterator =
247 0 : IntervalIterator<Interval, IntervalPartition>;
248 0 :
249 : inline function_interval_iterator intervals_begin(Function *F,
250 0 : bool DeleteInts = true) {
251 0 : return function_interval_iterator(F, DeleteInts);
252 0 : }
253 : inline function_interval_iterator intervals_end(Function *) {
254 : return function_interval_iterator();
255 0 : }
256 :
257 : inline interval_part_interval_iterator
258 : intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
259 0 : return interval_part_interval_iterator(IP, DeleteIntervals);
260 0 : }
261 :
262 0 : inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
263 0 : return interval_part_interval_iterator();
264 : }
265 0 :
266 0 : } // end namespace llvm
267 0 :
268 : #endif // LLVM_ANALYSIS_INTERVALITERATOR_H
|
