This is an archive of the discontinued LLVM Phabricator instance.

Differential D110517

[SCEV] Prove implication of predicates to their sign-flipped counterparts
ClosedPublic

Authored by mkazantsev on Sep 26 2021, 10:47 PM.

Details

Reviewers
reames
nikic
lebedev.ri
fhahn
efriedma
Commits
rG90ae538cab4b: [SCEV] Prove implication of predicates to their sign-flipped counterparts
Summary

This patch teaches SCEV two implication rules:

x <u y && y >=s 0 --> x <s y,
x <s y && y <s 0 --> x <u y.

And all equivalents with signs/parts swapped.

Diff Detail

Event Timeline

mkazantsev created this revision.Sep 26 2021, 10:47 PM
Herald added a subscriber: hiraditya. · View Herald TranscriptSep 26 2021, 10:47 PM
mkazantsev requested review of this revision.Sep 26 2021, 10:47 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 26 2021, 10:47 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
mkazantsev added a child revision: D110518: [SCEV] Prove isKnown(Non)Negative using CtxI when possible.Sep 26 2021, 11:05 PM
Harbormaster completed remote builds in B125792: Diff 375145.Sep 26 2021, 11:07 PM
nikic added inline comments.Sep 27 2021, 12:57 PM
llvm/lib/Analysis/ScalarEvolution.cpp
10793

This looks correct to me, but also rather ad-hoc -- it handles one out of multiple symmetrical patterns. For example, if we just swap both predicates (Pred == SGT and non-negative LHS) this will not trigger anymore. Or did that already get canonicalized away (in which case we should test it)?

reames added inline comments.Sep 27 2021, 3:22 PM
llvm/lib/Analysis/ScalarEvolution.cpp
10793

In line with the point Nikita makes, there's also an interesting case we should handle when RHS is known negative. In that case, ult A, B && A < 0 is enough to prove slt A, B. What's interesting to me is that we've already paid the cost of determining if A is known negative, so this becomes just a canonicalization.

All of this is building on the equivalence:
SLT A, B == (ULT A, B && signof(A) == signof(B)) || (A < 0 && B > 0)

(Note that ULT A, B + B > 0 => A > 0.)

Thinking about all this, it feels unfortunate that we're dropping to implication instead of rewriting based on equivalence. At the same time though, I don't really see an obvious code structure to use the equivalence fact though, so maybe there's nothing we can do on that front.

mkazantsev planned changes to this revision.Sep 27 2021, 9:23 PM
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
10793

As for canonicalization, we try to canonicalize so that LHS matched FoundLHS or RHS matched FoundRHS, and we also try to move constant to right hand side. So in practice, I think in some cases it will be canonicalized so that constant (which is surely a known (non) negative) will be in RHS, but it's not guaranteed for all cases. I'll add more tests to see how it reacts on different equivalent code patterns, and if it's not general enough, I'll try to make the logic smarter.

mkazantsev mentioned this in rG78873840ff41: [Test] Add some more symmetrical test cases for D110517.Oct 6 2021, 3:39 AM
mkazantsev mentioned this in rG576ab15b9092: [Test] Few more symmetrical test for D110517.Oct 6 2021, 5:02 AM
mkazantsev updated this revision to Diff 377512.Oct 6 2021, 5:47 AM
mkazantsev retitled this revision from [SCEV] Prove implication X <u Y, Y >=s 0 --> X <s Y to [SCEV] Prove implication of predicates to their sign-flipped counterparts.
mkazantsev edited the summary of this revision. (Show Details)

Generalized as widely as I could, now this covers all varieties of these.

Herald added a subscriber: javed.absar. · View Herald TranscriptOct 6 2021, 5:47 AM
mkazantsev edited the summary of this revision. (Show Details)Oct 6 2021, 5:47 AM
Harbormaster completed remote builds in B127271: Diff 377512.Oct 6 2021, 6:32 AM
mkazantsev added a comment.Oct 13 2021, 10:12 PM

Ping

nikic accepted this revision.Oct 14 2021, 12:14 PM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
10797

Is this malicious compliance? ^^

This revision is now accepted and ready to land.Oct 14 2021, 12:14 PM
mkazantsev added inline comments.Oct 14 2021, 8:57 PM
llvm/lib/Analysis/ScalarEvolution.cpp
10797

It's full-scaled paranoia! :)

Closed by commit rG90ae538cab4b: [SCEV] Prove implication of predicates to their sign-flipped counterparts (authored by mkazantsev). · Explain WhyOct 14 2021, 9:49 PM
This revision was automatically updated to reflect the committed changes.
mkazantsev added a commit: rG90ae538cab4b: [SCEV] Prove implication of predicates to their sign-flipped counterparts.

Revision Contents

PathSize
llvm/
lib/
Analysis/
43 lines
test/
Transforms/
IndVarSimplify/
32 lines

Diff 379916

llvm/lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 10,764 Lines • ▼ Show 20 Lines if (!FoundLHS->getType()->isPointerTy() &&
!FoundRHS->getType()->isPointerTy() && !FoundRHS->getType()->isPointerTy() &&
isImpliedCondOperands(Pred, LHS, RHS, getNotSCEV(FoundLHS), isImpliedCondOperands(Pred, LHS, RHS, getNotSCEV(FoundLHS),
getNotSCEV(FoundRHS), CtxI)) getNotSCEV(FoundRHS), CtxI))
return true; return true;
return false; return false;
} }
// Unsigned comparison is the same as signed comparison when both the operands
// are non-negative or negative.
auto IsSignFlippedPredicate = [](CmpInst::Predicate P1, auto IsSignFlippedPredicate = [](CmpInst::Predicate P1,
CmpInst::Predicate P2) { CmpInst::Predicate P2) {
assert(P1 != P2 && "Handled earlier!"); assert(P1 != P2 && "Handled earlier!");
return CmpInst::isRelational(P2) && return CmpInst::isRelational(P2) &&
P1 == CmpInst::getFlippedSignednessPredicate(P2); P1 == CmpInst::getFlippedSignednessPredicate(P2);
}; };
if (IsSignFlippedPredicate(Pred, FoundPred) && if (IsSignFlippedPredicate(Pred, FoundPred)) {
((isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) || // Unsigned comparison is the same as signed comparison when both the
(isKnownNegative(FoundLHS) && isKnownNegative(FoundRHS)))) // operands are non-negative or negative.
if ((isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) ||
(isKnownNegative(FoundLHS) && isKnownNegative(FoundRHS)))
return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI); return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
// Create local copies that we can freely swap and canonicalize our
// conditions to "le/lt".
ICmpInst::Predicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS,
*CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
if (ICmpInst::isGT(CanonicalPred) || ICmpInst::isGE(CanonicalPred)) {
CanonicalPred = ICmpInst::getSwappedPredicate(CanonicalPred);
CanonicalFoundPred = ICmpInst::getSwappedPredicate(CanonicalFoundPred);
std::swap(CanonicalLHS, CanonicalRHS);
nikicUnsubmitted
Not Done
ReplyInline Actions

This looks correct to me, but also rather ad-hoc -- it handles one out of multiple symmetrical patterns. For example, if we just swap both predicates (Pred == SGT and non-negative LHS) this will not trigger anymore. Or did that already get canonicalized away (in which case we should test it)?

nikic: This looks correct to me, but also rather ad-hoc -- it handles one out of multiple symmetrical…
reamesUnsubmitted
Not Done
ReplyInline Actions

In line with the point Nikita makes, there's also an interesting case we should handle when RHS is known negative. In that case, ult A, B && A < 0 is enough to prove slt A, B. What's interesting to me is that we've already paid the cost of determining if A is known negative, so this becomes just a canonicalization.

All of this is building on the equivalence:
SLT A, B == (ULT A, B && signof(A) == signof(B)) || (A < 0 && B > 0)

(Note that ULT A, B + B > 0 => A > 0.)

Thinking about all this, it feels unfortunate that we're dropping to implication instead of rewriting based on equivalence. At the same time though, I don't really see an obvious code structure to use the equivalence fact though, so maybe there's nothing we can do on that front.

reames: In line with the point Nikita makes, there's also an interesting case we should handle when RHS…
mkazantsevAuthorUnsubmitted
Done
ReplyInline Actions

As for canonicalization, we try to canonicalize so that LHS matched FoundLHS or RHS matched FoundRHS, and we also try to move constant to right hand side. So in practice, I think in some cases it will be canonicalized so that constant (which is surely a known (non) negative) will be in RHS, but it's not guaranteed for all cases. I'll add more tests to see how it reacts on different equivalent code patterns, and if it's not general enough, I'll try to make the logic smarter.

mkazantsev: As for canonicalization, we try to canonicalize so that `LHS` matched `FoundLHS` or `RHS`…
std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
}
assert((ICmpInst::isLT(CanonicalPred) || ICmpInst::isLE(CanonicalPred)) &&
"Must be!");
nikicUnsubmitted
Not Done
ReplyInline Actions

Is this malicious compliance? ^^

nikic: Is this malicious compliance? ^^
mkazantsevAuthorUnsubmitted
Done
ReplyInline Actions

It's full-scaled paranoia! :)

mkazantsev: It's full-scaled paranoia! :)
assert((ICmpInst::isLT(CanonicalFoundPred) ||
ICmpInst::isLE(CanonicalFoundPred)) &&
"Must be!");
if (ICmpInst::isSigned(CanonicalPred) && isKnownNonNegative(CanonicalRHS))
// Use implication:
// x <u y && y >=s 0 --> x <s y.
// If we can prove the left part, the right part is also proven.
return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
CanonicalRHS, CanonicalFoundLHS,
CanonicalFoundRHS);
if (ICmpInst::isUnsigned(CanonicalPred) && isKnownNegative(CanonicalRHS))
// Use implication:
// x <s y && y <s 0 --> x <u y.
// If we can prove the left part, the right part is also proven.
return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
CanonicalRHS, CanonicalFoundLHS,
CanonicalFoundRHS);
}
// Check if we can make progress by sharpening ranges. // Check if we can make progress by sharpening ranges.
if (FoundPred == ICmpInst::ICMP_NE && if (FoundPred == ICmpInst::ICMP_NE &&
(isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) { (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
const SCEVConstant *C = nullptr; const SCEVConstant *C = nullptr;
const SCEV *V = nullptr; const SCEV *V = nullptr;
▲ Show 20 Lines • Show All 2,963 Lines • Show Last 20 Lines

llvm/test/Transforms/IndVarSimplify/outer_phi.ll

Show First 20 Lines • Show All 457 Lines • ▼ Show 20 Linesside.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_01a, but non-negativity of %b is known without context. ; Same as test_01a, but non-negativity of %b is known without context.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05a(i32 %a, i32* %bp) { define i32 @test_05a(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05a( ; CHECK-LABEL: @test_05a(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] ; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Similar to test_05a, but inverted 2nd condition. ; Similar to test_05a, but inverted 2nd condition.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05b(i32 %a, i32* %bp) { define i32 @test_05b(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05b( ; CHECK-LABEL: @test_05b(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] ; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; We should prove implication: iv <s b, b <s 0 => iv <u b. ; We should prove implication: iv <s b, b <s 0 => iv <u b.
; FIXME: Can remove 2nd check
define i32 @test_05c(i32 %a, i32* %bp) { define i32 @test_05c(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05c( ; CHECK-LABEL: @test_05c(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1:![0-9]+]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1:![0-9]+]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] ; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_05c, but 2nd condition reversed. ; Same as test_05c, but 2nd condition reversed.
; FIXME: Can remove 2nd check
define i32 @test_05d(i32 %a, i32* %bp) { define i32 @test_05d(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05d( ; CHECK-LABEL: @test_05d(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] ; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 33 Linesside.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_05a, but 1st condition inverted. ; Same as test_05a, but 1st condition inverted.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05e(i32 %a, i32* %bp) { define i32 @test_05e(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05e( ; CHECK-LABEL: @test_05e(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] ; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_05b, but 1st condition inverted. ; Same as test_05b, but 1st condition inverted.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05f(i32 %a, i32* %bp) { define i32 @test_05f(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05f( ; CHECK-LABEL: @test_05f(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] ; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_05c, but 1st condition inverted. ; Same as test_05c, but 1st condition inverted.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05g(i32 %a, i32* %bp) { define i32 @test_05g(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05g( ; CHECK-LABEL: @test_05g(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] ; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
Show All 32 Lines
side.exit: side.exit:
ret i32 0 ret i32 0
exit: exit:
ret i32 1 ret i32 1
} }
; Same as test_05d, but 1st condition inverted. ; Same as test_05d, but 1st condition inverted.
; FIXME: We can remove 2nd check in loop.
define i32 @test_05h(i32 %a, i32* %bp) { define i32 @test_05h(i32 %a, i32* %bp) {
; CHECK-LABEL: @test_05h( ; CHECK-LABEL: @test_05h(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] ; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]]
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ]
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] ; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]]
; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] ; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
; CHECK: inner.1: ; CHECK: inner.1:
; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] ; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
; CHECK: inner.backedge: ; CHECK: inner.backedge:
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] ; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
; CHECK: outer.backedge: ; CHECK: outer.backedge:
; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] ; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() ; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
▲ Show 20 Lines • Show All 274 Lines • Show Last 20 Lines