[InstSimplify] fold icmp based on range of abs/nabs

[spatel]

Summary

This is a fix for PR39475:
https://bugs.llvm.org/show_bug.cgi?id=39475

We managed to get some of these patterns using the computeKnownBits logic in D47041, but I don't think that can be used for nabs().
Instead, put in some range-based logic, so we can fold both abs/nabs with icmp with a constant value.

Alive proofs:
https://rise4fun.com/Alive/21r

Name: abs_nsw_is_positive
  %cmp = icmp slt i32 %x, 0
  %negx = sub nsw i32 0, %x
  %abs = select i1 %cmp, i32 %negx, i32 %x
  %r = icmp sgt i32 %abs, -1
    =>
  %r = i1 true
 
Name: abs_nsw_is_not_negative
  %cmp = icmp slt i32 %x, 0
  %negx = sub nsw i32 0, %x
  %abs = select i1 %cmp, i32 %negx, i32 %x
  %r = icmp slt i32 %abs, 0
    =>
  %r = i1 false
 
Name: nabs_is_negative_or_0
  %cmp = icmp slt i32 %x, 0
  %negx = sub i32 0, %x
  %nabs = select i1 %cmp, i32 %x, i32 %negx
  %r = icmp slt i32 %nabs, 1
    =>
  %r = i1 true

Name: nabs_is_not_over_0
  %cmp = icmp slt i32 %x, 0
  %negx = sub i32 0, %x
  %nabs = select i1 %cmp, i32 %x, i32 %negx
  %r = icmp sgt i32 %nabs, 0
    =>
  %r = i1 false

[RKSimon]

I forgot to add it to PR39475 but what about float cases?

[spatel]

In D53844#1280144, @RKSimon wrote:

I forgot to add it to PR39475 but what about float cases?

That'll be an independent patch (but probably simpler since it's just a signbit test if we're ignoring -0.0/Nan).

[RKSimon]

LGTM

[sbc100]

I think this change was responsible for breaking test on the wasm waterfall: https://bugs.llvm.org/show_bug.cgi?id=39510

[spatel]

In D53844#1282871, @sbc100 wrote:

I think this change was responsible for breaking test on the wasm waterfall: https://bugs.llvm.org/show_bug.cgi?id=39510

Yes, sorry about that. Reverted at rL345780. Taking a look now.

lib/Analysis/InstructionSimplify.cpp

case Instruction::Shl: {
         return V;
       break;
     }
     }
   }
   return nullptr;
 }
 
+static Value *simplifyICmpWithAbsNabs(CmpInst::Predicate Pred, Value *Op0,
+                                      Value *Op1) {
+  // We need a comparison with a constant.
+  const APInt *C;
+  if (!match(Op1, m_APInt(C)))
+    return nullptr;
+
+  // matchSelectPattern returns the negation part of an abs pattern in SP1.
+  // If the negate has an NSW flag, abs(INT_MIN) is undefined. Without that
+  // constraint, we can't make a contiguous range for the result of abs.
+  ICmpInst::Predicate AbsPred = ICmpInst::BAD_ICMP_PREDICATE;
+  Value *SP0, *SP1;
+  SelectPatternFlavor SPF = matchSelectPattern(Op0, SP0, SP1).Flavor;
+  if (SPF == SelectPatternFlavor::SPF_ABS &&
+      cast<Instruction>(SP1)->hasNoSignedWrap())
+    // The result of abs(X) is >= 0 (with nsw).
+    AbsPred = ICmpInst::ICMP_SGE;
+  if (SPF == SelectPatternFlavor::SPF_NABS)
+    // The result of -abs(X) is <= 0.
+    AbsPred = ICmpInst::ICMP_SLE;
+
+  if (AbsPred == ICmpInst::BAD_ICMP_PREDICATE)
+    return nullptr;
+
+  // Intersect the range of abs/nabs with the range of this icmp.
+  // If there is no intersection, the icmp must be false.
+  // If the intersection equals the range of abs/nabs, the icmp must be true.
+  APInt Zero = APInt::getNullValue(C->getBitWidth());
+  ConstantRange AbsRange = ConstantRange::makeExactICmpRegion(AbsPred, Zero);
+  ConstantRange CmpRange = ConstantRange::makeExactICmpRegion(Pred, *C);
+  ConstantRange Intersection = AbsRange.intersectWith(CmpRange);
+  if (Intersection.isEmptySet())
+    return getFalse(GetCompareTy(Op0));
+  if (Intersection == AbsRange)
+    return getTrue(GetCompareTy(Op0));
+
+  return nullptr;
+}
+
 /// Simplify integer comparisons where at least one operand of the compare
 /// matches an integer min/max idiom.
 static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
                                      Value *RHS, const SimplifyQuery &Q,
                                      unsigned MaxRecurse) {
   Type *ITy = GetCompareTy(LHS); // The return type.
   Value *A, *B;
   CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
   }
 
   if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
     return V;
 
   if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
     return V;
 
+  if (Value *V = simplifyICmpWithAbsNabs(Pred, LHS, RHS))
+    return V;
+
   // Simplify comparisons of related pointers using a powerful, recursive
   // GEP-walk when we have target data available..
   if (LHS->getType()->isPointerTy())
     if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI,
                                      Q.IIQ, LHS, RHS))
       return C;
   if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
     if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))

test/Transforms/InstSimplify/icmp-abs-nabs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 ; This is canonical form for this IR.
 
 define i1 @abs_nsw_is_positive(i32 %x) {
 ; CHECK-LABEL: @abs_nsw_is_positive(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[ABS]], -1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub nsw i32 0, %x
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp sgt i32 %abs, -1
   ret i1 %r
 }
 
;
   %r = icmp sge i32 %abs, 0
   ret i1 %r
 }
 
 ; This is a range-based analysis. Any negative constant works.
 
 define i1 @abs_nsw_is_positive_reduced_range(i32 %x) {
 ; CHECK-LABEL: @abs_nsw_is_positive_reduced_range(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[ABS]], -42
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub nsw i32 0, %x
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp sgt i32 %abs, -42
   ret i1 %r
 }
 
;
   %r = icmp slt i32 %abs, 0
   ret i1 %r
 }
 
 ; Test non-canonical predicate and non-canonical form of abs().
 
 define i1 @abs_nsw_is_not_negative_sle(i32 %x) {
 ; CHECK-LABEL: @abs_nsw_is_not_negative_sle(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sle i32 [[ABS]], -1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i32 %x, 1
   %negx = sub nsw i32 0, %x
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp sle i32 %abs, -1
   ret i1 %r
 }
 
 ; This is a range-based analysis. Any negative constant works.
 
 define i1 @abs_nsw_is_not_negative_reduced_range(i32 %x) {
 ; CHECK-LABEL: @abs_nsw_is_not_negative_reduced_range(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[NEGX]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[ABS]], -24
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub nsw i32 0, %x
   %abs = select i1 %cmp, i32 %negx, i32 %x
   %r = icmp slt i32 %abs, -24
   ret i1 %r
 }
 
;
   %r = icmp sle i32 %abs, 0
   ret i1 %r
 }
 
 ; This is canonical form for this IR. For nabs(), we don't require 'nsw'
 
 define i1 @nabs_is_negative_or_0(i32 %x) {
 ; CHECK-LABEL: @nabs_is_negative_or_0(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[NABS]], 1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp slt i32 %nabs, 1
   ret i1 %r
 }
 
 ; Test non-canonical predicate and non-canonical form of nabs().
 
 define i1 @nabs_is_negative_or_0_sle(i32 %x) {
 ; CHECK-LABEL: @nabs_is_negative_or_0_sle(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sle i32 [[NABS]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 1
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp sle i32 %nabs, 0
   ret i1 %r
 }
 
 ; This is a range-based analysis. Any positive constant works.
 
 define i1 @nabs_is_negative_or_0_reduced_range(i32 %x) {
 ; CHECK-LABEL: @nabs_is_negative_or_0_reduced_range(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[NABS]], 421
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i32 %x, 1
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp slt i32 %nabs, 421
   ret i1 %r
 }
 
;
   %r = icmp slt i32 %nabs, 0
   ret i1 %r
 }
 
 ; This is canonical form for this IR. For nabs(), we don't require 'nsw'
 
 define i1 @nabs_is_not_over_0(i32 %x) {
 ; CHECK-LABEL: @nabs_is_not_over_0(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[NABS]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i32 %x, 0
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp sgt i32 %nabs, 0
   ret i1 %r
 }
 
 ; Test non-canonical predicate and non-canonical form of nabs().
 
 define i1 @nabs_is_not_over_0_sle(i32 %x) {
 ; CHECK-LABEL: @nabs_is_not_over_0_sle(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sge i32 [[NABS]], 1
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i32 %x, 1
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp sge i32 %nabs, 1
   ret i1 %r
 }
 
 ; This is a range-based analysis. Any positive constant works.
 
 define i1 @nabs_is_not_over_0_reduced_range(i32 %x) {
 ; CHECK-LABEL: @nabs_is_not_over_0_reduced_range(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[NABS]], 4223
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i32 %x, 1
   %negx = sub i32 0, %x
   %nabs = select i1 %cmp, i32 %x, i32 %negx
   %r = icmp sgt i32 %nabs, 4223
   ret i1 %r
 }
 
;
   %r = icmp eq i32 %abs, -8
   ret i1 %r
 }
 
 ; An unsigned compare may work.
 
 define i1 @abs_nsw_is_positive_ult(i8 %x) {
 ; CHECK-LABEL: @abs_nsw_is_positive_ult(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i8 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i8 [[NEGX]], i8 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[ABS]], -117
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i8 %x, 0
   %negx = sub nsw i8 0, %x
   %abs = select i1 %cmp, i8 %negx, i8 %x
   %r = icmp ult i8 %abs, 139
   ret i1 %r
 }
 
 ; An unsigned compare may work.
 
 define i1 @abs_nsw_is_not_negative_ugt(i8 %x) {
 ; CHECK-LABEL: @abs_nsw_is_not_negative_ugt(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i8 0, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i8 [[NEGX]], i8 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[ABS]], 127
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i8 %x, 0
   %negx = sub nsw i8 0, %x
   %abs = select i1 %cmp, i8 %negx, i8 %x
   %r = icmp ugt i8 %abs, 127
   ret i1 %r
 }
 
 ; Vector types are ok.
 
 define <2 x i1> @abs_nsw_is_not_negative_vec_splat(<2 x i32> %x) {
 ; CHECK-LABEL: @abs_nsw_is_not_negative_vec_splat(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i32> [[X:%.*]], zeroinitializer
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[ABS:%.*]] = select <2 x i1> [[CMP]], <2 x i32> [[NEGX]], <2 x i32> [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i32> [[ABS]], <i32 -8, i32 -8>
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %cmp = icmp slt <2 x i32> %x, zeroinitializer
   %negx = sub nsw <2 x i32> zeroinitializer, %x
   %abs = select <2 x i1> %cmp, <2 x i32> %negx, <2 x i32> %x
   %r = icmp slt <2 x i32> %abs, <i32 -8, i32 -8>
   ret <2 x i1> %r
 }
 
 ; Equality predicates are ok.
 
 define i1 @nabs_is_negative_or_0_ne(i8 %x) {
 ; CHECK-LABEL: @nabs_is_negative_or_0_ne(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 0
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i8 0, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select i1 [[CMP]], i8 [[X]], i8 [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[NABS]], 12
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i8 %x, 0
   %negx = sub i8 0, %x
   %nabs = select i1 %cmp, i8 %x, i8 %negx
   %r = icmp ne i8 %nabs, 12
   ret i1 %r
 }
 
 ; Vector types are ok.
 
 define <3 x i1> @nabs_is_not_over_0_sle_vec_splat(<3 x i33> %x) {
 ; CHECK-LABEL: @nabs_is_not_over_0_sle_vec_splat(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <3 x i33> [[X:%.*]], <i33 1, i33 1, i33 1>
-; CHECK-NEXT:    [[NEGX:%.*]] = sub <3 x i33> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[NABS:%.*]] = select <3 x i1> [[CMP]], <3 x i33> [[X]], <3 x i33> [[NEGX]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sge <3 x i33> [[NABS]], <i33 1, i33 1, i33 1>
-; CHECK-NEXT:    ret <3 x i1> [[R]]
+; CHECK-NEXT:    ret <3 x i1> zeroinitializer
 ;
   %cmp = icmp slt <3 x i33> %x, <i33 1, i33 1, i33 1>
   %negx = sub <3 x i33> zeroinitializer, %x
   %nabs = select <3 x i1> %cmp, <3 x i33> %x, <3 x i33> %negx
   %r = icmp sge <3 x i33> %nabs, <i33 1, i33 1, i33 1>
   ret <3 x i1> %r
 }