[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

314

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

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

314

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.

297

Separate whitespace change please.

411

Same as above.

412

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

412

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.

412

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

412

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

412

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

412

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

325

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 {
 
-// Get the condition of \p GuardInst.
-static Value *getGuardCondition(Instruction *GuardInst) {
-  IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
+// Get the condition of \p I. It can either be a guard or a conditional branch.
+static Value *getCondition(Instruction *I) {
+  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     return GI->getArgOperand(0);
   }
+  return cast<BranchInst>(I)->getCondition();
+}
 
-// Set the condition for \p GuardInst to \p NewCond.
-static void setGuardCondition(Instruction *GuardInst, Value *NewCond) {
-  IntrinsicInst *GI = cast<IntrinsicInst>(GuardInst);
+// Set the condition for \p I to \p NewCond. \p I can either be a guard or a
+// conditional branch.
+static void setCondition(Instruction *I, Value *NewCond) {
+  if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     GI->setArgOperand(0, NewCond);
+    return;
+  }
+  cast<BranchInst>(I)->setCondition(NewCond);
 }
 
 // Whether or not the particular instruction \p I is a guard.
 static bool isGuard(const Instruction *I) {
   using namespace llvm::PatternMatch;
   return match(I, m_Intrinsic<Intrinsic::experimental_guard>());
 }
 
 // Eliminates the guard instruction properly.
 static void eliminateGuard(Instruction *GuardInst) {
   GuardInst->eraseFromParent();
   ++GuardsEliminated;
 }
 
 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.
-  SmallVector<Instruction *, 16> EliminatedGuards;
+  /// The set of guards and conditional branches whose conditions have been
+  /// widened into dominating guards.
+  SmallVector<Instruction *, 16> EliminatedGuardsAndBranches;
 
   /// The set of guards which have been widened to include conditions to other
   /// guards.
   DenseSet<Instruction *> WidenedGuards;
 
   /// Try to eliminate guard \p Guard by widening it into an earlier dominating
   /// guard.  \p DFSI is the DFS iterator on the dominator tree that is
   /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
     return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
   }
 
   /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
   /// whatever it is already checking).
   void widenGuard(Instruction *ToWiden, Value *NewCondition) {
     Value *Result;
     widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result);
-    setGuardCondition(ToWiden, Result);
+    setCondition(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(EliminatedGuardsAndBranches.empty() || Changed);
+  for (auto *I : EliminatedGuardsAndBranches)
+    if (!WidenedGuards.count(I)) {
+      if (isGuard(I))
+        eliminateGuard(I);
+      else {
+        assert(isa<BranchInst>(I) &&
+               "Eliminated something other than guard or branch?");
+        ++CondBranchEliminated;
+      }
     }
-
-  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) {
#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)) {
       auto Score =
           computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop);
-      LLVM_DEBUG(dbgs() << "Score between " << *getGuardCondition(GuardInst)
-                        << " and " << *getGuardCondition(Candidate) << " is "
+      LLVM_DEBUG(dbgs() << "Score between " << *getCondition(GuardInst)
+                        << " and " << *getCondition(Candidate) << " is "
                         << scoreTypeToString(Score) << "\n");
       if (Score > BestScoreSoFar) {
         BestScoreSoFar = Score;
         BestSoFar = Candidate;
       }
     }
   }
 
   if (BestScoreSoFar == WS_IllegalOrNegative) {
     LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
     return false;
   }
 
   assert(BestSoFar != GuardInst && "Should have never visited same guard!");
   assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
 
   LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
                     << " with score " << scoreTypeToString(BestScoreSoFar)
                     << "\n");
-  widenGuard(BestSoFar, getGuardCondition(GuardInst));
-  setGuardCondition(GuardInst, ConstantInt::getTrue(GuardInst->getContext()));
-  EliminatedGuards.push_back(GuardInst);
+  widenGuard(BestSoFar, getCondition(GuardInst));
+  setCondition(GuardInst, ConstantInt::getTrue(GuardInst->getContext()));
+  EliminatedGuardsAndBranches.push_back(GuardInst);
   WidenedGuards.insert(BestSoFar);
   return true;
 }
 
 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
     Instruction *DominatedGuard, Loop *DominatedGuardLoop,
     Instruction *DominatingGuard, Loop *DominatingGuardLoop) {
   bool HoistingOutOfLoop = false;
 
   if (DominatingGuardLoop != DominatedGuardLoop) {
     // Be conservative and don't widen into a sibling loop.  TODO: If the
     // sibling is colder, we should consider allowing this.
     if (DominatingGuardLoop &&
         !DominatingGuardLoop->contains(DominatedGuardLoop))
       return WS_IllegalOrNegative;
 
     HoistingOutOfLoop = true;
   }
 
-  if (!isAvailableAt(getGuardCondition(DominatedGuard), DominatingGuard))
+  if (!isAvailableAt(getCondition(DominatedGuard), DominatingGuard))
     return WS_IllegalOrNegative;
 
   // If the guard was conditional executed, it may never be reached
   // dynamically.  There are two potential downsides to hoisting it out of the
   // conditionally executed region: 1) we may spuriously deopt without need and
   // 2) we have the extra cost of computing the guard condition in the common
   // case.  At the moment, we really only consider the second in our heuristic
   // here.  TODO: evaluate cost model for spurious deopt
   // NOTE: As written, this also lets us hoist right over another guard which
   // is essentially just another spelling for control flow.
-  if (isWideningCondProfitable(getGuardCondition(DominatedGuard),
-                               getGuardCondition(DominatingGuard)))
+  if (isWideningCondProfitable(getCondition(DominatedGuard),
+                               getCondition(DominatingGuard)))
     return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
 
   if (HoistingOutOfLoop)
     return WS_Positive;
 
   // Returns true if we might be hoisting above explicit control flow.  Note
   // that this completely ignores implicit control flow (guards, calls which
   // throw, etc...).  That choice appears arbitrary.

 }
 #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}