[KnownBits] Add computeForAddCarry()

[nikic]

Summary

This is for D60460. computeForAddSub() essentially already supports carries because it has to deal with subtractions. This revision extracts a lower-level computeForAddCarry() function, which allows computing the known bits for add (carry known zero), sub (carry known one) and addcarry (carry unknown).

As we don't seem to have any yet, I've added a unit test file for KnownBits and an exhaustive test for the computeForAddCarry functionality.

[lebedev.ri]

llvm/lib/Support/KnownBits.cpp

20–21 ↗

(On Diff #194548)

How about simply making it KnownBits(/*KnownBits=*/1) ?

[nikic]

llvm/lib/Support/KnownBits.cpp

20–21 ↗

(On Diff #194548)

It's a possibility, but I'm not convinced it's better here. The booleans directly enforce the contract that this is just one bit (while for KnownBits we could only assert that), they're cheaper to construct and use than two APInts, and the API is simpler to use, because we don't have to construct KnownBits (which is somewhat roundabout due to lack of a direct ctor).

I think the only place that would really benefit from passing carry as KnownBits is the testing code, while for other usages having this as booleans is more convenient and efficient.

[RKSimon]

llvm/lib/Support/KnownBits.cpp

35 ↗

(On Diff #194548)

Are we gaining much from using the std::move? It reduces grokability and in most cases we'll be dealing with APInts representing i64 or less so its not heap allocated.

llvm/unittests/Support/KnownBitsTest.cpp

49 ↗

(On Diff #194548)

AddCarryExhaustive

[bjope]

llvm/lib/Support/KnownBits.cpp

20–21 ↗

(On Diff #194548)

If we want to also track the carry in the future I guess we would get that as a "KnownBits".

So I think that for ADDCARRY we probably want to do

KnownBits KnownLHS = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
KnownBits KnownRHS = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
KnownBits KnownCarry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
Known = computeForAddCarry(KnownLHS, KnownRHS, KnownCarry.trunc(1));

if we also want to also track down the known bits of the carry.

So having a computeForAddCarry method that takes a KnownBits(1) might actually be useful (compared to trying to convert KnownCarry into two booleans on the user side of this API). If there is a use for also having the bool based interface, then perhaps we can have both?

[nikic]

Use KnownBits for carry in exported API, fix typo in test name.

[nikic]

llvm/lib/Support/KnownBits.cpp

20–21 ↗

(On Diff #194548)

That's a good point. I've changed the implementation to use a 1-bit KnownBits in the exported API. The variant that uses two booleans is now only used internally to shared between the exported computeForAddCarry and computeForAddSub APIs.

[nikic]

llvm/lib/Support/KnownBits.cpp

35 ↗

(On Diff #194548)

The use of std::move() in this code was introduced as part of D36433. Maybe @craig.topper could comment?

[bjope]

LGTM! (with a nit in the test case)

I also think we should consider to add more exhaustive tests for computeForAddSub, now when we got the unittest support from this patch.

llvm/unittests/Support/KnownBitsTest.cpp

1 ↗

(On Diff #194650)

nit: KnownBitsTest.cpp

48 ↗

(On Diff #194650)

The patch slightly touches the computeForAddSub implementation. So even if it can be seen as unrelated, maybe we should add a exhaustive test for computeForAddSub as well. Shouldn't be too hard given this framework, or what do you think?

[nikic]

Fix file name, add tests for computeForAddSub().

[nikic]

Also test NSW flag.

[lebedev.ri]

LG modulo nits, if @RKSimon has no further comments.

llvm/lib/Support/KnownBits.cpp

18 ↗

(On Diff #194859)

The signature is already different from computeForAddCarry() (2 bools vs 1 KnownBits),
i don't see the need for Internal suffix.
Also, i believe anonymous namespaces are preferred, so drop static, and wrap into namespace {}.

54 ↗

(On Diff #194859)

All these bool params are potential bugs, and really affect readability.
But i guess that would be too intrusive for this header.

[nikic]

llvm/lib/Support/KnownBits.cpp

18 ↗

(On Diff #194859)

Agree on the suffix being unnecessary. Regarding anonymous namespaces, https://llvm.org/docs/CodingStandards.html#anonymous-namespaces says:

Because of this, we have a simple guideline: make anonymous namespaces as small as possible, and only use them for class declarations.

If I'm understanding correctly, this means that anon namespaces should be used for classes and static for functions.

[RKSimon]

LGTM - let's leave the std::move issue for now

[lebedev.ri]

llvm/lib/Support/KnownBits.cpp

18 ↗

(On Diff #194859)

If I'm understanding correctly, this means that anon namespaces should be used for classes and static for functions.

There have been discussions about exactly that recently, in other reviews.
So i'm not confident what is currently considered as the best common practice for functions.

[nikic]

llvm/lib/Support/KnownBits.cpp

18 ↗

(On Diff #194859)

I'd prefer to leave this as a static function for now -- if there's interest in changing the recommended practice around this it should imho start with a patch to CodingStandards.

54 ↗

(On Diff #194859)

We might want to start a separate file outside Support (I'm thinking llvm/Analysis/KnownBitsOps.h and lib/Analysis/KnownBitsOps.cpp) that can depend on things like binop opcodes and obo flags and allow sharing more of the KnownBits code between ValueTracking and SDAG. The existing KnownBits header mostly has only primitive operations and is quite cumbersome to edit (because it rebuilds half of LLVM).

[lebedev.ri]

llvm/lib/Support/KnownBits.cpp

54 ↗

(On Diff #194859)

Sorry, there was another phrase between those two i posted:

All these bool params are potential bugs, and really affect readability.

"i'd prefer to pass them as some enum fields, e.g. the ones used elsewhere in IR for IR instructions and wrap flags"

But i guess that would be too intrusive for this header.

But yes, i guess it will be best to reinvent the wheel here, and add whole new enum.

llvm/trunk/include/llvm/Support/KnownBits.h

unsigned countMinPopulation() const {
     return One.countPopulation();
   }
 
   /// Returns the maximum number of bits that could be one.
   unsigned countMaxPopulation() const {
     return getBitWidth() - Zero.countPopulation();
   }
 
+  /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
+  static KnownBits computeForAddCarry(
+      const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
+
   /// Compute known bits resulting from adding LHS and RHS.
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
                                     KnownBits RHS);
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Support/KnownBits.cpp

 // computeKnownBits.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/KnownBits.h"
 
 using namespace llvm;
 
-KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
-                                      const KnownBits &LHS, KnownBits RHS) {
-  // Carry in a 1 for a subtract, rather than 0.
-  bool CarryIn = false;
-  if (!Add) {
-    // Sum = LHS + ~RHS + 1
-    std::swap(RHS.Zero, RHS.One);
-    CarryIn = true;
-  }
+static KnownBits computeForAddCarry(
+    const KnownBits &LHS, const KnownBits &RHS,
+    bool CarryZero, bool CarryOne) {
+  assert(!(CarryZero && CarryOne) &&
+         "Carry can't be zero and one at the same time");
 
-  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + CarryIn;
-  APInt PossibleSumOne = LHS.One + RHS.One + CarryIn;
+  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
+  APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
 
   // Compute known bits of the carry.
   APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
   APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
 
   // Compute set of known bits (where all three relevant bits are known).
   APInt LHSKnownUnion = LHS.Zero | LHS.One;
   APInt RHSKnownUnion = RHS.Zero | RHS.One;
   APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
   APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
 
   assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
          "known bits of sum differ");
 
   // Compute known bits of the result.
   KnownBits KnownOut;
   KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
   KnownOut.One = std::move(PossibleSumOne) & Known;
+  return KnownOut;
+}
+
+KnownBits KnownBits::computeForAddCarry(
+    const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
+  assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
+  return ::computeForAddCarry(
+      LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
+}
+
+KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
+                                      const KnownBits &LHS, KnownBits RHS) {
+  KnownBits KnownOut;
+  if (Add) {
+    // Sum = LHS + RHS + 0
+    KnownOut = ::computeForAddCarry(
+        LHS, RHS, /*CarryZero*/true, /*CarryOne*/false);
+  } else {
+    // Sum = LHS + ~RHS + 1
+    std::swap(RHS.Zero, RHS.One);
+    KnownOut = ::computeForAddCarry(
+        LHS, RHS, /*CarryZero*/false, /*CarryOne*/true);
+  }
 
   // Are we still trying to solve for the sign bit?
-  if (!Known.isSignBitSet()) {
+  if (!KnownOut.isNegative() && !KnownOut.isNonNegative()) {
     if (NSW) {
       // Adding two non-negative numbers, or subtracting a negative number from
       // a non-negative one, can't wrap into negative.
       if (LHS.isNonNegative() && RHS.isNonNegative())
         KnownOut.makeNonNegative();
       // Adding two negative numbers, or subtracting a non-negative number from
       // a negative one, can't wrap into non-negative.
       else if (LHS.isNegative() && RHS.isNegative())
         KnownOut.makeNegative();
     }
   }
 
   return KnownOut;
 }

llvm/trunk/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   ErrorOrTest.cpp
   ErrorTest.cpp
   FileOutputBufferTest.cpp
   FormatVariadicTest.cpp
   GlobPatternTest.cpp
   Host.cpp
   ItaniumManglingCanonicalizerTest.cpp
   JSONTest.cpp
+  KnownBitsTest.cpp
   LEB128Test.cpp
   LineIteratorTest.cpp
   LockFileManagerTest.cpp
   MD5Test.cpp
   ManagedStatic.cpp
   MathExtrasTest.cpp
   MemoryBufferTest.cpp
   MemoryTest.cpp

llvm/trunk/unittests/Support/KnownBitsTest.cpp

+//===- llvm/unittest/Support/KnownBitsTest.cpp - KnownBits tests ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements unit tests for KnownBits functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/KnownBits.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+template<typename FnTy>
+void ForeachKnownBits(unsigned Bits, FnTy Fn) {
+  unsigned Max = 1 << Bits;
+  KnownBits Known(Bits);
+  for (unsigned Zero = 0; Zero < Max; ++Zero) {
+    for (unsigned One = 0; One < Max; ++One) {
+      Known.Zero = Zero;
+      Known.One = One;
+      if (Known.hasConflict())
+        continue;
+
+      Fn(Known);
+    }
+  }
+}
+
+template<typename FnTy>
+void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
+  unsigned Bits = Known.getBitWidth();
+  unsigned Max = 1 << Bits;
+  for (unsigned N = 0; N < Max; ++N) {
+    APInt Num(Bits, N);
+    if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
+      continue;
+
+    Fn(Num);
+  }
+}
+
+TEST(KnownBitsTest, AddCarryExhaustive) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
+    ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
+      ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
+        // Explicitly compute known bits of the addition by trying all
+        // possibilities.
+        KnownBits Known(Bits);
+        Known.Zero.setAllBits();
+        Known.One.setAllBits();
+        ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
+          ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
+            ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
+              APInt Add = N1 + N2;
+              if (Carry.getBoolValue())
+                ++Add;
+
+              Known.One &= Add;
+              Known.Zero &= ~Add;
+            });
+          });
+        });
+
+        KnownBits KnownComputed = KnownBits::computeForAddCarry(
+            Known1, Known2, KnownCarry);
+        EXPECT_EQ(Known.Zero, KnownComputed.Zero);
+        EXPECT_EQ(Known.One, KnownComputed.One);
+      });
+    });
+  });
+}
+
+static void TestAddSubExhaustive(bool IsAdd) {
+  unsigned Bits = 4;
+  ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
+    ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
+      KnownBits Known(Bits), KnownNSW(Bits);
+      Known.Zero.setAllBits();
+      Known.One.setAllBits();
+      KnownNSW.Zero.setAllBits();
+      KnownNSW.One.setAllBits();
+
+      ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
+        ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
+          bool Overflow;
+          APInt Res;
+          if (IsAdd)
+            Res = N1.sadd_ov(N2, Overflow);
+          else
+            Res = N1.ssub_ov(N2, Overflow);
+
+          Known.One &= Res;
+          Known.Zero &= ~Res;
+
+          if (!Overflow) {
+            KnownNSW.One &= Res;
+            KnownNSW.Zero &= ~Res;
+          }
+        });
+      });
+
+      KnownBits KnownComputed = KnownBits::computeForAddSub(
+          IsAdd, /*NSW*/false, Known1, Known2);
+      EXPECT_EQ(Known.Zero, KnownComputed.Zero);
+      EXPECT_EQ(Known.One, KnownComputed.One);
+
+      // The NSW calculation is not precise, only check that it's
+      // conservatively correct.
+      KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
+          IsAdd, /*NSW*/true, Known1, Known2);
+      EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
+      EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
+    });
+  });
+}
+
+TEST(KnownBitsTest, AddSubExhaustive) {
+  TestAddSubExhaustive(true);
+  TestAddSubExhaustive(false);
+}
+
+} // end anonymous namespace