[KnownBits] Improve implementation of `KnownBits::abs`

[goldstein.w.n]

Summary

abs preserves the lowest set bit, so if we know the lowest set bit,
set it in the output.

As well, implement the case where the operand is known negative.

[RKSimon]

llvm/lib/Support/KnownBits.cpp

417

Maybe call these MaxTZ/MinTZ? Just to make it clear later on we're not talking about the possible min/max values

465

Worth adding a assert(!KnownAbs.hasConflict() && "KnownBits conflict!"); ?

[nikic]

llvm/lib/Support/KnownBits.cpp

470

You can pass IntMinIsPoison to the NSW argument.

473

Under which circumstance is KnownAbs better? Seems fishy.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

You can pass IntMinIsPoison to the NSW argument.

Can we? The 0-Negative_X is positive unless Negative_X == INT_MIN so if IntMinIsPoison we can't set NSW. Also would do slightly better and just do KnownAbs.isNonNegative() because it uses the IntMinIsPoison condition (and others) to try and set output sign.

But either way, since KnownAbs already has logic for setting output sign and we combine our result from negation with KnownAbs its kind of a non-issue.

473

Under which circumstance is KnownAbs better? Seems fishy.

The output sign at the very least. But when testing (even when I was getting the right sign from the computeForAddSub assert(KnownAbs.Zero.isSubsetOf(KnownNeg.Zero) && KnownAbs.isSubsetOf(KnownNeg.One)) was failing on the exhaustive tests.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

473

Its just the sign bit, ill update comment.

[goldstein.w.n]

Update comment about mergeing result. Check inputs/outputs

[nikic]

llvm/lib/Support/KnownBits.cpp

470

I don't understand. The only value for which 0-X wraps is INT_MIN, which is exactly what the IntMinIsPoison flag controls. The entire purpose of that flag is to allow an nsw assumption on the negation.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

Oh I mistakenly though something like sub nsw i8 0, 129 would be poison but guess not.
Either way though, we 'join' with the original abs value to get the signbit so nsw is unneeded no?

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Support/KnownBits.cpp

470

But can we drop that join if NSW is passed? Just making this if (isNegative(X)) return neg(X); would make this logic a lot cleaner.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

But can we drop that join if NSW is passed? Just making this if (isNegative(X)) return neg(X); would make this logic a lot cleaner.

I doesn't seem to cover all cases:

KnownBits Zero(getBitWidth());
Zero.setAllZero();

KnownBits KnownNeg = computeForAddSub(
    /*Add*/ false, KnownAbs.isNegative(), Zero, *this);

// Preserve signbit from `KnownAbs` as it has additional logic for figuring
// it out that we don't want to duplicate here.
KnownBits KnownAbsNoSign = KnownAbs;
KnownBits KnownNegNoSign = KnownNeg;
KnownAbsNoSign.One.clearSignBit();
KnownAbsNoSign.Zero.clearSignBit();
KnownNegNoSign.One.clearSignBit();
KnownNegNoSign.Zero.clearSignBit();

assert(KnownAbsNoSign.One.isSubsetOf(KnownNegNoSign.One));
assert(KnownAbsNoSign.Zero.isSubsetOf(KnownNegNoSign.Zero));

assert(KnownAbs.One.isSubsetOf(KnownNeg.One));
assert(KnownAbs.Zero.isSubsetOf(KnownNeg.Zero));

KnownNeg.One.clearSignBit();
KnownNeg.Zero.clearSignBit();
KnownAbs.One |= KnownNeg.One;
KnownAbs.Zero |= KnownNeg.Zero;

On the exhaustive tests fails:

KnownBits.cpp:440: llvm::KnownBits llvm::KnownBits::abs(bool) const: Assertion `KnownAbs.Zero.isSubsetOf(KnownNeg.Zero)' failed.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

But can we drop that join if NSW is passed? Just making this if (isNegative(X)) return neg(X); would make this logic a lot cleaner.

I doesn't seem to cover all cases:

KnownBits Zero(getBitWidth());
Zero.setAllZero();

KnownBits KnownNeg = computeForAddSub(
    /*Add*/ false, KnownAbs.isNegative(), Zero, *this);

This should be isNonNegative() but still fails the assertion.

// Preserve signbit from `KnownAbs` as it has additional logic for figuring
// it out that we don't want to duplicate here.
KnownBits KnownAbsNoSign = KnownAbs;
KnownBits KnownNegNoSign = KnownNeg;
KnownAbsNoSign.One.clearSignBit();
KnownAbsNoSign.Zero.clearSignBit();
KnownNegNoSign.One.clearSignBit();
KnownNegNoSign.Zero.clearSignBit();

assert(KnownAbsNoSign.One.isSubsetOf(KnownNegNoSign.One));
assert(KnownAbsNoSign.Zero.isSubsetOf(KnownNegNoSign.Zero));

assert(KnownAbs.One.isSubsetOf(KnownNeg.One));
assert(KnownAbs.Zero.isSubsetOf(KnownNeg.Zero));

KnownNeg.One.clearSignBit();
KnownNeg.Zero.clearSignBit();
KnownAbs.One |= KnownNeg.One;
KnownAbs.Zero |= KnownNeg.Zero;

On the exhaustive tests fails:

KnownBits.cpp:440: llvm::KnownBits llvm::KnownBits::abs(bool) const: Assertion `KnownAbs.Zero.isSubsetOf(KnownNeg.Zero)' failed.

[nikic]

llvm/lib/Support/KnownBits.cpp

470

The argument to the NSW flag should be IntMinIsPoison, not KnownAbs.isNegative(). Effectively you're assuming that the flag is always set, so I would expect that to cause exhaustive test failures.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

Earlier in the code is:

if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue())) {
  KnownAbs.One.clearSignBit();
  KnownAbs.Zero.setSignBit();
}

So if KnownAbs.isNonNegative() is a superset of IntMinPoison.

[nikic]

llvm/lib/Support/KnownBits.cpp

470

Okay, I rewrote our test infrastructure to make optimality failures easier to analyze. For a simple implementation using

if (isNegative())
  return computeForAddSub(/*Add*/ false, /*NSW*/ IntMinIsPoison,
                          KnownBits::makeConstant(APInt(getBitWidth(), 0)),
                          *this);

I get these failures:

/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 1?00, Computed = 0?00, Exact = 0100)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 10??, Computed = 0???, Exact = 01??)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 10?0, Computed = 0??0, Exact = 0110)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 100?, Computed = 0???, Exact = 0111)
Expected: true

Basically, the cases where it is non-optimal are cases where we don't make use of the fact that at least one of the unknown bits must be non-zero, otherwise the input would be IntMin. Those are differences in the non-sign bits though. And the optimality failures (for known negative numbers) that I get for your implementation with the KnownAbs fallback are exactly the same.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

470

Okay, I rewrote our test infrastructure to make optimality failures easier to analyze. For a simple implementation using

if (isNegative())
  return computeForAddSub(/*Add*/ false, /*NSW*/ IntMinIsPoison,
                          KnownBits::makeConstant(APInt(getBitWidth(), 0)),
                          *this);

I get these failures:

/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 1?00, Computed = 0?00, Exact = 0100)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 10??, Computed = 0???, Exact = 01??)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 10?0, Computed = 0??0, Exact = 0110)
Expected: true
/home/npopov/repos/llvm-project/llvm/unittests/Support/KnownBitsTest.cpp:86: Failure
Value of: isOptimal(Exact, Computed, Known)
  Actual: false (Inputs = 100?, Computed = 0???, Exact = 0111)
Expected: true

Basically, the cases where it is non-optimal are cases where we don't make use of the fact that at least one of the unknown bits must be non-zero, otherwise the input would be IntMin. Those are differences in the non-sign bits though. And the optimality failures (for known negative numbers) that I get for your implementation with the KnownAbs fallback are exactly the same.

You're right. Its only the poison case. Updating. Also think I can cover all these missing cases so will change to full optimal tests.

[goldstein.w.n]

Fill in the rest of the special cases + only use neg

[goldstein.w.n]

ping.

[foad]

LGTM. I hope that one day we can remove this logic in abs() when computeForAddSub() gets a precise nsw implementation.

[RKSimon]

LGTM

llvm/lib/Support/KnownBits.cpp

 
 KnownBits KnownBits::abs(bool IntMinIsPoison) const {
   // If the source's MSB is zero then we know the rest of the bits already.
   if (isNonNegative())
     return *this;
 
   // Absolute value preserves trailing zero count.
   KnownBits KnownAbs(getBitWidth());
-  KnownAbs.Zero.setLowBits(countMinTrailingZeros());
+
+  // If the input is negative, then abs(x) == -x.
+  if (isNegative()) {
+    KnownBits Tmp = *this;
+    // Special case for IntMinIsPoison. We know the sign bit is set and we know
+    // all the rest of the bits except one to be zero. Since we have
+    // IntMinIsPoison, that final bit MUST be a one, as otherwise the input is
+    // INT_MIN.
+    if (IntMinIsPoison && (Zero.popcount() + 2) == getBitWidth())
+      Tmp.One.setBit(countMinTrailingZeros());
+
+    KnownAbs = computeForAddSub(
+        /*Add*/ false, IntMinIsPoison,
+        KnownBits::makeConstant(APInt(getBitWidth(), 0)), Tmp);
+
+    // One more special case for IntMinIsPoison. If we don't know any ones other
+    // than the signbit, we know for certain that all the unknowns can't be
+    // zero. So if we know high zero bits, but have unknown low bits, we know
+    // for certain those high-zero bits will end up as one. This is because,
+    // the low bits can't be all zeros, so the +1 in (~x + 1) cannot carry up
+    // to the high bits. If we know a known INT_MIN input skip this. The result
+    // is poison anyways.
+    if (IntMinIsPoison && Tmp.countMinPopulation() == 1 &&
+        Tmp.countMaxPopulation() != 1) {
+      Tmp.One.clearSignBit();
+      Tmp.Zero.setSignBit();
+      KnownAbs.One.setBits(getBitWidth() - Tmp.countMinLeadingZeros(),
+                           getBitWidth() - 1);
+    }
+
+  } else {
+    unsigned MaxTZ = countMaxTrailingZeros();
+    unsigned MinTZ = countMinTrailingZeros();
+
+    KnownAbs.Zero.setLowBits(MinTZ);
+    // If we know the lowest set 1, then preserve it.
+    if (MaxTZ == MinTZ && MaxTZ < getBitWidth())
+      KnownAbs.One.setBit(MaxTZ);
 
     // We only know that the absolute values's MSB will be zero if INT_MIN is
     // poison, or there is a set bit that isn't the sign bit (otherwise it could
     // be INT_MIN).
-  if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue()))
+    if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue())) {
+      KnownAbs.One.clearSignBit();
       KnownAbs.Zero.setSignBit();
+    }
+  }
 
-  // FIXME: Handle known negative input?
-  // FIXME: Calculate the negated Known bits and combine them?
+  assert(!KnownAbs.hasConflict() && "Bad Output");
   return KnownAbs;
 }
 
 KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
                          bool NoUndefSelfMultiply) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
          !RHS.hasConflict() && "Operand mismatch");
   assert((!NoUndefSelfMultiply || LHS == RHS) &&
          "Self multiplication knownbits mismatch");
 
   // Compute the high known-0 bits by multiplying the unsigned max of each side.
   // Conservatively, M active bits * N active bits results in M + N bits in the
   // result. But if we know a value is a power-of-2 for example, then this
   // computes one more leading zero.
   // TODO: This could be generalized to number of sign bits (negative numbers).
   APInt UMaxLHS = LHS.getMaxValue();

llvm/test/Analysis/ValueTracking/knownbits-abs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instsimplify -S < %s | FileCheck %s
 declare i8 @llvm.abs.i8(i8, i1)
 
 define i1 @abs_low_bit_set(i8 %x) {
 ; CHECK-LABEL: @abs_low_bit_set(
-; CHECK-NEXT:    [[XX:%.*]] = and i8 [[X:%.*]], -16
-; CHECK-NEXT:    [[V:%.*]] = or i8 [[XX]], 4
-; CHECK-NEXT:    [[ABS:%.*]] = call i8 @llvm.abs.i8(i8 [[V]], i1 true)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[ABS]], 4
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %xx = and i8 %x, 240
   %v = or i8 %xx, 4
   %abs = call i8 @llvm.abs.i8(i8 %v, i1 true)
   %and = and i8 %abs, 4
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
;
   %abs = call i8 @llvm.abs.i8(i8 %v, i1 true)
   %and = and i8 %abs, 2
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @abs_negative(i8 %x) {
 ; CHECK-LABEL: @abs_negative(
-; CHECK-NEXT:    [[XX:%.*]] = and i8 [[X:%.*]], -16
-; CHECK-NEXT:    [[V:%.*]] = or i8 [[XX]], -124
-; CHECK-NEXT:    [[ABS:%.*]] = call i8 @llvm.abs.i8(i8 [[V]], i1 true)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[ABS]], 8
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %xx = and i8 %x, 240
   %v = or i8 %xx, 132
   %abs = call i8 @llvm.abs.i8(i8 %v, i1 true)
   %and = and i8 %abs, 8
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @abs_negative2(i8 %x) {
 ; CHECK-LABEL: @abs_negative2(
-; CHECK-NEXT:    [[V:%.*]] = or i8 [[X:%.*]], -125
-; CHECK-NEXT:    [[ABS:%.*]] = call i8 @llvm.abs.i8(i8 [[V]], i1 true)
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[ABS]], 2
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 2
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %v = or i8 %x, 131
   %abs = call i8 @llvm.abs.i8(i8 %v, i1 true)
   %and = and i8 %abs, 2
   %r = icmp eq i8 %and, 2
   ret i1 %r
 }
 

llvm/unittests/Support/KnownBitsTest.cpp

testBinaryOpExhaustive(
       [](const APInt &N1, const APInt &N2) {
         unsigned Bits = N1.getBitWidth();
         return (N1.zext(2 * Bits) * N2.zext(2 * Bits)).extractBits(Bits, Bits);
       },
       checkCorrectnessOnlyBinary);
 }
 
 TEST(KnownBitsTest, UnaryExhaustive) {
-  // TODO: Make optimal for cases that are not known non-negative.
-  testUnaryOpExhaustive(
-      [](const KnownBits &Known) { return Known.abs(); },
-      [](const APInt &N) { return N.abs(); },
-      [](const KnownBits &Known) { return Known.isNonNegative(); });
+  testUnaryOpExhaustive([](const KnownBits &Known) { return Known.abs(); },
+                        [](const APInt &N) { return N.abs(); });
 
-  testUnaryOpExhaustive(
-      [](const KnownBits &Known) { return Known.abs(true); },
+  testUnaryOpExhaustive([](const KnownBits &Known) { return Known.abs(true); },
                         [](const APInt &N) -> std::optional<APInt> {
                           if (N.isMinSignedValue())
                             return std::nullopt;
                           return N.abs();
-      },
-      [](const KnownBits &Known) { return Known.isNonNegative(); });
+                        });
 
   testUnaryOpExhaustive([](const KnownBits &Known) { return Known.blsi(); },
                         [](const APInt &N) { return N & -N; });
   testUnaryOpExhaustive([](const KnownBits &Known) { return Known.blsmsk(); },
                         [](const APInt &N) { return N ^ (N - 1); });
 
   testUnaryOpExhaustive(
       [](const KnownBits &Known) {