1 //===- BranchProbabilityInfoTest.cpp - BranchProbabilityInfo unit 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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/BranchProbabilityInfo.h" 10 #include "llvm/Analysis/LoopInfo.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/BasicBlock.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/Dominators.h" 15 #include "llvm/IR/Function.h" 16 #include "llvm/IR/Instructions.h" 17 #include "llvm/IR/LLVMContext.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/Support/DataTypes.h" 20 #include "llvm/Support/SourceMgr.h" 21 #include "llvm/Support/raw_ostream.h" 22 #include "gtest/gtest.h" 23 24 namespace llvm { 25 namespace { 26 27 struct BranchProbabilityInfoTest : public testing::Test { 28 std::unique_ptr<BranchProbabilityInfo> BPI; 29 std::unique_ptr<DominatorTree> DT; 30 std::unique_ptr<LoopInfo> LI; 31 LLVMContext C; 32 33 BranchProbabilityInfo &buildBPI(Function &F) { 34 DT.reset(new DominatorTree(F)); 35 LI.reset(new LoopInfo(*DT)); 36 BPI.reset(new BranchProbabilityInfo(F, *LI)); 37 return *BPI; 38 } 39 40 std::unique_ptr<Module> makeLLVMModule() { 41 const char *ModuleString = "define void @f() { exit: ret void }\n"; 42 SMDiagnostic Err; 43 return parseAssemblyString(ModuleString, Err, C); 44 } 45 }; 46 47 TEST_F(BranchProbabilityInfoTest, StressUnreachableHeuristic) { 48 auto M = makeLLVMModule(); 49 Function *F = M->getFunction("f"); 50 51 // define void @f() { 52 // entry: 53 // switch i32 poison, label %exit, [ 54 // i32 0, label %preexit 55 // ... ;;< Add lots of cases to stress the heuristic. 56 // ] 57 // preexit: 58 // unreachable 59 // exit: 60 // ret void 61 // } 62 63 auto *ExitBB = &F->back(); 64 auto *EntryBB = BasicBlock::Create(C, "entry", F, /*insertBefore=*/ExitBB); 65 66 auto *PreExitBB = 67 BasicBlock::Create(C, "preexit", F, /*insertBefore=*/ExitBB); 68 new UnreachableInst(C, PreExitBB); 69 70 unsigned NumCases = 4096; 71 auto *I32 = IntegerType::get(C, 32); 72 auto *Poison = PoisonValue::get(I32); 73 auto *Switch = SwitchInst::Create(Poison, ExitBB, NumCases, EntryBB); 74 for (unsigned I = 0; I < NumCases; ++I) 75 Switch->addCase(ConstantInt::get(I32, I), PreExitBB); 76 77 BranchProbabilityInfo &BPI = buildBPI(*F); 78 79 // FIXME: This doesn't seem optimal. Since all of the cases handled by the 80 // switch have the *same* destination block ("preexit"), shouldn't it be the 81 // hot one? I'd expect the results to be reversed here... 82 EXPECT_FALSE(BPI.isEdgeHot(EntryBB, PreExitBB)); 83 EXPECT_TRUE(BPI.isEdgeHot(EntryBB, ExitBB)); 84 } 85 86 TEST_F(BranchProbabilityInfoTest, SwapProbabilities) { 87 StringRef Assembly = R"( 88 define void @f() { 89 entry: 90 br label %loop 91 92 loop: 93 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] 94 %iv.next = add i32 %iv, 1 95 %cond = icmp slt i32 %iv.next, 10 96 br i1 %cond, label %exit, label %loop 97 98 exit: 99 ret void 100 } 101 )"; 102 LLVMContext Context; 103 SMDiagnostic Error; 104 auto M = parseAssemblyString(Assembly, Error, Context); 105 ASSERT_TRUE(M) << "Bad assembly?"; 106 107 Function *F = M->getFunction("f"); 108 auto *LoopHeaderBB = F->front().getSingleSuccessor(); 109 ASSERT_TRUE(LoopHeaderBB != nullptr); 110 BranchInst *Branch = dyn_cast<BranchInst>(LoopHeaderBB->getTerminator()); 111 ASSERT_TRUE(Branch != nullptr); 112 // Save the probabilities before successors swapping 113 BranchProbabilityInfo *BPI = &buildBPI(*F); 114 auto ProbEdge0 = BPI->getEdgeProbability(LoopHeaderBB, 0U); 115 auto ProbEdge1 = BPI->getEdgeProbability(LoopHeaderBB, 1U); 116 EXPECT_LT(ProbEdge0, ProbEdge1); 117 118 Branch->swapSuccessors(); 119 BPI->swapSuccEdgesProbabilities(LoopHeaderBB); 120 // TODO: Check the probabilities are swapped as well as the edges 121 EXPECT_EQ(ProbEdge0, BPI->getEdgeProbability(LoopHeaderBB, 1U)); 122 EXPECT_EQ(ProbEdge1, BPI->getEdgeProbability(LoopHeaderBB, 0U)); 123 } 124 125 } // end anonymous namespace 126 } // end namespace llvm 127