lib/Analysis/ConstantRange.cpp

   1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Represent a range of possible values that may occur when the program is run
  11 // for an integral value.  This keeps track of a lower and upper bound for the
  12 // constant, which MAY wrap around the end of the numeric range.  To do this, it
  13 // keeps track of a [lower, upper) bound, which specifies an interval just like
  14 // STL iterators.  When used with boolean values, the following are important
  15 // ranges (other integral ranges use min/max values for special range values):
  16 //
  17 //  [F, F) = {}     = Empty set
  18 //  [T, F) = {T}
  19 //  [F, T) = {F}
  20 //  [T, T) = {F, T} = Full set
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/Support/ConstantRange.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/Instruction.h"
  27 #include "llvm/Type.h"
  28 #include "llvm/Support/Streams.h"
  29 #include <ostream>
  30 using namespace llvm;
  31
  32 static ConstantIntegral *getMaxValue(const Type *Ty) {
  33   switch (Ty->getTypeID()) {
  34   case Type::BoolTyID:   return ConstantBool::getTrue();
  35   case Type::SByteTyID:
  36   case Type::ShortTyID:
  37   case Type::IntTyID:
  38   case Type::LongTyID: {
  39     // Calculate 011111111111111...
  40     unsigned TypeBits = Ty->getPrimitiveSize()*8;
  41     int64_t Val = INT64_MAX;             // All ones
  42     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
  43     return ConstantInt::get(Ty, Val);
  44   }
  45
  46   case Type::UByteTyID:
  47   case Type::UShortTyID:
  48   case Type::UIntTyID:
  49   case Type::ULongTyID:  return ConstantInt::getAllOnesValue(Ty);
  50
  51   default: return 0;
  52   }
  53 }
  54
  55 // Static constructor to create the minimum constant for an integral type...
  56 static ConstantIntegral *getMinValue(const Type *Ty) {
  57   switch (Ty->getTypeID()) {
  58   case Type::BoolTyID:   return ConstantBool::getFalse();
  59   case Type::SByteTyID:
  60   case Type::ShortTyID:
  61   case Type::IntTyID:
  62   case Type::LongTyID: {
  63      // Calculate 1111111111000000000000
  64      unsigned TypeBits = Ty->getPrimitiveSize()*8;
  65      int64_t Val = -1;                    // All ones
  66      Val <<= TypeBits-1;                  // Shift over to the right spot
  67      return ConstantInt::get(Ty, Val);
  68   }
  69
  70   case Type::UByteTyID:
  71   case Type::UShortTyID:
  72   case Type::UIntTyID:
  73   case Type::ULongTyID:  return ConstantInt::get(Ty, 0);
  74
  75   default: return 0;
  76   }
  77 }
  78 static ConstantIntegral *Next(ConstantIntegral *CI) {
  79   if (ConstantBool *CB = dyn_cast<ConstantBool>(CI))
  80     return ConstantBool::get(!CB->getValue());
  81
  82   Constant *Result = ConstantExpr::getAdd(CI,
  83                                           ConstantInt::get(CI->getType(), 1));
  84   return cast<ConstantIntegral>(Result);
  85 }
  86
  87 static bool LT(ConstantIntegral *A, ConstantIntegral *B) {
  88   Constant *C = ConstantExpr::getSetLT(A, B);
  89   assert(isa<ConstantBool>(C) && "Constant folding of integrals not impl??");
  90   return cast<ConstantBool>(C)->getValue();
  91 }
  92
  93 static bool LTE(ConstantIntegral *A, ConstantIntegral *B) {
  94   Constant *C = ConstantExpr::getSetLE(A, B);
  95   assert(isa<ConstantBool>(C) && "Constant folding of integrals not impl??");
  96   return cast<ConstantBool>(C)->getValue();
  97 }
  98
  99 static bool GT(ConstantIntegral *A, ConstantIntegral *B) { return LT(B, A); }
 100
 101 static ConstantIntegral *Min(ConstantIntegral *A, ConstantIntegral *B) {
 102   return LT(A, B) ? A : B;
 103 }
 104 static ConstantIntegral *Max(ConstantIntegral *A, ConstantIntegral *B) {
 105   return GT(A, B) ? A : B;
 106 }
 107
 108 /// Initialize a full (the default) or empty set for the specified type.
 109 ///
 110 ConstantRange::ConstantRange(const Type *Ty, bool Full) {
 111   assert(Ty->isIntegral() &&
 112          "Cannot make constant range of non-integral type!");
 113   if (Full)
 114     Lower = Upper = getMaxValue(Ty);
 115   else
 116     Lower = Upper = getMinValue(Ty);
 117 }
 118
 119 /// Initialize a range to hold the single specified value.
 120 ///
 121 ConstantRange::ConstantRange(Constant *V)
 122   : Lower(cast<ConstantIntegral>(V)), Upper(Next(cast<ConstantIntegral>(V))) {
 123 }
 124
 125 /// Initialize a range of values explicitly... this will assert out if
 126 /// Lower==Upper and Lower != Min or Max for its type (or if the two constants
 127 /// have different types)
 128 ///
 129 ConstantRange::ConstantRange(Constant *L, Constant *U)
 130   : Lower(cast<ConstantIntegral>(L)), Upper(cast<ConstantIntegral>(U)) {
 131   assert(Lower->getType() == Upper->getType() &&
 132          "Incompatible types for ConstantRange!");
 133
 134   // Make sure that if L & U are equal that they are either Min or Max...
 135   assert((L != U || (L == getMaxValue(L->getType()) ||
 136                      L == getMinValue(L->getType()))) &&
 137          "Lower == Upper, but they aren't min or max for type!");
 138 }
 139
 140 /// Initialize a set of values that all satisfy the condition with C.
 141 ///
 142 ConstantRange::ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C) {
 143   switch (SetCCOpcode) {
 144   default: assert(0 && "Invalid SetCC opcode to ConstantRange ctor!");
 145   case Instruction::SetEQ: Lower = C; Upper = Next(C); return;
 146   case Instruction::SetNE: Upper = C; Lower = Next(C); return;
 147   case Instruction::SetLT:
 148     Lower = getMinValue(C->getType());
 149     Upper = C;
 150     return;
 151   case Instruction::SetGT:
 152     Lower = Next(C);
 153     Upper = getMinValue(C->getType());  // Min = Next(Max)
 154     return;
 155   case Instruction::SetLE:
 156     Lower = getMinValue(C->getType());
 157     Upper = Next(C);
 158     return;
 159   case Instruction::SetGE:
 160     Lower = C;
 161     Upper = getMinValue(C->getType());  // Min = Next(Max)
 162     return;
 163   }
 164 }
 165
 166 /// getType - Return the LLVM data type of this range.
 167 ///
 168 const Type *ConstantRange::getType() const { return Lower->getType(); }
 169
 170 /// isFullSet - Return true if this set contains all of the elements possible
 171 /// for this data-type
 172 bool ConstantRange::isFullSet() const {
 173   return Lower == Upper && Lower == getMaxValue(getType());
 174 }
 175
 176 /// isEmptySet - Return true if this set contains no members.
 177 ///
 178 bool ConstantRange::isEmptySet() const {
 179   return Lower == Upper && Lower == getMinValue(getType());
 180 }
 181
 182 /// isWrappedSet - Return true if this set wraps around the top of the range,
 183 /// for example: [100, 8)
 184 ///
 185 bool ConstantRange::isWrappedSet() const {
 186   return GT(Lower, Upper);
 187 }
 188
 189
 190 /// getSingleElement - If this set contains a single element, return it,
 191 /// otherwise return null.
 192 ConstantIntegral *ConstantRange::getSingleElement() const {
 193   if (Upper == Next(Lower))  // Is it a single element range?
 194     return Lower;
 195   return 0;
 196 }
 197
 198 /// getSetSize - Return the number of elements in this set.
 199 ///
 200 uint64_t ConstantRange::getSetSize() const {
 201   if (isEmptySet()) return 0;
 202   if (getType() == Type::BoolTy) {
 203     if (Lower != Upper)  // One of T or F in the set...
 204       return 1;
 205     return 2;            // Must be full set...
 206   }
 207
 208   // Simply subtract the bounds...
 209   Constant *Result = ConstantExpr::getSub(Upper, Lower);
 210   return cast<ConstantInt>(Result)->getZExtValue();
 211 }
 212
 213 /// contains - Return true if the specified value is in the set.
 214 ///
 215 bool ConstantRange::contains(ConstantInt *Val) const {
 216   if (Lower == Upper) {
 217     if (isFullSet()) return true;
 218     return false;
 219   }
 220
 221   if (!isWrappedSet())
 222     return LTE(Lower, Val) && LT(Val, Upper);
 223   return LTE(Lower, Val) || LT(Val, Upper);
 224 }
 225
 226
 227
 228 /// subtract - Subtract the specified constant from the endpoints of this
 229 /// constant range.
 230 ConstantRange ConstantRange::subtract(ConstantInt *CI) const {
 231   assert(CI->getType() == getType() && getType()->isInteger() &&
 232          "Cannot subtract from different type range or non-integer!");
 233   // If the set is empty or full, don't modify the endpoints.
 234   if (Lower == Upper) return *this;
 235   return ConstantRange(ConstantExpr::getSub(Lower, CI),
 236                        ConstantExpr::getSub(Upper, CI));
 237 }
 238
 239
 240 // intersect1Wrapped - This helper function is used to intersect two ranges when
 241 // it is known that LHS is wrapped and RHS isn't.
 242 //
 243 static ConstantRange intersect1Wrapped(const ConstantRange &LHS,
 244                                        const ConstantRange &RHS) {
 245   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 246
 247   // Check to see if we overlap on the Left side of RHS...
 248   //
 249   if (LT(RHS.getLower(), LHS.getUpper())) {
 250     // We do overlap on the left side of RHS, see if we overlap on the right of
 251     // RHS...
 252     if (GT(RHS.getUpper(), LHS.getLower())) {
 253       // Ok, the result overlaps on both the left and right sides.  See if the
 254       // resultant interval will be smaller if we wrap or not...
 255       //
 256       if (LHS.getSetSize() < RHS.getSetSize())
 257         return LHS;
 258       else
 259         return RHS;
 260
 261     } else {
 262       // No overlap on the right, just on the left.
 263       return ConstantRange(RHS.getLower(), LHS.getUpper());
 264     }
 265
 266   } else {
 267     // We don't overlap on the left side of RHS, see if we overlap on the right
 268     // of RHS...
 269     if (GT(RHS.getUpper(), LHS.getLower())) {
 270       // Simple overlap...
 271       return ConstantRange(LHS.getLower(), RHS.getUpper());
 272     } else {
 273       // No overlap...
 274       return ConstantRange(LHS.getType(), false);
 275     }
 276   }
 277 }
 278
 279 /// intersect - Return the range that results from the intersection of this
 280 /// range with another range.
 281 ///
 282 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 283   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 284   // Handle common special cases
 285   if (isEmptySet() || CR.isFullSet())  return *this;
 286   if (isFullSet()  || CR.isEmptySet()) return CR;
 287
 288   if (!isWrappedSet()) {
 289     if (!CR.isWrappedSet()) {
 290       ConstantIntegral *L = Max(Lower, CR.Lower);
 291       ConstantIntegral *U = Min(Upper, CR.Upper);
 292
 293       if (LT(L, U))  // If range isn't empty...
 294         return ConstantRange(L, U);
 295       else
 296         return ConstantRange(getType(), false);  // Otherwise, return empty set
 297     } else
 298       return intersect1Wrapped(CR, *this);
 299   } else {   // We know "this" is wrapped...
 300     if (!CR.isWrappedSet())
 301       return intersect1Wrapped(*this, CR);
 302     else {
 303       // Both ranges are wrapped...
 304       ConstantIntegral *L = Max(Lower, CR.Lower);
 305       ConstantIntegral *U = Min(Upper, CR.Upper);
 306       return ConstantRange(L, U);
 307     }
 308   }
 309   return *this;
 310 }
 311
 312 /// union - Return the range that results from the union of this range with
 313 /// another range.  The resultant range is guaranteed to include the elements of
 314 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is [3,
 315 /// 15), which includes 9, 10, and 11, which were not included in either set
 316 /// before.
 317 ///
 318 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 319   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 320
 321   assert(0 && "Range union not implemented yet!");
 322
 323   return *this;
 324 }
 325
 326 /// zeroExtend - Return a new range in the specified integer type, which must
 327 /// be strictly larger than the current type.  The returned range will
 328 /// correspond to the possible range of values if the source range had been
 329 /// zero extended.
 330 ConstantRange ConstantRange::zeroExtend(const Type *Ty) const {
 331   assert(getLower()->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() &&
 332          "Not a value extension");
 333   if (isFullSet()) {
 334     // Change a source full set into [0, 1 << 8*numbytes)
 335     unsigned SrcTySize = getLower()->getType()->getPrimitiveSize();
 336     return ConstantRange(Constant::getNullValue(Ty),
 337                          ConstantInt::get(Ty, 1ULL << SrcTySize*8));
 338   }
 339
 340   Constant *Lower = getLower();
 341   Constant *Upper = getUpper();
 342
 343   return ConstantRange(ConstantExpr::getCast(Instruction::ZExt, Lower, Ty),
 344                        ConstantExpr::getCast(Instruction::ZExt, Upper, Ty));
 345 }
 346
 347 /// truncate - Return a new range in the specified integer type, which must be
 348 /// strictly smaller than the current type.  The returned range will
 349 /// correspond to the possible range of values if the source range had been
 350 /// truncated to the specified type.
 351 ConstantRange ConstantRange::truncate(const Type *Ty) const {
 352   assert(getLower()->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() &&
 353          "Not a value truncation");
 354   uint64_t Size = 1ULL << Ty->getPrimitiveSize()*8;
 355   if (isFullSet() || getSetSize() >= Size)
 356     return ConstantRange(getType());
 357
 358   return ConstantRange(
 359       ConstantExpr::getCast(Instruction::Trunc, getLower(), Ty),
 360       ConstantExpr::getCast(Instruction::Trunc, getUpper(), Ty));
 361 }
 362
 363
 364 /// print - Print out the bounds to a stream...
 365 ///
 366 void ConstantRange::print(std::ostream &OS) const {
 367   OS << "[" << *Lower << "," << *Upper << " )";
 368 }
 369
 370 /// dump - Allow printing from a debugger easily...
 371 ///
 372 void ConstantRange::dump() const {
 373   print(cerr);
 374 }