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