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