[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

1937

Blank comment line.

1941

Is this ever different from Denominator.ceilLogBase2()?

test/Analysis/ValueTracking/pr230011.ll

1

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

1937

Will fix.

1941

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

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

1941

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.  If the numerator is positive, then the remainder is in
+      // [0,C), and the minimum number of sign bits (all zero) is "CLZ(C-1)".
+      // If the numerator is negative, then the remainder is in [-C+1,0] and the
+      // minimum number of sign bits is "CLO(-C+1)".  Therefore a lower bound on
+      // the number of sign bits is MIN(CLZ(C-1), CLO(-C+1)).
+      //
+
+      unsigned WhenPositive = (*Denominator - 1).countLeadingZeros();
+      unsigned WhenNegative = (-(*Denominator) + 1).countLeadingOnes();
+      unsigned ResBits = std::min(WhenPositive, WhenNegative);
 
       return std::max(NumrBits, ResBits);
     }
     break;
   }
 
   case Instruction::AShr: {
     Tmp = ComputeNumSignBits(U->getOperand(0), DL, Depth + 1, Q);

test/Analysis/ValueTracking/pr230011.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+declare void @side_effect()
+
+define i1 @test1() {
+; CHECK-LABEL: @test1
+a:
+  br label %b
+b:
+  %rem = srem i32 2, 3
+  %cmp = icmp slt i32 0, %rem
+  br i1 %cmp, label %c, label %d
+c:
+; CHECK-LABEL: c:
+  %B = phi i32 [0, %b], [%incB, %c]
+  call void @side_effect()
+  %incB = add nsw i32 %B, 1
+  %cmpB = icmp slt i32 %incB, %rem
+  br i1 %cmpB, label %c, label %d
+; CHECK: br i1 %cmpB, label %c, label %d
+d:
+  ret i1 %cmp
+}