[InstCombine] Fold icmp ugt/ult (add nuw X, C2), C --> icmp ugt/ult X, (C - C2)

[Nicola]

Summary

Support for sgt/slt was added in https://reviews.llvm.org/D29774, this adds the same cases also for unsigned compares.

Alive proof is at: https://rise4fun.com/Alive/nyY

Name: ult
Pre: WillNotOverflowUnsignedSub(C2, C1)
%a = add nuw i8 %x, C1
%b = icmp ult %a, C2

=>

%b = icmp ult %x, C2-C1

Name: ugt
Pre: WillNotOverflowUnsignedSub(C2, C1)
%a = add nuw i8 %x, C1
%b = icmp ugt %a, C2

=>

%b = icmp ugt %x, C2-C1

I updated the tests that changed and added new tests for the new combines.

[xbolva00]

test/Transforms/LoopVectorize/runtime-check.ll

20 ↗

(On Diff #161479)

TMP2 is unused?

[Nicola]

test/Transforms/LoopVectorize/runtime-check.ll

20 ↗

(On Diff #161479)

It is still used on line 36, unfortunately.

[spatel]

test/Transforms/InstCombine/icmp-add.ll

1 ↗

(On Diff #161479)

Please commit the tests first. Use this script to auto-generate the current results. Then, update with this patch and auto-generate the new results.

[Nicola]

test/Transforms/InstCombine/icmp-add.ll

1 ↗

(On Diff #161479)

Ok, thanks. I'll create a separate review for it.
Should I also regenerate all the other tests that I'm touching? LoopVectorize/runtime-check.ll is adding a lot on new checks, and some others are changing in InstCombine/icmp-add.ll

[spatel]

test/Transforms/InstCombine/icmp-add.ll

1 ↗

(On Diff #161479)

No, it's not necessary to regenerate everything. I suggest doing it for this file because these are the primary/minimal tests for the transform though. If the patch gets reverted for some reason, we want to keep the evidence that we're missing an optimization.

And yes, other tests in the file will be affected if we regenerate the whole thing. That's ok; an older version of the script was used previously, and it behaved slightly differently. Alternatively, you can auto-gen just the new functions by specifying "--function=foo" as a parameter.

[Nicola]

Updated after I committed the new tests.

[spatel]

The code change LGTM.

Does the signed version of this fold have negative tests (eg, when there's no 'nsw' on the add)? Either way, if they don't already exist, please add negative tests for this transform where:

1. The add does not have 'nuw'.
2. usub_ov() actually does overflow.

...so we verify that this transform is sufficiently guarded.

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

if (Cmp.isEquality() || !match(Y, m_APInt(C2)))
     return nullptr;
 
   // Fold icmp pred (add X, C2), C.
   Value *X = Add->getOperand(0);
   Type *Ty = Add->getType();
   CmpInst::Predicate Pred = Cmp.getPredicate();
 
   // If the add does not wrap, we can always adjust the compare by subtracting
-  // the constants. Equality comparisons are handled elsewhere. SGE/SLE are
-  // canonicalized to SGT/SLT.
-  if (Add->hasNoSignedWrap() &&
-      (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) {
+  // the constants. Equality comparisons are handled elsewhere. SGE/SLE/UGE/ULE
+  // are canonicalized to SGT/SLT/UGT/ULT.
+  if ((Add->hasNoSignedWrap() &&
+       (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) ||
+      (Add->hasNoUnsignedWrap() &&
+       (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_ULT))) {
     bool Overflow;
-    APInt NewC = C.ssub_ov(*C2, Overflow);
+    APInt NewC =
+        Cmp.isSigned() ? C.ssub_ov(*C2, Overflow) : C.usub_ov(*C2, Overflow);
     // If there is overflow, the result must be true or false.
     // TODO: Can we assert there is no overflow because InstSimplify always
     // handles those cases?
     if (!Overflow)
       // icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2)
       return new ICmpInst(Pred, X, ConstantInt::get(Ty, NewC));
   }
 

llvm/trunk/test/Analysis/ValueTracking/non-negative-phi-bits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine < %s -S | FileCheck %s
 
 define void @test() #0 {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], 40
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 39
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %indvars.iv.next = add nsw i64 %indvars.iv, 1
   %exitcond = icmp slt i64 %indvars.iv.next, 40
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

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

 ;
   %y = add nuw i8 %x, 128
   %z = icmp slt i8 %y, 0
   ret i1 %z
 }
 
 define i1 @reduce_add_ult(i32 %in) {
 ; CHECK-LABEL: @reduce_add_ult(
-; CHECK-NEXT:    [[A6:%.*]] = add nuw i32 [[IN:%.*]], 3
-; CHECK-NEXT:    [[A18:%.*]] = icmp ult i32 [[A6]], 12
+; CHECK-NEXT:    [[A18:%.*]] = icmp ult i32 [[IN:%.*]], 9
 ; CHECK-NEXT:    ret i1 [[A18]]
 ;
   %a6 = add nuw i32 %in, 3
   %a18 = icmp ult i32 %a6, 12
   ret i1 %a18
 }
 
 define i1 @reduce_add_ugt(i32 %in) {
 ; CHECK-LABEL: @reduce_add_ugt(
-; CHECK-NEXT:    [[A6:%.*]] = add nuw i32 [[IN:%.*]], 3
-; CHECK-NEXT:    [[A18:%.*]] = icmp ugt i32 [[A6]], 12
+; CHECK-NEXT:    [[A18:%.*]] = icmp ugt i32 [[IN:%.*]], 9
 ; CHECK-NEXT:    ret i1 [[A18]]
 ;
   %a6 = add nuw i32 %in, 3
   %a18 = icmp ugt i32 %a6, 12
   ret i1 %a18
 }
 
 define i1 @reduce_add_ule(i32 %in) {
 ; CHECK-LABEL: @reduce_add_ule(
-; CHECK-NEXT:    [[A6:%.*]] = add nuw i32 [[IN:%.*]], 3
-; CHECK-NEXT:    [[A18:%.*]] = icmp ult i32 [[A6]], 13
+; CHECK-NEXT:    [[A18:%.*]] = icmp ult i32 [[IN:%.*]], 10
 ; CHECK-NEXT:    ret i1 [[A18]]
 ;
   %a6 = add nuw i32 %in, 3
   %a18 = icmp ule i32 %a6, 12
   ret i1 %a18
 }
 
 define i1 @reduce_add_uge(i32 %in) {
 ; CHECK-LABEL: @reduce_add_uge(
-; CHECK-NEXT:    [[A6:%.*]] = add nuw i32 [[IN:%.*]], 3
-; CHECK-NEXT:    [[A18:%.*]] = icmp ugt i32 [[A6]], 11
+; CHECK-NEXT:    [[A18:%.*]] = icmp ugt i32 [[IN:%.*]], 8
 ; CHECK-NEXT:    ret i1 [[A18]]
 ;
   %a6 = add nuw i32 %in, 3
   %a18 = icmp uge i32 %a6, 12
   ret i1 %a18
 }
+
+define i1 @ult_add_ssubov(i32 %in) {
+; CHECK-LABEL: @ult_add_ssubov(
+; CHECK-NEXT:    ret i1 false
+;
+  %a6 = add nuw i32 %in, 71
+  %a18 = icmp ult i32 %a6, 3
+  ret i1 %a18
+}
+
+define i1 @ult_add_nonuw(i8 %in) {
+; CHECK-LABEL: @ult_add_nonuw(
+; CHECK-NEXT:    [[A6:%.*]] = add i8 [[IN:%.*]], 71
+; CHECK-NEXT:    [[A18:%.*]] = icmp ult i8 [[A6]], 12
+; CHECK-NEXT:    ret i1 [[A18]]
+;
+  %a6 = add i8 %in, 71
+  %a18 = icmp ult i8 %a6, 12
+  ret i1 %a18
+}
+
+define i1 @uge_add_nonuw(i32 %in) {
+; CHECK-LABEL: @uge_add_nonuw(
+; CHECK-NEXT:    [[A6:%.*]] = add i32 [[IN:%.*]], 3
+; CHECK-NEXT:    [[A18:%.*]] = icmp ugt i32 [[A6]], 11
+; CHECK-NEXT:    ret i1 [[A18]]
+;
+  %a6 = add i32 %in, 3
+  %a18 = icmp uge i32 %a6, 12
+  ret i1 %a18
+}

llvm/trunk/test/Transforms/LoopVectorize/X86/masked_load_store.ll

 ; AVX1-NEXT:    [[TMP2:%.*]] = load double, double* [[ARRAYIDX3]], align 8
 ; AVX1-NEXT:    [[CONV:%.*]] = sitofp i32 [[TMP0]] to double
 ; AVX1-NEXT:    [[ADD:%.*]] = fadd double [[TMP2]], [[CONV]]
 ; AVX1-NEXT:    [[ARRAYIDX7:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 [[INDVARS_IV]]
 ; AVX1-NEXT:    store double [[ADD]], double* [[ARRAYIDX7]], align 8
 ; AVX1-NEXT:    br label [[FOR_INC]]
 ; AVX1:       for.inc:
 ; AVX1-NEXT:    [[INDVARS_IV_NEXT:%.*]] = or i64 [[INDVARS_IV]], 16
-; AVX1-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], 10000
+; AVX1-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INDVARS_IV]], 9984
 ; AVX1-NEXT:    br i1 [[CMP]], label [[FOR_BODY_1:%.*]], label [[FOR_END:%.*]]
 ; AVX1:       for.end:
 ; AVX1-NEXT:    ret void
 ; AVX1:       for.body.1:
 ; AVX1-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds i32, i32* [[TRIGGER]], i64 [[INDVARS_IV_NEXT]]
 ; AVX1-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX_1]], align 4
 ; AVX1-NEXT:    [[CMP1_1:%.*]] = icmp slt i32 [[TMP3]], 100
 ; AVX1-NEXT:    br i1 [[CMP1_1]], label [[IF_THEN_1:%.*]], label [[FOR_INC_1]]

 ; AVX2-NEXT:    [[TMP2:%.*]] = load double, double* [[ARRAYIDX3]], align 8
 ; AVX2-NEXT:    [[CONV:%.*]] = sitofp i32 [[TMP0]] to double
 ; AVX2-NEXT:    [[ADD:%.*]] = fadd double [[TMP2]], [[CONV]]
 ; AVX2-NEXT:    [[ARRAYIDX7:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 [[INDVARS_IV]]
 ; AVX2-NEXT:    store double [[ADD]], double* [[ARRAYIDX7]], align 8
 ; AVX2-NEXT:    br label [[FOR_INC]]
 ; AVX2:       for.inc:
 ; AVX2-NEXT:    [[INDVARS_IV_NEXT:%.*]] = or i64 [[INDVARS_IV]], 16
-; AVX2-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], 10000
+; AVX2-NEXT:    [[CMP:%.*]] = icmp ult i64 [[INDVARS_IV]], 9984
 ; AVX2-NEXT:    br i1 [[CMP]], label [[FOR_BODY_1:%.*]], label [[FOR_END:%.*]]
 ; AVX2:       for.end:
 ; AVX2-NEXT:    ret void
 ; AVX2:       for.body.1:
 ; AVX2-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds i32, i32* [[TRIGGER]], i64 [[INDVARS_IV_NEXT]]
 ; AVX2-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX_1]], align 4
 ; AVX2-NEXT:    [[CMP1_1:%.*]] = icmp slt i32 [[TMP3]], 100
 ; AVX2-NEXT:    br i1 [[CMP1_1]], label [[IF_THEN_1:%.*]], label [[FOR_INC_1:%.*]]

 ; AVX512-NEXT:    [[TMP40:%.*]] = load double, double* [[ARRAYIDX3_3]], align 8
 ; AVX512-NEXT:    [[CONV_3:%.*]] = sitofp i32 [[TMP38]] to double
 ; AVX512-NEXT:    [[ADD_3:%.*]] = fadd double [[TMP40]], [[CONV_3]]
 ; AVX512-NEXT:    [[ARRAYIDX7_3:%.*]] = getelementptr inbounds double, double* [[A]], i64 [[INDVARS_IV_NEXT_2]]
 ; AVX512-NEXT:    store double [[ADD_3]], double* [[ARRAYIDX7_3]], align 8
 ; AVX512-NEXT:    br label [[FOR_INC_3]]
 ; AVX512:       for.inc.3:
 ; AVX512-NEXT:    [[INDVARS_IV_NEXT_3]] = add nsw i64 [[INDVARS_IV]], 64
-; AVX512-NEXT:    [[CMP_3:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT_3]], 10000
+; AVX512-NEXT:    [[CMP_3:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT_2]], 9984
 ; AVX512-NEXT:    br i1 [[CMP_3]], label [[FOR_BODY]], label [[FOR_END]], !llvm.loop !52
 ;
 entry:
   %A.addr = alloca double*, align 8
   %B.addr = alloca double*, align 8
   %trigger.addr = alloca i32*, align 8
   %i = alloca i32, align 4
   store double* %A, double** %A.addr, align 8

llvm/trunk/test/Transforms/LoopVectorize/if-conversion-nest.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s  -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -enable-if-conversion -dce -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 define i32 @foo(i32* nocapture %A, i32* nocapture %B, i32 %n) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP26:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP26]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 1
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP2]], 4
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[TMP0]], 3
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
 ; CHECK:       vector.memcheck:
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[N]], -1
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[TMP3]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], 1
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[A:%.*]], i64 [[TMP5]]
 ; CHECK-NEXT:    [[SCEVGEP4:%.*]] = getelementptr i32, i32* [[B:%.*]], i64 [[TMP5]]
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt i32* [[SCEVGEP4]], [[A]]

llvm/trunk/test/Transforms/LoopVectorize/runtime-check.ll

 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP6:%.*]] = icmp sgt i32 [[N:%.*]], 0, !dbg !4
 ; CHECK-NEXT:    br i1 [[CMP6]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]], !dbg !4
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1, !dbg !9
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64, !dbg !9
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 1, !dbg !9
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP2]], 4, !dbg !9
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[TMP0]], 3, !dbg !9
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]], !dbg !9
 ; CHECK:       vector.memcheck:
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[N]], -1, !dbg !9
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[TMP3]] to i64, !dbg !9
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i64 [[TMP4]], 1, !dbg !9
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr float, float* [[A:%.*]], i64 [[TMP5]], !dbg !9
 ; CHECK-NEXT:    [[SCEVGEP4:%.*]] = getelementptr float, float* [[B:%.*]], i64 [[TMP5]], !dbg !9
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt float* [[SCEVGEP4]], [[A]], !dbg !9