unittests/Analysis/CFGTest.cpp

   1 //===- CFGTest.cpp - CFG tests --------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/CFG.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/Pass.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
  63   void ExpectPath(bool ExpectedResult) {
  64     static char ID;
  65     class IsPotentiallyReachableTestPass : public FunctionPass {
  66      public:
  67       IsPotentiallyReachableTestPass(bool ExpectedResult,
  68                                      Instruction *A, Instruction *B)
  69           : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
  70
  71       static int initialize() {
  72         PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
  73                                     "", &ID, nullptr, true, true);
  74         PassRegistry::getPassRegistry()->registerPass(*PI, false);
  75         initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
  76         initializeDominatorTreeWrapperPassPass(
  77             *PassRegistry::getPassRegistry());
  78         return 0;
  79       }
  80
  81       void getAnalysisUsage(AnalysisUsage &AU) const override {
  82         AU.setPreservesAll();
  83         AU.addRequired<LoopInfoWrapperPass>();
  84         AU.addRequired<DominatorTreeWrapperPass>();
  85       }
  86
  87       bool runOnFunction(Function &F) override {
  88         if (!F.hasName() || F.getName() != "test")
  89           return false;
  90
  91         LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  92         DominatorTree *DT =
  93             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  94         EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr),
  95                   ExpectedResult);
  96         EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult);
  97         EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult);
  98         EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
  99         return false;
 100       }
 101       bool ExpectedResult;
 102       Instruction *A, *B;
 103     };
 104
 105     static int initialize = IsPotentiallyReachableTestPass::initialize();
 106     (void)initialize;
 107
 108     IsPotentiallyReachableTestPass *P =
 109         new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
 110     legacy::PassManager PM;
 111     PM.add(P);
 112     PM.run(*M);
 113   }
 114
 115   LLVMContext Context;
 116   std::unique_ptr<Module> M;
 117   Instruction *A, *B;
 118 };
 119
 120 }
 121
 122 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
 123   ParseAssembly(
 124       "define void @test() {\n"
 125       "entry:\n"
 126       "  bitcast i8 undef to i8\n"
 127       "  %B = bitcast i8 undef to i8\n"
 128       "  bitcast i8 undef to i8\n"
 129       "  bitcast i8 undef to i8\n"
 130       "  %A = bitcast i8 undef to i8\n"
 131       "  ret void\n"
 132       "}\n");
 133   ExpectPath(false);
 134 }
 135
 136 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
 137   ParseAssembly(
 138       "define void @test() {\n"
 139       "entry:\n"
 140       "  %A = bitcast i8 undef to i8\n"
 141       "  bitcast i8 undef to i8\n"
 142       "  bitcast i8 undef to i8\n"
 143       "  %B = bitcast i8 undef to i8\n"
 144       "  ret void\n"
 145       "}\n");
 146   ExpectPath(true);
 147 }
 148
 149 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
 150   ParseAssembly(
 151       "define void @test() {\n"
 152       "entry:\n"
 153       "  br label %middle\n"
 154       "middle:\n"
 155       "  %B = bitcast i8 undef to i8\n"
 156       "  bitcast i8 undef to i8\n"
 157       "  bitcast i8 undef to i8\n"
 158       "  %A = bitcast i8 undef to i8\n"
 159       "  br label %nextblock\n"
 160       "nextblock:\n"
 161       "  ret void\n"
 162       "}\n");
 163   ExpectPath(false);
 164 }
 165
 166 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
 167   ParseAssembly(
 168       "define void @test() {\n"
 169       "entry:\n"
 170       "  %B = bitcast i8 undef to i8\n"
 171       "  br label %exit\n"
 172       "exit:\n"
 173       "  %A = bitcast i8 undef to i8\n"
 174       "  ret void\n"
 175       "}");
 176   ExpectPath(false);
 177 }
 178
 179 TEST_F(IsPotentiallyReachableTest, StraightPath) {
 180   ParseAssembly(
 181       "define void @test() {\n"
 182       "entry:\n"
 183       "  %A = bitcast i8 undef to i8\n"
 184       "  br label %exit\n"
 185       "exit:\n"
 186       "  %B = bitcast i8 undef to i8\n"
 187       "  ret void\n"
 188       "}");
 189   ExpectPath(true);
 190 }
 191
 192 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
 193   ParseAssembly(
 194       "define void @test() {\n"
 195       "entry:\n"
 196       "  br label %midblock\n"
 197       "midblock:\n"
 198       "  %A = bitcast i8 undef to i8\n"
 199       "  ret void\n"
 200       "unreachable:\n"
 201       "  %B = bitcast i8 undef to i8\n"
 202       "  br label %midblock\n"
 203       "}");
 204   ExpectPath(false);
 205 }
 206
 207 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
 208   ParseAssembly(
 209       "define void @test(i1 %x) {\n"
 210       "entry:\n"
 211       "  %A = bitcast i8 undef to i8\n"
 212       "  br i1 %x, label %block1, label %block2\n"
 213       "block1:\n"
 214       "  ret void\n"
 215       "block2:\n"
 216       "  %B = bitcast i8 undef to i8\n"
 217       "  ret void\n"
 218       "}");
 219   ExpectPath(true);
 220 }
 221
 222 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
 223   ParseAssembly(
 224       "declare i1 @switch()\n"
 225       "\n"
 226       "define void @test() {\n"
 227       "entry:\n"
 228       "  br label %loop\n"
 229       "loop:\n"
 230       "  %B = bitcast i8 undef to i8\n"
 231       "  %A = bitcast i8 undef to i8\n"
 232       "  %x = call i1 @switch()\n"
 233       "  br i1 %x, label %loop, label %exit\n"
 234       "exit:\n"
 235       "  ret void\n"
 236       "}");
 237   ExpectPath(true);
 238 }
 239
 240 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
 241   ParseAssembly(
 242       "declare i1 @switch()\n"
 243       "\n"
 244       "define void @test() {\n"
 245       "entry:\n"
 246       "  %B = bitcast i8 undef to i8\n"
 247       "  br label %loop\n"
 248       "loop:\n"
 249       "  %A = bitcast i8 undef to i8\n"
 250       "  %x = call i1 @switch()\n"
 251       "  br i1 %x, label %loop, label %exit\n"
 252       "exit:\n"
 253       "  ret void\n"
 254       "}");
 255   ExpectPath(false);
 256 }
 257
 258 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
 259   ParseAssembly(
 260       "declare i1 @switch()\n"
 261       "\n"
 262       "define void @test() {\n"
 263       "entry:\n"
 264       "  br label %loop\n"
 265       "loop:\n"
 266       "  %B = bitcast i8 undef to i8\n"
 267       "  %x = call i1 @switch()\n"
 268       "  br i1 %x, label %loop, label %exit\n"
 269       "exit:\n"
 270       "  %A = bitcast i8 undef to i8\n"
 271       "  ret void\n"
 272       "}");
 273   ExpectPath(false);
 274 }
 275
 276
 277 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
 278   ParseAssembly(
 279       "declare i1 @switch()\n"
 280       "\n"
 281       "define void @test() {\n"
 282       "entry:\n"
 283       "  br label %loop1\n"
 284       "loop1:\n"
 285       "  %A = bitcast i8 undef to i8\n"
 286       "  %x = call i1 @switch()\n"
 287       "  br i1 %x, label %loop1, label %loop1exit\n"
 288       "loop1exit:\n"
 289       "  br label %loop2\n"
 290       "loop2:\n"
 291       "  %B = bitcast i8 undef to i8\n"
 292       "  %y = call i1 @switch()\n"
 293       "  br i1 %x, label %loop2, label %loop2exit\n"
 294       "loop2exit:"
 295       "  ret void\n"
 296       "}");
 297   ExpectPath(true);
 298 }
 299
 300 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
 301   ParseAssembly(
 302       "declare i1 @switch()\n"
 303       "\n"
 304       "define void @test() {\n"
 305       "entry:\n"
 306       "  br label %loop1\n"
 307       "loop1:\n"
 308       "  %B = bitcast i8 undef to i8\n"
 309       "  %x = call i1 @switch()\n"
 310       "  br i1 %x, label %loop1, label %loop1exit\n"
 311       "loop1exit:\n"
 312       "  br label %loop2\n"
 313       "loop2:\n"
 314       "  %A = bitcast i8 undef to i8\n"
 315       "  %y = call i1 @switch()\n"
 316       "  br i1 %x, label %loop2, label %loop2exit\n"
 317       "loop2exit:"
 318       "  ret void\n"
 319       "}");
 320   ExpectPath(false);
 321 }
 322
 323 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
 324   ParseAssembly(
 325       "declare i1 @switch()\n"
 326       "\n"
 327       "define void @test() {\n"
 328       "entry:\n"
 329       "  br label %outerloop3\n"
 330       "outerloop3:\n"
 331       "  br label %innerloop1\n"
 332       "innerloop1:\n"
 333       "  %B = bitcast i8 undef to i8\n"
 334       "  %x = call i1 @switch()\n"
 335       "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
 336       "innerloop1exit:\n"
 337       "  br label %innerloop2\n"
 338       "innerloop2:\n"
 339       "  %A = bitcast i8 undef to i8\n"
 340       "  %y = call i1 @switch()\n"
 341       "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
 342       "innerloop2exit:"
 343       "  ;; In outer loop3 now.\n"
 344       "  %z = call i1 @switch()\n"
 345       "  br i1 %z, label %outerloop3, label %exit\n"
 346       "exit:\n"
 347       "  ret void\n"
 348       "}");
 349   ExpectPath(true);
 350 }
 351
 352 static const char *BranchInsideLoopIR =
 353     "declare i1 @switch()\n"
 354     "\n"
 355     "define void @test() {\n"
 356     "entry:\n"
 357     "  br label %loop\n"
 358     "loop:\n"
 359     "  %x = call i1 @switch()\n"
 360     "  br i1 %x, label %nextloopblock, label %exit\n"
 361     "nextloopblock:\n"
 362     "  %y = call i1 @switch()\n"
 363     "  br i1 %y, label %left, label %right\n"
 364     "left:\n"
 365     "  %A = bitcast i8 undef to i8\n"
 366     "  br label %loop\n"
 367     "right:\n"
 368     "  %B = bitcast i8 undef to i8\n"
 369     "  br label %loop\n"
 370     "exit:\n"
 371     "  ret void\n"
 372     "}";
 373
 374 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
 375   ParseAssembly(BranchInsideLoopIR);
 376   ExpectPath(true);
 377 }
 378
 379 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
 380   ParseAssembly(BranchInsideLoopIR);
 381
 382   succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());
 383   BasicBlock *OldBB = S[0];
 384   S[0] = S[1];
 385   ExpectPath(false);
 386   S[0] = OldBB;
 387   ExpectPath(true);
 388 }