Index: llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp +++ llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp @@ -145,7 +145,7 @@ bool eliminateGuardViaWidening( Instruction *Guard, const df_iterator &DFSI, const DenseMap> & - GuardsPerBlock); + GuardsPerBlock, bool InvertCondition = false); /// Used to keep track of which widening potential is more effective. enum WideningScore { @@ -169,11 +169,13 @@ /// 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) { @@ -189,13 +191,14 @@ 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 @@ -256,16 +259,20 @@ /// 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); } @@ -309,9 +316,15 @@ Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock); if (WidenFrequentBranches && BPI) if (auto *BI = dyn_cast(BB->getTerminator())) - if (BI->isConditional() && - BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken) - Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock); + 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); @@ -333,7 +346,7 @@ bool GuardWideningImpl::eliminateGuardViaWidening( Instruction *GuardInst, const df_iterator &DFSI, const DenseMap> & - GuardsInBlock) { + GuardsInBlock, bool InvertCondition) { Instruction *BestSoFar = nullptr; auto BestScoreSoFar = WS_IllegalOrNegative; auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent()); @@ -377,7 +390,8 @@ 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"); @@ -399,8 +413,11 @@ 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; @@ -408,7 +425,7 @@ GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore( Instruction *DominatedGuard, Loop *DominatedGuardLoop, - Instruction *DominatingGuard, Loop *DominatingGuardLoop) { + Instruction *DominatingGuard, Loop *DominatingGuardLoop, bool InvertCond) { bool HoistingOutOfLoop = false; if (DominatingGuardLoop != DominatedGuardLoop) { @@ -433,7 +450,7 @@ // 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) @@ -497,7 +514,8 @@ } bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1, - Instruction *InsertPt, Value *&Result) { + Instruction *InsertPt, Value *&Result, + bool InvertCondition) { using namespace llvm::PatternMatch; { @@ -507,6 +525,8 @@ 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()); @@ -540,7 +560,9 @@ { SmallVector 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; @@ -564,7 +586,8 @@ if (InsertPt) { makeAvailableAt(Cond0, InsertPt); makeAvailableAt(Cond1, InsertPt); - + if (InvertCondition) + Cond1 = BinaryOperator::CreateNot(Cond1, "inverted", InsertPt); Result = BinaryOperator::CreateAnd(Cond0, Cond1, "wide.chk", InsertPt); } Index: llvm/trunk/test/Transforms/GuardWidening/widen-frequent-branches.ll =================================================================== --- llvm/trunk/test/Transforms/GuardWidening/widen-frequent-branches.ll +++ llvm/trunk/test/Transforms/GuardWidening/widen-frequent-branches.ll @@ -101,6 +101,39 @@ 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( @@ -149,6 +182,55 @@ 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( @@ -197,6 +279,55 @@ 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) { @@ -208,7 +339,7 @@ ; 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:%.*]] @@ -224,7 +355,7 @@ ; 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:%.*]] @@ -304,6 +435,114 @@ 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( @@ -329,6 +568,32 @@ 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: @@ -358,6 +623,198 @@ 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}