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

[luqmana]

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)

[nikic]

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

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

3

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]

Split off CorrelatedValuePropagation changes to new revision: D60036

[luqmana]

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]

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

66

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

83–85

This is identical to the previous test.

[luqmana]

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

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

66

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

83–85

Good catch, meant to be a different negative test.

[lebedev.ri]

This comment was removed by lebedev.ri.

[lebedev.ri]

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

[luqmana]

Rebased on committed tests.

[lebedev.ri]

https://rise4fun.com/Alive/keCq

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 }
 
 /// Fold icmp (sub X, Y), C.
 Instruction *InstCombiner::foldICmpSubConstant(ICmpInst &Cmp,
                                                BinaryOperator *Sub,
                                                const APInt &C) {
   Value *X = Sub->getOperand(0), *Y = Sub->getOperand(1);
   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
   // is the icmp.
   if (!Sub->hasOneUse())
     return nullptr;
 
   if (Sub->hasNoSignedWrap()) {
     // (icmp sgt (sub nsw X, Y), -1) -> (icmp sge X, Y)
     if (Pred == ICmpInst::ICMP_SGT && C.isAllOnesValue())
       return new ICmpInst(ICmpInst::ICMP_SGE, X, Y);
 
     // (icmp sgt (sub nsw X, Y), 0) -> (icmp sgt X, Y)
     if (Pred == ICmpInst::ICMP_SGT && C.isNullValue())
       return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
 
     // (icmp slt (sub nsw X, Y), 0) -> (icmp slt X, Y)
     if (Pred == ICmpInst::ICMP_SLT && C.isNullValue())
       return new ICmpInst(ICmpInst::ICMP_SLT, X, Y);
 
     // (icmp slt (sub nsw X, Y), 1) -> (icmp sle X, Y)
     if (Pred == ICmpInst::ICMP_SLT && C.isOneValue())
       return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
   }
 
-  const APInt *C2;
   if (!match(X, m_APInt(C2)))
     return nullptr;
 
   // C2 - Y <u C -> (Y | (C - 1)) == C2
   //   iff (C2 & (C - 1)) == C - 1 and C is a power of 2
   if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() &&
       (*C2 & (C - 1)) == (C - 1))
     return new ICmpInst(ICmpInst::ICMP_EQ, Builder.CreateOr(Y, C - 1), X);

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

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

 ; CHECK-NEXT:    [[Z:%.*]] = icmp ult i64 [[Y]], 3
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = sub nsw i64 10, %x
   %z = icmp ult i64 %y, 3
   ret i1 %z
 }
 
 define i1 @test_negative_combined_sub_unsigned_overflow(i64 %x) {
 ; CHECK-LABEL: @test_negative_combined_sub_unsigned_overflow(
 ; CHECK-NEXT:    [[Y:%.*]] = sub nuw i64 10, [[X:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp ult i64 [[Y]], 11
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = sub nuw i64 10, %x
   %z = icmp ult i64 %y, 11
   ret i1 %z
 }
 
 define i1 @test_negative_combined_sub_signed_overflow(i8 %x) {
 ; CHECK-LABEL: @test_negative_combined_sub_signed_overflow(
 ; CHECK-NEXT:    [[Y:%.*]] = sub nsw i8 127, [[X:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[Y]], -1
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = sub nsw i8 127, %x
   %z = icmp slt i8 %y, -1
   ret i1 %z
 }