[ConstantRange] Shl of ConstantRanges considers full-set shifting to last bit position

[kariddi]

Summary

Hello, I'm not sure here what I did is correct , but I noticed that if we do SHL of two 16-bit ranges like [0, 30000) with [1,2) we get "full-set" instead of what I would have expected [0, 60000) which is still in the 16-bit unsigned range.

In the ConstantRange SHL code I noticed that we compare if we are shifting out of the range with "uge" which considers "0x7FFFU << 1" out of range even if the result "0xFFFE" would still be in range.

Now, maybe this is done for being conservative with respect to signed ranges? Is that the reason? With this question I posted this patch with a possible fix if that is not the case.

[kariddi]

Ping?

[nlopes]

This patch is not correct for this input:
lhs = FullSet
rhs = [0, 1)

should output FullSet
but this patch gives EmptySet

Here's a Z3 model if you want to play further with this patch: https://rise4fun.com/Z3/akYEt

[kariddi]

Thanks Nuno,

I updated my patch and tried the concept on the Z3 model.

I noticed that there might have been a bug

I think

(define-fun contains ((n Integer) (I Interval)) Bool

(ite
  (= (L I) (H I))
  (isFullSet I)
  (ite
    (not (isWrappedSet I))
    (and (bvule (L I) n) (bvult n (H I)))
    (or (bvule (L I) n) (bvult n (H I)))
  )
)

)

should have been

(define-fun contains ((n Integer) (I Interval)) Bool

(ite
  (= (L I) (H I))
  (isFullSet I)
  (ite
    (not (isWrappedSet I))
    (and (bvuge (L I) n) (bvult n (H I)))
    (or (bvuge (L I) n) (bvult n (H I)))
  )
)

)

right?

[nlopes]

I believe the contains function I wrote is correct. It says that an integer n belongs to interval I iff n >= lower(I) and n < upper(I) is there's no wrapping.
BTW, function isWrappedSet() just changed recently, so that needs tweaking in the Z3 model I sent (https://github.com/llvm-mirror/llvm/blob/master/lib/IR/ConstantRange.cpp#L347)

Can you please send a rise4fun.com permalink with your code changes?

[kariddi]

Sorry, you are right, I didn't notice the operands were flipped. I'm not familiar with Z3 syntax and I got confused :)

Here a link with the changes. As I said I'm not familiar with Z3 so let me know if there's something wrong

https://rise4fun.com/Z3/LoTq

[kariddi]

Here the one with your isWrappedSet changes

https://rise4fun.com/Z3/2haZ

[nlopes]

LGTM.
Minor: you have a typo in the comment: "return return"

[lebedev.ri]

Please always upload patches with full context (-U99999)
You have changed code, but there were no test changes as far as i can tell?

[nikic]

lib/IR/ConstantRange.cpp

1011

The !isWrappedSet() doesn't really make sense to me here. Other_umax (which is the inclusive unsigned maximum) for a wrapped set will always be MaxValue, so this check seems redundant.

unittests/IR/ConstantRangeTest.cpp

57

I'd suggest moving this into the shl test, as it is only used there.

[kariddi]

Hi Nikita, thanks for the review. I updated the patch based on your comment.

Let me know if that's ok for you now.

[lebedev.ri]

In D57983#1448821, @lebedev.ri wrote:

You have changed code, but there were no test changes as far as i can tell?

Please improve test coverage.

[kariddi]

Update coverage

[nikic]

Looks good, thanks for the update.

lib/IR/ConstantRange.cpp

 ConstantRange::shl(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 
   APInt max = getUnsignedMax();
   APInt Other_umax = Other.getUnsignedMax();
 
   // there's overflow!
-  if (Other_umax.uge(max.countLeadingZeros()))
+  if (Other_umax.ugt(max.countLeadingZeros()))
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   // FIXME: implement the other tricky cases
 
   APInt min = getUnsignedMin();
   min <<= Other.getUnsignedMin();
   max <<= Other_umax;
 
ConstantRange::lshr(const ConstantRange &Other) const {
 
   return ConstantRange(std::move(min), std::move(max));
 }
 
 ConstantRange
 ConstantRange::ashr(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 
   // May straddle zero, so handle both positive and negative cases.
   // 'PosMax' is the upper bound of the result of the ashr
   // operation, when Upper of the LHS of ashr is a non-negative.
   // number. Since ashr of a non-negative number will result in a
   // smaller number, the Upper value of LHS is shifted right with
   // the minimum value of 'Other' instead of the maximum value.
   APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
 

unittests/IR/ConstantRangeTest.cpp

 namespace {
 
 class ConstantRangeTest : public ::testing::Test {
 protected:
   static ConstantRange Full;
   static ConstantRange Empty;
   static ConstantRange One;
   static ConstantRange Some;
+  static ConstantRange Some2;
   static ConstantRange Wrap;
 };
 
 ConstantRange ConstantRangeTest::Full(16);
 ConstantRange ConstantRangeTest::Empty(16, false);
 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
+ConstantRange ConstantRangeTest::Some2(APInt(16, 0xfff), APInt(16, 0x8000));
 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
 
 TEST_F(ConstantRangeTest, Basics) {
   EXPECT_TRUE(Full.isFullSet());
   EXPECT_FALSE(Full.isEmptySet());
   EXPECT_TRUE(Full.inverse().isEmptySet());
   EXPECT_FALSE(Full.isWrappedSet());
   EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
   EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
   EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
   EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
   EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
 
   EXPECT_FALSE(Empty.isFullSet());
   EXPECT_TRUE(Empty.isEmptySet());
   EXPECT_TRUE(Empty.inverse().isFullSet());
   EXPECT_FALSE(Empty.isWrappedSet());
   EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
   EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
   EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
   EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
   EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
 
   EXPECT_FALSE(One.isFullSet());
   EXPECT_FALSE(One.isEmptySet());
   EXPECT_FALSE(One.isWrappedSet());
   EXPECT_FALSE(One.contains(APInt(16, 0x0)));
   EXPECT_FALSE(One.contains(APInt(16, 0x9)));
   EXPECT_TRUE(One.contains(APInt(16, 0xa)));
   EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
   EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
   EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
 
TEST_F(ConstantRangeTest, Shl) {
   EXPECT_EQ(Empty.shl(Wrap), Empty);
   EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
                                         APInt(16, (0xa << 0xa) + 1)));
   EXPECT_EQ(One.shl(Some), Full);    // TODO: [0xa << 0xa, 0)
   EXPECT_EQ(One.shl(Wrap), Full);    // TODO: [0xa, 0xa << 14 + 1)
   EXPECT_EQ(Some.shl(Some), Full);   // TODO: [0xa << 0xa, 0xfc01)
   EXPECT_EQ(Some.shl(Wrap), Full);   // TODO: [0xa, 0x7ff << 0x5 + 1)
   EXPECT_EQ(Wrap.shl(Wrap), Full);
+  EXPECT_EQ(Some2.shl(ConstantRange(APInt(16, 0x1))),
+    ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
 }
 
 TEST_F(ConstantRangeTest, Lshr) {
   EXPECT_EQ(Full.lshr(Full), Full);
   EXPECT_EQ(Full.lshr(Empty), Empty);
   EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
                                           APInt(16, (0xffff >> 0xa) + 1)));
   EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),