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