clang: lib/Analysis/IntervalPartition.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
15#include "llvm/ADT/BitVector.h"
16#include "llvm/ADT/STLExtras.h"
17#include
18#include
19#include
20
22
23
25
26
27
28 std::vector<const Node *> Nodes;
29
31};
32
33namespace internal {
36
37
38template
40 const Node *Header) {
41 assert(Header != nullptr);
43 Interval.Nodes.push_back(Header);
44 Partitioned.set(getID(*Header));
45
46
47
48
49
50 std::queue<const Node *> Worklist;
51 llvm::BitVector Workset(Partitioned.size(), false);
52 for (const Node *S : Header->succs())
53 if (S != nullptr)
54 if (auto SID = getID(*S); !Partitioned.test(SID)) {
55
56
57 Worklist.push(S);
58 Workset.set(SID);
59 }
60
61
62
63
64
65
66
67
68 std::vector<const Node *> MaybeSuccessors;
69
70 while (!Worklist.empty()) {
71 const auto *B = Worklist.front();
73 Worklist.pop();
74 Workset.reset(ID);
75
76
77
78 bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {
79 return llvm::is_contained(Interval.Nodes, P);
80 });
81 if (AllInInterval) {
82 Interval.Nodes.push_back(B);
83 Partitioned.set(ID);
84 for (const Node *S : B->succs())
85 if (S != nullptr)
86 if (auto SID = getID(*S);
87 !Partitioned.test(SID) && !Workset.test(SID)) {
88 Worklist.push(S);
89 Workset.set(SID);
90 }
91 } else {
92 MaybeSuccessors.push_back(B);
93 }
94 }
95
96
97 for (const Node *B : MaybeSuccessors)
98 if (!llvm::is_contained(Interval.Nodes, B))
100
101 return Interval;
102}
103
104template
106 std::vector<CFGIntervalNode *> &Index,
107 std::queue<const Node *> &Successors,
108 llvm::BitVector &Partitioned, const Node *Header) {
110 for (const auto *S : Result.Successors)
111 Successors.push(S);
112
113 CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());
114
115
116
117
118
119 for (const auto *N : Result.Nodes) {
120 assert(N != nullptr);
121 assert(getID(*N) < Index.size());
122 Index[getID(*N)] = &Interval;
123 }
124
125 if constexpr (std::is_same_v<std::decay_t, CFGBlock>)
126 Interval.Nodes = std::move(Result.Nodes);
127 else {
128 std::vector<const CFGBlock *> Nodes;
129
130 size_t Count = 0;
131 for (auto &N : Result.Nodes)
132 Count += N->Nodes.size();
133 Nodes.reserve(Count);
134 for (auto &N : Result.Nodes)
135 Nodes.insert(Nodes.end(), N->Nodes.begin(), N->Nodes.end());
137 }
138}
139
140template
142 const Node *EntryBlock) {
143 assert(EntryBlock != nullptr);
145
146
147
148 std::vector<CFGIntervalNode *> Index(NumBlockIDs, nullptr);
149
150
151
152
153
154 std::vector<std::pair<const Node *, CFGIntervalNode *>> Intervals;
155 llvm::BitVector Partitioned(NumBlockIDs, false);
156 std::queue<const Node *> Successors;
157
158 fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);
159 Intervals.emplace_back(EntryBlock, &Graph.back());
160
161 while (!Successors.empty()) {
162 const auto *B = Successors.front();
163 Successors.pop();
164 assert(B != nullptr);
165 if (Partitioned.test(getID(*B)))
166 continue;
167
168
169
171 Intervals.emplace_back(B, &Graph.back());
172 }
173
174
175 for (auto [H, N] : Intervals) {
176
177
178 for (const Node *P : H->preds()) {
179 if (P == nullptr)
180 continue;
181
182 assert(getID(*P) < NumBlockIDs);
184 if (Pred == nullptr)
185
186 continue;
187 if (Pred != N
189
190
191
193 }
194 }
195
196 return Graph;
197}
198
202}
203
206}
207
210}
211}
212
214
215 unsigned PrevSize = Cfg.size();
216 if (PrevSize == 0)
217 return {};
219 unsigned Size = Graph.size();
220 while (Size > 1 && Size < PrevSize) {
221 PrevSize = Graph.size();
223 Size = Graph.size();
224 }
225 if (Size > 1)
226
227 return std::nullopt;
228
229 assert(Size != 0);
230 return std::move(Graph[0].Nodes);
231}
232
234 if (WTO.empty())
235 return;
236 auto N = WTO[0]->getParent()->getNumBlockIDs();
238 for (unsigned I = 0, S = WTO.size(); I < S; ++I)
239 BlockOrder[WTO[I]->getBlockID()] = I + 1;
240}
241}
BoundNodesTreeBuilder Nodes
Represents a single basic block in a source-level CFG.
unsigned getBlockID() const
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
static void fillIntervalNode(CFGIntervalGraph &Graph, std::vector< CFGIntervalNode * > &Index, std::queue< const Node * > &Successors, llvm::BitVector &Partitioned, const Node *Header)
static unsigned getID(const CFGBlock &B)
std::vector< const CFGBlock * > buildInterval(const CFGBlock *Header)
std::deque< CFGIntervalNode > CFGIntervalGraph
static CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs, const Node *EntryBlock)
CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg)
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
std::vector< const CFGBlock * > WeakTopologicalOrdering
A weak topological ordering (WTO) of CFG nodes provides a total order over the CFG (defined in WTOCom...
std::optional< WeakTopologicalOrdering > getIntervalWTO(const CFG &Cfg)
llvm::SmallDenseSet< const Node * > Successors
std::vector< const Node * > Nodes
std::vector< unsigned > BlockOrder
WTOCompare(const WeakTopologicalOrdering &WTO)
std::vector< const CFGBlock * > Nodes
llvm::SmallDenseSet< const CFGIntervalNode * > Predecessors
llvm::SmallDenseSet< const CFGIntervalNode * > Successors