Index: llvm/include/llvm/Support/KnownBits.h =================================================================== --- llvm/include/llvm/Support/KnownBits.h +++ llvm/include/llvm/Support/KnownBits.h @@ -202,6 +202,11 @@ return getBitWidth() - Zero.countPopulation(); } + /// Compute known bits resulting from adding LHS, RHS and a possible Carry. + static KnownBits computeForAddCarry( + const KnownBits &LHS, const KnownBits &RHS, + bool CarryKnownZero, bool CarryKnownOne); + /// Compute known bits resulting from adding LHS and RHS. static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS); Index: llvm/lib/Support/KnownBits.cpp =================================================================== --- llvm/lib/Support/KnownBits.cpp +++ llvm/lib/Support/KnownBits.cpp @@ -15,18 +15,14 @@ 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; - } +KnownBits 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); @@ -45,9 +41,25 @@ KnownBits KnownOut; KnownOut.Zero = ~std::move(PossibleSumZero) & Known; KnownOut.One = std::move(PossibleSumOne) & Known; + return KnownOut; +} + +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. Index: llvm/unittests/Support/CMakeLists.txt =================================================================== --- llvm/unittests/Support/CMakeLists.txt +++ llvm/unittests/Support/CMakeLists.txt @@ -34,6 +34,7 @@ Host.cpp ItaniumManglingCanonicalizerTest.cpp JSONTest.cpp + KnownBitsTest.cpp LEB128Test.cpp LineIteratorTest.cpp LockFileManagerTest.cpp Index: llvm/unittests/Support/KnownBitsTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/Support/KnownBitsTest.cpp @@ -0,0 +1,82 @@ +//===- llvm/unittest/Support/KnownBits.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 +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 +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, AddCarryExhausive) { + 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.Zero.getBoolValue(), KnownCarry.One.getBoolValue()); + EXPECT_EQ(Known.Zero, KnownComputed.Zero); + EXPECT_EQ(Known.One, KnownComputed.One); + }); + }); + }); +} + +} // end anonymous namespace