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
18 namespace clang {
19
operator <<(llvm::raw_ostream & OS,const std::vector<const CFGBlock * > & Nodes)20 llvm::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
PrintTo(const std::vector<const CFGBlock * > & Nodes,std::ostream * OS)29 void 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
36 namespace internal {
operator <<(llvm::raw_ostream & OS,const CFGIntervalNode & I)37 llvm::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
operator <<(llvm::raw_ostream & OS,const CFGIntervalGraph & G)52 llvm::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
PrintTo(const CFGIntervalNode & I,std::ostream * OS)62 void 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
PrintTo(const CFGIntervalGraph & G,std::ostream * OS)69 void 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
79 namespace {
80
81 using ::clang::analysis::BuildCFG;
82 using ::clang::analysis::BuildResult;
83 using ::clang::internal::buildInterval;
84 using ::clang::internal::partitionIntoIntervals;
85 using ::testing::ElementsAre;
86 using ::testing::IsEmpty;
87 using ::testing::Optional;
88 using ::testing::Property;
89 using ::testing::UnorderedElementsAre;
90
91 MATCHER_P(intervalID, ID, "") { return arg->ID == ID; }
92
blockIDs(T...IDs)93 template <typename... T> auto blockIDs(T... IDs) {
94 return UnorderedElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
95 }
96
blockOrder(T...IDs)97 template <typename... T> auto blockOrder(T... IDs) {
98 return ElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
99 }
100
101 MATCHER_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
107 MATCHER_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
TEST(BuildInterval,PartitionSimpleOneInterval)113 TEST(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
TEST(BuildInterval,PartitionIfThenOneInterval)133 TEST(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
TEST(BuildInterval,PartitionWhileMultipleIntervals)156 TEST(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(LoopHeadBlock);
177 EXPECT_EQ(I2.size(), 5u);
178 }
179
TEST(PartitionIntoIntervals,PartitionIfThenOneInterval)180 TEST(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(*Result.getCFG());
193 EXPECT_EQ(Graph.size(), 1u);
194 EXPECT_THAT(Graph, ElementsAre(isInterval(0, IsEmpty(), IsEmpty())));
195 }
196
TEST(PartitionIntoIntervals,PartitionWhileTwoIntervals)197 TEST(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(*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
TEST(PartitionIntoIntervals,PartitionNestedWhileThreeIntervals)215 TEST(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(*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
TEST(PartitionIntoIntervals,PartitionSequentialWhileThreeIntervals)239 TEST(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(*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
TEST(PartitionIntoIntervals,LimitReducibleSequentialWhile)262 TEST(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(*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
TEST(PartitionIntoIntervals,LimitReducibleNestedWhile)292 TEST(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(*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
TEST(GetIntervalWTO,SequentialWhile)331 TEST(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
TEST(GetIntervalWTO,NestedWhile)347 TEST(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
TEST(GetIntervalWTO,UnreachablePred)363 TEST(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
TEST(WTOCompare,UnreachableBlock)379 TEST(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(*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