Line data Source code
1 : //===- llvm/Analysis/Interval.h - Interval Class 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 contains the declaration of the Interval class, which
11 : // represents a set of CFG nodes and is a portion of an interval partition.
12 : //
13 : // Intervals have some interesting and useful properties, including the
14 : // following:
15 : // 1. The header node of an interval dominates all of the elements of the
16 : // interval
17 : //
18 : //===----------------------------------------------------------------------===//
19 :
20 : #ifndef LLVM_ANALYSIS_INTERVAL_H
21 : #define LLVM_ANALYSIS_INTERVAL_H
22 :
23 : #include "llvm/ADT/GraphTraits.h"
24 : #include <vector>
25 :
26 : namespace llvm {
27 :
28 : class BasicBlock;
29 : class raw_ostream;
30 :
31 : //===----------------------------------------------------------------------===//
32 : //
33 : /// Interval Class - An Interval is a set of nodes defined such that every node
34 : /// in the interval has all of its predecessors in the interval (except for the
35 : /// header)
36 : ///
37 : class Interval {
38 : /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
39 : /// interval. Also, any loops in this interval must go through the HeaderNode.
40 : ///
41 : BasicBlock *HeaderNode;
42 :
43 : public:
44 : using succ_iterator = std::vector<BasicBlock*>::iterator;
45 : using pred_iterator = std::vector<BasicBlock*>::iterator;
46 : using node_iterator = std::vector<BasicBlock*>::iterator;
47 :
48 0 : inline Interval(BasicBlock *Header) : HeaderNode(Header) {
49 0 : Nodes.push_back(Header);
50 : }
51 :
52 0 : inline BasicBlock *getHeaderNode() const { return HeaderNode; }
53 :
54 : /// Nodes - The basic blocks in this interval.
55 : std::vector<BasicBlock*> Nodes;
56 :
57 : /// Successors - List of BasicBlocks that are reachable directly from nodes in
58 : /// this interval, but are not in the interval themselves.
59 : /// These nodes necessarily must be header nodes for other intervals.
60 : std::vector<BasicBlock*> Successors;
61 :
62 : /// Predecessors - List of BasicBlocks that have this Interval's header block
63 : /// as one of their successors.
64 : std::vector<BasicBlock*> Predecessors;
65 :
66 : /// contains - Find out if a basic block is in this interval
67 : inline bool contains(BasicBlock *BB) const {
68 0 : for (BasicBlock *Node : Nodes)
69 0 : if (Node == BB)
70 : return true;
71 : return false;
72 : // I don't want the dependency on <algorithm>
73 : //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
74 : }
75 :
76 : /// isSuccessor - find out if a basic block is a successor of this Interval
77 : inline bool isSuccessor(BasicBlock *BB) const {
78 0 : for (BasicBlock *Successor : Successors)
79 0 : if (Successor == BB)
80 : return true;
81 : return false;
82 : // I don't want the dependency on <algorithm>
83 : //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
84 : }
85 :
86 : /// Equality operator. It is only valid to compare two intervals from the
87 : /// same partition, because of this, all we have to check is the header node
88 : /// for equality.
89 : inline bool operator==(const Interval &I) const {
90 : return HeaderNode == I.HeaderNode;
91 : }
92 :
93 : /// isLoop - Find out if there is a back edge in this interval...
94 : bool isLoop() const;
95 :
96 : /// print - Show contents in human readable format...
97 : void print(raw_ostream &O) const;
98 : };
99 :
100 : /// succ_begin/succ_end - define methods so that Intervals may be used
101 : /// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
102 : ///
103 : inline Interval::succ_iterator succ_begin(Interval *I) {
104 : return I->Successors.begin();
105 : }
106 : inline Interval::succ_iterator succ_end(Interval *I) {
107 : return I->Successors.end();
108 : }
109 :
110 : /// pred_begin/pred_end - define methods so that Intervals may be used
111 : /// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
112 : ///
113 : inline Interval::pred_iterator pred_begin(Interval *I) {
114 : return I->Predecessors.begin();
115 : }
116 : inline Interval::pred_iterator pred_end(Interval *I) {
117 : return I->Predecessors.end();
118 : }
119 :
120 : template <> struct GraphTraits<Interval*> {
121 : using NodeRef = Interval *;
122 : using ChildIteratorType = Interval::succ_iterator;
123 :
124 : static NodeRef getEntryNode(Interval *I) { return I; }
125 :
126 : /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
127 : static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
128 : static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
129 : };
130 :
131 : template <> struct GraphTraits<Inverse<Interval*>> {
132 : using NodeRef = Interval *;
133 : using ChildIteratorType = Interval::pred_iterator;
134 :
135 : static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; }
136 : static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
137 : static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
138 : };
139 :
140 : } // end namespace llvm
141 :
142 : #endif // LLVM_ANALYSIS_INTERVAL_H
|
