LLVM API Documentation
00001 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Represent a range of possible values that may occur when the program is run 00011 // for an integral value. This keeps track of a lower and upper bound for the 00012 // constant, which MAY wrap around the end of the numeric range. To do this, it 00013 // keeps track of a [lower, upper) bound, which specifies an interval just like 00014 // STL iterators. When used with boolean values, the following are important 00015 // ranges (other integral ranges use min/max values for special range values): 00016 // 00017 // [F, F) = {} = Empty set 00018 // [T, F) = {T} 00019 // [F, T) = {F} 00020 // [T, T) = {F, T} = Full set 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #include "llvm/Support/ConstantRange.h" 00025 #include "llvm/Constants.h" 00026 #include "llvm/Instruction.h" 00027 #include "llvm/Type.h" 00028 #include <iostream> 00029 00030 using namespace llvm; 00031 00032 static ConstantIntegral *Next(ConstantIntegral *CI) { 00033 if (CI->getType() == Type::BoolTy) 00034 return CI == ConstantBool::True ? ConstantBool::False : ConstantBool::True; 00035 00036 Constant *Result = ConstantExpr::getAdd(CI, 00037 ConstantInt::get(CI->getType(), 1)); 00038 return cast<ConstantIntegral>(Result); 00039 } 00040 00041 static bool LT(ConstantIntegral *A, ConstantIntegral *B) { 00042 Constant *C = ConstantExpr::getSetLT(A, B); 00043 assert(isa<ConstantBool>(C) && "Constant folding of integrals not impl??"); 00044 return cast<ConstantBool>(C)->getValue(); 00045 } 00046 00047 static bool LTE(ConstantIntegral *A, ConstantIntegral *B) { 00048 Constant *C = ConstantExpr::getSetLE(A, B); 00049 assert(isa<ConstantBool>(C) && "Constant folding of integrals not impl??"); 00050 return cast<ConstantBool>(C)->getValue(); 00051 } 00052 00053 static bool GT(ConstantIntegral *A, ConstantIntegral *B) { return LT(B, A); } 00054 00055 static ConstantIntegral *Min(ConstantIntegral *A, ConstantIntegral *B) { 00056 return LT(A, B) ? A : B; 00057 } 00058 static ConstantIntegral *Max(ConstantIntegral *A, ConstantIntegral *B) { 00059 return GT(A, B) ? A : B; 00060 } 00061 00062 /// Initialize a full (the default) or empty set for the specified type. 00063 /// 00064 ConstantRange::ConstantRange(const Type *Ty, bool Full) { 00065 assert(Ty->isIntegral() && 00066 "Cannot make constant range of non-integral type!"); 00067 if (Full) 00068 Lower = Upper = ConstantIntegral::getMaxValue(Ty); 00069 else 00070 Lower = Upper = ConstantIntegral::getMinValue(Ty); 00071 } 00072 00073 /// Initialize a range to hold the single specified value. 00074 /// 00075 ConstantRange::ConstantRange(Constant *V) 00076 : Lower(cast<ConstantIntegral>(V)), Upper(Next(cast<ConstantIntegral>(V))) { 00077 } 00078 00079 /// Initialize a range of values explicitly... this will assert out if 00080 /// Lower==Upper and Lower != Min or Max for its type (or if the two constants 00081 /// have different types) 00082 /// 00083 ConstantRange::ConstantRange(Constant *L, Constant *U) 00084 : Lower(cast<ConstantIntegral>(L)), Upper(cast<ConstantIntegral>(U)) { 00085 assert(Lower->getType() == Upper->getType() && 00086 "Incompatible types for ConstantRange!"); 00087 00088 // Make sure that if L & U are equal that they are either Min or Max... 00089 assert((L != U || (L == ConstantIntegral::getMaxValue(L->getType()) || 00090 L == ConstantIntegral::getMinValue(L->getType()))) && 00091 "Lower == Upper, but they aren't min or max for type!"); 00092 } 00093 00094 /// Initialize a set of values that all satisfy the condition with C. 00095 /// 00096 ConstantRange::ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C) { 00097 switch (SetCCOpcode) { 00098 default: assert(0 && "Invalid SetCC opcode to ConstantRange ctor!"); 00099 case Instruction::SetEQ: Lower = C; Upper = Next(C); return; 00100 case Instruction::SetNE: Upper = C; Lower = Next(C); return; 00101 case Instruction::SetLT: 00102 Lower = ConstantIntegral::getMinValue(C->getType()); 00103 Upper = C; 00104 return; 00105 case Instruction::SetGT: 00106 Lower = Next(C); 00107 Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max) 00108 return; 00109 case Instruction::SetLE: 00110 Lower = ConstantIntegral::getMinValue(C->getType()); 00111 Upper = Next(C); 00112 return; 00113 case Instruction::SetGE: 00114 Lower = C; 00115 Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max) 00116 return; 00117 } 00118 } 00119 00120 /// getType - Return the LLVM data type of this range. 00121 /// 00122 const Type *ConstantRange::getType() const { return Lower->getType(); } 00123 00124 /// isFullSet - Return true if this set contains all of the elements possible 00125 /// for this data-type 00126 bool ConstantRange::isFullSet() const { 00127 return Lower == Upper && Lower == ConstantIntegral::getMaxValue(getType()); 00128 } 00129 00130 /// isEmptySet - Return true if this set contains no members. 00131 /// 00132 bool ConstantRange::isEmptySet() const { 00133 return Lower == Upper && Lower == ConstantIntegral::getMinValue(getType()); 00134 } 00135 00136 /// isWrappedSet - Return true if this set wraps around the top of the range, 00137 /// for example: [100, 8) 00138 /// 00139 bool ConstantRange::isWrappedSet() const { 00140 return GT(Lower, Upper); 00141 } 00142 00143 00144 /// getSingleElement - If this set contains a single element, return it, 00145 /// otherwise return null. 00146 ConstantIntegral *ConstantRange::getSingleElement() const { 00147 if (Upper == Next(Lower)) // Is it a single element range? 00148 return Lower; 00149 return 0; 00150 } 00151 00152 /// getSetSize - Return the number of elements in this set. 00153 /// 00154 uint64_t ConstantRange::getSetSize() const { 00155 if (isEmptySet()) return 0; 00156 if (getType() == Type::BoolTy) { 00157 if (Lower != Upper) // One of T or F in the set... 00158 return 1; 00159 return 2; // Must be full set... 00160 } 00161 00162 // Simply subtract the bounds... 00163 Constant *Result = ConstantExpr::getSub(Upper, Lower); 00164 return cast<ConstantInt>(Result)->getRawValue(); 00165 } 00166 00167 /// contains - Return true if the specified value is in the set. 00168 /// 00169 bool ConstantRange::contains(ConstantInt *Val) const { 00170 if (Lower == Upper) { 00171 if (isFullSet()) return true; 00172 return false; 00173 } 00174 00175 if (!isWrappedSet()) 00176 return LTE(Lower, Val) && LT(Val, Upper); 00177 return LTE(Lower, Val) || LT(Val, Upper); 00178 } 00179 00180 00181 00182 /// subtract - Subtract the specified constant from the endpoints of this 00183 /// constant range. 00184 ConstantRange ConstantRange::subtract(ConstantInt *CI) const { 00185 assert(CI->getType() == getType() && getType()->isInteger() && 00186 "Cannot subtract from different type range or non-integer!"); 00187 // If the set is empty or full, don't modify the endpoints. 00188 if (Lower == Upper) return *this; 00189 return ConstantRange(ConstantExpr::getSub(Lower, CI), 00190 ConstantExpr::getSub(Upper, CI)); 00191 } 00192 00193 00194 // intersect1Wrapped - This helper function is used to intersect two ranges when 00195 // it is known that LHS is wrapped and RHS isn't. 00196 // 00197 static ConstantRange intersect1Wrapped(const ConstantRange &LHS, 00198 const ConstantRange &RHS) { 00199 assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); 00200 00201 // Check to see if we overlap on the Left side of RHS... 00202 // 00203 if (LT(RHS.getLower(), LHS.getUpper())) { 00204 // We do overlap on the left side of RHS, see if we overlap on the right of 00205 // RHS... 00206 if (GT(RHS.getUpper(), LHS.getLower())) { 00207 // Ok, the result overlaps on both the left and right sides. See if the 00208 // resultant interval will be smaller if we wrap or not... 00209 // 00210 if (LHS.getSetSize() < RHS.getSetSize()) 00211 return LHS; 00212 else 00213 return RHS; 00214 00215 } else { 00216 // No overlap on the right, just on the left. 00217 return ConstantRange(RHS.getLower(), LHS.getUpper()); 00218 } 00219 00220 } else { 00221 // We don't overlap on the left side of RHS, see if we overlap on the right 00222 // of RHS... 00223 if (GT(RHS.getUpper(), LHS.getLower())) { 00224 // Simple overlap... 00225 return ConstantRange(LHS.getLower(), RHS.getUpper()); 00226 } else { 00227 // No overlap... 00228 return ConstantRange(LHS.getType(), false); 00229 } 00230 } 00231 } 00232 00233 /// intersect - Return the range that results from the intersection of this 00234 /// range with another range. 00235 /// 00236 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 00237 assert(getType() == CR.getType() && "ConstantRange types don't agree!"); 00238 // Handle common special cases 00239 if (isEmptySet() || CR.isFullSet()) return *this; 00240 if (isFullSet() || CR.isEmptySet()) return CR; 00241 00242 if (!isWrappedSet()) { 00243 if (!CR.isWrappedSet()) { 00244 ConstantIntegral *L = Max(Lower, CR.Lower); 00245 ConstantIntegral *U = Min(Upper, CR.Upper); 00246 00247 if (LT(L, U)) // If range isn't empty... 00248 return ConstantRange(L, U); 00249 else 00250 return ConstantRange(getType(), false); // Otherwise, return empty set 00251 } else 00252 return intersect1Wrapped(CR, *this); 00253 } else { // We know "this" is wrapped... 00254 if (!CR.isWrappedSet()) 00255 return intersect1Wrapped(*this, CR); 00256 else { 00257 // Both ranges are wrapped... 00258 ConstantIntegral *L = Max(Lower, CR.Lower); 00259 ConstantIntegral *U = Min(Upper, CR.Upper); 00260 return ConstantRange(L, U); 00261 } 00262 } 00263 return *this; 00264 } 00265 00266 /// union - Return the range that results from the union of this range with 00267 /// another range. The resultant range is guaranteed to include the elements of 00268 /// both sets, but may contain more. For example, [3, 9) union [12,15) is [3, 00269 /// 15), which includes 9, 10, and 11, which were not included in either set 00270 /// before. 00271 /// 00272 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 00273 assert(getType() == CR.getType() && "ConstantRange types don't agree!"); 00274 00275 assert(0 && "Range union not implemented yet!"); 00276 00277 return *this; 00278 } 00279 00280 /// zeroExtend - Return a new range in the specified integer type, which must 00281 /// be strictly larger than the current type. The returned range will 00282 /// correspond to the possible range of values if the source range had been 00283 /// zero extended. 00284 ConstantRange ConstantRange::zeroExtend(const Type *Ty) const { 00285 assert(getLower()->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && 00286 "Not a value extension"); 00287 if (isFullSet()) { 00288 // Change a source full set into [0, 1 << 8*numbytes) 00289 unsigned SrcTySize = getLower()->getType()->getPrimitiveSize(); 00290 return ConstantRange(Constant::getNullValue(Ty), 00291 ConstantUInt::get(Ty, 1ULL << SrcTySize*8)); 00292 } 00293 00294 Constant *Lower = getLower(); 00295 Constant *Upper = getUpper(); 00296 if (Lower->getType()->isInteger() && !Lower->getType()->isUnsigned()) { 00297 // Ensure we are doing a ZERO extension even if the input range is signed. 00298 Lower = ConstantExpr::getCast(Lower, Ty->getUnsignedVersion()); 00299 Upper = ConstantExpr::getCast(Upper, Ty->getUnsignedVersion()); 00300 } 00301 00302 return ConstantRange(ConstantExpr::getCast(Lower, Ty), 00303 ConstantExpr::getCast(Upper, Ty)); 00304 } 00305 00306 /// truncate - Return a new range in the specified integer type, which must be 00307 /// strictly smaller than the current type. The returned range will 00308 /// correspond to the possible range of values if the source range had been 00309 /// truncated to the specified type. 00310 ConstantRange ConstantRange::truncate(const Type *Ty) const { 00311 assert(getLower()->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && 00312 "Not a value truncation"); 00313 uint64_t Size = 1ULL << Ty->getPrimitiveSize()*8; 00314 if (isFullSet() || getSetSize() >= Size) 00315 return ConstantRange(getType()); 00316 00317 return ConstantRange(ConstantExpr::getCast(getLower(), Ty), 00318 ConstantExpr::getCast(getUpper(), Ty)); 00319 } 00320 00321 00322 /// print - Print out the bounds to a stream... 00323 /// 00324 void ConstantRange::print(std::ostream &OS) const { 00325 OS << "[" << *Lower << "," << *Upper << " )"; 00326 } 00327 00328 /// dump - Allow printing from a debugger easily... 00329 /// 00330 void ConstantRange::dump() const { 00331 print(std::cerr); 00332 }