1//===- unittests/Analysis/IntervalPartitionTest.cpp -----------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "clang/Analysis/Analyses/IntervalPartition.h"
10#include "CFGBuildResult.h"
11#include "clang/Analysis/CFG.h"
12#include "llvm/Support/raw_ostream.h"
13#include "gmock/gmock.h"
14#include "gtest/gtest.h"
15#include <type_traits>
16#include <variant>
17
18namespace clang {
19
20llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
21 const std::vector<const CFGBlock *> &Nodes) {
22 OS << "Blocks{";
23 for (const auto *B : Nodes)
24 OS << B->getBlockID() << ", ";
25 OS << "}";
26 return OS;
27}
28
29void PrintTo(const std::vector<const CFGBlock *> &Nodes, std::ostream *OS) {
30 std::string Result;
31 llvm::raw_string_ostream StringOS(Result);
32 StringOS << Nodes;
33 *OS << Result;
34}
35
36namespace internal {
37llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CFGIntervalNode &I) {
38 OS << "Interval{ID = " << I.ID << ", ";
39 OS << "Blocks{";
40 for (const auto *B : I.Nodes)
41 OS << B->getBlockID() << ", ";
42 OS << "}, Pre{";
43 for (const auto *P : I.Predecessors)
44 OS << P->ID << ",";
45 OS << "}, Succ{";
46 for (const auto *P : I.Successors)
47 OS << P->ID << ",";
48 OS << "}}";
49 return OS;
50}
51
52llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
53 const CFGIntervalGraph &G) {
54 OS << "Intervals{";
55 for (const auto &I : G) {
56 OS << I << ", ";
57 }
58 OS << "}";
59 return OS;
60}
61
62void PrintTo(const CFGIntervalNode &I, std::ostream *OS) {
63 std::string Result;
64 llvm::raw_string_ostream StringOS(Result);
65 StringOS << I;
66 *OS << Result;
67}
68
69void PrintTo(const CFGIntervalGraph &G, std::ostream *OS) {
70 *OS << "Intervals{";
71 for (const auto &I : G) {
72 PrintTo(I, OS);
73 *OS << ", ";
74 }
75 *OS << "}";
76}
77} // namespace internal
78
79namespace {
80
81using ::clang::analysis::BuildCFG;
82using ::clang::analysis::BuildResult;
83using ::clang::internal::buildInterval;
84using ::clang::internal::partitionIntoIntervals;
85using ::testing::ElementsAre;
86using ::testing::IsEmpty;
87using ::testing::Optional;
88using ::testing::Property;
89using ::testing::UnorderedElementsAre;
90
91MATCHER_P(intervalID, ID, "") { return arg->ID == ID; }
92
93template <typename... T> auto blockIDs(T... IDs) {
94 return UnorderedElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
95}
96
97template <typename... T> auto blockOrder(T... IDs) {
98 return ElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
99}
100
101MATCHER_P3(isInterval, ID, Preds, Succs, "") {
102 return testing::Matches(ID)(arg.ID) &&
103 testing::Matches(Preds)(arg.Predecessors) &&
104 testing::Matches(Succs)(arg.Successors);
105}
106
107MATCHER_P4(isInterval, ID, Nodes, Preds, Succs, "") {
108 return testing::Matches(ID)(arg.ID) && testing::Matches(Nodes)(arg.Nodes) &&
109 testing::Matches(Preds)(arg.Predecessors) &&
110 testing::Matches(Succs)(arg.Successors);
111}
112
113TEST(BuildInterval, PartitionSimpleOneInterval) {
114 const char *Code = R"(void f() {
115 int x = 3;
116 int y = 7;
117 x = y + x;
118 })";
119 BuildResult Result = BuildCFG(Code);
120 EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
121
122 CFG *cfg = Result.getCFG();
123
124 // Basic correctness checks.
125 ASSERT_EQ(cfg->size(), 3u);
126
127 auto &EntryBlock = cfg->getEntry();
128
129 std::vector<const CFGBlock *> I = buildInterval(&EntryBlock);
130 EXPECT_EQ(I.size(), 3u);
131}
132
133TEST(BuildInterval, PartitionIfThenOneInterval) {
134 const char *Code = R"(void f() {
135 int x = 3;
136 if (x > 3)
137 x = 2;
138 else
139 x = 7;
140 x = x + x;
141 })";
142 BuildResult Result = BuildCFG(Code);
143 EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
144
145 CFG *cfg = Result.getCFG();
146
147 // Basic correctness checks.
148 ASSERT_EQ(cfg->size(), 6u);
149
150 auto &EntryBlock = cfg->getEntry();
151
152 std::vector<const CFGBlock *> I = buildInterval(&EntryBlock);
153 EXPECT_EQ(I.size(), 6u);
154}
155
156TEST(BuildInterval, PartitionWhileMultipleIntervals) {
157 const char *Code = R"(void f() {
158 int x = 3;
159 while (x >= 3)
160 --x;
161 x = x + x;
162 })";
163 BuildResult Result = BuildCFG(Code);
164 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
165
166 CFG *cfg = Result.getCFG();
167 ASSERT_EQ(cfg->size(), 7u);
168
169 auto *EntryBlock = &cfg->getEntry();
170 CFGBlock *InitXBlock = *EntryBlock->succ_begin();
171 CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
172
173 std::vector<const CFGBlock *> I1 = buildInterval(EntryBlock);
174 EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock));
175
176 std::vector<const CFGBlock *> I2 = buildInterval(Header: LoopHeadBlock);
177 EXPECT_EQ(I2.size(), 5u);
178}
179
180TEST(PartitionIntoIntervals, PartitionIfThenOneInterval) {
181 const char *Code = R"(void f() {
182 int x = 3;
183 if (x > 3)
184 x = 2;
185 else
186 x = 7;
187 x = x + x;
188 })";
189 BuildResult Result = BuildCFG(Code);
190 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
191
192 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
193 EXPECT_EQ(Graph.size(), 1u);
194 EXPECT_THAT(Graph, ElementsAre(isInterval(0, IsEmpty(), IsEmpty())));
195}
196
197TEST(PartitionIntoIntervals, PartitionWhileTwoIntervals) {
198 const char *Code = R"(void f() {
199 int x = 3;
200 while (x >= 3)
201 --x;
202 x = x + x;
203 })";
204 BuildResult Result = BuildCFG(Code);
205 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
206
207 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
208 EXPECT_THAT(
209 Graph,
210 ElementsAre(
211 isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
212 isInterval(1, UnorderedElementsAre(intervalID(0u)), IsEmpty())));
213}
214
215TEST(PartitionIntoIntervals, PartitionNestedWhileThreeIntervals) {
216 const char *Code = R"(void f() {
217 int x = 3;
218 while (x >= 3) {
219 --x;
220 int y = x;
221 while (y > 0) --y;
222 }
223 x = x + x;
224 })";
225 BuildResult Result = BuildCFG(Code);
226 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
227
228 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
229 EXPECT_THAT(
230 Graph,
231 ElementsAre(
232 isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
233 isInterval(1, UnorderedElementsAre(intervalID(0u), intervalID(2u)),
234 UnorderedElementsAre(intervalID(2u))),
235 isInterval(2, UnorderedElementsAre(intervalID(1u)),
236 UnorderedElementsAre(intervalID(1u)))));
237}
238
239TEST(PartitionIntoIntervals, PartitionSequentialWhileThreeIntervals) {
240 const char *Code = R"(void f() {
241 int x = 3;
242 while (x >= 3) {
243 --x;
244 }
245 x = x + x;
246 int y = x;
247 while (y > 0) --y;
248 })";
249 BuildResult Result = BuildCFG(Code);
250 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
251
252 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
253 EXPECT_THAT(
254 Graph,
255 ElementsAre(
256 isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
257 isInterval(1, UnorderedElementsAre(intervalID(0u)),
258 UnorderedElementsAre(intervalID(2u))),
259 isInterval(2, UnorderedElementsAre(intervalID(1u)), IsEmpty())));
260}
261
262TEST(PartitionIntoIntervals, LimitReducibleSequentialWhile) {
263 const char *Code = R"(void f() {
264 int x = 3;
265 while (x >= 3) {
266 --x;
267 }
268 x = x + x;
269 int y = x;
270 while (y > 0) --y;
271 })";
272 BuildResult Result = BuildCFG(Code);
273 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
274
275 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
276 ASSERT_THAT(
277 Graph,
278 ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
279 UnorderedElementsAre(intervalID(1u))),
280 isInterval(1, blockOrder(7, 6, 4, 5),
281 UnorderedElementsAre(intervalID(0u)),
282 UnorderedElementsAre(intervalID(2u))),
283 isInterval(2, blockOrder(3, 2, 0, 1),
284 UnorderedElementsAre(intervalID(1u)), IsEmpty())));
285
286 auto Graph2 = partitionIntoIntervals(Graph);
287 EXPECT_THAT(Graph2, ElementsAre(isInterval(
288 0, blockOrder(9, 8, 7, 6, 4, 5, 3, 2, 0, 1),
289 IsEmpty(), IsEmpty())));
290}
291
292TEST(PartitionIntoIntervals, LimitReducibleNestedWhile) {
293 const char *Code = R"(void f() {
294 int x = 3;
295 while (x >= 3) {
296 --x;
297 int y = x;
298 while (y > 0) --y;
299 }
300 x = x + x;
301 })";
302 BuildResult Result = BuildCFG(Code);
303 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
304
305 auto Graph = partitionIntoIntervals(Cfg: *Result.getCFG());
306 ASSERT_THAT(Graph,
307 ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
308 UnorderedElementsAre(intervalID(1u))),
309 isInterval(1, blockOrder(7, 6, 1, 0),
310 UnorderedElementsAre(intervalID(0u),
311 intervalID(2u)),
312 UnorderedElementsAre(intervalID(2u))),
313 isInterval(2, blockOrder(5, 4, 2, 3),
314 UnorderedElementsAre(intervalID(1u)),
315 UnorderedElementsAre(intervalID(1u)))));
316
317 auto Graph2 = partitionIntoIntervals(Graph);
318 EXPECT_THAT(
319 Graph2,
320 ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
321 UnorderedElementsAre(intervalID(1u))),
322 isInterval(1, blockOrder(7, 6, 1, 0, 5, 4, 2, 3),
323 UnorderedElementsAre(intervalID(0u)), IsEmpty())));
324
325 auto Graph3 = partitionIntoIntervals(Graph2);
326 EXPECT_THAT(Graph3, ElementsAre(isInterval(
327 0, blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3),
328 IsEmpty(), IsEmpty())));
329}
330
331TEST(GetIntervalWTO, SequentialWhile) {
332 const char *Code = R"(void f() {
333 int x = 3;
334 while (x >= 3) {
335 --x;
336 }
337 x = x + x;
338 int y = x;
339 while (y > 0) --y;
340 })";
341 BuildResult Result = BuildCFG(Code);
342 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
343 EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
344 Optional(blockOrder(9, 8, 7, 6, 4, 5, 3, 2, 0, 1)));
345}
346
347TEST(GetIntervalWTO, NestedWhile) {
348 const char *Code = R"(void f() {
349 int x = 3;
350 while (x >= 3) {
351 --x;
352 int y = x;
353 while (y > 0) --y;
354 }
355 x = x + x;
356 })";
357 BuildResult Result = BuildCFG(Code);
358 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
359 EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
360 Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
361}
362
363TEST(GetIntervalWTO, UnreachablePred) {
364 const char *Code = R"(
365 void target(bool Foo) {
366 bool Bar = false;
367 if (Foo)
368 Bar = Foo;
369 else
370 __builtin_unreachable();
371 (void)0;
372 })";
373 BuildResult Result = BuildCFG(Code);
374 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
375 EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
376 Optional(blockOrder(5, 4, 3, 2, 1, 0)));
377}
378
379TEST(WTOCompare, UnreachableBlock) {
380 const char *Code = R"(
381 void target() {
382 while (true) {}
383 (void)0;
384 /*[[p]]*/
385 })";
386 BuildResult Result = BuildCFG(Code);
387 ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
388 std::optional<WeakTopologicalOrdering> WTO = getIntervalWTO(Cfg: *Result.getCFG());
389 ASSERT_THAT(WTO, Optional(blockOrder(4, 3, 2)));
390 auto Cmp = WTOCompare(*WTO);
391 const CFGBlock &Entry = Result.getCFG()->getEntry();
392 const CFGBlock &Exit = Result.getCFG()->getExit();
393 EXPECT_TRUE(Cmp(&Entry, &Exit));
394}
395
396} // namespace
397} // namespace clang
398

source code of clang/unittests/Analysis/IntervalPartitionTest.cpp