Teach BasicAA about the aliasing properties of memset_pattern16.

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

diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index defb8189b6285b9d4000acf7329df028e18fe28c..b6f823465266caf50089eac58e70041e3c017f1c 100644 (file)
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -21,11 +21,10 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Constants.h"
+#include "llvm/InstrTypes.h"
 #include "llvm/Support/ConstantRange.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Instructions.h"
 using namespace llvm;
 
 /// Initialize a full (the default) or empty set for the specified type.
@@ -51,43 +50,61 @@ ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
 
 ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
                                             const ConstantRange &CR) {
+  if (CR.isEmptySet())
+    return CR;
+
   uint32_t W = CR.getBitWidth();
   switch (Pred) {
     default: assert(!"Invalid ICmp predicate to makeICmpRegion()");
-    case ICmpInst::ICMP_EQ:
+    case CmpInst::ICMP_EQ:
       return CR;
-    case ICmpInst::ICMP_NE:
+    case CmpInst::ICMP_NE:
       if (CR.isSingleElement())
         return ConstantRange(CR.getUpper(), CR.getLower());
       return ConstantRange(W);
-    case ICmpInst::ICMP_ULT:
-      return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax());
-    case ICmpInst::ICMP_SLT:
-      return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax());
-    case ICmpInst::ICMP_ULE: {
+    case CmpInst::ICMP_ULT: {
+      APInt UMax(CR.getUnsignedMax());
+      if (UMax.isMinValue())
+        return ConstantRange(W, /* empty */ false);
+      return ConstantRange(APInt::getMinValue(W), UMax);
+    }
+    case CmpInst::ICMP_SLT: {
+      APInt SMax(CR.getSignedMax());
+      if (SMax.isMinSignedValue())
+        return ConstantRange(W, /* empty */ false);
+      return ConstantRange(APInt::getSignedMinValue(W), SMax);
+    }
+    case CmpInst::ICMP_ULE: {
       APInt UMax(CR.getUnsignedMax());
       if (UMax.isMaxValue())
         return ConstantRange(W);
       return ConstantRange(APInt::getMinValue(W), UMax + 1);
     }
-    case ICmpInst::ICMP_SLE: {
+    case CmpInst::ICMP_SLE: {
       APInt SMax(CR.getSignedMax());
-      if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue())
+      if (SMax.isMaxSignedValue())
         return ConstantRange(W);
       return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
     }
-    case ICmpInst::ICMP_UGT:
-      return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W));
-    case ICmpInst::ICMP_SGT:
-      return ConstantRange(CR.getSignedMin() + 1,
-                           APInt::getSignedMinValue(W));
-    case ICmpInst::ICMP_UGE: {
+    case CmpInst::ICMP_UGT: {
+      APInt UMin(CR.getUnsignedMin());
+      if (UMin.isMaxValue())
+        return ConstantRange(W, /* empty */ false);
+      return ConstantRange(UMin + 1, APInt::getNullValue(W));
+    }
+    case CmpInst::ICMP_SGT: {
+      APInt SMin(CR.getSignedMin());
+      if (SMin.isMaxSignedValue())
+        return ConstantRange(W, /* empty */ false);
+      return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
+    }
+    case CmpInst::ICMP_UGE: {
       APInt UMin(CR.getUnsignedMin());
       if (UMin.isMinValue())
         return ConstantRange(W);
       return ConstantRange(UMin, APInt::getNullValue(W));
     }
-    case ICmpInst::ICMP_SGE: {
+    case CmpInst::ICMP_SGE: {
       APInt SMin(CR.getSignedMin());
       if (SMin.isMinSignedValue())
         return ConstantRange(W);
@@ -424,9 +441,7 @@ ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
     // Change into [0, 1 << src bit width)
     return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
 
-  APInt L = Lower; L.zext(DstTySize);
-  APInt U = Upper; U.zext(DstTySize);
-  return ConstantRange(L, U);
+  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
 }
 
 /// signExtend - Return a new range in the specified integer type, which must
@@ -443,9 +458,7 @@ ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
   }
 
-  APInt L = Lower; L.sext(DstTySize);
-  APInt U = Upper; U.sext(DstTySize);
-  return ConstantRange(L, U);
+  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
 }
 
 /// truncate - Return a new range in the specified integer type, which must be
@@ -459,9 +472,7 @@ ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
   if (isFullSet() || getSetSize().ugt(Size))
     return ConstantRange(DstTySize, /*isFullSet=*/true);
 
-  APInt L = Lower; L.trunc(DstTySize);
-  APInt U = Upper; U.trunc(DstTySize);
-  return ConstantRange(L, U);
+  return ConstantRange(Lower.trunc(DstTySize), Upper.trunc(DstTySize));
 }
 
 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
@@ -517,8 +528,8 @@ ConstantRange::sub(const ConstantRange &Other) const {
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
-  APInt NewLower = getLower() - Other.getLower();
-  APInt NewUpper = getUpper() - Other.getUpper() + 1;
+  APInt NewLower = getLower() - Other.getUpper() + 1;
+  APInt NewUpper = getUpper() - Other.getLower();
   if (NewLower == NewUpper)
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
@@ -607,6 +618,32 @@ ConstantRange::udiv(const ConstantRange &RHS) const {
   return ConstantRange(Lower, Upper);
 }
 
+ConstantRange
+ConstantRange::binaryAnd(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+
+  // TODO: replace this with something less conservative
+
+  APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
+  if (umin.isAllOnesValue())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+  return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
+}
+
+ConstantRange
+ConstantRange::binaryOr(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+
+  // TODO: replace this with something less conservative
+
+  APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
+  if (umax.isMinValue())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+  return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
+}
+
 ConstantRange
 ConstantRange::shl(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())