[GuardWidening] Widen very likely non-taken br instructions

[mkazantsev]

Summary

This is a second part of D49974 that handles widening of conditional branches that
have very likely false branch.

[mkazantsev]

Rebased.

[mkazantsev]

Rebased.

[reames]

lib/Transforms/Scalar/GuardWidening.cpp

526 ↗

(On Diff #158975)

You should be able to handle this case by simply inverting Pred1 if InvertCondition is true.

[mkazantsev]

Removed one of TODO limitations, added corresponding tests.

[mkazantsev]

ping

[reames]

LGTM w/one required change before commit. I'm assuming the fix is 2-3 lines (basically adding a param pass through), if it's anything other than that, please come back for another round of review.

lib/Transforms/Scalar/GuardWidening.cpp

391 ↗

(On Diff #159440)

It looks like you forgot to invert the condition when checking profit. Should be an easy fix, but add a test case which shows the problem too.

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

391 ↗

(On Diff #159440)

I'm not sure what do you mean. This function only checks if we are hoisting out of loop or not and availability of condition at candidate's point. How can inversion of condition affect that?

[mkazantsev]

lib/Transforms/Scalar/GuardWidening.cpp

391 ↗

(On Diff #159440)

Just realized that isWideningCondProfitable does a really ugly thing inside and may end up creating instructions. I will propagate the inversion flag there, but it must be rework in the follow-up.

llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp

class GuardWideningImpl {
 
   /// 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
   /// maps BasicBlocks to the set of guards seen in that block.
   bool eliminateGuardViaWidening(
       Instruction *Guard, const df_iterator<DomTreeNode *> &DFSI,
       const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
-          GuardsPerBlock);
+          GuardsPerBlock, bool InvertCondition = false);
 
   /// Used to keep track of which widening potential is more effective.
   enum WideningScore {
     /// Don't widen.
     WS_IllegalOrNegative,
 
     /// Widening is performance neutral as far as the cycles spent in check
     /// conditions goes (but can still help, e.g., code layout, having less
     /// deopt state).
     WS_Neutral,
 
     /// Widening is profitable.
     WS_Positive,
 
     /// Widening is very profitable.  Not significantly different from \c
     /// WS_Positive, except by the order.
     WS_VeryPositive
   };
 
   static StringRef scoreTypeToString(WideningScore WS);
 
   /// Compute the score for widening the condition in \p DominatedGuard
   /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
-  /// \p DominatingGuardLoop).
+  /// \p DominatingGuardLoop). If \p InvertCond is set, then we widen the
+  /// inverted condition of the dominating guard.
   WideningScore computeWideningScore(Instruction *DominatedGuard,
                                      Loop *DominatedGuardLoop,
                                      Instruction *DominatingGuard,
-                                     Loop *DominatingGuardLoop);
+                                     Loop *DominatingGuardLoop,
+                                     bool InvertCond);
 
   /// Helper to check if \p V can be hoisted to \p InsertPos.
   bool isAvailableAt(Value *V, Instruction *InsertPos) {
     SmallPtrSet<Instruction *, 8> Visited;
     return isAvailableAt(V, InsertPos, Visited);
   }
 
   bool isAvailableAt(Value *V, Instruction *InsertPos,
                      SmallPtrSetImpl<Instruction *> &Visited);
 
   /// Helper to hoist \p V to \p InsertPos.  Guaranteed to succeed if \c
   /// isAvailableAt returned true.
   void makeAvailableAt(Value *V, Instruction *InsertPos);
 
   /// Common helper used by \c widenGuard and \c isWideningCondProfitable.  Try
-  /// to generate an expression computing the logical AND of \p Cond0 and \p
-  /// Cond1.  Return true if the expression computing the AND is only as
+  /// to generate an expression computing the logical AND of \p Cond0 and (\p
+  /// Cond1 XOR \p InvertCondition).
+  /// Return true if the expression computing the AND is only as
   /// expensive as computing one of the two. If \p InsertPt is true then
   /// actually generate the resulting expression, make it available at \p
   /// InsertPt and return it in \p Result (else no change to the IR is made).
   bool widenCondCommon(Value *Cond0, Value *Cond1, Instruction *InsertPt,
-                       Value *&Result);
+                       Value *&Result, bool InvertCondition);
 
   /// Represents a range check of the form \c Base + \c Offset u< \c Length,
   /// with the constraint that \c Length is not negative.  \c CheckInst is the
   /// pre-existing instruction in the IR that computes the result of this range
   /// check.
   class RangeCheck {
     Value *Base;
     ConstantInt *Offset;
class GuardWideningImpl {
   /// them into \p CombinedChecks.  Return true on success (i.e. all of checks
   /// in \p Checks were combined into \p CombinedChecks).  Clobbers \p Checks
   /// and \p CombinedChecks on success and on failure.
   bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
                           SmallVectorImpl<RangeCheck> &CombinedChecks);
 
   /// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
   /// computing only one of the two expressions?
-  bool isWideningCondProfitable(Value *Cond0, Value *Cond1) {
+  bool isWideningCondProfitable(Value *Cond0, Value *Cond1, bool InvertCond) {
     Value *ResultUnused;
-    return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused);
+    return widenCondCommon(Cond0, Cond1, /*InsertPt=*/nullptr, ResultUnused,
+                           InvertCond);
   }
 
-  /// Widen \p ToWiden to fail if \p NewCondition is false (in addition to
-  /// whatever it is already checking).
-  void widenGuard(Instruction *ToWiden, Value *NewCondition) {
+  /// If \p InvertCondition is false, Widen \p ToWiden to fail if
+  /// \p NewCondition is false, otherwise make it fail if \p NewCondition is
+  /// true (in addition to whatever it is already checking).
+  void widenGuard(Instruction *ToWiden, Value *NewCondition,
+                  bool InvertCondition) {
     Value *Result;
-    widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result);
+    widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result,
+                    InvertCondition);
     setCondition(ToWiden, Result);
   }
 
 public:
 
   explicit GuardWideningImpl(DominatorTree &DT, PostDominatorTree *PDT,
                              LoopInfo &LI, BranchProbabilityInfo *BPI,
                              DomTreeNode *Root,
for (auto DFI = df_begin(Root), DFE = df_end(Root);
     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)
+        if (BI->isConditional()) {
+          // If one of branches of a conditional is likely taken, try to
+          // eliminate it.
+          if (BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken)
             Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock);
+          else if (BPI->getEdgeProbability(BB, 1U) >= *LikelyTaken)
+            Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock,
+                                                 /*InvertCondition*/true);
+        }
   }
 
   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;
       }
     }
 
   return Changed;
 }
 
 bool GuardWideningImpl::eliminateGuardViaWidening(
     Instruction *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
     const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
-        GuardsInBlock) {
+        GuardsInBlock, bool InvertCondition) {
   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();
if (i == (e - 1) && CurBB->getTerminator() != GuardInst) {
       // 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);
+          computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop,
+                               InvertCondition);
       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, getCondition(GuardInst));
-  setCondition(GuardInst, ConstantInt::getTrue(GuardInst->getContext()));
+  widenGuard(BestSoFar, getCondition(GuardInst), InvertCondition);
+  auto NewGuardCondition = InvertCondition
+                               ? ConstantInt::getFalse(GuardInst->getContext())
+                               : ConstantInt::getTrue(GuardInst->getContext());
+  setCondition(GuardInst, NewGuardCondition);
   EliminatedGuardsAndBranches.push_back(GuardInst);
   WidenedGuards.insert(BestSoFar);
   return true;
 }
 
 GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
     Instruction *DominatedGuard, Loop *DominatedGuardLoop,
-    Instruction *DominatingGuard, Loop *DominatingGuardLoop) {
+    Instruction *DominatingGuard, Loop *DominatingGuardLoop, bool InvertCond) {
   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(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(getCondition(DominatedGuard),
-                               getCondition(DominatingGuard)))
+                               getCondition(DominatingGuard), InvertCond))
     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.
void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
 
   for (Value *Op : Inst->operands())
     makeAvailableAt(Op, Loc);
 
   Inst->moveBefore(Loc);
 }
 
 bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
-                                        Instruction *InsertPt, Value *&Result) {
+                                        Instruction *InsertPt, Value *&Result,
+                                        bool InvertCondition) {
   using namespace llvm::PatternMatch;
 
   {
     // L >u C0 && L >u C1  ->  L >u max(C0, C1)
     ConstantInt *RHS0, *RHS1;
     Value *LHS;
     ICmpInst::Predicate Pred0, Pred1;
     if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
         match(Cond1, m_ICmp(Pred1, m_Specific(LHS), m_ConstantInt(RHS1)))) {
+      if (InvertCondition)
+        Pred1 = ICmpInst::getInversePredicate(Pred1);
 
       ConstantRange CR0 =
           ConstantRange::makeExactICmpRegion(Pred0, RHS0->getValue());
       ConstantRange CR1 =
           ConstantRange::makeExactICmpRegion(Pred1, RHS1->getValue());
 
       // SubsetIntersect is a subset of the actual mathematical intersection of
       // CR0 and CR1, while SupersetIntersect is a superset of the actual
if (match(Cond0, m_ICmp(Pred0, m_Value(LHS), m_ConstantInt(RHS0))) &&
         }
         return true;
       }
     }
   }
 
   {
     SmallVector<GuardWideningImpl::RangeCheck, 4> Checks, CombinedChecks;
-    if (parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
+    // TODO: Support InvertCondition case?
+    if (!InvertCondition &&
+        parseRangeChecks(Cond0, Checks) && parseRangeChecks(Cond1, Checks) &&
         combineRangeChecks(Checks, CombinedChecks)) {
       if (InsertPt) {
         Result = nullptr;
         for (auto &RC : CombinedChecks) {
           makeAvailableAt(RC.getCheckInst(), InsertPt);
           if (Result)
             Result = BinaryOperator::CreateAnd(RC.getCheckInst(), Result, "",
                                                InsertPt);
           else
             Result = RC.getCheckInst();
         }
 
         Result->setName("wide.chk");
       }
       return true;
     }
   }
 
   // Base case -- just logical-and the two conditions together.
 
   if (InsertPt) {
     makeAvailableAt(Cond0, InsertPt);
     makeAvailableAt(Cond1, InsertPt);
-
+    if (InvertCondition)
+      Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt);
     Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt);
   }
 
   // We were not able to compute Cond0 AND Cond1 for the price of one.
   return false;
 }
 
 bool GuardWideningImpl::parseRangeChecks(

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

 if.false:
   call void @bar()
   br label %merge
 
 merge:
   ret void
 }
 
+; Similar to test_03, but the likely taken branch is the false branch.
+define void @test_03_not_taken(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_03_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; 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 !3
+
+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:
merge:
   %iv.next = add i32 %iv, 1
   %cond = icmp slt i32 %iv.next, %n
   br i1 %cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
+; Similar to test_04, but the likely taken branch is the false branch.
+define void @test_04_not_taken(i1 %cond_0, i1 %cond_1, i32 %n) {
+; CHECK-LABEL: @test_04_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; 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 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; 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 !3
+
+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:%.*]]
merge:
   %iv.next = add i32 %iv, 1
   %cond = icmp slt i32 %iv.next, %n
   br i1 %cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
+; Similar to test_05, but the likely taken branch is the false branch.
+define void @test_05_not_taken(i1 %cond_0, i1 %cond_1, i32 %n) {
+; CHECK-LABEL: @test_05_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[MERGE:%.*]] ]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; 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 !3
+
+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-NEXT:    br i1 [[COND_1:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]], !prof !3
 ; 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-NEXT:    br i1 [[COND_3:%.*]], label [[IF_TRUE_3:%.*]], label [[IF_FALSE_3:%.*]], !prof !3
 ; 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
backedge:
   %iv.next = add i32 %iv, 1
   %cond = icmp slt i32 %iv.next, %n
   br i1 %cond, label %loop, label %exit
 
 exit:
   ret void
 }
 
+; Similar to test_06, but the likely taken branch is the false branch.
+define void @test_06_not_taken(i1 %cond_0, i1 %cond_1, i1 %cond_2, i1 %cond_3, i1 %cond_4, i32 %n) {
+; CHECK-LABEL: @test_06_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_2:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; CHECK-NEXT:    [[INVERTED1:%.*]] = xor i1 [[COND_4:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK2:%.*]] = and i1 [[WIDE_CHK]], [[INVERTED1]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK2]]) [ "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 !3
+; 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 false, label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]], !prof !2
+; 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 !3
+; 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 false, label [[IF_TRUE_4:%.*]], label [[IF_FALSE_4:%.*]], !prof !2
+; 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 !3
+
+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 !3
+
+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:

 if.true:
   call void @foo()
   br label %merge
 
 merge:
   ret void
 }
 
+; Similar to test_07, but the likely taken branch is the false branch.
+define void @test_07_not_taken(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_07_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[MERGE:%.*]], !prof !2
+; 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 !3
+
+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()

 
 if.false:
   ret void
 
 merge:
   ret void
 }
 
+define void @test_08_not_taken(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @test_08_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = and i1 [[COND_0:%.*]], [[INVERTED]]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; 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 !3
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  ret void
+
+merge:
+  ret void
+}
+
+; Check that L >u C0 && L >u C1  ->  L >u max(C0, C1).
+define void @test_09(i32 %L) {
+; CHECK-LABEL: @test_09(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp ugt i32 [[L]], 456
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
+; 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:
+  %cond_0 = icmp ugt i32 %L, 123
+  %cond_1 = icmp ugt i32 %L, 456
+  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
+}
+
+; Check that L >u C0 && !(L <=u C1)  ->  L >u max(C0, C1).
+define void @test_09_not_taken(i32 %L) {
+; CHECK-LABEL: @test_09_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp ule i32 [[L]], 456
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; 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:
+  %cond_0 = icmp ugt i32 %L, 123
+  %cond_1 = icmp ule i32 %L, 456
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !3
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  ret void
+
+merge:
+  ret void
+}
+
+; Check that a profitable transform is preferred over non-profitable.
+define void @test_10(i32 %L, i1 %irrelevant_cond, i1 %infinite_loop_cond) {
+; CHECK-LABEL: @test_10(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp ugt i32 [[L]], 456
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IRRELEVANT_COND:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 [[INFINITE_LOOP_COND:%.*]], label [[LOOP]], label [[AFTER_LOOP:%.*]]
+; CHECK:       after_loop:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
+; 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:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cond_0 = icmp ugt i32 %L, 123
+  %cond_1 = icmp ugt i32 %L, 456
+  br label %loop
+
+loop:
+  call void(i1, ...) @llvm.experimental.guard(i1 %irrelevant_cond) [ "deopt"() ]
+  br i1 %infinite_loop_cond, label %loop, label %after_loop
+
+after_loop:
+  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:
+  br label %merge
+
+merge:
+  ret void
+}
+
+; Check that a profitable transform is preferred over non-profitable.
+
+define void @test_10_not_taken(i32 %L, i1 %irrelevant_cond, i1 %infinite_loop_cond) {
+; CHECK-LABEL: @test_10_not_taken(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_0:%.*]] = icmp ugt i32 [[L:%.*]], 123
+; CHECK-NEXT:    [[COND_1:%.*]] = icmp ule i32 [[L]], 456
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[IRRELEVANT_COND:%.*]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 [[INFINITE_LOOP_COND:%.*]], label [[LOOP]], label [[AFTER_LOOP:%.*]]
+; CHECK:       after_loop:
+; CHECK-NEXT:    [[WIDE_CHK:%.*]] = icmp uge i32 [[L]], 457
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[WIDE_CHK]]) [ "deopt"() ]
+; CHECK-NEXT:    br i1 false, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]], !prof !2
+; CHECK:       if.true:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cond_0 = icmp ugt i32 %L, 123
+  %cond_1 = icmp ule i32 %L, 456
+  br label %loop
+
+loop:
+  call void(i1, ...) @llvm.experimental.guard(i1 %irrelevant_cond) [ "deopt"() ]
+  br i1 %infinite_loop_cond, label %loop, label %after_loop
+
+after_loop:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cond_0) [ "deopt"() ]
+  br i1 %cond_1, label %if.true, label %if.false, !prof !3
+
+if.true:
+  call void @foo()
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  ret void
+}
+
 !0 = !{!"branch_weights", i32 998, i32 1}
 !1 = !{!"branch_weights", i32 999, i32 1}
 !2 = !{!"branch_weights", i32 500, i32 500}
+!3 = !{!"branch_weights", i32 1, i32 999}