simplify getSetSize() per Duncan's comments

[oota-llvm.git] / lib / Support / ConstantRange.cpp

diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index b6f823465266caf50089eac58e70041e3c017f1c..b7b38e4c2e12656f20e604f4704e2a9bae7e53ce 100644 (file)
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -55,7 +55,7 @@ ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
 
   uint32_t W = CR.getBitWidth();
   switch (Pred) {
-    default: assert(!"Invalid ICmp predicate to makeICmpRegion()");
+    default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
     case CmpInst::ICMP_EQ:
       return CR;
     case CmpInst::ICMP_NE:
@@ -143,16 +143,17 @@ bool ConstantRange::isSignWrappedSet() const {
 /// getSetSize - Return the number of elements in this set.
 ///
 APInt ConstantRange::getSetSize() const {
-  if (isEmptySet()) 
-    return APInt(getBitWidth(), 0);
-  if (getBitWidth() == 1) {
-    if (Lower != Upper)  // One of T or F in the set...
-      return APInt(2, 1);
-    return APInt(2, 2);      // Must be full set...
+  if (isEmptySet())
+    return APInt(getBitWidth()+1, 0);
+
+  if (isFullSet()) {
+    APInt Size(getBitWidth()+1, 0);
+    Size.setBit(getBitWidth());
+    return Size;
   }
 
-  // Simply subtract the bounds...
-  return Upper - Lower;
+  // This is also correct for wrapped sets.
+  return (Upper - Lower).zext(getBitWidth()+1);
 }
 
 /// getUnsignedMax - Return the largest unsigned value contained in the
@@ -161,8 +162,7 @@ APInt ConstantRange::getSetSize() const {
 APInt ConstantRange::getUnsignedMax() const {
   if (isFullSet() || isWrappedSet())
     return APInt::getMaxValue(getBitWidth());
-  else
-    return getUpper() - 1;
+  return getUpper() - 1;
 }
 
 /// getUnsignedMin - Return the smallest unsigned value contained in the
@@ -171,8 +171,7 @@ APInt ConstantRange::getUnsignedMax() const {
 APInt ConstantRange::getUnsignedMin() const {
   if (isFullSet() || (isWrappedSet() && getUpper() != 0))
     return APInt::getMinValue(getBitWidth());
-  else
-    return getLower();
+  return getLower();
 }
 
 /// getSignedMax - Return the largest signed value contained in the
@@ -183,14 +182,11 @@ APInt ConstantRange::getSignedMax() const {
   if (!isWrappedSet()) {
     if (getLower().sle(getUpper() - 1))
       return getUpper() - 1;
-    else
-      return SignedMax;
-  } else {
-    if (getLower().isNegative() == getUpper().isNegative())
-      return SignedMax;
-    else
-      return getUpper() - 1;
+    return SignedMax;
   }
+  if (getLower().isNegative() == getUpper().isNegative())
+    return SignedMax;
+  return getUpper() - 1;
 }
 
 /// getSignedMin - Return the smallest signed value contained in the
@@ -201,18 +197,13 @@ APInt ConstantRange::getSignedMin() const {
   if (!isWrappedSet()) {
     if (getLower().sle(getUpper() - 1))
       return getLower();
-    else
+    return SignedMin;
+  }
+  if ((getUpper() - 1).slt(getLower())) {
+    if (getUpper() != SignedMin)
       return SignedMin;
-  } else {
-    if ((getUpper() - 1).slt(getLower())) {
-      if (getUpper() != SignedMin)
-        return SignedMin;
-      else
-        return getLower();
-    } else {
-      return getLower();
-    }
   }
+  return getLower();
 }
 
 /// contains - Return true if the specified value is in the set.
@@ -223,8 +214,7 @@ bool ConstantRange::contains(const APInt &V) const {
 
   if (!isWrappedSet())
     return Lower.ule(V) && V.ult(Upper);
-  else
-    return Lower.ule(V) || V.ult(Upper);
+  return Lower.ule(V) || V.ult(Upper);
 }
 
 /// contains - Return true if the argument is a subset of this range.
@@ -259,6 +249,12 @@ ConstantRange ConstantRange::subtract(const APInt &Val) const {
   return ConstantRange(Lower - Val, Upper - Val);
 }
 
+/// \brief Subtract the specified range from this range (aka relative complement
+/// of the sets).
+ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
+  return intersectWith(CR.inverse());
+}
+
 /// intersectWith - Return the range that results from the intersection of this
 /// range with another range.  The resultant range is guaranteed to include all
 /// elements contained in both input ranges, and to have the smallest possible
@@ -284,15 +280,14 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
         return ConstantRange(CR.Lower, Upper);
 
       return CR;
-    } else {
-      if (Upper.ult(CR.Upper))
-        return *this;
+    }
+    if (Upper.ult(CR.Upper))
+      return *this;
 
-      if (Lower.ult(CR.Upper))
-        return ConstantRange(Lower, CR.Upper);
+    if (Lower.ult(CR.Upper))
+      return ConstantRange(Lower, CR.Upper);
 
-      return ConstantRange(getBitWidth(), false);
-    }
+    return ConstantRange(getBitWidth(), false);
   }
 
   if (isWrappedSet() && !CR.isWrappedSet()) {
@@ -300,14 +295,14 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
       if (CR.Upper.ult(Upper))
         return CR;
 
-      if (CR.Upper.ult(Lower))
+      if (CR.Upper.ule(Lower))
         return ConstantRange(CR.Lower, Upper);
 
       if (getSetSize().ult(CR.getSetSize()))
         return *this;
-      else
-        return CR;
-    } else if (CR.Lower.ult(Lower)) {
+      return CR;
+    }
+    if (CR.Lower.ult(Lower)) {
       if (CR.Upper.ule(Lower))
         return ConstantRange(getBitWidth(), false);
 
@@ -320,15 +315,15 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
     if (CR.Lower.ult(Upper)) {
       if (getSetSize().ult(CR.getSetSize()))
         return *this;
-      else
-        return CR;
+      return CR;
     }
 
     if (CR.Lower.ult(Lower))
       return ConstantRange(Lower, CR.Upper);
 
     return CR;
-  } else if (CR.Upper.ult(Lower)) {
+  }
+  if (CR.Upper.ule(Lower)) {
     if (CR.Lower.ult(Lower))
       return *this;
 
@@ -336,8 +331,7 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
   }
   if (getSetSize().ult(CR.getSetSize()))
     return *this;
-  else
-    return CR;
+  return CR;
 }
 
 
@@ -362,8 +356,7 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
       if (d1.ult(d2))
         return ConstantRange(Lower, CR.Upper);
-      else
-        return ConstantRange(CR.Lower, Upper);
+      return ConstantRange(CR.Lower, Upper);
     }
 
     APInt L = Lower, U = Upper;
@@ -396,8 +389,7 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
       if (d1.ult(d2))
         return ConstantRange(Lower, CR.Upper);
-      else
-        return ConstantRange(CR.Lower, Upper);
+      return ConstantRange(CR.Lower, Upper);
     }
 
     // ----U     L----- : this
@@ -407,13 +399,11 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 
     // ------U    L---- : this
     //    L-----U       : CR
-    if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower))
-      return ConstantRange(Lower, CR.Upper);
+    assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
+           "ConstantRange::unionWith missed a case with one range wrapped");
+    return ConstantRange(Lower, CR.Upper);
   }
 
-  assert(isWrappedSet() && CR.isWrappedSet() &&
-         "ConstantRange::unionWith missed wrapped union unwrapped case");
-
   // ------U    L----  and  ------U    L---- : this
   // -U  L-----------  and  ------------U  L : CR
   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
@@ -466,10 +456,8 @@ ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 /// correspond to the possible range of values as if the source range had been
 /// truncated to the specified type.
 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
-  unsigned SrcTySize = getBitWidth();
-  assert(SrcTySize > DstTySize && "Not a value truncation");
-  APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
-  if (isFullSet() || getSetSize().ugt(Size))
+  assert(getBitWidth() > DstTySize && "Not a value truncation");
+  if (isFullSet() || getSetSize().getActiveBits() > DstTySize)
     return ConstantRange(DstTySize, /*isFullSet=*/true);
 
   return ConstantRange(Lower.trunc(DstTySize), Upper.trunc(DstTySize));
@@ -481,10 +469,9 @@ ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
   unsigned SrcTySize = getBitWidth();
   if (SrcTySize > DstTySize)
     return truncate(DstTySize);
-  else if (SrcTySize < DstTySize)
+  if (SrcTySize < DstTySize)
     return zeroExtend(DstTySize);
-  else
-    return *this;
+  return *this;
 }
 
 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
@@ -493,10 +480,9 @@ ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
   unsigned SrcTySize = getBitWidth();
   if (SrcTySize > DstTySize)
     return truncate(DstTySize);
-  else if (SrcTySize < DstTySize)
+  if (SrcTySize < DstTySize)
     return signExtend(DstTySize);
-  else
-    return *this;
+  return *this;
 }
 
 ConstantRange
@@ -550,6 +536,12 @@ ConstantRange::multiply(const ConstantRange &Other) const {
 
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+
+  // If any of the operands is zero, then the result is also zero.
+  if ((getSingleElement() && *getSingleElement() == 0) ||
+      (Other.getSingleElement() && *Other.getSingleElement() == 0))
+    return ConstantRange(APInt(getBitWidth(), 0));
+
   if (isFullSet() || Other.isFullSet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
@@ -675,11 +667,10 @@ ConstantRange::lshr(const ConstantRange &Other) const {
 }
 
 ConstantRange ConstantRange::inverse() const {
-  if (isFullSet()) {
+  if (isFullSet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
-  } else if (isEmptySet()) {
+  if (isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
-  }
   return ConstantRange(Upper, Lower);
 }