398 lines · cpp
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-exception6//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 internal78 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 else139 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(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 else186 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 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(*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(*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(*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(*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(*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 else370 __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(*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} // namespace397} // namespace clang398