InstSimplify: The upper bound of X / C was missing a rounding step

[majnemer]

Summary

When calculating the upper bound of X / -8589934592, we would perform
the following calculation: Floor[INT_MAX / 8589934592]

However, flooring the result would make us wrongly come to the
conclusion that 1073741824 was not in the set of possible values.
Instead, use the ceiling of the result.

[nlewycky]

LGTM

FYI, this testcase should also be canonicalized by instcombine, which makes
sense to add now that instsimplify isn't catch it ;-)

[majnemer]

Closed by commit rL212976 (authored by @majnemer).

[majnemer]

We already get this with InstCombine:

%cmp = icmp ne i64 %call, -9223372036854775808
ret i1 %cmp

lib/Analysis/InstructionSimplify.cpp

if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
       }
     } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) {
       // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2].
       APInt IntMin = APInt::getSignedMinValue(Width);
       APInt IntMax = APInt::getSignedMaxValue(Width);
       APInt Val = CI2->getValue().abs();
       if (!Val.isMinValue()) {
         Lower = IntMin.sdiv(Val);
-        Upper = IntMax.sdiv(Val) + 1;
+        APInt Rem;
+        APInt::sdivrem(IntMax, Val, Upper, Rem);
+        // We may need to round the result of the INT_MAX / CI2 calculation up
+        // if we see that the division was not exact.
+        if (Rem.isMinValue())
+          Upper = Upper + 1;
+        else
+          Upper = Upper + 2;
+        assert(Upper != Lower && "Upper part of range has wrapped!");
       }
     } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
       // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
       APInt NegOne = APInt::getAllOnesValue(Width);
       if (CI2->getValue().ult(Width))
         Upper = NegOne.lshr(CI2->getValue()) + 1;
     } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) {
       // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2].

test/Transforms/InstSimplify/compare.ll

define i1 @icmp_sdiv_int_min(i32 %a) {
   %cmp = icmp ne i32 %div, -1073741824
   ret i1 %cmp
 
 ; CHECK-LABEL: @icmp_sdiv_int_min
 ; CHECK-NEXT: [[DIV:%.*]] = sdiv i32 -2147483648, %a
 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[DIV]], -1073741824
 ; CHECK-NEXT: ret i1 [[CMP]]
 }
+
+define i1 @icmp_sdiv_pr20288(i64 %a) {
+   %div = sdiv i64 %a, -8589934592
+   %cmp = icmp ne i64 %div, 1073741824
+   ret i1 %cmp
+
+; CHECK-LABEL: @icmp_sdiv_pr20288
+; CHECK-NEXT: [[DIV:%.*]] = sdiv i64 %a, -8589934592
+; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[DIV]], 1073741824
+; CHECK-NEXT: ret i1 [[CMP]]
+}