Interval.h revision 564de7d79bd0e7c3b42988b112f325f15cd575ea 
1//===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=//
2//
3// This file contains the declaration of the cfg::IntervalPartition class, which
4// calculates and represent the interval partition of a method.
5//
6//===----------------------------------------------------------------------===//
7
8#ifndef LLVM_INTERVALS_H
9#define LLVM_INTERVALS_H
10
11#include <vector>
12#include <map>
13#include <algorithm>
14
15class Method;
16class BasicBlock;
17
18namespace cfg {
19
20class IntervalPartition;
21
22// Interval Class - An Interval is a set of nodes defined such that every node
23// in the interval has all of its predecessors in the interval (except for the
24// header)
25class Interval {
26  friend class IntervalPartition;
27public:
28  typedef vector<BasicBlock*>::iterator succ_iterator;
29  typedef vector<BasicBlock*>::iterator pred_iterator;
30  typedef vector<BasicBlock*>::iterator node_iterator;
31
32  // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
33  // interval.  Also, any loops in this interval must go through the HeaderNode.
34  //
35  BasicBlock *HeaderNode;
36
37  // Nodes - The basic blocks in this interval.
38  //
39  vector<BasicBlock*> Nodes;
40
41  // Successors - List of BasicBlocks that are reachable directly from nodes in
42  // this interval, but are not in the interval themselves.
43  // These nodes neccesarily must be header nodes for other intervals.
44  //
45  vector<BasicBlock*> Successors;
46
47  // Predecessors - List of BasicBlocks that have this Interval's header block
48  // as one of their successors.
49  //
50  vector<BasicBlock*> Predecessors;
51
52  inline bool contains(BasicBlock *BB) {
53    return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
54  }
55
56  inline bool isSuccessor(BasicBlock *BB) {
57    return find(Successors.begin(), Successors.end(), BB) != Successors.end();
58  }
59
60private:           // Only accessable by IntervalPartition class
61  inline Interval(BasicBlock *Header) : HeaderNode(Header) {
62    Nodes.push_back(Header);
63  }
64};
65
66
67// IntervalPartition - This class builds and holds an "interval partition" for
68// a method.  This partition divides the control flow graph into a set of
69// maximal intervals, as defined with the properties above.  Intuitively, a
70// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
71// nodes following it.
72//
73class IntervalPartition {
74  typedef map<BasicBlock*, Interval*> IntervalMapTy;
75  IntervalMapTy IntervalMap;
76
77  typedef vector<Interval*> IntervalListTy;
78  IntervalListTy IntervalList;
79  Interval *RootInterval;
80
81public:
82  typedef IntervalListTy::iterator iterator;
83
84public:
85  // IntervalPartition ctor - Build the partition for the specified method
86  IntervalPartition(Method *M);
87
88  // getRootInterval() - Return the root interval that contains the starting
89  // block of the method
90  inline Interval *getRootInterval() { return RootInterval; }
91
92  inline Interval *getBlockInterval(BasicBlock *BB) {
93    IntervalMapTy::iterator I = IntervalMap.find(BB);
94    if (I != IntervalMap.end())
95      return I->second;
96    else
97      return 0;
98  }
99
100  // Iterators to iterate over all of the intervals in the method
101  inline iterator begin() { return IntervalList.begin(); }
102  inline iterator end()   { return IntervalList.end(); }
103
104private:
105  void ProcessInterval(BasicBlock *Header);
106  void ProcessBasicBlock(Interval *I, BasicBlock *BB);
107  void UpdateSuccessors(Interval *Int);
108};
109
110}    // End namespace cfg
111
112#endif
113