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