[ConstantRange] Add toKnownBits() method

Add toKnownBits() method to mirror fromKnownBits(). We know the
top bits that are constant between min and max.

The return value for an empty range is chosen to be conservative.

3 files changed, 40 insertions, 0 deletions

diff --git a/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h
index fea4d0d..68abf4e 100644
--- a/llvm/include/llvm/IR/ConstantRange.h
+++ b/llvm/include/llvm/IR/ConstantRange.h
@@ -553,6 +553,9 @@ public:
   /// Return whether unsigned mul of the two ranges always/never overflows.
   OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const;
 
+  /// Return known bits for values in this range.
+  KnownBits toKnownBits() const;
+
   /// Print out the bounds to a stream.
   void print(raw_ostream &OS) const;
 
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index a0f2179..16eb4d0 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -75,6 +75,24 @@ ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
   return ConstantRange(Lower, Upper + 1);
 }
 
+KnownBits ConstantRange::toKnownBits() const {
+  // TODO: We could return conflicting known bits here, but consumers are
+  // likely not prepared for that.
+  if (isEmptySet())
+    return KnownBits(getBitWidth());
+
+  // We can only retain the top bits that are the same between min and max.
+  APInt Min = getUnsignedMin();
+  APInt Max = getUnsignedMax();
+  KnownBits Known = KnownBits::makeConstant(Min);
+  if (Optional<unsigned> DifferentBit =
+          APIntOps::GetMostSignificantDifferentBit(Min, Max)) {
+    Known.Zero.clearLowBits(*DifferentBit + 1);
+    Known.One.clearLowBits(*DifferentBit + 1);
+  }
+  return Known;
+}
+
 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
                                                    const ConstantRange &CR) {
   if (CR.isEmptySet())
diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp
index 2c54b1c6..9aee84e 100644
--- a/llvm/unittests/IR/ConstantRangeTest.cpp
+++ b/llvm/unittests/IR/ConstantRangeTest.cpp
@@ -2366,6 +2366,25 @@ TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
   }
 }
 
+TEST_F(ConstantRangeTest, ToKnownBits) {
+  unsigned Bits = 4;
+  EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
+    KnownBits Known = CR.toKnownBits();
+    KnownBits ExpectedKnown(Bits);
+    ExpectedKnown.Zero.setAllBits();
+    ExpectedKnown.One.setAllBits();
+    ForeachNumInConstantRange(CR, [&](const APInt &N) {
+      ExpectedKnown.One &= N;
+      ExpectedKnown.Zero &= ~N;
+    });
+    // For an empty CR any result would be legal.
+    if (!CR.isEmptySet()) {
+      EXPECT_EQ(ExpectedKnown.One, Known.One);
+      EXPECT_EQ(ExpectedKnown.Zero, Known.Zero);
+    }
+  });
+}
+
 TEST_F(ConstantRangeTest, Negative) {
   // All elements in an empty set (of which there are none) are both negative
   // and non-negative. Empty & full sets checked explicitly for clarity, but