[ConstantRange] Add fromKnownBits() method

[nikic]

Summary

Following the suggestion in D59450, I'm moving the code for constructing a ConstantRange from KnownBits out of ValueTracking, which also allows us to add a couple of unit tests...

I'm adding this method to ConstantRange rather than KnownBits (which would have been a bit nicer) to avoid creating a dependency from Support to IR, where ConstantRange lives.

PS: C++14 binary literals would be great for these kinds of tests...

[lebedev.ri]

Nice!

Would it be possible/reasonable to also add exaustive tests?

[nikic]

Add exhaustive test.

[lebedev.ri]

LGTM, nice, thank you very much!

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

58–59

Last-minute thought: should there be a assert(!Known.hasConflict() && "Expected valid KnownBits"); ?
The used methods of KnownBits won't assert that by themselves..

[nikic]

llvm/lib/IR/ConstantRange.cpp

58–59

I've added this assertion in rL356346.

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

58–59

Thanks

llvm/include/llvm/IR/ConstantRange.h

 #include "llvm/IR/Instruction.h"
 #include "llvm/Support/Compiler.h"
 #include <cstdint>
 
 namespace llvm {
 
 class MDNode;
 class raw_ostream;
+struct KnownBits;
 
 /// This class represents a range of values.
 class LLVM_NODISCARD ConstantRange {
   APInt Lower, Upper;
 
 public:
   /// Initialize a full (the default) or empty set for the specified bit width.
   explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true);
 
   /// Initialize a range to hold the single specified value.
   ConstantRange(APInt Value);
 
   /// Initialize a range of values explicitly. This will assert out if
   /// Lower==Upper and Lower != Min or Max value for its type. It will also
   /// assert out if the two APInt's are not the same bit width.
   ConstantRange(APInt Lower, APInt Upper);
 
+  /// Initialize a range based on a known bits constraint. The IsSigned flag
+  /// indicates whether the constant range should not wrap in the signed or
+  /// unsigned domain.
+  static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned);
+
   /// Produce the smallest range such that all values that may satisfy the given
   /// predicate with any value contained within Other is contained in the
   /// returned range.  Formally, this returns a superset of
   /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
   /// answer is not representable as a ConstantRange, the return value will be a
   /// proper superset of the above.
   ///
   /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)

llvm/lib/Analysis/ValueTracking.cpp

switch (OR) {
     case ConstantRange::OverflowResult::AlwaysOverflows:
       return OverflowResult::AlwaysOverflows;
     case ConstantRange::OverflowResult::NeverOverflows:
       return OverflowResult::NeverOverflows;
   }
   llvm_unreachable("Unknown OverflowResult");
 }
 
-static ConstantRange constantRangeFromKnownBits(const KnownBits &Known) {
-  if (Known.isUnknown())
-    return ConstantRange(Known.getBitWidth(), /* full */ true);
-
-  return ConstantRange(Known.One, ~Known.Zero + 1);
-}
-
 OverflowResult llvm::computeOverflowForUnsignedAdd(
     const Value *LHS, const Value *RHS, const DataLayout &DL,
     AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT,
     bool UseInstrInfo) {
   KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT,
                                         nullptr, UseInstrInfo);
   KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT,
                                         nullptr, UseInstrInfo);
-  ConstantRange LHSRange = constantRangeFromKnownBits(LHSKnown);
-  ConstantRange RHSRange = constantRangeFromKnownBits(RHSKnown);
+  ConstantRange LHSRange =
+      ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
+  ConstantRange RHSRange =
+      ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
   return mapOverflowResult(LHSRange.unsignedAddMayOverflow(RHSRange));
 }
 
 /// Return true if we can prove that adding the two values of the
 /// knownbits will not overflow.
 /// Otherwise return false.
 static bool checkRippleForSignedAdd(const KnownBits &LHSKnown,
                                     const KnownBits &RHSKnown) {

 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
   KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
   KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
-  ConstantRange LHSRange = constantRangeFromKnownBits(LHSKnown);
-  ConstantRange RHSRange = constantRangeFromKnownBits(RHSKnown);
+  ConstantRange LHSRange =
+      ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false);
+  ConstantRange RHSRange =
+      ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false);
   return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange));
 }
 
 OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
                                                  const Value *RHS,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,

llvm/lib/IR/ConstantRange.cpp

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/KnownBits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 
 using namespace llvm;
 
 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
       Upper(Lower) {}
 
 ConstantRange::ConstantRange(APInt V)
     : Lower(std::move(V)), Upper(Lower + 1) {}
 
 ConstantRange::ConstantRange(APInt L, APInt U)
     : Lower(std::move(L)), Upper(std::move(U)) {
   assert(Lower.getBitWidth() == Upper.getBitWidth() &&
          "ConstantRange with unequal bit widths");
   assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
          "Lower == Upper, but they aren't min or max value!");
 }
 
+ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
+                                           bool IsSigned) {
+  if (Known.isUnknown())
+    return ConstantRange(Known.getBitWidth(), /* full */ true);
+
+  // For unsigned ranges, or signed ranges with known sign bit, create a simple
+  // range between the smallest and largest possible value.
+  if (!IsSigned || Known.isNegative() || Known.isNonNegative())
+    return ConstantRange(Known.One, ~Known.Zero + 1);
+
+  // If we don't know the sign bit, pick the lower bound as a negative number
+  // and the upper bound as a non-negative one.
+  APInt Lower = Known.One, Upper = ~Known.Zero;
+  Lower.setSignBit();
+  Upper.clearSignBit();
+  return ConstantRange(Lower, Upper + 1);
+}
+
 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
                                                    const ConstantRange &CR) {
   if (CR.isEmptySet())
     return CR;
 
   uint32_t W = CR.getBitWidth();
   switch (Pred) {
   default:

llvm/unittests/IR/ConstantRangeTest.cpp

 //===- ConstantRangeTest.cpp - ConstantRange 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/Support/KnownBits.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 class ConstantRangeTest : public ::testing::Test {
 protected:
TestOverflowExhaustive(
         (void) N1.ssub_ov(N2, Overflow);
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.signedSubMayOverflow(CR2);
       });
 }
 
+TEST_F(ConstantRangeTest, FromKnownBits) {
+  KnownBits Unknown(16);
+  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
+  EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
+
+  // .10..01. -> unsigned 01000010 (66)  to 11011011 (219)
+  //          -> signed   11000010 (194) to 01011011 (91)
+  KnownBits Known(8);
+  Known.Zero = 36;
+  Known.One = 66;
+  ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
+  ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
+  EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
+  EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
+
+  // 1.10.10. -> 10100100 (164) to 11101101 (237)
+  Known.Zero = 18;
+  Known.One = 164;
+  ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
+  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
+  EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
+
+  // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
+  Known.Zero = 145;
+  Known.One = 68;
+  ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
+  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
+  EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
+}
+
+TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
+  unsigned Bits = 4;
+  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() || Known.isUnknown())
+        continue;
+
+      APInt MinUnsigned = APInt::getMaxValue(Bits);
+      APInt MaxUnsigned = APInt::getMinValue(Bits);
+      APInt MinSigned = APInt::getSignedMaxValue(Bits);
+      APInt MaxSigned = APInt::getSignedMinValue(Bits);
+      for (unsigned N = 0; N < Max; ++N) {
+        APInt Num(Bits, N);
+        if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
+          continue;
+
+        if (Num.ult(MinUnsigned)) MinUnsigned = Num;
+        if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num;
+        if (Num.slt(MinSigned)) MinSigned = Num;
+        if (Num.sgt(MaxSigned)) MaxSigned = Num;
+      }
+
+      ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
+      ConstantRange SignedCR(MinSigned, MaxSigned + 1);
+      EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
+      EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
+    }
+  }
+}
+
 }  // anonymous namespace