[ValueTracking] Fix PR23011.

[sanjoy]

Summary

ComputeNumSignBits returns incorrect results for srem instructions.
This change fixes the issue and adds a test case.

[nicholas]

lib/Analysis/ValueTracking.cpp

1936

Blank comment line.

1940

Is this ever different from Denominator.ceilLogBase2()?

test/Analysis/ValueTracking/pr230011.ll

1 ↗

(On Diff #22626)

File name is off "pr230011.ll" should be "pr23011.ll".

Also, if this is a bug in value tracking, isn't there a more direct way to observe it than this? Maybe just srem + and and then opt -instsimplify?

[sanjoy]

lib/Analysis/ValueTracking.cpp

1936

Will fix.

1940

The only case where this differs from TyBits - ceilLogBase2 is when Denominator = 1 -- TyBits - ceilLogBase2 will correctly be TyBits in that case (i.e. all bits are sign bits) but the current version of the code will return 0 (i.e. no bits are sign bits). I noticed this just now, and it was not intentional. I can think of two ways to fix this:

• use ceilLogBase2. I had decided to against this because I think it is easier to see why the analysis is correct in the current form (i.e. with CLZ/CLO).
• special case WhenNegative (or the whole computation) when Denominator is 1.

I'd prefer doing the latter. WDYT?

test/Analysis/ValueTracking/pr230011.ll

1 ↗

(On Diff #22626)

Yes. I think I'll also switch out the constant-foldable instruction with something like srem %foo, 3.

[nadav]

Nick, Sanjoy,

I am sorry for the bug. Thanks for catching and fixing it. One easy way to write a testcase is to rely on the 'overflow' optimizations in instcombine. See the function overflow_mod_mul in Transforms/InstCombine/intrinsics.ll.

-Nadav

[nlewycky]

lib/Analysis/ValueTracking.cpp

1940

I have a weak preference to keep the comment explaining it as it does, then to use ceilLogBase2 in the implementation. I like code reuse and don't think Denominator==1 should ever make it this far so I'd rather not special case it, but either way is just fine with me.

[sanjoy]

Address review:

• use ceilLogBase2
• fix test case file name
• test case to use @llvm.smul.with.overflow.i8

[nlewycky]

LGTM

lib/Analysis/ValueTracking.cpp

if (match(U->getOperand(1), m_APInt(Denominator))) {
       // Add floor(log(C)) bits to the numerator bits.
       return std::min(TyBits, NumBits + Denominator->logBase2());
     }
     break;
   }
 
   case Instruction::SRem: {
     const APInt *Denominator;
-    // srem X, C -> we know that the result is within 0..C-1 when C is a
-    // positive constant and the sign bits are at most TypeBits - log2(C).
+    // srem X, C -> we know that the result is within [-C+1,C) when C is a
+    // positive constant.  This let us put a lower bound on the number of sign
+    // bits.
     if (match(U->getOperand(1), m_APInt(Denominator))) {
 
       // Ignore non-positive denominator.
       if (!Denominator->isStrictlyPositive())
         break;
 
       // Calculate the incoming numerator bits. SRem by a positive constant
       // can't lower the number of sign bits.
       unsigned NumrBits =
           ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
 
       // Calculate the leading sign bit constraints by examining the
-      // denominator. The remainder is in the range 0..C-1, which is
-      // calculated by the log2(denominator). The sign bits are the bit-width
-      // minus this value. The result of this subtraction has to be positive.
-      unsigned ResBits = TyBits - Denominator->logBase2();
+      // denominator.  Given that the denominator is positive, there are two
+      // cases:
+      //
+      //  1. the numerator is positive.  The result range is [0,C) and [0,C) u<
+      //     (1 << ceilLogBase2(C)).
+      //
+      //  2. the numerator is negative.  Then the result range is (-C,0] and
+      //     integers in (-C,0] are either 0 or >u (-1 << ceilLogBase2(C)).
+      //
+      // Thus a lower bound on the number of sign bits is `TyBits -
+      // ceilLogBase2(C)`.
 
+      unsigned ResBits = TyBits - Denominator->ceilLogBase2();
       return std::max(NumrBits, ResBits);
     }
     break;
   }
 
   case Instruction::AShr: {
     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);
     // ashr X, C   -> adds C sign bits.  Vectors too.

test/Analysis/ValueTracking/pr23011.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+declare { i8, i1 } @llvm.smul.with.overflow.i8(i8, i8) nounwind readnone
+
+define i1 @test1(i8 %x) {
+ entry:
+; CHECK-LABEL: @test1
+  %rem = srem i8 %x, 15
+  %t = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %rem, i8 %rem)
+; CHECK: %t = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 %rem, i8 %rem)
+; CHECK: %obit = extractvalue { i8, i1 } %t, 1
+; CHECK: ret i1 %obit
+  %obit = extractvalue { i8, i1 } %t, 1
+  ret i1 %obit
+}