This is an archive of the discontinued LLVM Phabricator instance.

Differential D59916

[InstCombine] Combine no-wrap sub and icmp w/ constant.
ClosedPublic

Authored by luqmana on Mar 27 2019, 10:53 PM.

Details

Reviewers
majnemer
apilipenko
sanjoy
spatel
lebedev.ri
Commits
rG8911c5be46b9: [InstCombine] Combine no-wrap sub and icmp w/ constant.
rL357674: [InstCombine] Combine no-wrap sub and icmp w/ constant.
Summary

Originally reported in Rust: https://github.com/rust-lang/rust/issues/58602

llvm
define i64 @test_icmp_sub_elide(i64 %offset) {
start:
  %0 = icmp ult i64 %offset, 8
  br i1 %0, label %body, label %end

body:
  %1 = sub i64 10, %offset
  %2 = icmp ult i64 %1, 3
  br i1 %2, label %dead_branch, label %end

dead_branch:
  ret i64 %1

end:
  ret i64 0
}

In the above snippet, we already check that offset < 8 in the first block but can't figure out that 10-offset < 3 is redundant. This changes fixes it in 2 parts:

  1. Teach CorrelatedValuePropagation to also handle sub instructions in addition to add. Relatively simple since makeGuaranteedNoWrapRegion already understood sub instructions. Only subtle change is which range is passed as "Other" to that function, since sub isn't commutative. Moved to separate revision: D60036
  2. Teach InstCombine the transformation (icmp P (sub nuw|nsw C2, Y), C) -> (icmp swap(P) Y, C2-C)

Diff Detail

Repository
rL LLVM

Event Timeline

luqmana created this revision.Mar 27 2019, 10:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 27 2019, 10:53 PM
Herald added subscribers: llvm-commits, jdoerfert, jfb and 2 others. · View Herald Transcript
nikic added a subscriber: nikic.Mar 28 2019, 1:20 AM

Can you please split off the InstCombine change into a separate revision?

llvm/test/Transforms/InstCombine/icmp-sub.ll
3 ↗(On Diff #192564)

For the instcombine tests it's enough to just check the sub+icmp folding to true/false, such as:

define i1 @test(i64 %x) {
  %y = sub nuw i64 10, %x
  %z = icmp ult i64 %y, 3
  ret i1 %z
}

Instead we'd want to test more variations here, in particular: Both nuw and nsw should be covered. Cases where the subtraction overflows should be covered. And I believe this transform also needs to be guarded based on the signedness of the predicate -- i.e. you can't do it if you have sub nsw and ult, so we'd want to test such combinations as well.

Test checks can be generated using utils/update_test_checks.py.

luqmana updated this revision to Diff 192993.Mar 30 2019, 2:40 PM
luqmana retitled this revision from [CorrelatedValuePropagation][InstCombine] Teach CorrelatedValuePropagation to also mark sub as no wrap and use that in InstCombine to fold icmp+sub. to [InstCombine] Combine no-wrap sub and icmp w/ constant..
luqmana edited the summary of this revision. (Show Details)

Split off CorrelatedValuePropagation changes to new revision: D60036

luqmana added a comment.Mar 30 2019, 2:41 PM
In D59916#1445590, @nikic wrote:

Can you please split off the InstCombine change into a separate revision?

Left the InstCombine changes on this revision as you already commented on its test here.

lebedev.ri added a subscriber: lebedev.ri.Mar 30 2019, 2:51 PM
lebedev.ri added inline comments.
llvm/test/Transforms/InstCombine/icmp-sub.ll
66 ↗(On Diff #192993)

Would be good to give tests more meaningful names.
Is this a negative test?

83–85 ↗(On Diff #192993)

This is identical to the previous test.

luqmana updated this revision to Diff 193000.Mar 31 2019, 1:06 AM
luqmana marked 3 inline comments as done.

Give tests more descriptive names and add one more negative test.

llvm/test/Transforms/InstCombine/icmp-sub.ll
66 ↗(On Diff #192993)

Good point, updated the names. And yup, that is a negative test. I've made it more clear.

83–85 ↗(On Diff #192993)

Good catch, meant to be a different negative test.

lebedev.ri added a comment.Mar 31 2019, 1:12 AM
This comment was removed by lebedev.ri.
lebedev.ri added a comment.Mar 31 2019, 1:13 AM

Tests look good, please precommit them and rebase the differential (so that the test changes are visible).

luqmana updated this revision to Diff 193001.Mar 31 2019, 2:01 AM

Rebased on committed tests.

lebedev.ri accepted this revision.Mar 31 2019, 2:29 AM
lebedev.ri added reviewers: spatel, lebedev.ri.

https://rise4fun.com/Alive/keCq

This revision is now accepted and ready to land.Mar 31 2019, 2:29 AM
dmgreen added a subscriber: dmgreen.Apr 1 2019, 2:00 AM
Closed by commit rL357674: [InstCombine] Combine no-wrap sub and icmp w/ constant. (authored by luqmana). · Explain WhyApr 4 2019, 12:09 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
Transforms/
InstCombine/
11 lines
test/
Transforms/
InstCombine/
12 lines

Diff 193668

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Show First 20 Lines • Show All 2,315 Lines • ▼ Show 20 Lines
} }
/// Fold icmp (sub X, Y), C. /// Fold icmp (sub X, Y), C.
Instruction *InstCombiner::foldICmpSubConstant(ICmpInst &Cmp, Instruction *InstCombiner::foldICmpSubConstant(ICmpInst &Cmp,
BinaryOperator *Sub, BinaryOperator *Sub,
const APInt &C) { const APInt &C) {
Value *X = Sub->getOperand(0), *Y = Sub->getOperand(1); Value *X = Sub->getOperand(0), *Y = Sub->getOperand(1);
ICmpInst::Predicate Pred = Cmp.getPredicate(); ICmpInst::Predicate Pred = Cmp.getPredicate();
const APInt *C2;
APInt SubResult;
// (icmp P (sub nuw|nsw C2, Y), C) -> (icmp swap(P) Y, C2-C)
if (match(X, m_APInt(C2)) &&
((Cmp.isUnsigned() && Sub->hasNoUnsignedWrap()) ||
(Cmp.isSigned() && Sub->hasNoSignedWrap())) &&
!subWithOverflow(SubResult, *C2, C, Cmp.isSigned()))
return new ICmpInst(Cmp.getSwappedPredicate(), Y,
ConstantInt::get(Y->getType(), SubResult));
// The following transforms are only worth it if the only user of the subtract // The following transforms are only worth it if the only user of the subtract
// is the icmp. // is the icmp.
if (!Sub->hasOneUse()) if (!Sub->hasOneUse())
return nullptr; return nullptr;
if (Sub->hasNoSignedWrap()) { if (Sub->hasNoSignedWrap()) {
// (icmp sgt (sub nsw X, Y), -1) -> (icmp sge X, Y) // (icmp sgt (sub nsw X, Y), -1) -> (icmp sge X, Y)
if (Pred == ICmpInst::ICMP_SGT && C.isAllOnesValue()) if (Pred == ICmpInst::ICMP_SGT && C.isAllOnesValue())
return new ICmpInst(ICmpInst::ICMP_SGE, X, Y); return new ICmpInst(ICmpInst::ICMP_SGE, X, Y);
// (icmp sgt (sub nsw X, Y), 0) -> (icmp sgt X, Y) // (icmp sgt (sub nsw X, Y), 0) -> (icmp sgt X, Y)
if (Pred == ICmpInst::ICMP_SGT && C.isNullValue()) if (Pred == ICmpInst::ICMP_SGT && C.isNullValue())
return new ICmpInst(ICmpInst::ICMP_SGT, X, Y); return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
// (icmp slt (sub nsw X, Y), 0) -> (icmp slt X, Y) // (icmp slt (sub nsw X, Y), 0) -> (icmp slt X, Y)
if (Pred == ICmpInst::ICMP_SLT && C.isNullValue()) if (Pred == ICmpInst::ICMP_SLT && C.isNullValue())
return new ICmpInst(ICmpInst::ICMP_SLT, X, Y); return new ICmpInst(ICmpInst::ICMP_SLT, X, Y);
// (icmp slt (sub nsw X, Y), 1) -> (icmp sle X, Y) // (icmp slt (sub nsw X, Y), 1) -> (icmp sle X, Y)
if (Pred == ICmpInst::ICMP_SLT && C.isOneValue()) if (Pred == ICmpInst::ICMP_SLT && C.isOneValue())
return new ICmpInst(ICmpInst::ICMP_SLE, X, Y); return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
} }
const APInt *C2;
if (!match(X, m_APInt(C2))) if (!match(X, m_APInt(C2)))
return nullptr; return nullptr;
// C2 - Y <u C -> (Y | (C - 1)) == C2 // C2 - Y <u C -> (Y | (C - 1)) == C2
// iff (C2 & (C - 1)) == C - 1 and C is a power of 2 // iff (C2 & (C - 1)) == C - 1 and C is a power of 2
if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() && if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() &&
(*C2 & (C - 1)) == (C - 1)) (*C2 & (C - 1)) == (C - 1))
return new ICmpInst(ICmpInst::ICMP_EQ, Builder.CreateOr(Y, C - 1), X); return new ICmpInst(ICmpInst::ICMP_EQ, Builder.CreateOr(Y, C - 1), X);
▲ Show 20 Lines • Show All 3,260 Lines • Show Last 20 Lines

llvm/trunk/test/Transforms/InstCombine/icmp-sub.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -instcombine -S | FileCheck %s ; RUN: opt < %s -instcombine -S | FileCheck %s
define i1 @test_nuw_and_unsigned_pred(i64 %x) { define i1 @test_nuw_and_unsigned_pred(i64 %x) {
; CHECK-LABEL: @test_nuw_and_unsigned_pred( ; CHECK-LABEL: @test_nuw_and_unsigned_pred(
; CHECK-NEXT: [[Y:%.*]] = sub nuw i64 10, [[X:%.*]] ; CHECK-NEXT: [[Z:%.*]] = icmp ugt i64 [[X:%.*]], 7
; CHECK-NEXT: [[Z:%.*]] = icmp ult i64 [[Y]], 3
; CHECK-NEXT: ret i1 [[Z]] ; CHECK-NEXT: ret i1 [[Z]]
; ;
%y = sub nuw i64 10, %x %y = sub nuw i64 10, %x
%z = icmp ult i64 %y, 3 %z = icmp ult i64 %y, 3
ret i1 %z ret i1 %z
} }
define i1 @test_nsw_and_signed_pred(i64 %x) { define i1 @test_nsw_and_signed_pred(i64 %x) {
; CHECK-LABEL: @test_nsw_and_signed_pred( ; CHECK-LABEL: @test_nsw_and_signed_pred(
; CHECK-NEXT: [[Y:%.*]] = sub nsw i64 3, [[X:%.*]] ; CHECK-NEXT: [[Z:%.*]] = icmp slt i64 [[X:%.*]], -7
; CHECK-NEXT: [[Z:%.*]] = icmp sgt i64 [[Y]], 10
; CHECK-NEXT: ret i1 [[Z]] ; CHECK-NEXT: ret i1 [[Z]]
; ;
%y = sub nsw i64 3, %x %y = sub nsw i64 3, %x
%z = icmp sgt i64 %y, 10 %z = icmp sgt i64 %y, 10
ret i1 %z ret i1 %z
} }
define i1 @test_nuw_nsw_and_unsigned_pred(i64 %x) { define i1 @test_nuw_nsw_and_unsigned_pred(i64 %x) {
; CHECK-LABEL: @test_nuw_nsw_and_unsigned_pred( ; CHECK-LABEL: @test_nuw_nsw_and_unsigned_pred(
; CHECK-NEXT: [[Y:%.*]] = sub nuw nsw i64 10, [[X:%.*]] ; CHECK-NEXT: [[Z:%.*]] = icmp ugt i64 [[X:%.*]], 6
; CHECK-NEXT: [[Z:%.*]] = icmp ult i64 [[Y]], 4
; CHECK-NEXT: ret i1 [[Z]] ; CHECK-NEXT: ret i1 [[Z]]
; ;
%y = sub nuw nsw i64 10, %x %y = sub nuw nsw i64 10, %x
%z = icmp ule i64 %y, 3 %z = icmp ule i64 %y, 3
ret i1 %z ret i1 %z
} }
define i1 @test_nuw_nsw_and_signed_pred(i64 %x) { define i1 @test_nuw_nsw_and_signed_pred(i64 %x) {
; CHECK-LABEL: @test_nuw_nsw_and_signed_pred( ; CHECK-LABEL: @test_nuw_nsw_and_signed_pred(
; CHECK-NEXT: [[Y:%.*]] = sub nuw nsw i64 10, [[X:%.*]] ; CHECK-NEXT: [[Z:%.*]] = icmp sgt i64 [[X:%.*]], 7
; CHECK-NEXT: [[Z:%.*]] = icmp slt i64 [[Y]], 3
; CHECK-NEXT: ret i1 [[Z]] ; CHECK-NEXT: ret i1 [[Z]]
; ;
%y = sub nuw nsw i64 10, %x %y = sub nuw nsw i64 10, %x
%z = icmp slt i64 %y, 3 %z = icmp slt i64 %y, 3
ret i1 %z ret i1 %z
} }
define i1 @test_negative_nuw_and_signed_pred(i64 %x) { define i1 @test_negative_nuw_and_signed_pred(i64 %x) {
▲ Show 20 Lines • Show All 42 Lines • Show Last 20 Lines