[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

284 ↗

(On Diff #157924)

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

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

284 ↗

(On Diff #157924)

Will do.

[reames]

lib/Transforms/Scalar/GuardWidening.cpp

70 ↗

(On Diff #157924)

This definitely needs to default to false initially. :)

77 ↗

(On Diff #157924)

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.

267 ↗

(On Diff #157924)

Separate whitespace change please.

377 ↗

(On Diff #157924)

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

390 ↗

(On Diff #157924)

Same as above.

408 ↗

(On Diff #157924)

Better to move this check into the caller.

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

10 ↗

(On Diff #157924)

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

70 ↗

(On Diff #157924)

Agreed. :)

77 ↗

(On Diff #157924)

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

408 ↗

(On Diff #157924)

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 ↗

(On Diff #157924)

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 ↗

(On Diff #157924)

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 ↗

(On Diff #157924)

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 ↗

(On Diff #158973)

Add assert that the branch condition is a constant.

llvm/trunk/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)) {
+      assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
+      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();
 }

llvm/trunk/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}