llvm/unittests/Analysis/BranchProbabilityInfoTest.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-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