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