1 //===- IntervalPartition.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_INTERVAL_PARTITION_H
17 #define LLVM_INTERVAL_PARTITION_H
19 #include "llvm/Analysis/Interval.h"
26 //===----------------------------------------------------------------------===//
28 // IntervalPartition - This class builds and holds an "interval partition" for
29 // a method. This partition divides the control flow graph into a set of
30 // maximal intervals, as defined with the properties above. Intuitively, a
31 // BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
32 // nodes following it.
34 class IntervalPartition {
35 typedef map<BasicBlock*, Interval*> IntervalMapTy;
36 IntervalMapTy IntervalMap;
38 typedef vector<Interval*> IntervalListTy;
39 IntervalListTy IntervalList;
40 Interval *RootInterval;
43 typedef IntervalListTy::iterator iterator;
46 // IntervalPartition ctor - Build the partition for the specified method
47 IntervalPartition(Method *M);
49 // IntervalPartition ctor - Build a reduced interval partition from an
50 // existing interval graph. This takes an additional boolean parameter to
51 // distinguish it from a copy constructor. Always pass in false for now.
53 IntervalPartition(IntervalPartition &I, bool);
55 // Destructor - Free memory
58 // getRootInterval() - Return the root interval that contains the starting
59 // block of the method.
60 inline Interval *getRootInterval() { return RootInterval; }
62 // isDegeneratePartition() - Returns true if the interval partition contains
63 // a single interval, and thus cannot be simplified anymore.
64 bool isDegeneratePartition() { return size() == 1; }
66 // TODO: isIrreducible - look for triangle graph.
68 // getBlockInterval - Return the interval that a basic block exists in.
69 inline Interval *getBlockInterval(BasicBlock *BB) {
70 IntervalMapTy::iterator I = IntervalMap.find(BB);
71 return I != IntervalMap.end() ? I->second : 0;
74 // Iterators to iterate over all of the intervals in the method
75 inline iterator begin() { return IntervalList.begin(); }
76 inline iterator end() { return IntervalList.end(); }
77 inline unsigned size() { return IntervalList.size(); }
80 // ProcessInterval - This method is used during the construction of the
81 // interval graph. It walks through the source graph, recursively creating
82 // an interval per invokation until the entire graph is covered. This uses
83 // the ProcessNode method to add all of the nodes to the interval.
85 // This method is templated because it may operate on two different source
86 // graphs: a basic block graph, or a preexisting interval graph.
88 template<class NodeTy, class OrigContainer>
89 void ProcessInterval(NodeTy *Node, OrigContainer *OC);
91 // ProcessNode - This method is called by ProcessInterval to add nodes to the
92 // interval being constructed, and it is also called recursively as it walks
93 // the source graph. A node is added to the current interval only if all of
94 // its predecessors are already in the graph. This also takes care of keeping
95 // the successor set of an interval up to date.
97 // This method is templated because it may operate on two different source
98 // graphs: a basic block graph, or a preexisting interval graph.
100 template<class NodeTy, class OrigContainer>
101 void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
103 // addNodeToInterval - This method exists to assist the generic ProcessNode
104 // with the task of adding a node to the new interval, depending on the
105 // type of the source node. In the case of a CFG source graph (BasicBlock
106 // case), the BasicBlock itself is added to the interval. In the case of
107 // an IntervalPartition source graph (Interval case), all of the member
108 // BasicBlocks are added to the interval.
110 inline void addNodeToInterval(Interval *Int, Interval *I);
111 inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
113 // updatePredecessors - Interval generation only sets the successor fields of
114 // the interval data structures. After interval generation is complete,
115 // run through all of the intervals and propogate successor info as
118 void updatePredecessors(Interval *Int);
121 } // End namespace cfg