llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp

   1 //===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
   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/Transforms/Utils/BasicBlockUtils.h"
  10 #include "llvm/Analysis/AssumptionCache.h"
  11 #include "llvm/Analysis/BasicAliasAnalysis.h"
  12 #include "llvm/Analysis/BlockFrequencyInfo.h"
  13 #include "llvm/Analysis/BranchProbabilityInfo.h"
  14 #include "llvm/Analysis/CFG.h"
  15 #include "llvm/Analysis/DomTreeUpdater.h"
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/Analysis/MemorySSA.h"
  18 #include "llvm/Analysis/MemorySSAUpdater.h"
  19 #include "llvm/Analysis/PostDominators.h"
  20 #include "llvm/Analysis/TargetLibraryInfo.h"
  21 #include "llvm/AsmParser/Parser.h"
  22 #include "llvm/IR/BasicBlock.h"
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/IR/LLVMContext.h"
  25 #include "llvm/Support/SourceMgr.h"
  26 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
  27 #include "gtest/gtest.h"
  28
  29 using namespace llvm;
  30
  31 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
  32   SMDiagnostic Err;
  33   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
  34   if (!Mod)
  35     Err.print("BasicBlockUtilsTests", errs());
  36   return Mod;
  37 }
  38
  39 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
  40   for (BasicBlock &BB : F)
  41     if (BB.getName() == Name)
  42       return &BB;
  43   llvm_unreachable("Expected to find basic block!");
  44 }
  45
  46 TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
  47   LLVMContext C;
  48   std::unique_ptr<Module> M = parseIR(C, R"IR(
  49 define i32 @has_unreachable(i1 %cond) {
  50 entry:
  51   br i1 %cond, label %bb0, label %bb1
  52 bb0:
  53   br label %bb1
  54 bb1:
  55   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
  56   ret i32 %phi
  57 bb2:
  58   ret i32 42
  59 }
  60 )IR");
  61   Function *F = M->getFunction("has_unreachable");
  62   DominatorTree DT(*F);
  63   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
  64
  65   EXPECT_EQ(F->size(), (size_t)4);
  66   bool Result = EliminateUnreachableBlocks(*F, &DTU);
  67   EXPECT_TRUE(Result);
  68   EXPECT_EQ(F->size(), (size_t)3);
  69   EXPECT_TRUE(DT.verify());
  70 }
  71
  72 TEST(BasicBlockUtils, SplitEdge_ex1) {
  73   LLVMContext C;
  74   std::unique_ptr<Module> M = parseIR(C, R"IR(
  75 define void @foo(i1 %cond0) {
  76 entry:
  77   br i1 %cond0, label %bb0, label %bb1
  78 bb0:
  79  %0 = mul i32 1, 2
  80   br label %bb1
  81 bb1:
  82   br label %bb2
  83 bb2:
  84   ret void
  85 }
  86 )IR");
  87   Function *F = M->getFunction("foo");
  88   DominatorTree DT(*F);
  89   BasicBlock *SrcBlock;
  90   BasicBlock *DestBlock;
  91   BasicBlock *NewBB;
  92
  93   SrcBlock = getBasicBlockByName(*F, "entry");
  94   DestBlock = getBasicBlockByName(*F, "bb0");
  95   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
  96
  97   EXPECT_TRUE(DT.verify());
  98   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
  99   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
 100   EXPECT_EQ(NewBB->getParent(), F);
 101
 102   bool BBFlag = false;
 103   for (BasicBlock &BB : *F) {
 104     if (BB.getName() == NewBB->getName()) {
 105       BBFlag = true;
 106     }
 107   }
 108   EXPECT_TRUE(BBFlag);
 109 }
 110
 111 TEST(BasicBlockUtils, SplitEdge_ex2) {
 112   LLVMContext C;
 113   std::unique_ptr<Module> M = parseIR(C, R"IR(
 114 define void @foo() {
 115 bb0:
 116   br label %bb2
 117 bb1:
 118   br label %bb2
 119 bb2:
 120   ret void
 121 }
 122 )IR");
 123   Function *F = M->getFunction("foo");
 124   DominatorTree DT(*F);
 125
 126   BasicBlock *SrcBlock;
 127   BasicBlock *DestBlock;
 128   BasicBlock *NewBB;
 129
 130   SrcBlock = getBasicBlockByName(*F, "bb0");
 131   DestBlock = getBasicBlockByName(*F, "bb2");
 132   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
 133
 134   EXPECT_TRUE(DT.verify());
 135   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
 136   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
 137   EXPECT_EQ(NewBB->getParent(), F);
 138
 139   bool BBFlag = false;
 140   for (BasicBlock &BB : *F) {
 141     if (BB.getName() == NewBB->getName()) {
 142       BBFlag = true;
 143     }
 144   }
 145   EXPECT_TRUE(BBFlag);
 146 }
 147
 148 TEST(BasicBlockUtils, SplitEdge_ex3) {
 149   LLVMContext C;
 150   std::unique_ptr<Module> M = parseIR(C, R"IR(
 151 define i32 @foo(i32 %n) {
 152 entry:
 153  br label %header
 154 header:
 155  %sum.02 = phi i32 [ 0, %entry ], [ %sum.1, %bb3 ]
 156  %0 = phi i32 [ 0, %entry ], [ %4, %bb3 ]
 157  %1 = icmp slt i32 %0, %n
 158  br i1 %1, label %bb0, label %bb1
 159 bb0:
 160   %2 = add nsw i32 %sum.02, 2
 161   br label %bb2
 162 bb1:
 163   %3 = add nsw i32 %sum.02, 1
 164   br label %bb2
 165 bb2:
 166   %sum.1 = phi i32 [ %2, %bb0 ], [ %3, %bb1 ]
 167   br label %bb3
 168 bb3:
 169   %4 = add nsw i32 %0, 1
 170   %5 = icmp slt i32 %4, 100
 171   br i1 %5, label %header, label %bb4
 172 bb4:
 173  %sum.0.lcssa = phi i32 [ %sum.1, %bb3 ]
 174  ret i32 %sum.0.lcssa
 175 }
 176 )IR");
 177   Function *F = M->getFunction("foo");
 178   DominatorTree DT(*F);
 179
 180   LoopInfo LI(DT);
 181
 182   DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128");
 183   TargetLibraryInfoImpl TLII;
 184   TargetLibraryInfo TLI(TLII);
 185   AssumptionCache AC(*F);
 186   AAResults AA(TLI);
 187
 188   BasicAAResult BAA(DL, *F, TLI, AC, &DT);
 189   AA.addAAResult(BAA);
 190
 191   MemorySSA MSSA(*F, &AA, &DT);
 192   MemorySSAUpdater Updater(&MSSA);
 193
 194   BasicBlock *SrcBlock;
 195   BasicBlock *DestBlock;
 196   BasicBlock *NewBB;
 197
 198   SrcBlock = getBasicBlockByName(*F, "header");
 199   DestBlock = getBasicBlockByName(*F, "bb0");
 200   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &Updater);
 201
 202   Updater.getMemorySSA()->verifyMemorySSA();
 203   EXPECT_TRUE(DT.verify());
 204   EXPECT_NE(LI.getLoopFor(SrcBlock), nullptr);
 205   EXPECT_NE(LI.getLoopFor(DestBlock), nullptr);
 206   EXPECT_NE(LI.getLoopFor(NewBB), nullptr);
 207   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
 208   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
 209   EXPECT_EQ(NewBB->getParent(), F);
 210
 211   bool BBFlag = false;
 212   for (BasicBlock &BB : *F) {
 213     if (BB.getName() == NewBB->getName()) {
 214       BBFlag = true;
 215     }
 216   }
 217   EXPECT_TRUE(BBFlag);
 218 }
 219
 220 TEST(BasicBlockUtils, SplitEdge_ex4) {
 221   LLVMContext C;
 222   std::unique_ptr<Module> M = parseIR(C, R"IR(
 223 define void @bar(i32 %cond) personality i8 0 {
 224 entry:
 225   switch i32 %cond, label %exit [
 226     i32 -1, label %continue
 227     i32 0, label %continue
 228     i32 1, label %continue_alt
 229     i32 2, label %continue_alt
 230   ]
 231 exit:
 232   ret void
 233 continue:
 234   invoke void @sink() to label %normal unwind label %exception
 235 continue_alt:
 236   invoke void @sink_alt() to label %normal unwind label %exception
 237 exception:
 238   %cleanup = landingpad i8 cleanup
 239   br label %trivial-eh-handler
 240 trivial-eh-handler:
 241   call void @sideeffect(i32 1)
 242   br label %normal
 243 normal:
 244   call void @sideeffect(i32 0)
 245   ret void
 246 }
 247
 248 declare void @sideeffect(i32)
 249 declare void @sink() cold
 250 declare void @sink_alt() cold
 251 )IR");
 252   Function *F = M->getFunction("bar");
 253
 254   DominatorTree DT(*F);
 255
 256   LoopInfo LI(DT);
 257
 258   TargetLibraryInfoImpl TLII;
 259   TargetLibraryInfo TLI(TLII);
 260
 261   AAResults AA(TLI);
 262
 263   MemorySSA MSSA(*F, &AA, &DT);
 264   MemorySSAUpdater MSSAU(&MSSA);
 265
 266   BasicBlock *SrcBlock;
 267   BasicBlock *DestBlock;
 268
 269   SrcBlock = getBasicBlockByName(*F, "continue");
 270   DestBlock = getBasicBlockByName(*F, "exception");
 271
 272   unsigned SuccNum = GetSuccessorNumber(SrcBlock, DestBlock);
 273   Instruction *LatchTerm = SrcBlock->getTerminator();
 274
 275   const CriticalEdgeSplittingOptions Options =
 276       CriticalEdgeSplittingOptions(&DT, &LI, &MSSAU);
 277
 278   // Check that the following edge is both critical and the destination block is
 279   // an exception block. These must be handled differently by SplitEdge
 280   bool CriticalEdge =
 281       isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges);
 282   EXPECT_TRUE(CriticalEdge);
 283
 284   bool Ehpad = DestBlock->isEHPad();
 285   EXPECT_TRUE(Ehpad);
 286
 287   BasicBlock *NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &MSSAU, "");
 288
 289   MSSA.verifyMemorySSA();
 290   EXPECT_TRUE(DT.verify());
 291   EXPECT_NE(NewBB, nullptr);
 292   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
 293   EXPECT_EQ(NewBB, SrcBlock->getTerminator()->getSuccessor(SuccNum));
 294   EXPECT_EQ(NewBB->getParent(), F);
 295
 296   bool BBFlag = false;
 297   for (BasicBlock &BB : *F) {
 298     if (BB.getName() == NewBB->getName()) {
 299       BBFlag = true;
 300       break;
 301     }
 302   }
 303   EXPECT_TRUE(BBFlag);
 304 }
 305
 306 TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) {
 307   LLVMContext C;
 308   std::unique_ptr<Module> M = parseIR(C, R"IR(
 309 define void @foo() {
 310 bb0:
 311  %0 = mul i32 1, 2
 312   br label %bb2
 313 bb1:
 314   br label %bb3
 315 bb2:
 316   %1 = phi  i32 [ %0, %bb0 ]
 317   br label %bb3
 318 bb3:
 319   ret void
 320 }
 321 )IR");
 322   Function *F = M->getFunction("foo");
 323   DominatorTree DT(*F);
 324
 325   BasicBlock *DestBlock;
 326   BasicBlock *NewBB;
 327
 328   DestBlock = getBasicBlockByName(*F, "bb2");
 329
 330   NewBB = DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
 331                                            "test");
 332
 333   PHINode *PN = dyn_cast<PHINode>(&(DestBlock->front()));
 334   EXPECT_EQ(PN->getIncomingBlock(0), NewBB);
 335   EXPECT_EQ(NewBB->getName(), "test");
 336   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
 337   EXPECT_EQ(DestBlock->getSinglePredecessor(), NewBB);
 338 }
 339
 340 #ifndef NDEBUG
 341 TEST(BasicBlockUtils, splitBasicBlockBefore_ex2) {
 342   LLVMContext C;
 343   std::unique_ptr<Module> M = parseIR(C, R"IR(
 344 define void @foo() {
 345 bb0:
 346  %0 = mul i32 1, 2
 347   br label %bb2
 348 bb1:
 349   br label %bb2
 350 bb2:
 351   %1 = phi  i32 [ %0, %bb0 ], [ 1, %bb1 ]
 352   br label %bb3
 353 bb3:
 354   ret void
 355 }
 356 )IR");
 357   Function *F = M->getFunction("foo");
 358   DominatorTree DT(*F);
 359
 360   BasicBlock *DestBlock = getBasicBlockByName(*F, "bb2");
 361
 362   ASSERT_DEATH(
 363       {
 364         DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
 365                                          "test");
 366       },
 367       "cannot split on multi incoming phis");
 368 }
 369 #endif
 370
 371 TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
 372   LLVMContext C;
 373   std::unique_ptr<Module> M = parseIR(C, R"IR(
 374 define i32 @no_unreachable(i1 %cond) {
 375 entry:
 376   br i1 %cond, label %bb0, label %bb1
 377 bb0:
 378   br label %bb1
 379 bb1:
 380   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
 381   ret i32 %phi
 382 }
 383 )IR");
 384   Function *F = M->getFunction("no_unreachable");
 385   DominatorTree DT(*F);
 386   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 387
 388   EXPECT_EQ(F->size(), (size_t)3);
 389   bool Result = EliminateUnreachableBlocks(*F, &DTU);
 390   EXPECT_FALSE(Result);
 391   EXPECT_EQ(F->size(), (size_t)3);
 392   EXPECT_TRUE(DT.verify());
 393 }
 394
 395 TEST(BasicBlockUtils, SplitBlockPredecessors) {
 396   LLVMContext C;
 397   std::unique_ptr<Module> M = parseIR(C, R"IR(
 398 define i32 @basic_func(i1 %cond) {
 399 entry:
 400   br i1 %cond, label %bb0, label %bb1
 401 bb0:
 402   br label %bb1
 403 bb1:
 404   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
 405   ret i32 %phi
 406 }
 407 )IR");
 408   Function *F = M->getFunction("basic_func");
 409   DominatorTree DT(*F);
 410
 411   // Make sure the dominator tree is properly updated if calling this on the
 412   // entry block.
 413   SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
 414   EXPECT_TRUE(DT.verify());
 415 }
 416
 417 TEST(BasicBlockUtils, SplitCriticalEdge) {
 418   LLVMContext C;
 419   std::unique_ptr<Module> M = parseIR(C, R"IR(
 420 define void @crit_edge(i1 %cond0, i1 %cond1) {
 421 entry:
 422   br i1 %cond0, label %bb0, label %bb1
 423 bb0:
 424   br label %bb1
 425 bb1:
 426   br label %bb2
 427 bb2:
 428   ret void
 429 }
 430 )IR");
 431   Function *F = M->getFunction("crit_edge");
 432   DominatorTree DT(*F);
 433   PostDominatorTree PDT(*F);
 434
 435   CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT);
 436   EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
 437   EXPECT_TRUE(DT.verify());
 438   EXPECT_TRUE(PDT.verify());
 439 }
 440
 441 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdgesIgnorePHIs) {
 442   LLVMContext C;
 443   std::unique_ptr<Module> M = parseIR(C, R"IR(
 444 define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
 445 entry:
 446   indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
 447 bb0:
 448   br i1 %cond0, label %bb1, label %bb2
 449 bb1:
 450   %p = phi i32 [0, %bb0], [0, %entry]
 451   br i1 %cond1, label %bb3, label %bb4
 452 bb2:
 453   ret void
 454 bb3:
 455   ret void
 456 bb4:
 457   ret void
 458 }
 459 )IR");
 460   Function *F = M->getFunction("crit_edge");
 461   DominatorTree DT(*F);
 462   LoopInfo LI(DT);
 463   BranchProbabilityInfo BPI(*F, LI);
 464   BlockFrequencyInfo BFI(*F, BPI, LI);
 465
 466   ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/true,
 467                                            &BPI, &BFI));
 468
 469   // Check that successors of the split block get their probability correct.
 470   BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
 471   BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
 472   ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
 473   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
 474   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
 475
 476   // bb2 has no PHI, so we shouldn't split bb0 -> bb2
 477   BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
 478   ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
 479   EXPECT_EQ(BB0->getTerminator()->getSuccessor(1),
 480             getBasicBlockByName(*F, "bb2"));
 481 }
 482
 483 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdges) {
 484   LLVMContext C;
 485   std::unique_ptr<Module> M = parseIR(C, R"IR(
 486 define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
 487 entry:
 488   indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
 489 bb0:
 490   br i1 %cond0, label %bb1, label %bb2
 491 bb1:
 492   %p = phi i32 [0, %bb0], [0, %entry]
 493   br i1 %cond1, label %bb3, label %bb4
 494 bb2:
 495   ret void
 496 bb3:
 497   ret void
 498 bb4:
 499   ret void
 500 }
 501 )IR");
 502   Function *F = M->getFunction("crit_edge");
 503   DominatorTree DT(*F);
 504   LoopInfo LI(DT);
 505   BranchProbabilityInfo BPI(*F, LI);
 506   BlockFrequencyInfo BFI(*F, BPI, LI);
 507
 508   ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/false,
 509                                            &BPI, &BFI));
 510
 511   // Check that successors of the split block get their probability correct.
 512   BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
 513   BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
 514   ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
 515   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
 516   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
 517
 518   // Should split, resulting in:
 519   //   bb0 -> bb2.clone; bb2 -> split1; bb2.clone -> split,
 520   BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
 521   ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
 522   BasicBlock *BB2Clone = BB0->getTerminator()->getSuccessor(1);
 523   BasicBlock *BB2 = getBasicBlockByName(*F, "bb2");
 524   EXPECT_NE(BB2Clone, BB2);
 525   ASSERT_EQ(1u, BB2->getTerminator()->getNumSuccessors());
 526   ASSERT_EQ(1u, BB2Clone->getTerminator()->getNumSuccessors());
 527   EXPECT_EQ(BB2->getTerminator()->getSuccessor(0),
 528             BB2Clone->getTerminator()->getSuccessor(0));
 529 }
 530
 531 TEST(BasicBlockUtils, SetEdgeProbability) {
 532   LLVMContext C;
 533   std::unique_ptr<Module> M = parseIR(C, R"IR(
 534 define void @edge_probability(i32 %0) {
 535 entry:
 536 switch i32 %0, label %LD [
 537   i32 700, label %L0
 538   i32 701, label %L1
 539   i32 702, label %L2
 540   i32 703, label %L3
 541   i32 704, label %L4
 542   i32 705, label %L5
 543   i32 706, label %L6
 544   i32 707, label %L7
 545   i32 708, label %L8
 546   i32 709, label %L9
 547   i32 710, label %L10
 548   i32 711, label %L11
 549   i32 712, label %L12
 550   i32 713, label %L13
 551   i32 714, label %L14
 552   i32 715, label %L15
 553   i32 716, label %L16
 554   i32 717, label %L17
 555   i32 718, label %L18
 556   i32 719, label %L19
 557 ], !prof !{!"branch_weights", i32 1, i32 1, i32 1, i32 1, i32 1, i32 451, i32 1,
 558            i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1,
 559            i32 1, i32 1, i32 1, i32 1, i32 1}
 560 LD:
 561   unreachable
 562 L0:
 563   ret void
 564 L1:
 565   ret void
 566 L2:
 567   ret void
 568 L3:
 569   ret void
 570 L4:
 571   ret void
 572 L5:
 573   ret void
 574 L6:
 575   ret void
 576 L7:
 577   ret void
 578 L8:
 579   ret void
 580 L9:
 581   ret void
 582 L10:
 583   ret void
 584 L11:
 585   ret void
 586 L12:
 587   ret void
 588 L13:
 589   ret void
 590 L14:
 591   ret void
 592 L15:
 593   ret void
 594 L16:
 595   ret void
 596 L17:
 597   ret void
 598 L18:
 599   ret void
 600 L19:
 601   ret void
 602 }
 603 )IR");
 604   Function *F = M->getFunction("edge_probability");
 605   DominatorTree DT(*F);
 606   LoopInfo LI(DT);
 607   BranchProbabilityInfo BPI(*F, LI);
 608
 609   // Check that the unreachable block has the minimal probability.
 610   const BasicBlock *EntryBB = getBasicBlockByName(*F, "entry");
 611   const BasicBlock *UnreachableBB = getBasicBlockByName(*F, "LD");
 612   EXPECT_EQ(BranchProbability::getRaw(1),
 613             BPI.getEdgeProbability(EntryBB, UnreachableBB));
 614 }