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, StraightNoPath) {
 151   ParseAssembly(
 152       "define void @test() {\n"
 153       "entry:\n"
 154       "  %B = bitcast i8 undef to i8\n"
 155       "  br label %exit\n"
 156       "exit:\n"
 157       "  %A = bitcast i8 undef to i8\n"
 158       "  ret void\n"
 159       "}");
 160   ExpectPath(false);
 161 }
 162
 163 TEST_F(IsPotentiallyReachableTest, StraightPath) {
 164   ParseAssembly(
 165       "define void @test() {\n"
 166       "entry:\n"
 167       "  %A = bitcast i8 undef to i8\n"
 168       "  br label %exit\n"
 169       "exit:\n"
 170       "  %B = bitcast i8 undef to i8\n"
 171       "  ret void\n"
 172       "}");
 173   ExpectPath(true);
 174 }
 175
 176 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
 177   ParseAssembly(
 178       "define void @test() {\n"
 179       "entry:\n"
 180       "  br label %midblock\n"
 181       "midblock:\n"
 182       "  %A = bitcast i8 undef to i8\n"
 183       "  ret void\n"
 184       "unreachable:\n"
 185       "  %B = bitcast i8 undef to i8\n"
 186       "  br label %midblock\n"
 187       "}");
 188   ExpectPath(false);
 189 }
 190
 191 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
 192   ParseAssembly(
 193       "define void @test(i1 %x) {\n"
 194       "entry:\n"
 195       "  %A = bitcast i8 undef to i8\n"
 196       "  br i1 %x, label %block1, label %block2\n"
 197       "block1:\n"
 198       "  ret void\n"
 199       "block2:\n"
 200       "  %B = bitcast i8 undef to i8\n"
 201       "  ret void\n"
 202       "}");
 203   ExpectPath(true);
 204 }
 205
 206 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
 207   ParseAssembly(
 208       "declare i1 @switch()\n"
 209       "\n"
 210       "define void @test() {\n"
 211       "entry:\n"
 212       "  br label %loop\n"
 213       "loop:\n"
 214       "  %B = bitcast i8 undef to i8\n"
 215       "  %A = bitcast i8 undef to i8\n"
 216       "  %x = call i1 @switch()\n"
 217       "  br i1 %x, label %loop, label %exit\n"
 218       "exit:\n"
 219       "  ret void\n"
 220       "}");
 221   ExpectPath(true);
 222 }
 223
 224 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
 225   ParseAssembly(
 226       "declare i1 @switch()\n"
 227       "\n"
 228       "define void @test() {\n"
 229       "entry:\n"
 230       "  %B = bitcast i8 undef to i8\n"
 231       "  br label %loop\n"
 232       "loop:\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(false);
 240 }
 241
 242 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
 243   ParseAssembly(
 244       "declare i1 @switch()\n"
 245       "\n"
 246       "define void @test() {\n"
 247       "entry:\n"
 248       "  br label %loop\n"
 249       "loop:\n"
 250       "  %B = 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       "  %A = bitcast i8 undef to i8\n"
 255       "  ret void\n"
 256       "}");
 257   ExpectPath(false);
 258 }
 259
 260
 261 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
 262   ParseAssembly(
 263       "declare i1 @switch()\n"
 264       "\n"
 265       "define void @test() {\n"
 266       "entry:\n"
 267       "  br label %loop1\n"
 268       "loop1:\n"
 269       "  %A = bitcast i8 undef to i8\n"
 270       "  %x = call i1 @switch()\n"
 271       "  br i1 %x, label %loop1, label %loop1exit\n"
 272       "loop1exit:\n"
 273       "  br label %loop2\n"
 274       "loop2:\n"
 275       "  %B = bitcast i8 undef to i8\n"
 276       "  %y = call i1 @switch()\n"
 277       "  br i1 %x, label %loop2, label %loop2exit\n"
 278       "loop2exit:"
 279       "  ret void\n"
 280       "}");
 281   ExpectPath(true);
 282 }
 283
 284 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
 285   ParseAssembly(
 286       "declare i1 @switch()\n"
 287       "\n"
 288       "define void @test() {\n"
 289       "entry:\n"
 290       "  br label %loop1\n"
 291       "loop1:\n"
 292       "  %B = bitcast i8 undef to i8\n"
 293       "  %x = call i1 @switch()\n"
 294       "  br i1 %x, label %loop1, label %loop1exit\n"
 295       "loop1exit:\n"
 296       "  br label %loop2\n"
 297       "loop2:\n"
 298       "  %A = bitcast i8 undef to i8\n"
 299       "  %y = call i1 @switch()\n"
 300       "  br i1 %x, label %loop2, label %loop2exit\n"
 301       "loop2exit:"
 302       "  ret void\n"
 303       "}");
 304   ExpectPath(false);
 305 }
 306
 307 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
 308   ParseAssembly(
 309       "declare i1 @switch()\n"
 310       "\n"
 311       "define void @test() {\n"
 312       "entry:\n"
 313       "  br label %outerloop3\n"
 314       "outerloop3:\n"
 315       "  br label %innerloop1\n"
 316       "innerloop1:\n"
 317       "  %B = bitcast i8 undef to i8\n"
 318       "  %x = call i1 @switch()\n"
 319       "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
 320       "innerloop1exit:\n"
 321       "  br label %innerloop2\n"
 322       "innerloop2:\n"
 323       "  %A = bitcast i8 undef to i8\n"
 324       "  %y = call i1 @switch()\n"
 325       "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
 326       "innerloop2exit:"
 327       "  ;; In outer loop3 now.\n"
 328       "  %z = call i1 @switch()\n"
 329       "  br i1 %z, label %outerloop3, label %exit\n"
 330       "exit:\n"
 331       "  ret void\n"
 332       "}");
 333   ExpectPath(true);
 334 }
 335
 336 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
 337   ParseAssembly(
 338       "declare i1 @switch()\n"
 339       "\n"
 340       "define void @test() {\n"
 341       "entry:\n"
 342       "  br label %loop\n"
 343       "loop:\n"
 344       "  %x = call i1 @switch()\n"
 345       "  br i1 %x, label %nextloopblock, label %exit\n"
 346       "nextloopblock:\n"
 347       "  %y = call i1 @switch()\n"
 348       "  br i1 %y, label %left, label %right\n"
 349       "left:\n"
 350       "  %A = bitcast i8 undef to i8\n"
 351       "  br label %loop\n"
 352       "right:\n"
 353       "  %B = bitcast i8 undef to i8\n"
 354       "  br label %loop\n"
 355       "exit:\n"
 356       "  ret void\n"
 357       "}");
 358   ExpectPath(true);
 359 }