[ConstantRange] [a, b) udiv a full range is [0, umax(b)).

[fhahn]

The main problem this patch addresses is the RHS == full-set case, where we exit early.

[nikic]

llvm/lib/IR/ConstantRange.cpp

1015

This full set check looks pretty bogus to me The result of CR1 udiv CR2 should be some subset of [0, umax(CR1)], as you won't get back a larger value from a division. Your patch makes [0, 1) udiv full-set return [0, 1), but there are also other cases where the current code is inaccurate:

[0, 5) udiv full-set should be [0, 5)
[5, 10) udiv full-set should be [0, 10)

Would it be possible to just drop this check?

[nikic]

Reverse ping

[fhahn]

Generalize patch to handle [a, b) udiv full set == [0, b).

[fhahn]

llvm/lib/IR/ConstantRange.cpp

1015

Not sure why the check was there in the first place! It looks like we can generalize the handling and drop it.

[nikic]

LGTM

llvm/lib/IR/ConstantRange.cpp

if (NewU == NewL)
     return getFull();
   return ConstantRange(std::move(NewL), std::move(NewU));
 }
 
 ConstantRange
 ConstantRange::udiv(const ConstantRange &RHS) const {
   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     return getEmpty();
+  if (isSingleElement() && getSingleElement()->isNullValue())
+    return *this;
   if (RHS.isFullSet())
     return getFull();
 
   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
 
   APInt RHS_umin = RHS.getUnsignedMin();
   if (RHS_umin.isNullValue()) {
     // We want the lowest value in RHS excluding zero. Usually that would be 1
     // except for a range in the form of [X, 1) in which case it would be X.
     if (RHS.getUpper() == 1)

llvm/unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, UDiv) {
   EXPECT_EQ(Empty.udiv(Some), Empty);
   EXPECT_EQ(Empty.udiv(Wrap), Empty);
   EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
   EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
   EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
   EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
   EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
   EXPECT_EQ(Wrap.udiv(Wrap), Full);
+
+  ConstantRange Zero(APInt(16, 0));
+  EXPECT_EQ(Zero.udiv(One), Zero);
+  EXPECT_EQ(Zero.udiv(Full), Zero);
 }
 
 TEST_F(ConstantRangeTest, Shl) {
   ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
   ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
   EXPECT_EQ(Full.shl(Full), Full);
   EXPECT_EQ(Full.shl(Empty), Empty);
   EXPECT_EQ(Full.shl(One), Full);    // TODO: [0, (-1 << 0xa) + 1)