127 lines · cpp
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-exception6//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 24namespace llvm {25namespace {26 27struct 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 47TEST_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 %preexit55 // ... ;;< Add lots of cases to stress the heuristic.56 // ]57 // preexit:58 // unreachable59 // exit:60 // ret void61 // }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 the80 // switch have the *same* destination block ("preexit"), shouldn't it be the81 // 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 86TEST_F(BranchProbabilityInfoTest, SwapProbabilities) {87 StringRef Assembly = R"(88 define void @f() {89 entry:90 br label %loop91 92 loop:93 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]94 %iv.next = add i32 %iv, 195 %cond = icmp slt i32 %iv.next, 1096 br i1 %cond, label %exit, label %loop97 98 exit:99 ret void100 }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 swapping113 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 edges121 EXPECT_EQ(ProbEdge0, BPI->getEdgeProbability(LoopHeaderBB, 1U));122 EXPECT_EQ(ProbEdge1, BPI->getEdgeProbability(LoopHeaderBB, 0U));123}124 125} // end anonymous namespace126} // end namespace llvm127