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/IR/LegacyPassManager.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, getGlobalContext());
  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 {
  82         AU.setPreservesAll();
  83         AU.addRequired<LoopInfoWrapperPass>();
  84         AU.addRequired<DominatorTreeWrapperPass>();
  85       }
  86
  87       bool runOnFunction(Function &F) {
  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   std::unique_ptr<Module> M;
 116   Instruction *A, *B;
 117 };
 118
 119 }
 120
 121 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
 122   ParseAssembly(
 123       "define void @test() {\n"
 124       "entry:\n"
 125       "  bitcast i8 undef to i8\n"
 126       "  %B = bitcast i8 undef to i8\n"
 127       "  bitcast i8 undef to i8\n"
 128       "  bitcast i8 undef to i8\n"
 129       "  %A = bitcast i8 undef to i8\n"
 130       "  ret void\n"
 131       "}\n");
 132   ExpectPath(false);
 133 }
 134
 135 TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
 136   ParseAssembly(
 137       "define void @test() {\n"
 138       "entry:\n"
 139       "  %A = bitcast i8 undef to i8\n"
 140       "  bitcast i8 undef to i8\n"
 141       "  bitcast i8 undef to i8\n"
 142       "  %B = bitcast i8 undef to i8\n"
 143       "  ret void\n"
 144       "}\n");
 145   ExpectPath(true);
 146 }
 147
 148 TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {
 149   ParseAssembly(
 150       "define void @test() {\n"
 151       "entry:\n"
 152       "  br label %middle\n"
 153       "middle:\n"
 154       "  %B = bitcast i8 undef to i8\n"
 155       "  bitcast i8 undef to i8\n"
 156       "  bitcast i8 undef to i8\n"
 157       "  %A = bitcast i8 undef to i8\n"
 158       "  br label %nextblock\n"
 159       "nextblock:\n"
 160       "  ret void\n"
 161       "}\n");
 162   ExpectPath(false);
 163 }
 164
 165 TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
 166   ParseAssembly(
 167       "define void @test() {\n"
 168       "entry:\n"
 169       "  %B = bitcast i8 undef to i8\n"
 170       "  br label %exit\n"
 171       "exit:\n"
 172       "  %A = bitcast i8 undef to i8\n"
 173       "  ret void\n"
 174       "}");
 175   ExpectPath(false);
 176 }
 177
 178 TEST_F(IsPotentiallyReachableTest, StraightPath) {
 179   ParseAssembly(
 180       "define void @test() {\n"
 181       "entry:\n"
 182       "  %A = bitcast i8 undef to i8\n"
 183       "  br label %exit\n"
 184       "exit:\n"
 185       "  %B = bitcast i8 undef to i8\n"
 186       "  ret void\n"
 187       "}");
 188   ExpectPath(true);
 189 }
 190
 191 TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
 192   ParseAssembly(
 193       "define void @test() {\n"
 194       "entry:\n"
 195       "  br label %midblock\n"
 196       "midblock:\n"
 197       "  %A = bitcast i8 undef to i8\n"
 198       "  ret void\n"
 199       "unreachable:\n"
 200       "  %B = bitcast i8 undef to i8\n"
 201       "  br label %midblock\n"
 202       "}");
 203   ExpectPath(false);
 204 }
 205
 206 TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
 207   ParseAssembly(
 208       "define void @test(i1 %x) {\n"
 209       "entry:\n"
 210       "  %A = bitcast i8 undef to i8\n"
 211       "  br i1 %x, label %block1, label %block2\n"
 212       "block1:\n"
 213       "  ret void\n"
 214       "block2:\n"
 215       "  %B = bitcast i8 undef to i8\n"
 216       "  ret void\n"
 217       "}");
 218   ExpectPath(true);
 219 }
 220
 221 TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
 222   ParseAssembly(
 223       "declare i1 @switch()\n"
 224       "\n"
 225       "define void @test() {\n"
 226       "entry:\n"
 227       "  br label %loop\n"
 228       "loop:\n"
 229       "  %B = bitcast i8 undef to i8\n"
 230       "  %A = bitcast i8 undef to i8\n"
 231       "  %x = call i1 @switch()\n"
 232       "  br i1 %x, label %loop, label %exit\n"
 233       "exit:\n"
 234       "  ret void\n"
 235       "}");
 236   ExpectPath(true);
 237 }
 238
 239 TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
 240   ParseAssembly(
 241       "declare i1 @switch()\n"
 242       "\n"
 243       "define void @test() {\n"
 244       "entry:\n"
 245       "  %B = bitcast i8 undef to i8\n"
 246       "  br label %loop\n"
 247       "loop:\n"
 248       "  %A = bitcast i8 undef to i8\n"
 249       "  %x = call i1 @switch()\n"
 250       "  br i1 %x, label %loop, label %exit\n"
 251       "exit:\n"
 252       "  ret void\n"
 253       "}");
 254   ExpectPath(false);
 255 }
 256
 257 TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
 258   ParseAssembly(
 259       "declare i1 @switch()\n"
 260       "\n"
 261       "define void @test() {\n"
 262       "entry:\n"
 263       "  br label %loop\n"
 264       "loop:\n"
 265       "  %B = bitcast i8 undef to i8\n"
 266       "  %x = call i1 @switch()\n"
 267       "  br i1 %x, label %loop, label %exit\n"
 268       "exit:\n"
 269       "  %A = bitcast i8 undef to i8\n"
 270       "  ret void\n"
 271       "}");
 272   ExpectPath(false);
 273 }
 274
 275
 276 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
 277   ParseAssembly(
 278       "declare i1 @switch()\n"
 279       "\n"
 280       "define void @test() {\n"
 281       "entry:\n"
 282       "  br label %loop1\n"
 283       "loop1:\n"
 284       "  %A = bitcast i8 undef to i8\n"
 285       "  %x = call i1 @switch()\n"
 286       "  br i1 %x, label %loop1, label %loop1exit\n"
 287       "loop1exit:\n"
 288       "  br label %loop2\n"
 289       "loop2:\n"
 290       "  %B = bitcast i8 undef to i8\n"
 291       "  %y = call i1 @switch()\n"
 292       "  br i1 %x, label %loop2, label %loop2exit\n"
 293       "loop2exit:"
 294       "  ret void\n"
 295       "}");
 296   ExpectPath(true);
 297 }
 298
 299 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
 300   ParseAssembly(
 301       "declare i1 @switch()\n"
 302       "\n"
 303       "define void @test() {\n"
 304       "entry:\n"
 305       "  br label %loop1\n"
 306       "loop1:\n"
 307       "  %B = bitcast i8 undef to i8\n"
 308       "  %x = call i1 @switch()\n"
 309       "  br i1 %x, label %loop1, label %loop1exit\n"
 310       "loop1exit:\n"
 311       "  br label %loop2\n"
 312       "loop2:\n"
 313       "  %A = bitcast i8 undef to i8\n"
 314       "  %y = call i1 @switch()\n"
 315       "  br i1 %x, label %loop2, label %loop2exit\n"
 316       "loop2exit:"
 317       "  ret void\n"
 318       "}");
 319   ExpectPath(false);
 320 }
 321
 322 TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
 323   ParseAssembly(
 324       "declare i1 @switch()\n"
 325       "\n"
 326       "define void @test() {\n"
 327       "entry:\n"
 328       "  br label %outerloop3\n"
 329       "outerloop3:\n"
 330       "  br label %innerloop1\n"
 331       "innerloop1:\n"
 332       "  %B = bitcast i8 undef to i8\n"
 333       "  %x = call i1 @switch()\n"
 334       "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
 335       "innerloop1exit:\n"
 336       "  br label %innerloop2\n"
 337       "innerloop2:\n"
 338       "  %A = bitcast i8 undef to i8\n"
 339       "  %y = call i1 @switch()\n"
 340       "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
 341       "innerloop2exit:"
 342       "  ;; In outer loop3 now.\n"
 343       "  %z = call i1 @switch()\n"
 344       "  br i1 %z, label %outerloop3, label %exit\n"
 345       "exit:\n"
 346       "  ret void\n"
 347       "}");
 348   ExpectPath(true);
 349 }
 350
 351 static const char *BranchInsideLoopIR =
 352     "declare i1 @switch()\n"
 353     "\n"
 354     "define void @test() {\n"
 355     "entry:\n"
 356     "  br label %loop\n"
 357     "loop:\n"
 358     "  %x = call i1 @switch()\n"
 359     "  br i1 %x, label %nextloopblock, label %exit\n"
 360     "nextloopblock:\n"
 361     "  %y = call i1 @switch()\n"
 362     "  br i1 %y, label %left, label %right\n"
 363     "left:\n"
 364     "  %A = bitcast i8 undef to i8\n"
 365     "  br label %loop\n"
 366     "right:\n"
 367     "  %B = bitcast i8 undef to i8\n"
 368     "  br label %loop\n"
 369     "exit:\n"
 370     "  ret void\n"
 371     "}";
 372
 373 TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
 374   ParseAssembly(BranchInsideLoopIR);
 375   ExpectPath(true);
 376 }
 377
 378 TEST_F(IsPotentiallyReachableTest, ModifyTest) {
 379   ParseAssembly(BranchInsideLoopIR);
 380
 381   succ_iterator S = succ_begin(++M->getFunction("test")->begin());
 382   BasicBlock *OldBB = S[0];
 383   S[0] = S[1];
 384   ExpectPath(false);
 385   S[0] = OldBB;
 386   ExpectPath(true);
 387 }