[InstructionSimplify] icmp simplification

[SjoerdMeijer]

Summary

This improves simplifications for pattern icmp (X+Y), (X+Z) -> icmp Y,Z if only one of the operands has NSW set, e.g.:

icmp slt (x + 5), (x +nsw 6)

We can still safely rewrite this to:

icmp slt 5, 6

because we know that the LHS can't overflow if the RHS has NSW set and constant Y <= Z.

This is useful because ScalarEvolutionExpander which is used to generate code for SCEVs in different loop optimisers is not always able to put back NSW flags across control-flow.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

2882

Please compare APInt's themselves, otherwise this will crash with an assertion for e.g. i65.

llvm/test/Transforms/InstSimplify/compare.ll

1766

Please precommit the tests.

1828

At least this one is already folded away by instcombine,
so likely there's some code to be moved/refactored/shared.
https://godbolt.org/z/Yo3d6h

[SjoerdMeijer]

Thanks for reviewing.

• I have precommitted the tests in rG66f22411e1bb, and
• use APInts in the comparisons.

[SjoerdMeijer]

llvm/test/Transforms/InstSimplify/compare.ll

1828

Yeah, I will look as a follow up. There is some interaction with other passes. I.e., for my motivating code example, this change enables the unroller to fully unroll these type of loops (i.e. loops with an imcp x+y, x+z condition), and then SimplifyCFG can get rid of control-flow. Thus, I need to look if there's overlap and how the passes interact, also with instcombine.

[SjoerdMeijer]

friendly ping

[spatel]

This seems to be missing some other preconditions on the constant values:
https://rise4fun.com/Alive/EvB

[SjoerdMeijer]

In D89317#2338631, @spatel wrote:

This seems to be missing some other preconditions on the constant values:
https://rise4fun.com/Alive/EvB

Ah yes! Thanks for checking. It's an off-by-one error, and we need positive constants, so should be: Pre: C1 < C2 && C1 >= 0. Will fix this.

[SjoerdMeijer]

Fixed precondition, and added a test case for that.

[spatel]

1. Please upload with context: https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface
2. There should be at least 4 positive tests to exercise each of the commuted pattern paths. Vary the types (include a vector test) for more coverage/functionality. Do we have negative tests for when nsw is on the wrong add or the predicate is not slt?
3. I don't like the way the code around here is structured already, and this patch is making it more complicated. How about something like this:

static bool trySimplifyICmpWithAdds(CmpInst::Predicate Pred, Value *LHS,
                                    Value *RHS) {
  // Canonicalize nsw add as RHS.
  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
    std::swap(LHS, RHS);
  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
    return false;

  Value *X;
  const APInt *C1, *C2;
  if (!match(LHS, m_c_Add(m_Value(X), m_APInt(C1))) ||
      !match(RHS, m_c_Add(m_Specific(X), m_APInt(C2))))
    return false;

  return C1->slt(*C2) && C1->isNonNegative();
}

[RKSimon]

llvm/lib/Analysis/InstructionSimplify.cpp

2879

Please would it be possible to use match + m_APInt instead? And add some uniform vector test coverage.

[SjoerdMeijer]

Thanks for your help.

• this is using your function, the pattern matching, which indeed is much nicer,
• and I think all tests are there, positive and negative. For example, for the positive tests, I have added all the combos, the different data types, including a vector test, and for the negative tests, there are indeed tests with different predicate and the nsw is on the 'wrong' add, etc.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2870–2871

I think this works, but I'm worried that it could break if we are not careful.
If we are swapping the operands, should we also swap the predicate, and then check if it is SLT after the swap?

llvm/test/Transforms/InstSimplify/compare.ll

1875

This is not what I was expecting. To test that the commuted pattern matchibng is working, the first operand on one or both of the adds should be the constant value.

Please do go ahead with pre-committing the extra tests. No review needed unless something is still not clear.

[SjoerdMeijer]

• Precommitted the extra tests in rG782b8f0d38c9.
• Rebased this on that.

[SjoerdMeijer]

• Precommitted 3 tests for testing commuting the operands in rGe86a70ce3def,
• And rebased this on that again.

[SjoerdMeijer]

llvm/lib/Analysis/InstructionSimplify.cpp

2870–2871

Yep, more predicates could be supported here, but I thought to have a start with SLT first, hence the Pred != CmpInst::ICMP_SLT check above on line 2866, so should be fine for now?

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2870–2871

I think it's correct:
https://rise4fun.com/Alive/gyqW

So it's a question of what we mean when we say "canonicalize" in the code comment. Transforming the icmp so that the operands are swapped implies that the predicate is also swapped.

Either way, this patch is not complete as-is even for the SLT predicate alone. We miss this:
https://rise4fun.com/Alive/VgB

So we should note that with another TODO comment.

[SjoerdMeijer]

Thanks!
I have added support for the other SLT case and have added tests, which I have not precommitted this time (hopefully easy to spot these cases), just to completely cover the SLT case. After this, I can quickly follow up to address other predicates, if that is okay.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

2884

I don't think this is the correct condition:
https://rise4fun.com/Alive/EeGe

Please add a test like this to verify:

define i1 @icmp_nsw_false(i8 %V) {
  %add = add i8 %V, 121
  %addnsw = add nsw i8 %V, -104
  %cmp = icmp slt i8 %add, %addnsw
  ret i1 %cmp
}

[SjoerdMeijer]

Cheers, typo fixed: C2->isNonPositive() -> C1->isNonPositive(). And the test case added.

[spatel]

LGTM

[SjoerdMeijer]

Many thanks for reviewing!

llvm/lib/Analysis/InstructionSimplify.cpp

if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)
       return getTrue(ITy);
   }
 
   return nullptr;
 }
 
+
+// If only one of the icmp's operands has NSW flags, try to prove that:
+//
+//   icmp slt (x + C1), (x +nsw C2)
+//
+// is equivalent to:
+//
+//   icmp slt C1, C2
+//
+// which is true if x + C2 has the NSW flags set and:
+// *) C1 < C2 && C1 >= 0, or
+// *) C2 < C1 && C1 <= 0.
+//
+static bool trySimplifyICmpWithAdds(CmpInst::Predicate Pred, Value *LHS,
+                                    Value *RHS) {
+  // TODO: only support icmp slt for now.
+  if (Pred != CmpInst::ICMP_SLT)
+    return false;
+
+  // Canonicalize nsw add as RHS.
+  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
+    std::swap(LHS, RHS);
+  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
+    return false;
+
+  Value *X;
+  const APInt *C1, *C2;
+  if (!match(LHS, m_c_Add(m_Value(X), m_APInt(C1))) ||
+      !match(RHS, m_c_Add(m_Specific(X), m_APInt(C2))))
+    return false;
+
+  return (C1->slt(*C2) && C1->isNonNegative()) ||
+         (C2->slt(*C1) && C2->isNonPositive());
+}
+
+
 /// TODO: A large part of this logic is duplicated in InstCombine's
 /// foldICmpBinOp(). We should be able to share that and avoid the code
 /// duplication.
 static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
                                     Value *RHS, const SimplifyQuery &Q,
                                     unsigned MaxRecurse) {
   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
if (MaxRecurse && (LBO || RBO)) {
     // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
     if ((C == LHS || D == LHS) && NoRHSWrapProblem)
       if (Value *V =
               SimplifyICmpInst(Pred, Constant::getNullValue(LHS->getType()),
                                C == LHS ? D : C, Q, MaxRecurse - 1))
         return V;
 
     // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
-    if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
-        NoRHSWrapProblem) {
+    bool CanSimplify = (NoLHSWrapProblem && NoRHSWrapProblem) ||
+                       trySimplifyICmpWithAdds(Pred, LHS, RHS);
+    if (A && C && (A == C || A == D || B == C || B == D) && CanSimplify) {
       // Determine Y and Z in the form icmp (X+Y), (X+Z).
       Value *Y, *Z;
       if (A == C) {
         // C + B == C + D  ->  B == D
         Y = B;
         Z = D;
       } else if (A == D) {
         // D + B == C + D  ->  B == C

llvm/test/Transforms/InstSimplify/compare.ll

 ; CHECK-NEXT:    ret i1 true
 ;
   %p0 = addrspacecast i32 addrspace(1)* %p1 to i32*
   %p0.1 = getelementptr inbounds i32, i32* %p0, i64 1
   %cmp = icmp ne i32* %p0, %p0.1
   ret i1 %cmp
 }
 
 ; Test simplifications for: icmp (X+Y), (X+Z) -> icmp Y,Z
 ; Test the overflow check when the RHS has NSW set and constant Z is greater
 ; than Y, then we know X+Y also can't overflow.
 
 define i1 @icmp_nsw_1(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_1(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
-; CHECK-NEXT:    [[S1:%.*]] = sext i32 [[ADD5]] to i64
-; CHECK-NEXT:    [[S2:%.*]] = sext i32 [[ADD6]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[S1]], [[S2]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 %V, 5
   %add6 = add nsw i32 %V, 6
   %s1 = sext i32 %add5 to i64
   %s2 = sext i32 %add6 to i64
   %cmp = icmp slt i64 %s1, %s2
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_2(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_2(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 %V, 5
   %add6 = add nsw i32 %V, 6
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_commute(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_commute(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 5, [[V:%.*]]
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 5, %V
   %add6 = add nsw i32 %V, 6
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_commute2(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_commute2(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 6, [[V]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 %V, 5
   %add6 = add nsw i32 6, %V
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_commute3(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_commute3(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i32 5, [[V:%.*]]
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 6, [[V]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i32 5, %V
   %add6 = add nsw i32 6, %V
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_22(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_22(
 ; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add nsw i32 %V, 5
   %add6 = add nsw i32 %V, 6
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_23(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_23(
 ; CHECK-NEXT:    [[ADD5:%.*]] = add nsw i32 [[V:%.*]], 5
 ; CHECK-NEXT:    [[ADD6:%.*]] = add i32 [[V]], 6
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add5 = add nsw i32 %V, 5
   %add6 = add i32 %V, 6
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_false(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_false(
-; CHECK-NEXT:    [[ADD5:%.*]] = add nsw i32 [[V:%.*]], 6
-; CHECK-NEXT:    [[ADD6:%.*]] = add i32 [[V]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add5 = add nsw i32 %V, 6
   %add6 = add i32 %V, 5
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_false_2(i32 %V) {

 ; CHECK-NEXT:    [[ADD5:%.*]] = add nsw i32 [[V:%.*]], 5
 ; CHECK-NEXT:    [[ADD6:%.*]] = add i32 [[V]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add5 = add nsw i32 %V, 5
   %add6 = add i32 %V, 5
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_false_4(i32 %V) {
 ; CHECK-LABEL: @icmp_nsw_false_4(
 ; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 6
 ; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i32 [[V]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[ADD6]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add5 = add i32 %V, 6
   %add6 = add nsw i32 %V, 5
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_i8(i8 %V) {
 ; CHECK-LABEL: @icmp_nsw_i8(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i8 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i8 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i8 %V, 5
   %add6 = add nsw i8 %V, 6
   %cmp = icmp slt i8 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_i16(i16 %V) {
 ; CHECK-LABEL: @icmp_nsw_i16(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i16 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i16 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i16 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
-  %add5 = add i16 %V, 5
-  %add6 = add nsw i16 %V, 6
+  %add5 = add i16 %V, 0
+  %add6 = add nsw i16 %V, 1
   %cmp = icmp slt i16 %add5, %add6
   ret i1 %cmp
 }
 
 define i1 @icmp_nsw_i64(i64 %V) {
 ; CHECK-LABEL: @icmp_nsw_i64(
-; CHECK-NEXT:    [[ADD5:%.*]] = add i64 [[V:%.*]], 5
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw i64 [[V]], 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add5 = add i64 %V, 5
   %add6 = add nsw i64 %V, 6
   %cmp = icmp slt i64 %add5, %add6
   ret i1 %cmp
 }
 
 define <4 x i1> @icmp_nsw_vec(<4 x i32> %V) {
 ; CHECK-LABEL: @icmp_nsw_vec(
-; CHECK-NEXT:    [[ADD5:%.*]] = add <4 x i32> [[V:%.*]], <i32 5, i32 5, i32 5, i32 5>
-; CHECK-NEXT:    [[ADD6:%.*]] = add nsw <4 x i32> [[V]], <i32 6, i32 6, i32 6, i32 6>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <4 x i32> [[ADD5]], [[ADD6]]
-; CHECK-NEXT:    ret <4 x i1> [[CMP]]
+; CHECK-NEXT:    ret <4 x i1> <i1 true, i1 true, i1 true, i1 true>
 ;
   %add5 = add <4 x i32> %V, <i32 5, i32 5, i32 5, i32 5>
   %add6 = add nsw <4 x i32> %V, <i32 6, i32 6, i32 6, i32 6>
   %cmp = icmp slt <4 x i32> %add5, %add6
   ret <4 x i1> %cmp
 }
 
 define i1 @icmp_nsw_3(i32 %V) {

 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add5 = add i32 %V, -125
   %add6 = add nsw i32 %V, -99
   %cmp = icmp slt i32 %add5, %add6
   ret i1 %cmp
 }
 
+define i1 @icmp_nsw_nonpos(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_nonpos(
+; CHECK-NEXT:    ret i1 false
+;
+  %add5 = add i32 %V, 0
+  %add6 = add nsw i32 %V, -1
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
+define i1 @icmp_nsw_nonpos2(i32 %V) {
+; CHECK-LABEL: @icmp_nsw_nonpos2(
+; CHECK-NEXT:    [[ADD5:%.*]] = add i32 [[V:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD5]], [[V]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %add5 = add i32 %V, 1
+  %add6 = add nsw i32 %V, 0
+  %cmp = icmp slt i32 %add5, %add6
+  ret i1 %cmp
+}
+
 attributes #0 = { null_pointer_is_valid }