508 lines · cpp
1//===- CFGTest.cpp - CFG tests --------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/CFG.h"10#include "llvm/ADT/SmallPtrSet.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/LegacyPassManager.h"18#include "llvm/IR/Module.h"19#include "llvm/InitializePasses.h"20#include "llvm/Support/ErrorHandling.h"21#include "llvm/Support/SourceMgr.h"22#include "gtest/gtest.h"23 24using namespace llvm;25 26namespace {27 28// This fixture assists in running the isPotentiallyReachable utility four ways29// and ensuring it produces the correct answer each time.30class IsPotentiallyReachableTest : public testing::Test {31protected:32 void ParseAssembly(const char *Assembly) {33 SMDiagnostic Error;34 M = parseAssemblyString(Assembly, Error, Context);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(errMsg.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 assert(ExclusionSet.empty());63 for (auto I = F->begin(), E = F->end(); I != E; ++I) {64 if (I->hasName() && I->getName().starts_with("excluded"))65 ExclusionSet.insert(&*I);66 }67 }68 69 void ExpectPath(bool ExpectedResult) {70 static char ID;71 class IsPotentiallyReachableTestPass : public FunctionPass {72 public:73 IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A,74 Instruction *B,75 SmallPtrSet<BasicBlock *, 4> ExclusionSet)76 : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B),77 ExclusionSet(ExclusionSet) {}78 79 static int initialize() {80 PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "",81 &ID, nullptr, true, true);82 PassRegistry::getPassRegistry()->registerPass(*PI, true);83 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());84 initializeDominatorTreeWrapperPassPass(85 *PassRegistry::getPassRegistry());86 return 0;87 }88 89 void getAnalysisUsage(AnalysisUsage &AU) const override {90 AU.setPreservesAll();91 AU.addRequired<LoopInfoWrapperPass>();92 AU.addRequired<DominatorTreeWrapperPass>();93 }94 95 bool runOnFunction(Function &F) override {96 if (!F.hasName() || F.getName() != "test")97 return false;98 99 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();100 DominatorTree *DT =101 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();102 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr),103 ExpectedResult);104 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr),105 ExpectedResult);106 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI),107 ExpectedResult);108 EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI),109 ExpectedResult);110 return false;111 }112 bool ExpectedResult;113 Instruction *A, *B;114 SmallPtrSet<BasicBlock *, 4> ExclusionSet;115 };116 117 static int initialize = IsPotentiallyReachableTestPass::initialize();118 (void)initialize;119 120 IsPotentiallyReachableTestPass *P =121 new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet);122 legacy::PassManager PM;123 PM.add(P);124 PM.run(*M);125 }126 127 LLVMContext Context;128 std::unique_ptr<Module> M;129 Instruction *A, *B;130 SmallPtrSet<BasicBlock *, 4> ExclusionSet;131};132 133}134 135TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {136 ParseAssembly(137 "define void @test() {\n"138 "entry:\n"139 " bitcast i8 undef to i8\n"140 " %B = bitcast i8 undef to i8\n"141 " bitcast i8 undef to i8\n"142 " bitcast i8 undef to i8\n"143 " %A = bitcast i8 undef to i8\n"144 " ret void\n"145 "}\n");146 ExpectPath(false);147}148 149TEST_F(IsPotentiallyReachableTest, SameBlockPath) {150 ParseAssembly(151 "define void @test() {\n"152 "entry:\n"153 " %A = bitcast i8 undef to i8\n"154 " bitcast i8 undef to i8\n"155 " bitcast i8 undef to i8\n"156 " %B = bitcast i8 undef to i8\n"157 " ret void\n"158 "}\n");159 ExpectPath(true);160}161 162TEST_F(IsPotentiallyReachableTest, SameBlockNoLoop) {163 ParseAssembly(164 "define void @test() {\n"165 "entry:\n"166 " br label %middle\n"167 "middle:\n"168 " %B = bitcast i8 undef to i8\n"169 " bitcast i8 undef to i8\n"170 " bitcast i8 undef to i8\n"171 " %A = bitcast i8 undef to i8\n"172 " br label %nextblock\n"173 "nextblock:\n"174 " ret void\n"175 "}\n");176 ExpectPath(false);177}178 179TEST_F(IsPotentiallyReachableTest, StraightNoPath) {180 ParseAssembly(181 "define void @test() {\n"182 "entry:\n"183 " %B = bitcast i8 undef to i8\n"184 " br label %exit\n"185 "exit:\n"186 " %A = bitcast i8 undef to i8\n"187 " ret void\n"188 "}");189 ExpectPath(false);190}191 192TEST_F(IsPotentiallyReachableTest, StraightPath) {193 ParseAssembly(194 "define void @test() {\n"195 "entry:\n"196 " %A = bitcast i8 undef to i8\n"197 " br label %exit\n"198 "exit:\n"199 " %B = bitcast i8 undef to i8\n"200 " ret void\n"201 "}");202 ExpectPath(true);203}204 205TEST_F(IsPotentiallyReachableTest, DestUnreachable) {206 ParseAssembly(207 "define void @test() {\n"208 "entry:\n"209 " br label %midblock\n"210 "midblock:\n"211 " %A = bitcast i8 undef to i8\n"212 " ret void\n"213 "unreachable:\n"214 " %B = bitcast i8 undef to i8\n"215 " br label %midblock\n"216 "}");217 ExpectPath(false);218}219 220TEST_F(IsPotentiallyReachableTest, BranchToReturn) {221 ParseAssembly(222 "define void @test(i1 %x) {\n"223 "entry:\n"224 " %A = bitcast i8 undef to i8\n"225 " br i1 %x, label %block1, label %block2\n"226 "block1:\n"227 " ret void\n"228 "block2:\n"229 " %B = bitcast i8 undef to i8\n"230 " ret void\n"231 "}");232 ExpectPath(true);233}234 235TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {236 ParseAssembly(237 "declare i1 @switch()\n"238 "\n"239 "define void @test() {\n"240 "entry:\n"241 " br label %loop\n"242 "loop:\n"243 " %B = bitcast i8 undef to i8\n"244 " %A = bitcast i8 undef to i8\n"245 " %x = call i1 @switch()\n"246 " br i1 %x, label %loop, label %exit\n"247 "exit:\n"248 " ret void\n"249 "}");250 ExpectPath(true);251}252 253TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {254 ParseAssembly(255 "declare i1 @switch()\n"256 "\n"257 "define void @test() {\n"258 "entry:\n"259 " %B = bitcast i8 undef to i8\n"260 " br label %loop\n"261 "loop:\n"262 " %A = bitcast i8 undef to i8\n"263 " %x = call i1 @switch()\n"264 " br i1 %x, label %loop, label %exit\n"265 "exit:\n"266 " ret void\n"267 "}");268 ExpectPath(false);269}270 271TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {272 ParseAssembly(273 "declare i1 @switch()\n"274 "\n"275 "define void @test() {\n"276 "entry:\n"277 " br label %loop\n"278 "loop:\n"279 " %B = bitcast i8 undef to i8\n"280 " %x = call i1 @switch()\n"281 " br i1 %x, label %loop, label %exit\n"282 "exit:\n"283 " %A = bitcast i8 undef to i8\n"284 " ret void\n"285 "}");286 ExpectPath(false);287}288 289 290TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {291 ParseAssembly(292 "declare i1 @switch()\n"293 "\n"294 "define void @test() {\n"295 "entry:\n"296 " br label %loop1\n"297 "loop1:\n"298 " %A = bitcast i8 undef to i8\n"299 " %x = call i1 @switch()\n"300 " br i1 %x, label %loop1, label %loop1exit\n"301 "loop1exit:\n"302 " br label %loop2\n"303 "loop2:\n"304 " %B = bitcast i8 undef to i8\n"305 " %y = call i1 @switch()\n"306 " br i1 %x, label %loop2, label %loop2exit\n"307 "loop2exit:"308 " ret void\n"309 "}");310 ExpectPath(true);311}312 313TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {314 ParseAssembly(315 "declare i1 @switch()\n"316 "\n"317 "define void @test() {\n"318 "entry:\n"319 " br label %loop1\n"320 "loop1:\n"321 " %B = bitcast i8 undef to i8\n"322 " %x = call i1 @switch()\n"323 " br i1 %x, label %loop1, label %loop1exit\n"324 "loop1exit:\n"325 " br label %loop2\n"326 "loop2:\n"327 " %A = bitcast i8 undef to i8\n"328 " %y = call i1 @switch()\n"329 " br i1 %x, label %loop2, label %loop2exit\n"330 "loop2exit:"331 " ret void\n"332 "}");333 ExpectPath(false);334}335 336TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {337 ParseAssembly(338 "declare i1 @switch()\n"339 "\n"340 "define void @test() {\n"341 "entry:\n"342 " br label %outerloop3\n"343 "outerloop3:\n"344 " br label %innerloop1\n"345 "innerloop1:\n"346 " %B = bitcast i8 undef to i8\n"347 " %x = call i1 @switch()\n"348 " br i1 %x, label %innerloop1, label %innerloop1exit\n"349 "innerloop1exit:\n"350 " br label %innerloop2\n"351 "innerloop2:\n"352 " %A = bitcast i8 undef to i8\n"353 " %y = call i1 @switch()\n"354 " br i1 %x, label %innerloop2, label %innerloop2exit\n"355 "innerloop2exit:"356 " ;; In outer loop3 now.\n"357 " %z = call i1 @switch()\n"358 " br i1 %z, label %outerloop3, label %exit\n"359 "exit:\n"360 " ret void\n"361 "}");362 ExpectPath(true);363}364 365static const char *BranchInsideLoopIR =366 "declare i1 @switch()\n"367 "\n"368 "define void @test() {\n"369 "entry:\n"370 " br label %loop\n"371 "loop:\n"372 " %x = call i1 @switch()\n"373 " br i1 %x, label %nextloopblock, label %exit\n"374 "nextloopblock:\n"375 " %y = call i1 @switch()\n"376 " br i1 %y, label %left, label %right\n"377 "left:\n"378 " %A = bitcast i8 undef to i8\n"379 " br label %loop\n"380 "right:\n"381 " %B = bitcast i8 undef to i8\n"382 " br label %loop\n"383 "exit:\n"384 " ret void\n"385 "}";386 387TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {388 ParseAssembly(BranchInsideLoopIR);389 ExpectPath(true);390}391 392TEST_F(IsPotentiallyReachableTest, ModifyTest) {393 ParseAssembly(BranchInsideLoopIR);394 395 succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());396 BasicBlock *OldBB = S[0];397 S[0] = S[1];398 ExpectPath(false);399 S[0] = OldBB;400 ExpectPath(true);401}402 403TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) {404 ParseAssembly("define void @test() {\n"405 "entry:\n"406 " %A = bitcast i8 undef to i8\n"407 " ret void\n"408 "not.reachable:\n"409 " %B = bitcast i8 undef to i8\n"410 " ret void\n"411 "}");412 ExpectPath(false);413}414 415TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) {416 ParseAssembly("define void @test() {\n"417 "entry:\n"418 " ret void\n"419 "not.reachable.1:\n"420 " %A = bitcast i8 undef to i8\n"421 " br label %not.reachable.2\n"422 "not.reachable.2:\n"423 " %B = bitcast i8 undef to i8\n"424 " ret void\n"425 "}");426 ExpectPath(true);427}428 429TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) {430 ParseAssembly("define void @test() {\n"431 "entry:\n"432 " ret void\n"433 "not.reachable.1:\n"434 " %B = bitcast i8 undef to i8\n"435 " br label %not.reachable.2\n"436 "not.reachable.2:\n"437 " %A = bitcast i8 undef to i8\n"438 " ret void\n"439 "}");440 ExpectPath(false);441}442 443TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) {444 ParseAssembly("define void @test() {\n"445 "entry:\n"446 " %A = bitcast i8 undef to i8\n"447 " br label %excluded\n"448 "excluded:\n"449 " br label %exit\n"450 "exit:\n"451 " %B = bitcast i8 undef to i8\n"452 " ret void\n"453 "}");454 ExpectPath(false);455}456 457TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) {458 ParseAssembly("declare i1 @switch()\n"459 "\n"460 "define void @test() {\n"461 "entry:\n"462 " %x = call i1 @switch()\n"463 " %A = bitcast i8 undef to i8\n"464 " br i1 %x, label %excluded.1, label %excluded.2\n"465 "excluded.1:\n"466 " br label %exit\n"467 "excluded.2:\n"468 " br label %exit\n"469 "exit:\n"470 " %B = bitcast i8 undef to i8\n"471 " ret void\n"472 "}");473 ExpectPath(false);474}475 476TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) {477 ParseAssembly("declare i1 @switch()\n"478 "\n"479 "define void @test() {\n"480 "entry:\n"481 " %x = call i1 @switch()\n"482 " %A = bitcast i8 undef to i8\n"483 " br i1 %x, label %excluded, label %diamond\n"484 "excluded:\n"485 " br label %exit\n"486 "diamond:\n"487 " br label %exit\n"488 "exit:\n"489 " %B = bitcast i8 undef to i8\n"490 " ret void\n"491 "}");492 ExpectPath(true);493}494 495TEST_F(IsPotentiallyReachableTest, UnreachableToReachable) {496 ParseAssembly("define void @test() {\n"497 "entry:\n"498 " br label %exit\n"499 "unreachableblock:\n"500 " %A = bitcast i8 undef to i8\n"501 " br label %exit\n"502 "exit:\n"503 " %B = bitcast i8 undef to i8\n"504 " ret void\n"505 "}");506 ExpectPath(true);507}508