clang/unittests/Analysis/IntervalPartitionTest.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-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
  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
  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 {
  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
  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
  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
  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
  93 template <typename... T> auto blockIDs(T... IDs) {
  94   return UnorderedElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
  95 }
  96
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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