[ValueTracking] Don't do an unchecked shift in ComputeNumSignBits

[sanjoy]

Summary

Previously we used to return a bogus result, 0, for IR like `ashr %val,
-1`.

I've also added an assert checking that ComputeNumSignBits at least
returns 1. That assert found an already checked in test case where we
were returning a bad result for ashr %val, -1.

Fixes PR32045.

[majnemer]

lib/Analysis/ValueTracking.cpp

2209 ↗

(On Diff #89562)

Shouldn't we treat this in the same way we treat Instruction::Shl?

[sanjoy]

lib/Analysis/ValueTracking.cpp

2209 ↗

(On Diff #89562)

You mean return 1 for undefined shifts? I don't see a good reason why we should do that (both here and in shl) -- ashr ing more than the bitwidth is undef anyway, so why not be maximally aggressive?

[efriedma]

why not be maximally aggressive?

This is not how undef works... unlike poison, you can't assert sign bits you don't actually have.

[sanjoy]

In D30311#685140, @efriedma wrote:

why not be maximally aggressive?

This is not how undef works... unlike poison, you can't assert sign bits you don't actually have.

Not sure I fully understand you, but I interpreted ashr 's "If op2 is (statically or dynamically) equal to or larger than the number of bits in op1, the result is undefined" rule as meaning ashr i32 %V, 32 is undef. This would mean I can pretend ashr i32 %V, 32 is 0, which has 32 sign bits.

[majnemer]

lib/Analysis/ValueTracking.cpp

2209 ↗

(On Diff #89562)

It is undef but I don't think ComputeNumSignBits it allowed to assign known bits to undef values.

[sanjoy]

• Address review

lib/Analysis/ValueTracking.cpp

2209 ↗

(On Diff #89562)

I see what you mean. I'm a bit embarrassed now that it took me this long. :)

[majnemer]

lib/Analysis/ValueTracking.cpp

2210 ↗

(On Diff #89594)

Should it be == or >= ?

[sanjoy]

lib/Analysis/ValueTracking.cpp

2210 ↗

(On Diff #89594)

The getLimitedValue would've taken care about the > case. Though -- I can change it to getZExtValue() if you want.

[majnemer]

LGTM

lib/Analysis/ValueTracking.cpp

2210 ↗

(On Diff #89594)

Ah, I see. I think it'd be slightly more clear if we used getZExtValue here.

[spatel]

lib/Analysis/ValueTracking.cpp

2209 ↗

(On Diff #89562)

Since it's non-obvious how undef is handled, how about adding a comment to explain why we don't saturate to TyBits? This could be a function-level comment because this can occur with more than just Ashr (and Shl?).

test/Transforms/IndVarSimplify/pr32045.ll

7 ↗

(On Diff #89594)

I think IndVars does make a transformation on this test, so it would be better to check the correct output rather than just checking that no assert occurs. The script at utils/update_test_checks.py can be used with loops now. :)

[sanjoy]

• Address review

[spatel]

LGTM.

llvm/trunk/lib/Analysis/ValueTracking.cpp

for (unsigned i = 0; i != NumElts; ++i) {
     if (EltVal.isNegative())
       EltVal = ~EltVal;
     MinSignBits = std::min(MinSignBits, EltVal.countLeadingZeros());
   }
 
   return MinSignBits;
 }
 
+static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
+                                       const Query &Q);
+
+static unsigned ComputeNumSignBits(const Value *V, unsigned Depth,
+                                   const Query &Q) {
+  unsigned Result = ComputeNumSignBitsImpl(V, Depth, Q);
+  assert(Result > 0 && "At least one sign bit needs to be present!");
+  return Result;
+}
+
 /// Return the number of times the sign bit of the register is replicated into
 /// the other bits. We know that at least 1 bit is always equal to the sign bit
 /// (itself), but other cases can give us information. For example, immediately
 /// after an "ashr X, 2", we know that the top 3 bits are all equal to each
 /// other, so we return 3. For vectors, return the number of sign bits for the
 /// vector element with the mininum number of known sign bits.
-unsigned ComputeNumSignBits(const Value *V, unsigned Depth, const Query &Q) {
+static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
+                                       const Query &Q) {
+
+  // We return the minimum number of sign bits that are guaranteed to be present
+  // in V, so for undef we have to conservatively return 1.  We don't have the
+  // same behavior for poison though -- that's a FIXME today.
+
   unsigned TyBits = Q.DL.getTypeSizeInBits(V->getType()->getScalarType());
   unsigned Tmp, Tmp2;
   unsigned FirstAnswer = 1;
 
   // Note that ConstantInt is handled by the general computeKnownBits case
   // below.
 
   if (Depth == MaxDepth)
case Instruction::SRem: {
     break;
   }
 
   case Instruction::AShr: {
     Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
     // ashr X, C   -> adds C sign bits.  Vectors too.
     const APInt *ShAmt;
     if (match(U->getOperand(1), m_APInt(ShAmt))) {
-      Tmp += ShAmt->getZExtValue();
+      unsigned ShAmtLimited = ShAmt->getZExtValue();
+      if (ShAmtLimited >= TyBits)
+        break;  // Bad shift.
+      Tmp += ShAmtLimited;
       if (Tmp > TyBits) Tmp = TyBits;
     }
     return Tmp;
   }
   case Instruction::Shl: {
     const APInt *ShAmt;
     if (match(U->getOperand(1), m_APInt(ShAmt))) {
       // shl destroys sign bits.

llvm/trunk/test/Transforms/IndVarSimplify/pr32045.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+; This is not an IndVarSimplify bug, but the original symptom
+; manifested as one.
+
+define i32 @foo(i32 %a, i32 %b, i32 %c, i32* %sink) {
+; CHECK-LABEL: @foo(
+; CHECK:       for.end:
+; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 %neg3, -1
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[SHR]]
+; CHECK-NEXT:    [[SHR1:%.*]] = ashr i32 [[SUB]], [[B:%.*]]
+; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[SHR1]], -1
+; CHECK-NEXT:    store i32 [[NEG]], i32* %sink
+;
+entry:
+  %tobool2 = icmp eq i32 %a, 0
+  br i1 %tobool2, label %exit, label %preheader
+
+preheader:
+  %neg3 = phi i32 [ %c, %entry ], [ %neg, %for.end ]
+  br label %for
+
+for:
+  %p = phi i32 [ %dec, %for ], [ 1, %preheader ]
+  %cmp = icmp sgt i32 %p, -1
+  %dec = add nsw i32 %p, -1
+  br i1 %cmp, label %for, label %for.end
+
+for.end:
+  %shr = ashr i32 %neg3, %p
+  %sub = sub nsw i32 0, %shr
+  %shr1 = ashr i32 %sub, %b
+  %neg = xor i32 %shr1, -1
+  store i32 %neg, i32* %sink
+  br i1 false, label %exit, label %preheader
+
+exit:
+  ret i32 0
+}

llvm/trunk/unittests/Analysis/ValueTrackingTest.cpp

TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) {
   int Index = 0;
   for (auto &I : BB) {
     EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I),
               ExpectedAnswers[Index])
         << "Incorrect answer at instruction " << Index << " = " << I;
     Index++;
   }
 }
+
+TEST(ValueTracking, ComputeNumSignBits_PR32045) {
+  StringRef Assembly = "define i32 @f(i32 %a) { "
+                       "  %val = ashr i32 %a, -1 "
+                       "  ret i32 %val "
+                       "} ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  auto *RVal =
+      cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0);
+  EXPECT_EQ(ComputeNumSignBits(RVal, M->getDataLayout()), 1);
+}