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: Provide an interval iterator that codifies the internals of
11 // IntervalPartition. Inside, it would have a stack of Interval*'s, and would
12 // walk the interval partition in depth first order. IntervalPartition would
13 // then be a client of this iterator. The iterator should work on Method*,
14 // const Method*, IntervalPartition*, and const IntervalPartition*.
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_INTERVALS_H
19 #define LLVM_INTERVALS_H
30 class IntervalPartition;
32 //===----------------------------------------------------------------------===//
34 // Interval Class - An Interval is a set of nodes defined such that every node
35 // in the interval has all of its predecessors in the interval (except for the
39 friend class IntervalPartition;
41 // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
42 // interval. Also, any loops in this interval must go through the HeaderNode.
44 BasicBlock *HeaderNode;
46 typedef vector<BasicBlock*>::iterator succ_iterator;
47 typedef vector<BasicBlock*>::iterator pred_iterator;
48 typedef vector<BasicBlock*>::iterator node_iterator;
50 inline BasicBlock *getHeaderNode() const { return HeaderNode; }
52 // Nodes - The basic blocks in this interval.
54 vector<BasicBlock*> Nodes;
56 // Successors - List of BasicBlocks that are reachable directly from nodes in
57 // this interval, but are not in the interval themselves.
58 // These nodes neccesarily must be header nodes for other intervals.
60 vector<BasicBlock*> Successors;
62 // Predecessors - List of BasicBlocks that have this Interval's header block
63 // as one of their successors.
65 vector<BasicBlock*> Predecessors;
67 // contains - Find out if a basic block is in this interval
68 inline bool contains(BasicBlock *BB) const {
69 return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
72 // isSuccessor - find out if a basic block is a successor of this Interval
73 inline bool isSuccessor(BasicBlock *BB) const {
74 return find(Successors.begin(), Successors.end(), BB) != Successors.end();
77 // isLoop - Find out if there is a back edge in this interval...
80 private: // Only accessable by IntervalPartition class
81 inline Interval(BasicBlock *Header) : HeaderNode(Header) {
82 Nodes.push_back(Header);
87 // succ_begin/succ_end - define global functions so that Intervals may be used
88 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
90 inline Interval::succ_iterator succ_begin(Interval *I) {
91 return I->Successors.begin();
93 inline Interval::succ_iterator succ_end(Interval *I) {
94 return I->Successors.end();
97 // pred_begin/pred_end - define global functions so that Intervals may be used
98 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
100 inline Interval::pred_iterator pred_begin(Interval *I) {
101 return I->Predecessors.begin();
103 inline Interval::pred_iterator pred_end(Interval *I) {
104 return I->Predecessors.end();
108 //===----------------------------------------------------------------------===//
110 // IntervalPartition - This class builds and holds an "interval partition" for
111 // a method. This partition divides the control flow graph into a set of
112 // maximal intervals, as defined with the properties above. Intuitively, a
113 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
114 // nodes following it.
116 class IntervalPartition {
117 typedef map<BasicBlock*, Interval*> IntervalMapTy;
118 IntervalMapTy IntervalMap;
120 typedef vector<Interval*> IntervalListTy;
121 IntervalListTy IntervalList;
122 Interval *RootInterval;
125 typedef IntervalListTy::iterator iterator;
128 // IntervalPartition ctor - Build the partition for the specified method
129 IntervalPartition(Method *M);
131 // IntervalPartition ctor - Build a reduced interval partition from an
132 // existing interval graph. This takes an additional boolean parameter to
133 // distinguish it from a copy constructor. Always pass in false for now.
135 IntervalPartition(IntervalPartition &I, bool);
137 // Destructor - Free memory
138 ~IntervalPartition();
140 // getRootInterval() - Return the root interval that contains the starting
141 // block of the method.
142 inline Interval *getRootInterval() { return RootInterval; }
144 // isDegeneratePartition() - Returns true if the interval partition contains
145 // a single interval, and thus cannot be simplified anymore.
146 bool isDegeneratePartition() { return size() == 1; }
148 // TODO: isIrreducible - look for triangle graph.
150 // getBlockInterval - Return the interval that a basic block exists in.
151 inline Interval *getBlockInterval(BasicBlock *BB) {
152 IntervalMapTy::iterator I = IntervalMap.find(BB);
153 return I != IntervalMap.end() ? I->second : 0;
156 // Iterators to iterate over all of the intervals in the method
157 inline iterator begin() { return IntervalList.begin(); }
158 inline iterator end() { return IntervalList.end(); }
159 inline unsigned size() { return IntervalList.size(); }
162 // ProcessInterval - This method is used during the construction of the
163 // interval graph. It walks through the source graph, recursively creating
164 // an interval per invokation until the entire graph is covered. This uses
165 // the ProcessNode method to add all of the nodes to the interval.
167 // This method is templated because it may operate on two different source
168 // graphs: a basic block graph, or a preexisting interval graph.
170 template<class NodeTy, class OrigContainer>
171 void ProcessInterval(NodeTy *Node, OrigContainer *OC);
173 // ProcessNode - This method is called by ProcessInterval to add nodes to the
174 // interval being constructed, and it is also called recursively as it walks
175 // the source graph. A node is added to the current interval only if all of
176 // its predecessors are already in the graph. This also takes care of keeping
177 // the successor set of an interval up to date.
179 // This method is templated because it may operate on two different source
180 // graphs: a basic block graph, or a preexisting interval graph.
182 template<class NodeTy, class OrigContainer>
183 void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
185 // addNodeToInterval - This method exists to assist the generic ProcessNode
186 // with the task of adding a node to the new interval, depending on the
187 // type of the source node. In the case of a CFG source graph (BasicBlock
188 // case), the BasicBlock itself is added to the interval. In the case of
189 // an IntervalPartition source graph (Interval case), all of the member
190 // BasicBlocks are added to the interval.
192 inline void addNodeToInterval(Interval *Int, Interval *I);
193 inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
195 // updatePredecessors - Interval generation only sets the successor fields of
196 // the interval data structures. After interval generation is complete,
197 // run through all of the intervals and propogate successor info as
200 void updatePredecessors(Interval *Int);
203 } // End namespace cfg