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/Dominators.h"
  13 #include "llvm/Analysis/LoopInfo.h"
  14 #include "llvm/Assembly/Parser.h"
  15 #include "llvm/IR/LLVMContext.h"
  16 #include "llvm/IR/Function.h"
  17 #include "llvm/IR/Module.h"
  18 #include "llvm/Support/ErrorHandling.h"
  19 #include "llvm/Support/InstIterator.h"
  20 #include "llvm/Support/SourceMgr.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/PassManager.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         initializeDominatorTreePass(*PassRegistry::getPassRegistry());
  82         return 0;
  83       }
  84
  85       void getAnalysisUsage(AnalysisUsage &AU) const {
  86         AU.setPreservesAll();
  87         AU.addRequired<LoopInfo>();
  88         AU.addRequired<DominatorTree>();
  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 = &getAnalysis<DominatorTree>();
  97         EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
  98         EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
  99         EXPECT_EQ(isPotentiallyReachable(A, B, 0, LI), ExpectedResult);
 100         EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
 101         return false;
 102       }
 103       bool ExpectedResult;
 104       Instruction *A, *B;
 105     };
 106
 107     static int initialize = IsPotentiallyReachableTestPass::initialize();
 108     (void)initialize;
 109
 110     IsPotentiallyReachableTestPass *P =
 111         new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
 112     PassManager PM;
 113     PM.add(P);
 114     PM.run(*M);
 115   }
 116 private:
 117   OwningPtr<Module> M;
 118   Instruction *A, *B;
 119 };
 120
 121 }
 122
 123 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
 124   ParseAssembly(
 125       "define void @test() {\n"
 126       "entry:\n"
 127       "  bitcast i8 undef to i8\n"
 128       "  %B = bitcast i8 undef to i8\n"
 129       "  bitcast i8 undef to i8\n"
 130       "  bitcast i8 undef to i8\n"
 131       "  %A = bitcast i8 undef to i8\n"
 132       "  ret void\n"
 133       "}\n");
 134   ExpectPath(false);
 135 }
 136
 137 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
 138   ParseAssembly(
 139       "define void @test() {\n"
 140       "entry:\n"
 141       "  %A = bitcast i8 undef to i8\n"
 142       "  bitcast i8 undef to i8\n"
 143       "  bitcast i8 undef to i8\n"
 144       "  %B = bitcast i8 undef to i8\n"
 145       "  ret void\n"
 146       "}\n");
 147   ExpectPath(true);
 148 }
 149
 150 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
 151   ParseAssembly(
 152       "define void @test() {\n"
 153       "entry:\n"
 154       "  br label %middle\n"
 155       "middle:\n"
 156       "  %B = bitcast i8 undef to i8\n"
 157       "  bitcast i8 undef to i8\n"
 158       "  bitcast i8 undef to i8\n"
 159       "  %A = bitcast i8 undef to i8\n"
 160       "  br label %nextblock\n"
 161       "nextblock:\n"
 162       "  ret void\n"
 163       "}\n");
 164   ExpectPath(false);
 165 }
 166
 167 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
 168   ParseAssembly(
 169       "define void @test() {\n"
 170       "entry:\n"
 171       "  %B = bitcast i8 undef to i8\n"
 172       "  br label %exit\n"
 173       "exit:\n"
 174       "  %A = bitcast i8 undef to i8\n"
 175       "  ret void\n"
 176       "}");
 177   ExpectPath(false);
 178 }
 179
 180 TEST_F(IsPotentiallyReachableTest, StraightPath) {
 181   ParseAssembly(
 182       "define void @test() {\n"
 183       "entry:\n"
 184       "  %A = bitcast i8 undef to i8\n"
 185       "  br label %exit\n"
 186       "exit:\n"
 187       "  %B = bitcast i8 undef to i8\n"
 188       "  ret void\n"
 189       "}");
 190   ExpectPath(true);
 191 }
 192
 193 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
 194   ParseAssembly(
 195       "define void @test() {\n"
 196       "entry:\n"
 197       "  br label %midblock\n"
 198       "midblock:\n"
 199       "  %A = bitcast i8 undef to i8\n"
 200       "  ret void\n"
 201       "unreachable:\n"
 202       "  %B = bitcast i8 undef to i8\n"
 203       "  br label %midblock\n"
 204       "}");
 205   ExpectPath(false);
 206 }
 207
 208 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
 209   ParseAssembly(
 210       "define void @test(i1 %x) {\n"
 211       "entry:\n"
 212       "  %A = bitcast i8 undef to i8\n"
 213       "  br i1 %x, label %block1, label %block2\n"
 214       "block1:\n"
 215       "  ret void\n"
 216       "block2:\n"
 217       "  %B = bitcast i8 undef to i8\n"
 218       "  ret void\n"
 219       "}");
 220   ExpectPath(true);
 221 }
 222
 223 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
 224   ParseAssembly(
 225       "declare i1 @switch()\n"
 226       "\n"
 227       "define void @test() {\n"
 228       "entry:\n"
 229       "  br label %loop\n"
 230       "loop:\n"
 231       "  %B = bitcast i8 undef to i8\n"
 232       "  %A = bitcast i8 undef to i8\n"
 233       "  %x = call i1 @switch()\n"
 234       "  br i1 %x, label %loop, label %exit\n"
 235       "exit:\n"
 236       "  ret void\n"
 237       "}");
 238   ExpectPath(true);
 239 }
 240
 241 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
 242   ParseAssembly(
 243       "declare i1 @switch()\n"
 244       "\n"
 245       "define void @test() {\n"
 246       "entry:\n"
 247       "  %B = bitcast i8 undef to i8\n"
 248       "  br label %loop\n"
 249       "loop:\n"
 250       "  %A = bitcast i8 undef to i8\n"
 251       "  %x = call i1 @switch()\n"
 252       "  br i1 %x, label %loop, label %exit\n"
 253       "exit:\n"
 254       "  ret void\n"
 255       "}");
 256   ExpectPath(false);
 257 }
 258
 259 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
 260   ParseAssembly(
 261       "declare i1 @switch()\n"
 262       "\n"
 263       "define void @test() {\n"
 264       "entry:\n"
 265       "  br label %loop\n"
 266       "loop:\n"
 267       "  %B = bitcast i8 undef to i8\n"
 268       "  %x = call i1 @switch()\n"
 269       "  br i1 %x, label %loop, label %exit\n"
 270       "exit:\n"
 271       "  %A = bitcast i8 undef to i8\n"
 272       "  ret void\n"
 273       "}");
 274   ExpectPath(false);
 275 }
 276
 277
 278 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
 279   ParseAssembly(
 280       "declare i1 @switch()\n"
 281       "\n"
 282       "define void @test() {\n"
 283       "entry:\n"
 284       "  br label %loop1\n"
 285       "loop1:\n"
 286       "  %A = bitcast i8 undef to i8\n"
 287       "  %x = call i1 @switch()\n"
 288       "  br i1 %x, label %loop1, label %loop1exit\n"
 289       "loop1exit:\n"
 290       "  br label %loop2\n"
 291       "loop2:\n"
 292       "  %B = bitcast i8 undef to i8\n"
 293       "  %y = call i1 @switch()\n"
 294       "  br i1 %x, label %loop2, label %loop2exit\n"
 295       "loop2exit:"
 296       "  ret void\n"
 297       "}");
 298   ExpectPath(true);
 299 }
 300
 301 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
 302   ParseAssembly(
 303       "declare i1 @switch()\n"
 304       "\n"
 305       "define void @test() {\n"
 306       "entry:\n"
 307       "  br label %loop1\n"
 308       "loop1:\n"
 309       "  %B = bitcast i8 undef to i8\n"
 310       "  %x = call i1 @switch()\n"
 311       "  br i1 %x, label %loop1, label %loop1exit\n"
 312       "loop1exit:\n"
 313       "  br label %loop2\n"
 314       "loop2:\n"
 315       "  %A = bitcast i8 undef to i8\n"
 316       "  %y = call i1 @switch()\n"
 317       "  br i1 %x, label %loop2, label %loop2exit\n"
 318       "loop2exit:"
 319       "  ret void\n"
 320       "}");
 321   ExpectPath(false);
 322 }
 323
 324 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
 325   ParseAssembly(
 326       "declare i1 @switch()\n"
 327       "\n"
 328       "define void @test() {\n"
 329       "entry:\n"
 330       "  br label %outerloop3\n"
 331       "outerloop3:\n"
 332       "  br label %innerloop1\n"
 333       "innerloop1:\n"
 334       "  %B = bitcast i8 undef to i8\n"
 335       "  %x = call i1 @switch()\n"
 336       "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
 337       "innerloop1exit:\n"
 338       "  br label %innerloop2\n"
 339       "innerloop2:\n"
 340       "  %A = bitcast i8 undef to i8\n"
 341       "  %y = call i1 @switch()\n"
 342       "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
 343       "innerloop2exit:"
 344       "  ;; In outer loop3 now.\n"
 345       "  %z = call i1 @switch()\n"
 346       "  br i1 %z, label %outerloop3, label %exit\n"
 347       "exit:\n"
 348       "  ret void\n"
 349       "}");
 350   ExpectPath(true);
 351 }
 352
 353 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
 354   ParseAssembly(
 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   ExpectPath(true);
 376 }