1 //===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=//
3 // This file contains the declaration of the cfg::IntervalPartition class, which
4 // calculates and represents the interval partition of a method, or a
5 // preexisting interval partition.
7 // In this way, the interval partition may be used to reduce a flow graph down
8 // to its degenerate single node interval partition (unless it is irreducible).
10 // TODO: The IntervalPartition class should take a bool parameter that tells
11 // whether it should add the "tails" of an interval to an interval itself or if
12 // they should be represented as distinct intervals.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_INTERVALS_H
17 #define LLVM_INTERVALS_H
19 #include "llvm/Method.h"
32 class IntervalPartition;
34 //===----------------------------------------------------------------------===//
36 // Interval Class - An Interval is a set of nodes defined such that every node
37 // in the interval has all of its predecessors in the interval (except for the
41 friend class IntervalPartition;
43 // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
44 // interval. Also, any loops in this interval must go through the HeaderNode.
46 BasicBlock *HeaderNode;
48 typedef vector<BasicBlock*>::iterator succ_iterator;
49 typedef vector<BasicBlock*>::iterator pred_iterator;
50 typedef vector<BasicBlock*>::iterator node_iterator;
52 inline BasicBlock *getHeaderNode() const { return HeaderNode; }
54 // Nodes - The basic blocks in this interval.
56 vector<BasicBlock*> Nodes;
58 // Successors - List of BasicBlocks that are reachable directly from nodes in
59 // this interval, but are not in the interval themselves.
60 // These nodes neccesarily must be header nodes for other intervals.
62 vector<BasicBlock*> Successors;
64 // Predecessors - List of BasicBlocks that have this Interval's header block
65 // as one of their successors.
67 vector<BasicBlock*> Predecessors;
69 // contains - Find out if a basic block is in this interval
70 inline bool contains(BasicBlock *BB) const {
71 return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
74 // isSuccessor - find out if a basic block is a successor of this Interval
75 inline bool isSuccessor(BasicBlock *BB) const {
76 return find(Successors.begin(), Successors.end(), BB) != Successors.end();
79 // isLoop - Find out if there is a back edge in this interval...
82 //private: // Only accessable by IntervalPartition class
83 inline Interval(BasicBlock *Header) : HeaderNode(Header) {
84 Nodes.push_back(Header);
89 // succ_begin/succ_end - define global functions so that Intervals may be used
90 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
92 inline Interval::succ_iterator succ_begin(Interval *I) {
93 return I->Successors.begin();
95 inline Interval::succ_iterator succ_end(Interval *I) {
96 return I->Successors.end();
99 // pred_begin/pred_end - define global functions so that Intervals may be used
100 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
102 inline Interval::pred_iterator pred_begin(Interval *I) {
103 return I->Predecessors.begin();
105 inline Interval::pred_iterator pred_end(Interval *I) {
106 return I->Predecessors.end();
110 //===----------------------------------------------------------------------===//
113 // TODO: Provide an interval iterator that codifies the internals of
114 // IntervalPartition. Inside, it would have a stack of Interval*'s, and would
115 // walk the interval partition in depth first order. IntervalPartition would
116 // then be a client of this iterator. The iterator should work on Method*,
117 // const Method*, IntervalPartition*, and const IntervalPartition*.
120 template<class NodeTy, class OrigContainer_t>
121 class IntervalIterator {
122 stack<pair<Interval, typename Interval::succ_iterator> > IntStack;
123 set<BasicBlock*> Visited;
124 OrigContainer_t *OrigContainer;
126 typedef BasicBlock* _BB;
128 typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
129 typedef forward_iterator_tag iterator_category;
131 IntervalIterator() {} // End iterator, empty stack
132 IntervalIterator(Method *M) {
134 if (!ProcessInterval(M->getBasicBlocks().front())) {
135 assert(0 && "ProcessInterval should never fail for first interval!");
139 inline bool operator==(const _Self& x) const { return IntStack == x.IntStack; }
140 inline bool operator!=(const _Self& x) const { return !operator==(x); }
142 inline Interval &operator*() const { return IntStack.top(); }
143 inline Interval *operator->() const { return &(operator*()); }
145 inline _Self& operator++() { // Preincrement
147 // All of the intervals on the stack have been visited. Try visiting their
149 Interval &CurInt = IntStack.top().first;
150 Interval::iterator &SuccIt = IntStack.top().second,End = succ_end(&CurInt);
152 for (; SuccIt != End; ++SuccIt) // Loop over all interval successors
153 if (ProcessInterval(*SuccIt)) // Found a new interval!
154 return *this; // Use it!
156 // We ran out of successors for this interval... pop off the stack
158 } while (!IntStack.empty());
162 inline _Self operator++(int) { // Postincrement
163 _Self tmp = *this; ++*this; return tmp;
167 // ProcessInterval - This method is used during the construction of the
168 // interval graph. It walks through the source graph, recursively creating
169 // an interval per invokation until the entire graph is covered. This uses
170 // the ProcessNode method to add all of the nodes to the interval.
172 // This method is templated because it may operate on two different source
173 // graphs: a basic block graph, or a preexisting interval graph.
175 bool ProcessInterval(NodeTy *Node) {
176 BasicBlock *Header = getNodeHeader(Node);
177 if (Visited.count(Header)) return false;
179 Interval Int(Header);
180 Visited.insert(Header); // The header has now been visited!
182 // Check all of our successors to see if they are in the interval...
183 for (typename NodeTy::succ_iterator I = succ_begin(Node), E = succ_end(Node);
185 ProcessNode(&Int, getSourceGraphNode(OrigContainer, *I));
187 IntStack.push(make_pair(Int, succ_begin(&Int)));
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.
197 // This method is templated because it may operate on two different source
198 // graphs: a basic block graph, or a preexisting interval graph.
200 void ProcessNode(Interval *Int, NodeTy *Node) {
201 assert(Int && "Null interval == bad!");
202 assert(Node && "Null Node == bad!");
204 BasicBlock *NodeHeader = getNodeHeader(Node);
206 if (Visited.count(NodeHeader)) { // Node already been visited?
207 if (Int->contains(NodeHeader)) { // Already in this interval...
209 } else { // In another interval, add as successor
210 if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
211 Int->Successors.push_back(NodeHeader);
213 } else { // Otherwise, not in interval yet
214 for (typename NodeTy::pred_iterator I = pred_begin(Node),
215 E = pred_end(Node); I != E; ++I) {
216 if (!Int->contains(*I)) { // If pred not in interval, we can't be
217 if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
218 Int->Successors.push_back(NodeHeader);
219 return; // See you later
223 // If we get here, then all of the predecessors of BB are in the interval
224 // already. In this case, we must add BB to the interval!
225 addNodeToInterval(Int, Node);
226 Visited.insert(NodeHeader); // The node has now been visited!
228 if (Int->isSuccessor(NodeHeader)) {
229 // If we were in the successor list from before... remove from succ list
230 Int->Successors.erase(remove(Int->Successors.begin(),
231 Int->Successors.end(), NodeHeader),
232 Int->Successors.end());
235 // Now that we have discovered that Node is in the interval, perhaps some
236 // of its successors are as well?
237 for (typename NodeTy::succ_iterator It = succ_begin(Node),
238 End = succ_end(Node); It != End; ++It)
239 ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
245 //===----------------------------------------------------------------------===//
247 // IntervalPartition - This class builds and holds an "interval partition" for
248 // a method. This partition divides the control flow graph into a set of
249 // maximal intervals, as defined with the properties above. Intuitively, a
250 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
251 // nodes following it.
253 class IntervalPartition {
254 typedef map<BasicBlock*, Interval*> IntervalMapTy;
255 IntervalMapTy IntervalMap;
257 typedef vector<Interval*> IntervalListTy;
258 IntervalListTy IntervalList;
259 Interval *RootInterval;
262 typedef IntervalListTy::iterator iterator;
265 // IntervalPartition ctor - Build the partition for the specified method
266 IntervalPartition(Method *M);
268 // IntervalPartition ctor - Build a reduced interval partition from an
269 // existing interval graph. This takes an additional boolean parameter to
270 // distinguish it from a copy constructor. Always pass in false for now.
272 IntervalPartition(IntervalPartition &I, bool);
274 // Destructor - Free memory
275 ~IntervalPartition();
277 // getRootInterval() - Return the root interval that contains the starting
278 // block of the method.
279 inline Interval *getRootInterval() { return RootInterval; }
281 // isDegeneratePartition() - Returns true if the interval partition contains
282 // a single interval, and thus cannot be simplified anymore.
283 bool isDegeneratePartition() { return size() == 1; }
285 // TODO: isIrreducible - look for triangle graph.
287 // getBlockInterval - Return the interval that a basic block exists in.
288 inline Interval *getBlockInterval(BasicBlock *BB) {
289 IntervalMapTy::iterator I = IntervalMap.find(BB);
290 return I != IntervalMap.end() ? I->second : 0;
293 // Iterators to iterate over all of the intervals in the method
294 inline iterator begin() { return IntervalList.begin(); }
295 inline iterator end() { return IntervalList.end(); }
296 inline unsigned size() { return IntervalList.size(); }
299 // ProcessInterval - This method is used during the construction of the
300 // interval graph. It walks through the source graph, recursively creating
301 // an interval per invokation until the entire graph is covered. This uses
302 // the ProcessNode method to add all of the nodes to the interval.
304 // This method is templated because it may operate on two different source
305 // graphs: a basic block graph, or a preexisting interval graph.
307 template<class NodeTy, class OrigContainer>
308 void ProcessInterval(NodeTy *Node, OrigContainer *OC);
310 // ProcessNode - This method is called by ProcessInterval to add nodes to the
311 // interval being constructed, and it is also called recursively as it walks
312 // the source graph. A node is added to the current interval only if all of
313 // its predecessors are already in the graph. This also takes care of keeping
314 // the successor set of an interval up to date.
316 // This method is templated because it may operate on two different source
317 // graphs: a basic block graph, or a preexisting interval graph.
319 template<class NodeTy, class OrigContainer>
320 void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
322 // addNodeToInterval - This method exists to assist the generic ProcessNode
323 // with the task of adding a node to the new interval, depending on the
324 // type of the source node. In the case of a CFG source graph (BasicBlock
325 // case), the BasicBlock itself is added to the interval. In the case of
326 // an IntervalPartition source graph (Interval case), all of the member
327 // BasicBlocks are added to the interval.
329 inline void addNodeToInterval(Interval *Int, Interval *I);
330 inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
332 // updatePredecessors - Interval generation only sets the successor fields of
333 // the interval data structures. After interval generation is complete,
334 // run through all of the intervals and propogate successor info as
337 void updatePredecessors(Interval *Int);
342 // getNodeHeader - Given a source graph node and the source graph, return the
343 // BasicBlock that is the header node. This is the opposite of
344 // getSourceGraphNode.
346 inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
347 inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
349 // getSourceGraphNode - Given a BasicBlock and the source graph, return the
350 // source graph node that corresponds to the BasicBlock. This is the opposite
353 inline BasicBlock *getSourceGraphNode(Method *, BasicBlock *BB) {
356 inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
357 return IP->getBlockInterval(BB);
360 // addNodeToInterval - This method exists to assist the generic ProcessNode
361 // with the task of adding a node to the new interval, depending on the
362 // type of the source node. In the case of a CFG source graph (BasicBlock
363 // case), the BasicBlock itself is added to the interval.
365 inline void addNodeToInterval(Interval *Int, BasicBlock *BB){
366 Int->Nodes.push_back(BB);
369 // addNodeToInterval - This method exists to assist the generic ProcessNode
370 // with the task of adding a node to the new interval, depending on the
371 // type of the source node. In the case of a CFG source graph (BasicBlock
372 // case), the BasicBlock itself is added to the interval. In the case of
373 // an IntervalPartition source graph (Interval case), all of the member
374 // BasicBlocks are added to the interval.
376 inline void addNodeToInterval(Interval *Int, Interval *I) {
377 // Add all of the nodes in I as new nodes in Int.
378 copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
384 typedef IntervalIterator<BasicBlock, Method> method_interval_iterator;
387 method_interval_iterator intervals_begin(Method *M) {
388 return method_interval_iterator(M);
390 method_interval_iterator intervals_end(Method *M) {
391 return method_interval_iterator();
394 } // End namespace cfg