llvm/unittests/Analysis/CFGTest.cpp

   1 //===- CFGTest.cpp - CFG tests --------------------------------------------===//
   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 "llvm/Analysis/CFG.h"
  10 #include "llvm/ADT/SmallPtrSet.h"
  11 #include "llvm/Analysis/LoopInfo.h"
  12 #include "llvm/AsmParser/Parser.h"
  13 #include "llvm/IR/Dominators.h"
  14 #include "llvm/IR/Function.h"
  15 #include "llvm/IR/InstIterator.h"
  16 #include "llvm/IR/LLVMContext.h"
  17 #include "llvm/IR/LegacyPassManager.h"
  18 #include "llvm/IR/Module.h"
  19 #include "llvm/InitializePasses.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/SourceMgr.h"
  22 #include "gtest/gtest.h"
  23
  24 using namespace llvm;
  25
  26 namespace {
  27
  28 // This fixture assists in running the isPotentiallyReachable utility four ways
  29 // and ensuring it produces the correct answer each time.
  30 class IsPotentiallyReachableTest : public testing::Test {
  31 protected:
  32   void ParseAssembly(const char *Assembly) {
  33     SMDiagnostic Error;
  34     M = parseAssemblyString(Assembly, Error, Context);
  35
  36     std::string errMsg;
  37     raw_string_ostream os(errMsg);
  38     Error.print("", os);
  39
  40     // A failure here means that the test itself is buggy.
  41     if (!M)
  42       report_fatal_error(os.str().c_str());
  43
  44     Function *F = M->getFunction("test");
  45     if (F == nullptr)
  46       report_fatal_error("Test must have a function named @test");
  47
  48     A = B = nullptr;
  49     for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
  50       if (I->hasName()) {
  51         if (I->getName() == "A")
  52           A = &*I;
  53         else if (I->getName() == "B")
  54           B = &*I;
  55       }
  56     }
  57     if (A == nullptr)
  58       report_fatal_error("@test must have an instruction %A");
  59     if (B == nullptr)
  60       report_fatal_error("@test must have an instruction %B");
  61
  62     assert(ExclusionSet.empty());
  63     for (auto I = F->begin(), E = F->end(); I != E; ++I) {
  64       if (I->hasName() && I->getName().startswith("excluded"))
  65         ExclusionSet.insert(&*I);
  66     }
  67   }
  68
  69   void ExpectPath(bool ExpectedResult) {
  70     static char ID;
  71     class IsPotentiallyReachableTestPass : public FunctionPass {
  72      public:
  73        IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A,
  74                                       Instruction *B,
  75                                       SmallPtrSet<BasicBlock *, 4> ExclusionSet)
  76            : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B),
  77              ExclusionSet(ExclusionSet) {}
  78
  79        static int initialize() {
  80          PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "",
  81                                      &ID, nullptr, true, true);
  82          PassRegistry::getPassRegistry()->registerPass(*PI, true);
  83          initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
  84          initializeDominatorTreeWrapperPassPass(
  85              *PassRegistry::getPassRegistry());
  86          return 0;
  87       }
  88
  89       void getAnalysisUsage(AnalysisUsage &AU) const override {
  90         AU.setPreservesAll();
  91         AU.addRequired<LoopInfoWrapperPass>();
  92         AU.addRequired<DominatorTreeWrapperPass>();
  93       }
  94
  95       bool runOnFunction(Function &F) override {
  96         if (!F.hasName() || F.getName() != "test")
  97           return false;
  98
  99         LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 100         DominatorTree *DT =
 101             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 102         EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr),
 103                   ExpectedResult);
 104         EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr),
 105                   ExpectedResult);
 106         EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI),
 107                   ExpectedResult);
 108         EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI),
 109                   ExpectedResult);
 110         return false;
 111       }
 112       bool ExpectedResult;
 113       Instruction *A, *B;
 114       SmallPtrSet<BasicBlock *, 4> ExclusionSet;
 115     };
 116
 117     static int initialize = IsPotentiallyReachableTestPass::initialize();
 118     (void)initialize;
 119
 120     IsPotentiallyReachableTestPass *P =
 121         new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet);
 122     legacy::PassManager PM;
 123     PM.add(P);
 124     PM.run(*M);
 125   }
 126
 127   LLVMContext Context;
 128   std::unique_ptr<Module> M;
 129   Instruction *A, *B;
 130   SmallPtrSet<BasicBlock *, 4> ExclusionSet;
 131 };
 132
 133 }
 134
 135 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
 136   ParseAssembly(
 137       "define void @test() {\n"
 138       "entry:\n"
 139       "  bitcast i8 undef to i8\n"
 140       "  %B = bitcast i8 undef to i8\n"
 141       "  bitcast i8 undef to i8\n"
 142       "  bitcast i8 undef to i8\n"
 143       "  %A = bitcast i8 undef to i8\n"
 144       "  ret void\n"
 145       "}\n");
 146   ExpectPath(false);
 147 }
 148
 149 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
 150   ParseAssembly(
 151       "define void @test() {\n"
 152       "entry:\n"
 153       "  %A = bitcast i8 undef to i8\n"
 154       "  bitcast i8 undef to i8\n"
 155       "  bitcast i8 undef to i8\n"
 156       "  %B = bitcast i8 undef to i8\n"
 157       "  ret void\n"
 158       "}\n");
 159   ExpectPath(true);
 160 }
 161
 162 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
 163   ParseAssembly(
 164       "define void @test() {\n"
 165       "entry:\n"
 166       "  br label %middle\n"
 167       "middle:\n"
 168       "  %B = bitcast i8 undef to i8\n"
 169       "  bitcast i8 undef to i8\n"
 170       "  bitcast i8 undef to i8\n"
 171       "  %A = bitcast i8 undef to i8\n"
 172       "  br label %nextblock\n"
 173       "nextblock:\n"
 174       "  ret void\n"
 175       "}\n");
 176   ExpectPath(false);
 177 }
 178
 179 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
 180   ParseAssembly(
 181       "define void @test() {\n"
 182       "entry:\n"
 183       "  %B = bitcast i8 undef to i8\n"
 184       "  br label %exit\n"
 185       "exit:\n"
 186       "  %A = bitcast i8 undef to i8\n"
 187       "  ret void\n"
 188       "}");
 189   ExpectPath(false);
 190 }
 191
 192 TEST_F(IsPotentiallyReachableTest, StraightPath) {
 193   ParseAssembly(
 194       "define void @test() {\n"
 195       "entry:\n"
 196       "  %A = bitcast i8 undef to i8\n"
 197       "  br label %exit\n"
 198       "exit:\n"
 199       "  %B = bitcast i8 undef to i8\n"
 200       "  ret void\n"
 201       "}");
 202   ExpectPath(true);
 203 }
 204
 205 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
 206   ParseAssembly(
 207       "define void @test() {\n"
 208       "entry:\n"
 209       "  br label %midblock\n"
 210       "midblock:\n"
 211       "  %A = bitcast i8 undef to i8\n"
 212       "  ret void\n"
 213       "unreachable:\n"
 214       "  %B = bitcast i8 undef to i8\n"
 215       "  br label %midblock\n"
 216       "}");
 217   ExpectPath(false);
 218 }
 219
 220 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
 221   ParseAssembly(
 222       "define void @test(i1 %x) {\n"
 223       "entry:\n"
 224       "  %A = bitcast i8 undef to i8\n"
 225       "  br i1 %x, label %block1, label %block2\n"
 226       "block1:\n"
 227       "  ret void\n"
 228       "block2:\n"
 229       "  %B = bitcast i8 undef to i8\n"
 230       "  ret void\n"
 231       "}");
 232   ExpectPath(true);
 233 }
 234
 235 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
 236   ParseAssembly(
 237       "declare i1 @switch()\n"
 238       "\n"
 239       "define void @test() {\n"
 240       "entry:\n"
 241       "  br label %loop\n"
 242       "loop:\n"
 243       "  %B = bitcast i8 undef to i8\n"
 244       "  %A = bitcast i8 undef to i8\n"
 245       "  %x = call i1 @switch()\n"
 246       "  br i1 %x, label %loop, label %exit\n"
 247       "exit:\n"
 248       "  ret void\n"
 249       "}");
 250   ExpectPath(true);
 251 }
 252
 253 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
 254   ParseAssembly(
 255       "declare i1 @switch()\n"
 256       "\n"
 257       "define void @test() {\n"
 258       "entry:\n"
 259       "  %B = bitcast i8 undef to i8\n"
 260       "  br label %loop\n"
 261       "loop:\n"
 262       "  %A = bitcast i8 undef to i8\n"
 263       "  %x = call i1 @switch()\n"
 264       "  br i1 %x, label %loop, label %exit\n"
 265       "exit:\n"
 266       "  ret void\n"
 267       "}");
 268   ExpectPath(false);
 269 }
 270
 271 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
 272   ParseAssembly(
 273       "declare i1 @switch()\n"
 274       "\n"
 275       "define void @test() {\n"
 276       "entry:\n"
 277       "  br label %loop\n"
 278       "loop:\n"
 279       "  %B = bitcast i8 undef to i8\n"
 280       "  %x = call i1 @switch()\n"
 281       "  br i1 %x, label %loop, label %exit\n"
 282       "exit:\n"
 283       "  %A = bitcast i8 undef to i8\n"
 284       "  ret void\n"
 285       "}");
 286   ExpectPath(false);
 287 }
 288
 289
 290 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
 291   ParseAssembly(
 292       "declare i1 @switch()\n"
 293       "\n"
 294       "define void @test() {\n"
 295       "entry:\n"
 296       "  br label %loop1\n"
 297       "loop1:\n"
 298       "  %A = bitcast i8 undef to i8\n"
 299       "  %x = call i1 @switch()\n"
 300       "  br i1 %x, label %loop1, label %loop1exit\n"
 301       "loop1exit:\n"
 302       "  br label %loop2\n"
 303       "loop2:\n"
 304       "  %B = bitcast i8 undef to i8\n"
 305       "  %y = call i1 @switch()\n"
 306       "  br i1 %x, label %loop2, label %loop2exit\n"
 307       "loop2exit:"
 308       "  ret void\n"
 309       "}");
 310   ExpectPath(true);
 311 }
 312
 313 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
 314   ParseAssembly(
 315       "declare i1 @switch()\n"
 316       "\n"
 317       "define void @test() {\n"
 318       "entry:\n"
 319       "  br label %loop1\n"
 320       "loop1:\n"
 321       "  %B = bitcast i8 undef to i8\n"
 322       "  %x = call i1 @switch()\n"
 323       "  br i1 %x, label %loop1, label %loop1exit\n"
 324       "loop1exit:\n"
 325       "  br label %loop2\n"
 326       "loop2:\n"
 327       "  %A = bitcast i8 undef to i8\n"
 328       "  %y = call i1 @switch()\n"
 329       "  br i1 %x, label %loop2, label %loop2exit\n"
 330       "loop2exit:"
 331       "  ret void\n"
 332       "}");
 333   ExpectPath(false);
 334 }
 335
 336 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
 337   ParseAssembly(
 338       "declare i1 @switch()\n"
 339       "\n"
 340       "define void @test() {\n"
 341       "entry:\n"
 342       "  br label %outerloop3\n"
 343       "outerloop3:\n"
 344       "  br label %innerloop1\n"
 345       "innerloop1:\n"
 346       "  %B = bitcast i8 undef to i8\n"
 347       "  %x = call i1 @switch()\n"
 348       "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
 349       "innerloop1exit:\n"
 350       "  br label %innerloop2\n"
 351       "innerloop2:\n"
 352       "  %A = bitcast i8 undef to i8\n"
 353       "  %y = call i1 @switch()\n"
 354       "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
 355       "innerloop2exit:"
 356       "  ;; In outer loop3 now.\n"
 357       "  %z = call i1 @switch()\n"
 358       "  br i1 %z, label %outerloop3, label %exit\n"
 359       "exit:\n"
 360       "  ret void\n"
 361       "}");
 362   ExpectPath(true);
 363 }
 364
 365 static const char *BranchInsideLoopIR =
 366     "declare i1 @switch()\n"
 367     "\n"
 368     "define void @test() {\n"
 369     "entry:\n"
 370     "  br label %loop\n"
 371     "loop:\n"
 372     "  %x = call i1 @switch()\n"
 373     "  br i1 %x, label %nextloopblock, label %exit\n"
 374     "nextloopblock:\n"
 375     "  %y = call i1 @switch()\n"
 376     "  br i1 %y, label %left, label %right\n"
 377     "left:\n"
 378     "  %A = bitcast i8 undef to i8\n"
 379     "  br label %loop\n"
 380     "right:\n"
 381     "  %B = bitcast i8 undef to i8\n"
 382     "  br label %loop\n"
 383     "exit:\n"
 384     "  ret void\n"
 385     "}";
 386
 387 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
 388   ParseAssembly(BranchInsideLoopIR);
 389   ExpectPath(true);
 390 }
 391
 392 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
 393   ParseAssembly(BranchInsideLoopIR);
 394
 395   succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());
 396   BasicBlock *OldBB = S[0];
 397   S[0] = S[1];
 398   ExpectPath(false);
 399   S[0] = OldBB;
 400   ExpectPath(true);
 401 }
 402
 403 TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) {
 404   ParseAssembly("define void @test() {\n"
 405                 "entry:\n"
 406                 "  %A = bitcast i8 undef to i8\n"
 407                 "  ret void\n"
 408                 "not.reachable:\n"
 409                 "  %B = bitcast i8 undef to i8\n"
 410                 "  ret void\n"
 411                 "}");
 412   ExpectPath(false);
 413 }
 414
 415 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) {
 416   ParseAssembly("define void @test() {\n"
 417                 "entry:\n"
 418                 "  ret void\n"
 419                 "not.reachable.1:\n"
 420                 "  %A = bitcast i8 undef to i8\n"
 421                 "  br label %not.reachable.2\n"
 422                 "not.reachable.2:\n"
 423                 "  %B = bitcast i8 undef to i8\n"
 424                 "  ret void\n"
 425                 "}");
 426   ExpectPath(true);
 427 }
 428
 429 TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) {
 430   ParseAssembly("define void @test() {\n"
 431                 "entry:\n"
 432                 "  ret void\n"
 433                 "not.reachable.1:\n"
 434                 "  %B = bitcast i8 undef to i8\n"
 435                 "  br label %not.reachable.2\n"
 436                 "not.reachable.2:\n"
 437                 "  %A = bitcast i8 undef to i8\n"
 438                 "  ret void\n"
 439                 "}");
 440   ExpectPath(false);
 441 }
 442
 443 TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) {
 444   ParseAssembly("define void @test() {\n"
 445                 "entry:\n"
 446                 "  %A = bitcast i8 undef to i8\n"
 447                 "  br label %excluded\n"
 448                 "excluded:\n"
 449                 "  br label %exit\n"
 450                 "exit:\n"
 451                 "  %B = bitcast i8 undef to i8\n"
 452                 "  ret void\n"
 453                 "}");
 454   ExpectPath(false);
 455 }
 456
 457 TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) {
 458   ParseAssembly("declare i1 @switch()\n"
 459                 "\n"
 460                 "define void @test() {\n"
 461                 "entry:\n"
 462                 "  %x = call i1 @switch()\n"
 463                 "  %A = bitcast i8 undef to i8\n"
 464                 "  br i1 %x, label %excluded.1, label %excluded.2\n"
 465                 "excluded.1:\n"
 466                 "  br label %exit\n"
 467                 "excluded.2:\n"
 468                 "  br label %exit\n"
 469                 "exit:\n"
 470                 "  %B = bitcast i8 undef to i8\n"
 471                 "  ret void\n"
 472                 "}");
 473   ExpectPath(false);
 474 }
 475
 476 TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) {
 477   ParseAssembly("declare i1 @switch()\n"
 478                 "\n"
 479                 "define void @test() {\n"
 480                 "entry:\n"
 481                 "  %x = call i1 @switch()\n"
 482                 "  %A = bitcast i8 undef to i8\n"
 483                 "  br i1 %x, label %excluded, label %diamond\n"
 484                 "excluded:\n"
 485                 "  br label %exit\n"
 486                 "diamond:\n"
 487                 "  br label %exit\n"
 488                 "exit:\n"
 489                 "  %B = bitcast i8 undef to i8\n"
 490                 "  ret void\n"
 491                 "}");
 492   ExpectPath(true);
 493 }
 494
 495 TEST_F(IsPotentiallyReachableTest, UnreachableToReachable) {
 496   ParseAssembly("define void @test() {\n"
 497                 "entry:\n"
 498                 "  br label %exit\n"
 499                 "unreachableblock:\n"
 500                 "  %A = bitcast i8 undef to i8\n"
 501                 "  br label %exit\n"
 502                 "exit:\n"
 503                 "  %B = bitcast i8 undef to i8\n"
 504                 "  ret void\n"
 505                 "}");
 506   ExpectPath(true);
 507 }