Teach ComputeNumSignBits about signed divisions

[nadav]

Summary

Hi,

The attached patch teaches ComputeNumSignBits that when a number is divided by a positive constant then the top floor(log(n)) bits are identical.

Thanks,
Nadav

[sanjoy]

lib/Analysis/ValueTracking.cpp

1732 ↗

(On Diff #21087)

Nit: "non-positive"

1733 ↗

(On Diff #21087)

Why not do this check before the call to ComputeNumSignBits? Then we'll bail out earlier without doing unnecessary work.

[majnemer]

../llvm/lib/Analysis/ValueTracking.cpp

1738

I think this result can become larger than the bitwidth if your numerator is very small and your denominator is very large.

Arithmetically, the result of such a division would be zero but we might not have simplified it yet.

An example of this would be

%and = and i32 %x, 1
%div = sdiv i32 %and, 1073741824

The number of sign bits in %and is 31 and they are all zero.
The log-base2 of the denominator is 30. I don't think the answer coming from this query cannot be larger than the bitwdith.

[nadav]

r231140

../llvm/lib/Analysis/ValueTracking.cpp

     Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
     return ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q) + Tmp;
 
+  case Instruction::SDiv:
+    const APInt *Denominator;
+    // sdiv X, C -> adds log(C) sign bits.
+    if (match(U->getOperand(1), m_APInt(Denominator))) {
+
+      // Ignore non-positive denominator.
+      if (!Denominator->isStrictlyPositive())
+        break;
+
+      unsigned NumBits = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
+
+      // Add floor(log(c)) bits.
+      return NumBits + Denominator->logBase2();
+    }
+    break;
+
   case Instruction::AShr: {
     Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1, Q);
     // ashr X, C   -> adds C sign bits.  Vectors too.

../llvm/test/Transforms/InstCombine/intrinsics.ll

 ; CHECK-NEXT: call i32 @llvm.cttz.i32(i32 %Value, i1 false)
 ; CHECK-NEXT: ret i32
 }
+
+; CHECK-LABEL: @overflow_div(
+; CHECK: ret i1 false
+define i1 @overflow_div(i32 %v1, i32 %v2) nounwind {
+entry:
+  %div = sdiv i32 %v1, 2
+  %t = call %ov.result.32 @llvm.sadd.with.overflow.i32(i32 %div, i32 1)
+  %obit = extractvalue %ov.result.32 %t, 1
+  ret i1 %obit
+}
+