[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

976–977

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

976–977

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

ConstantRange::umin(const ConstantRange &Other) const {
   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
   return getNonEmpty(std::move(NewL), std::move(NewU));
 }
 
 ConstantRange
 ConstantRange::udiv(const ConstantRange &RHS) const {
   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     return getEmpty();
-  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)
       RHS_umin = RHS.getLower();

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);
+
+  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
+            ConstantRange(APInt(16, 0), APInt(16, 99)));
+  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
+            ConstantRange(APInt(16, 0), APInt(16, 99)));
 }
 
 TEST_F(ConstantRangeTest, URem) {
   EXPECT_EQ(Full.urem(Empty), Empty);
   EXPECT_EQ(Empty.urem(Full), Empty);
   // urem by zero is poison.
   EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
   // urem by full range doesn't contain MaxValue.