[GuardWidening] Widen guards with conditions of frequently taken dominated branches

[mkazantsev]

Summary

If there is a frequently taken branch dominated by a guard, and its condition is available
at the point of the guard, we can widen guard with condition of this branch and convert
the branch into unconditional:

guard(cond1)
if (cond2) {
  // taken in 99.9% cases
  // do something
} else {
  // do something else    
}

Converts to

guard(cond1 && cond2)
// do something

[mkazantsev]

Fixed indents.

[fedor.sergeev]

lib/Transforms/Scalar/GuardWidening.cpp

291

What about adding some STATISTICS here?
Would be useful for experiments with this new mode...

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

291

Will do.

[reames]

lib/Transforms/Scalar/GuardWidening.cpp

71

This definitely needs to default to false initially. :)

78

Er, how is a frequency 1000? I would expect a percentage here. Are you using N-to-1 or (N-1)/N instead? If so, the comment on the flag needs updated.

274

Separate whitespace change please.

384

Just use conditional early return followed by unchecked cast<BranchInst>

393

Same as above.

408

Better to move this check into the caller.

test/Transforms/GuardWidening/widen-frequent-branches.ll

11

Please add at least some tests for CFGs other than diamonds. Triangles and simple early returns are also good.

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

71

Agreed. :)

78

I'm using (N-1)/N. Will update the comment to make it clear.

408

No, it is here because we should not remove br instructions. We don't want the caller to know about possible types of guards.

[reames]

lib/Transforms/Scalar/GuardWidening.cpp

408

I was suggesting that we only call this function for guards, not for branches. Calling a function called "eliminateGuard" on a branch seems a bit odd.

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

408

Here (and in other places like "getGuardCondition") we assume that the word "guard" has a wider definition than llvm.experimental.guard intrinsic. A branch can be a guard as well in some circumstances.

[fedor.sergeev]

lib/Transforms/Scalar/GuardWidening.cpp

408

Technically this is widening of a guard with a branch/guard condition.
And in this patch we are not treating dominated condition exactly as a guard.
And elimination happens for branches and guards differently.
So I definitely see a merit in what Philip suggests.

Alternatively you might call it eliminateBranchConditionOrGuard ;)

[mkazantsev]

Yeah, I see now why this naming confused you... I will try to find the better naming for that.

[reames]

LGTM

lib/Transforms/Scalar/GuardWidening.cpp

305

Add assert that the branch condition is a constant.

lib/Transforms/Scalar/GuardWidening.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/GuardWidening.h"
 #include <functional>
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "guard-widening"
 
 STATISTIC(GuardsEliminated, "Number of eliminated guards");
+STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
+
+static cl::opt<bool> WidenFrequentBranches(
+    "guard-widening-widen-frequent-branches", cl::Hidden,
+    cl::desc("Widen conditions of explicit branches into dominating guards in "
+             "case if their taken frequency exceeds threshold set by "
+             "guard-widening-frequent-branch-threshold option"),
+    cl::init(false));
+
+static cl::opt<unsigned> FrequentBranchThreshold(
+    "guard-widening-frequent-branch-threshold", cl::Hidden,
+    cl::desc("When WidenFrequentBranches is set to true, this option is used "
+             "to determine which branches are frequently taken. The criteria "
+             "that a branch is taken more often than "
+             "((FrequentBranchThreshold - 1) / FrequentBranchThreshold), then "
+             "it is considered frequently taken"),
+    cl::init(1000));
 
 namespace {
 
 class GuardWideningImpl {
   DominatorTree &DT;
   PostDominatorTree *PDT;
   LoopInfo &LI;
+  BranchProbabilityInfo *BPI;
 
   /// Together, these describe the region of interest.  This might be all of
   /// the blocks within a function, or only a given loop's blocks and preheader.
   DomTreeNode *Root;
   std::function<bool(BasicBlock*)> BlockFilter;
 
   /// The set of guards whose conditions have been widened into dominating
   /// guards.
void widenGuard(Instruction *ToWiden, Value *NewCondition) {
     Value *Result;
     widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result);
     setGuardCondition(ToWiden, Result);
   }
 
 public:
 
   explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
-                             LoopInfo &LI, DomTreeNode *Root,
+                             LoopInfo &LI, BranchProbabilityInfo *BPI,
+                             DomTreeNode *Root,
                              std::function<bool(BasicBlock*)> BlockFilter)
-    : DT(DT), PDT(PDT), LI(LI), Root(Root), BlockFilter(BlockFilter) {}
+    : DT(DT), PDT(PDT), LI(LI), BPI(BPI), Root(Root), BlockFilter(BlockFilter)
+        {}
 
   /// The entry point for this pass.
   bool run();
 };
 }
 
 bool GuardWideningImpl::run() {
   DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> GuardsInBlock;
   bool Changed = false;
+  Optional<BranchProbability> LikelyTaken = None;
+  if (WidenFrequentBranches && BPI) {
+    unsigned Threshold = FrequentBranchThreshold;
+    assert(Threshold > 0 && "Zero threshold makes no sense!");
+    LikelyTaken = std::move(BranchProbability(Threshold - 1, Threshold));
+  }
 
   for (auto DFI = df_begin(Root), DFE = df_end(Root);
        DFI != DFE; ++DFI) {
     auto *BB = (*DFI)->getBlock();
     if (!BlockFilter(BB))
       continue;
 
     auto &CurrentList = GuardsInBlock[BB];
 
     for (auto &I : *BB)
       if (isGuard(&I))
         CurrentList.push_back(cast<Instruction>(&I));
 
     for (auto *II : CurrentList)
       Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
+    if (WidenFrequentBranches && BPI)
+      if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
+        if (BI->isConditional() &&
+            BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken)
+          Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock);
   }
 
   assert(EliminatedGuards.empty() || Changed);
   for (auto *II : EliminatedGuards)
     if (!WidenedGuards.count(II))
       eliminateGuard(II);
 
   return Changed;
 }
 
 bool GuardWideningImpl::eliminateGuardViaWidening(
     Instruction *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
     const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
         GuardsInBlock) {
   Instruction *BestSoFar = nullptr;
   auto BestScoreSoFar = WS_IllegalOrNegative;
   auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
 
   // In the set of dominating guards, find the one we can merge GuardInst with
   // for the most profit.
   for (unsigned i = 0, e = DFSI.getPathLength(); i != e; ++i) {
     auto *CurBB = DFSI.getPath(i)->getBlock();
#ifndef NDEBUG
       }
       assert(Index == GuardsInCurBB.size() &&
              "Guards expected to be in order!");
     }
 #endif
 
     assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
 
-    if (i == (e - 1)) {
+    if (i == (e - 1) && CurBB->getTerminator() != GuardInst) {
       // Corner case: make sure we're only looking at guards strictly dominating
       // GuardInst when visiting GuardInst->getParent().
       auto NewEnd = std::find(I, E, GuardInst);
       assert(NewEnd != E && "GuardInst not in its own block?");
       E = NewEnd;
     }
 
     for (auto *Candidate : make_range(I, E)) {
#endif
   widenGuard(BestSoFar, getGuardCondition(GuardInst));
   setGuardCondition(GuardInst, ConstantInt::getTrue(GuardInst->getContext()));
   EliminatedGuards.push_back(GuardInst);
   WidenedGuards.insert(BestSoFar);
   return true;
 }
 
 Value *GuardWideningImpl::getGuardCondition(Instruction *GuardInst) {
-  IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
+  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(GuardInst)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     return GI->getArgOperand(0);
   }
+  return cast<BranchInst>(GuardInst)->getCondition();
+}
 
 void GuardWideningImpl::setGuardCondition(Instruction *GuardInst,
                                           Value *NewCond) {
-  IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
+  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(GuardInst)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     GI->setArgOperand(0, NewCond);
+    return;
+  }
+  cast<BranchInst>(GuardInst)->setCondition(NewCond);
 }
 
 bool GuardWideningImpl::isGuard(const Instruction* I) {
   using namespace llvm::PatternMatch;
   return match(I, m_Intrinsic<Intrinsic::experimental_guard>());
 }
 
 void GuardWideningImpl::eliminateGuard(Instruction *GuardInst) {
-  GuardInst->eraseFromParent();
+  // Make sure that the condition of the guard to eliminate is already true.
+  assert(getGuardCondition(GuardInst) ==
+             ConstantInt::getTrue(GuardInst->getContext()) &&
+         "Attempt eliminate a guard with not trivial true condition?");
+  // Only erase guard intrinsics. Do nothing about branches.
+  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(GuardInst)) {
+    GI->eraseFromParent();
     ++GuardsEliminated;
+  } else {
+    assert(isa<BranchInst>(GuardInst) && "Should be!");
+    ++CondBranchEliminated;
+  }
 }
 
 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
     Instruction *DominatedGuard, Loop *DominatedGuardLoop,
     Instruction *DominatingGuard, Loop *DominatingGuardLoop) {
   bool HoistingOutOfLoop = false;
 
   if (DominatingGuardLoop != DominatedGuardLoop) {

 }
 #endif
 
 PreservedAnalyses GuardWideningPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
-  if (!GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
+  BranchProbabilityInfo *BPI = nullptr;
+  if (WidenFrequentBranches)
+    BPI = AM.getCachedResult<BranchProbabilityAnalysis>(F);
+  if (!GuardWideningImpl(DT, &PDT, LI, BPI, DT.getRootNode(),
                          [](BasicBlock*) { return true; } ).run())
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   return PA;
 }
 
 namespace {
 struct GuardWideningLegacyPass : public FunctionPass {
   static char ID;
 
   GuardWideningLegacyPass() : FunctionPass(ID) {
     initializeGuardWideningLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
-    return GuardWideningImpl(DT, &PDT, LI, DT.getRootNode(),
+    BranchProbabilityInfo *BPI = nullptr;
+    if (WidenFrequentBranches)
+      BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+    return GuardWideningImpl(DT, &PDT, LI, BPI, DT.getRootNode(),
                          [](BasicBlock*) { return true; } ).run();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
+    if (WidenFrequentBranches)
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
   }
 };
 
 /// Same as above, but restricted to a single loop at a time.  Can be
 /// scheduled with other loop passes w/o breaking out of LPM
 struct LoopGuardWideningLegacyPass : public LoopPass {
   static char ID;
 
bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
     auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
     BasicBlock *RootBB = L->getLoopPredecessor();
     if (!RootBB)
       RootBB = L->getHeader();
     auto BlockFilter = [&](BasicBlock *BB) {
       return BB == RootBB || L->contains(BB);
     };
-    return GuardWideningImpl(DT, PDT, LI,
+    BranchProbabilityInfo *BPI = nullptr;
+    if (WidenFrequentBranches)
+      BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+    return GuardWideningImpl(DT, PDT, LI, BPI,
                              DT.getNode(RootBB), BlockFilter).run();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    if (WidenFrequentBranches)
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
     AU.setPreservesCFG();
     getLoopAnalysisUsage(AU);
     AU.addPreserved<PostDominatorTreeWrapperPass>();
   }
 };
 }
 
 char GuardWideningLegacyPass::ID = 0;
 char LoopGuardWideningLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(GuardWideningLegacyPass, "guard-widening", "Widen guards",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+if (WidenFrequentBranches)
+  INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 INITIALIZE_PASS_END(GuardWideningLegacyPass, "guard-widening", "Widen guards",
                     false, false)
 
 INITIALIZE_PASS_BEGIN(LoopGuardWideningLegacyPass, "loop-guard-widening",
                       "Widen guards (within a single loop, as a loop pass)",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+if (WidenFrequentBranches)
+  INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 INITIALIZE_PASS_END(LoopGuardWideningLegacyPass, "loop-guard-widening",
                     "Widen guards (within a single loop, as a loop pass)",
                     false, false)
 
 FunctionPass *llvm::createGuardWideningPass() {
   return new GuardWideningLegacyPass();
 }
 
 Pass *llvm::createLoopGuardWideningPass() {
   return new LoopGuardWideningLegacyPass();
 }

test/Transforms/GuardWidening/widen-frequent-branches.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -guard-widening-widen-frequent-branches=true -guard-widening-frequent-branch-threshold=1000 -S -guard-widening < %s        | FileCheck %s
+; RUN: opt -guard-widening-widen-frequent-branches=true -guard-widening-frequent-branch-threshold=1000 -S -passes='require<branch-prob>,guard-widening' < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1,...)
+declare void @foo()
+declare void @bar()
+
+; Check that we don't widen without branch probability.
+define void @test_01(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND_0:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  call void @bar()
+  br label %merge
+
+merge:
+  ret void
+}
+
+; Check that we don't widen with branch probability below threshold.
+define void @test_02(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND_0:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !0
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !0
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  call void @bar()
+  br label %merge
+
+merge:
+  ret void
+}
+
+; Check that we widen conditions of explicit branches into dominating guards
+; when the probability is high enough.
+define void @test_03(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_03(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !1
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  call void @bar()
+  br label %merge
+
+merge:
+  ret void
+}
+
+; Widen loop-invariant condition into the guard in preheader.
+define void @test_04(i1 %cond_0, i1 %cond_1, i32 %n) {
+; CHECK-LABEL: @test_04(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !1
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  call void @bar()
+  br label %merge
+
+merge:
+  %iv.next = add i32 %iv, 1
+  %cond = icmp slt i32 %iv.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Widen loop-invariant condition into the guard in the same loop.
+define void @test_05(i1 %cond_0, i1 %cond_1, i32 %n) {
+; CHECK-LABEL: @test_05(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %merge ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !1
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  call void @bar()
+  br label %merge
+
+merge:
+  %iv.next = add i32 %iv, 1
+  %cond = icmp slt i32 %iv.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Some of checks are frequently taken and some are not, make sure that we only
+; widen frequent ones.
+define void @test_06(i1 %cond_0, i1 %cond_1, i1 %cond_2, i1 %cond_3, i1 %cond_4, i32 %n) {
+; CHECK-LABEL: @test_06(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_2:%.*]]
+; CHECK-NEXT:    [[WIDE_CHK1:%.*]] = and i1 [[WIDE_CHK]], [[COND_4:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK1]]) [ "deopt"() ]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]], !prof !2
+; CHECK:       if.true_1:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE_1:%.*]]
+; CHECK:       if.false_1:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE_1]]
+; CHECK:       merge_1:
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]], !prof !1
+; CHECK:       if.true_2:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE_2:%.*]]
+; CHECK:       if.false_2:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE_2]]
+; CHECK:       merge_2:
+; CHECK-NEXT:    br i1 [[COND_3:%.*]], label [[IF_TRUE_3:%.*]], label [[IF_FALSE_3:%.*]], !prof !2
+; CHECK:       if.true_3:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE_3:%.*]]
+; CHECK:       if.false_3:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[MERGE_3]]
+; CHECK:       merge_3:
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE_4:%.*]], label [[IF_FALSE_4:%.*]], !prof !1
+; CHECK:       if.true_4:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       if.false_4:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  br i1 %cond_1, label %if.true_1, label %if.false_1, !prof !2
+
+if.true_1:
+  call void @foo()
+  br label %merge_1
+
+if.false_1:
+  call void @bar()
+  br label %merge_1
+
+merge_1:
+  br i1 %cond_2, label %if.true_2, label %if.false_2, !prof !1
+
+if.true_2:
+  call void @foo()
+  br label %merge_2
+
+if.false_2:
+  call void @bar()
+  br label %merge_2
+
+merge_2:
+  br i1 %cond_3, label %if.true_3, label %if.false_3, !prof !2
+
+if.true_3:
+  call void @foo()
+  br label %merge_3
+
+if.false_3:
+  call void @bar()
+  br label %merge_3
+
+merge_3:
+  br i1 %cond_4, label %if.true_4, label %if.false_4, !prof !1
+
+if.true_4:
+  call void @foo()
+  br label %backedge
+
+if.false_4:
+  call void @bar()
+  br label %backedge
+
+backedge:
+  %iv.next = add i32 %iv, 1
+  %cond = icmp slt i32 %iv.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Check triangle CFG pattern.
+define void @test_07(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_07(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[MERGE:%.*]], !prof !1
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %merge, !prof !1
+
+if.true:
+  call void @foo()
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test_08(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_08(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[COND_1:%.*]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !1
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    ret void
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !1
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  ret void
+
+merge:
+  ret void
+}
+
+!0 = !{!"branch_weights", i32 998, i32 1}
+!1 = !{!"branch_weights", i32 999, i32 1}
+!2 = !{!"branch_weights", i32 500, i32 500}