LLVM  6.0.0svn
Interval.h
Go to the documentation of this file.
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  inline Interval(BasicBlock *Header) : HeaderNode(Header) {
49  Nodes.push_back(Header);
50  }
51 
52  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  for (BasicBlock *Node : Nodes)
69  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  for (BasicBlock *Successor : Successors)
79  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 ///
104  return I->Successors.begin();
105 }
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 ///
114  return I->Predecessors.begin();
115 }
117  return I->Predecessors.end();
118 }
119 
120 template <> struct GraphTraits<Interval*> {
121  using NodeRef = Interval *;
123 
124  static NodeRef getEntryNode(Interval *I) { return I; }
125 
126  /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
129 };
130 
131 template <> struct GraphTraits<Inverse<Interval*>> {
132  using NodeRef = Interval *;
134 
138 };
139 
140 } // end namespace llvm
141 
142 #endif // LLVM_ANALYSIS_INTERVAL_H
Interval::pred_iterator ChildIteratorType
Definition: Interval.h:133
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isLoop() const
isLoop - Find out if there is a back edge in this interval...
Definition: Interval.cpp:27
Various leaf nodes.
Definition: ISDOpcodes.h:60
std::vector< BasicBlock * >::iterator pred_iterator
Definition: Interval.h:45
bool operator==(const Interval &I) const
Equality operator.
Definition: Interval.h:89
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:37
static ChildIteratorType child_begin(NodeRef N)
nodes_iterator/begin/end - Allow iteration over all nodes in the graph
Definition: Interval.h:127
std::vector< BasicBlock * >::iterator node_iterator
Definition: Interval.h:46
static NodeRef getEntryNode(Inverse< Interval *> G)
Definition: Interval.h:135
std::vector< BasicBlock * >::iterator succ_iterator
Definition: Interval.h:44
static ChildIteratorType child_end(NodeRef N)
Definition: Interval.h:128
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
static ChildIteratorType child_begin(NodeRef N)
Definition: Interval.h:136
bool contains(BasicBlock *BB) const
contains - Find out if a basic block is in this interval
Definition: Interval.h:67
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
BasicBlock * getHeaderNode() const
Definition: Interval.h:52
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
bool isSuccessor(BasicBlock *BB) const
isSuccessor - find out if a basic block is a successor of this Interval
Definition: Interval.h:77
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
std::vector< BasicBlock * > Nodes
Nodes - The basic blocks in this interval.
Definition: Interval.h:55
const GraphType & Graph
Definition: GraphTraits.h:77
static NodeRef getEntryNode(Interval *I)
Definition: Interval.h:124
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
std::vector< BasicBlock * > Predecessors
Predecessors - List of BasicBlocks that have this Interval&#39;s header block as one of their successors...
Definition: Interval.h:64
std::vector< BasicBlock * > Successors
Successors - List of BasicBlocks that are reachable directly from nodes in this interval, but are not in the interval themselves.
Definition: Interval.h:60
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Interval::succ_iterator ChildIteratorType
Definition: Interval.h:122
void print(raw_ostream &O) const
print - Show contents in human readable format...
Definition: Interval.cpp:37
static ChildIteratorType child_end(NodeRef N)
Definition: Interval.h:137
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
Interval(BasicBlock *Header)
Definition: Interval.h:48