lib/Support/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/Type.h"
  26 #include "llvm/Instruction.h"
  27 #include "llvm/ConstantHandling.h"
  28
  29 namespace llvm {
  30
  31 /// Initialize a full (the default) or empty set for the specified type.
  32 ///
  33 ConstantRange::ConstantRange(const Type *Ty, bool Full) {
  34   assert(Ty->isIntegral() &&
  35          "Cannot make constant range of non-integral type!");
  36   if (Full)
  37     Lower = Upper = ConstantIntegral::getMaxValue(Ty);
  38   else
  39     Lower = Upper = ConstantIntegral::getMinValue(Ty);
  40 }
  41
  42 /// Initialize a range of values explicitly... this will assert out if
  43 /// Lower==Upper and Lower != Min or Max for its type (or if the two constants
  44 /// have different types)
  45 ///
  46 ConstantRange::ConstantRange(ConstantIntegral *L,
  47                              ConstantIntegral *U) : Lower(L), Upper(U) {
  48   assert(Lower->getType() == Upper->getType() &&
  49          "Incompatible types for ConstantRange!");
  50
  51   // Make sure that if L & U are equal that they are either Min or Max...
  52   assert((L != U || (L == ConstantIntegral::getMaxValue(L->getType()) ||
  53                      L == ConstantIntegral::getMinValue(L->getType()))) &&
  54          "Lower == Upper, but they aren't min or max for type!");
  55 }
  56
  57 static ConstantIntegral *Next(ConstantIntegral *CI) {
  58   if (CI->getType() == Type::BoolTy)
  59     return CI == ConstantBool::True ? ConstantBool::False : ConstantBool::True;
  60
  61   // Otherwise use operator+ in the ConstantHandling Library.
  62   Constant *Result = *ConstantInt::get(CI->getType(), 1) + *CI;
  63   assert(Result && "ConstantHandling not implemented for integral plus!?");
  64   return cast<ConstantIntegral>(Result);
  65 }
  66
  67 /// Initialize a set of values that all satisfy the condition with C.
  68 ///
  69 ConstantRange::ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C) {
  70   switch (SetCCOpcode) {
  71   default: assert(0 && "Invalid SetCC opcode to ConstantRange ctor!");
  72   case Instruction::SetEQ: Lower = C; Upper = Next(C); return;
  73   case Instruction::SetNE: Upper = C; Lower = Next(C); return;
  74   case Instruction::SetLT:
  75     Lower = ConstantIntegral::getMinValue(C->getType());
  76     Upper = C;
  77     return;
  78   case Instruction::SetGT:
  79     Lower = Next(C);
  80     Upper = ConstantIntegral::getMinValue(C->getType());  // Min = Next(Max)
  81     return;
  82   case Instruction::SetLE:
  83     Lower = ConstantIntegral::getMinValue(C->getType());
  84     Upper = Next(C);
  85     return;
  86   case Instruction::SetGE:
  87     Lower = C;
  88     Upper = ConstantIntegral::getMinValue(C->getType());  // Min = Next(Max)
  89     return;
  90   }
  91 }
  92
  93 /// getType - Return the LLVM data type of this range.
  94 ///
  95 const Type *ConstantRange::getType() const { return Lower->getType(); }
  96
  97 /// isFullSet - Return true if this set contains all of the elements possible
  98 /// for this data-type
  99 bool ConstantRange::isFullSet() const {
 100   return Lower == Upper && Lower == ConstantIntegral::getMaxValue(getType());
 101 }
 102
 103 /// isEmptySet - Return true if this set contains no members.
 104 ///
 105 bool ConstantRange::isEmptySet() const {
 106   return Lower == Upper && Lower == ConstantIntegral::getMinValue(getType());
 107 }
 108
 109 /// isWrappedSet - Return true if this set wraps around the top of the range,
 110 /// for example: [100, 8)
 111 ///
 112 bool ConstantRange::isWrappedSet() const {
 113   return (*(Constant*)Lower > *(Constant*)Upper)->getValue();
 114 }
 115
 116
 117 /// getSingleElement - If this set contains a single element, return it,
 118 /// otherwise return null.
 119 ConstantIntegral *ConstantRange::getSingleElement() const {
 120   if (Upper == Next(Lower))  // Is it a single element range?
 121     return Lower;
 122   return 0;
 123 }
 124
 125 /// getSetSize - Return the number of elements in this set.
 126 ///
 127 uint64_t ConstantRange::getSetSize() const {
 128   if (isEmptySet()) return 0;
 129   if (getType() == Type::BoolTy) {
 130     if (Lower != Upper)  // One of T or F in the set...
 131       return 1;
 132     return 2;            // Must be full set...
 133   }
 134
 135   // Simply subtract the bounds...
 136   Constant *Result = *(Constant*)Upper - *(Constant*)Lower;
 137   assert(Result && "Subtraction of constant integers not implemented?");
 138   return cast<ConstantInt>(Result)->getRawValue();
 139 }
 140
 141
 142
 143
 144 // intersect1Wrapped - This helper function is used to intersect two ranges when
 145 // it is known that LHS is wrapped and RHS isn't.
 146 //
 147 static ConstantRange intersect1Wrapped(const ConstantRange &LHS,
 148                                        const ConstantRange &RHS) {
 149   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 150
 151   // Check to see if we overlap on the Left side of RHS...
 152   //
 153   if ((*(Constant*)RHS.getLower() < *(Constant*)LHS.getUpper())->getValue()) {
 154     // We do overlap on the left side of RHS, see if we overlap on the right of
 155     // RHS...
 156     if ((*(Constant*)RHS.getUpper() > *(Constant*)LHS.getLower())->getValue()) {
 157       // Ok, the result overlaps on both the left and right sides.  See if the
 158       // resultant interval will be smaller if we wrap or not...
 159       //
 160       if (LHS.getSetSize() < RHS.getSetSize())
 161         return LHS;
 162       else
 163         return RHS;
 164
 165     } else {
 166       // No overlap on the right, just on the left.
 167       return ConstantRange(RHS.getLower(), LHS.getUpper());
 168     }
 169
 170   } else {
 171     // We don't overlap on the left side of RHS, see if we overlap on the right
 172     // of RHS...
 173     if ((*(Constant*)RHS.getUpper() > *(Constant*)LHS.getLower())->getValue()) {
 174       // Simple overlap...
 175       return ConstantRange(LHS.getLower(), RHS.getUpper());
 176     } else {
 177       // No overlap...
 178       return ConstantRange(LHS.getType(), false);
 179     }
 180   }
 181 }
 182
 183 static ConstantIntegral *Min(ConstantIntegral *A, ConstantIntegral *B) {
 184   if ((*(Constant*)A < *(Constant*)B)->getValue())
 185     return A;
 186   return B;
 187 }
 188 static ConstantIntegral *Max(ConstantIntegral *A, ConstantIntegral *B) {
 189   if ((*(Constant*)A > *(Constant*)B)->getValue())
 190     return A;
 191   return B;
 192 }
 193
 194
 195 /// intersect - Return the range that results from the intersection of this
 196 /// range with another range.
 197 ///
 198 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 199   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 200   // Handle common special cases
 201   if (isEmptySet() || CR.isFullSet())  return *this;
 202   if (isFullSet()  || CR.isEmptySet()) return CR;
 203
 204   if (!isWrappedSet()) {
 205     if (!CR.isWrappedSet()) {
 206       ConstantIntegral *L = Max(Lower, CR.Lower);
 207       ConstantIntegral *U = Min(Upper, CR.Upper);
 208
 209       if ((*L < *U)->getValue())  // If range isn't empty...
 210         return ConstantRange(L, U);
 211       else
 212         return ConstantRange(getType(), false);  // Otherwise, return empty set
 213     } else
 214       return intersect1Wrapped(CR, *this);
 215   } else {   // We know "this" is wrapped...
 216     if (!CR.isWrappedSet())
 217       return intersect1Wrapped(*this, CR);
 218     else {
 219       // Both ranges are wrapped...
 220       ConstantIntegral *L = Max(Lower, CR.Lower);
 221       ConstantIntegral *U = Min(Upper, CR.Upper);
 222       return ConstantRange(L, U);
 223     }
 224   }
 225   return *this;
 226 }
 227
 228 /// union - Return the range that results from the union of this range with
 229 /// another range.  The resultant range is guaranteed to include the elements of
 230 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is [3,
 231 /// 15), which includes 9, 10, and 11, which were not included in either set
 232 /// before.
 233 ///
 234 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 235   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 236
 237   assert(0 && "Range union not implemented yet!");
 238
 239   return *this;
 240 }
 241
 242 /// print - Print out the bounds to a stream...
 243 ///
 244 void ConstantRange::print(std::ostream &OS) const {
 245   OS << "[" << Lower << "," << Upper << " )";
 246 }
 247
 248 /// dump - Allow printing from a debugger easily...
 249 ///
 250 void ConstantRange::dump() const {
 251   print(std::cerr);
 252 }
 253
 254 } // End llvm namespace