1 //===- ConstantRange.h - Represent a range ----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Represent a range of possible values that may occur when the program is run 10 // for an integral value. This keeps track of a lower and upper bound for the 11 // constant, which MAY wrap around the end of the numeric range. To do this, it 12 // keeps track of a [lower, upper) bound, which specifies an interval just like 13 // STL iterators. When used with boolean values, the following are important 14 // ranges: : 15 // 16 // [F, F) = {} = Empty set 17 // [T, F) = {T} 18 // [F, T) = {F} 19 // [T, T) = {F, T} = Full set 20 // 21 // The other integral ranges use min/max values for special range values. For 22 // example, for 8-bit types, it uses: 23 // [0, 0) = {} = Empty set 24 // [255, 255) = {0..255} = Full Set 25 // 26 // Note that ConstantRange can be used to represent either signed or 27 // unsigned ranges. 28 // 29 //===----------------------------------------------------------------------===// 30 31 #ifndef LLVM_IR_CONSTANTRANGE_H 32 #define LLVM_IR_CONSTANTRANGE_H 33 34 #include "llvm/ADT/APInt.h" 35 #include "llvm/IR/InstrTypes.h" 36 #include "llvm/IR/Instruction.h" 37 #include "llvm/Support/Compiler.h" 38 #include <cstdint> 39 40 namespace llvm { 41 42 class MDNode; 43 class raw_ostream; 44 struct KnownBits; 45 46 /// This class represents a range of values. 47 class LLVM_NODISCARD ConstantRange { 48 APInt Lower, Upper; 49 50 /// Create empty constant range with same bitwidth. getEmpty()51 ConstantRange getEmpty() const { 52 return ConstantRange(getBitWidth(), false); 53 } 54 55 /// Create full constant range with same bitwidth. getFull()56 ConstantRange getFull() const { 57 return ConstantRange(getBitWidth(), true); 58 } 59 60 public: 61 /// Initialize a full or empty set for the specified bit width. 62 explicit ConstantRange(uint32_t BitWidth, bool isFullSet); 63 64 /// Initialize a range to hold the single specified value. 65 ConstantRange(APInt Value); 66 67 /// Initialize a range of values explicitly. This will assert out if 68 /// Lower==Upper and Lower != Min or Max value for its type. It will also 69 /// assert out if the two APInt's are not the same bit width. 70 ConstantRange(APInt Lower, APInt Upper); 71 72 /// Create empty constant range with the given bit width. getEmpty(uint32_t BitWidth)73 static ConstantRange getEmpty(uint32_t BitWidth) { 74 return ConstantRange(BitWidth, false); 75 } 76 77 /// Create full constant range with the given bit width. getFull(uint32_t BitWidth)78 static ConstantRange getFull(uint32_t BitWidth) { 79 return ConstantRange(BitWidth, true); 80 } 81 82 /// Create non-empty constant range with the given bounds. If Lower and 83 /// Upper are the same, a full range is returned. getNonEmpty(APInt Lower,APInt Upper)84 static ConstantRange getNonEmpty(APInt Lower, APInt Upper) { 85 if (Lower == Upper) 86 return getFull(Lower.getBitWidth()); 87 return ConstantRange(std::move(Lower), std::move(Upper)); 88 } 89 90 /// Initialize a range based on a known bits constraint. The IsSigned flag 91 /// indicates whether the constant range should not wrap in the signed or 92 /// unsigned domain. 93 static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned); 94 95 /// Produce the smallest range such that all values that may satisfy the given 96 /// predicate with any value contained within Other is contained in the 97 /// returned range. Formally, this returns a superset of 98 /// 'union over all y in Other . { x : icmp op x y is true }'. If the exact 99 /// answer is not representable as a ConstantRange, the return value will be a 100 /// proper superset of the above. 101 /// 102 /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4) 103 static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, 104 const ConstantRange &Other); 105 106 /// Produce the largest range such that all values in the returned range 107 /// satisfy the given predicate with all values contained within Other. 108 /// Formally, this returns a subset of 109 /// 'intersection over all y in Other . { x : icmp op x y is true }'. If the 110 /// exact answer is not representable as a ConstantRange, the return value 111 /// will be a proper subset of the above. 112 /// 113 /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2) 114 static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, 115 const ConstantRange &Other); 116 117 /// Produce the exact range such that all values in the returned range satisfy 118 /// the given predicate with any value contained within Other. Formally, this 119 /// returns the exact answer when the superset of 'union over all y in Other 120 /// is exactly same as the subset of intersection over all y in Other. 121 /// { x : icmp op x y is true}'. 122 /// 123 /// Example: Pred = ult and Other = i8 3 returns [0, 3) 124 static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, 125 const APInt &Other); 126 127 /// Produce the largest range containing all X such that "X BinOp Y" is 128 /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may 129 /// be *some* Y in Other for which additional X not contained in the result 130 /// also do not overflow. 131 /// 132 /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap. 133 /// 134 /// Examples: 135 /// typedef OverflowingBinaryOperator OBO; 136 /// #define MGNR makeGuaranteedNoWrapRegion 137 /// MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127) 138 /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1) 139 /// MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set 140 /// MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4) 141 /// MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128) 142 /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0) 143 static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, 144 const ConstantRange &Other, 145 unsigned NoWrapKind); 146 147 /// Produce the range that contains X if and only if "X BinOp Other" does 148 /// not wrap. 149 static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, 150 const APInt &Other, 151 unsigned NoWrapKind); 152 153 /// Set up \p Pred and \p RHS such that 154 /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this. Return true if 155 /// successful. 156 bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const; 157 158 /// Return the lower value for this range. getLower()159 const APInt &getLower() const { return Lower; } 160 161 /// Return the upper value for this range. getUpper()162 const APInt &getUpper() const { return Upper; } 163 164 /// Get the bit width of this ConstantRange. getBitWidth()165 uint32_t getBitWidth() const { return Lower.getBitWidth(); } 166 167 /// Return true if this set contains all of the elements possible 168 /// for this data-type. 169 bool isFullSet() const; 170 171 /// Return true if this set contains no members. 172 bool isEmptySet() const; 173 174 /// Return true if this set wraps around the unsigned domain. Special cases: 175 /// * Empty set: Not wrapped. 176 /// * Full set: Not wrapped. 177 /// * [X, 0) == [X, Max]: Not wrapped. 178 bool isWrappedSet() const; 179 180 /// Return true if the exclusive upper bound wraps around the unsigned 181 /// domain. Special cases: 182 /// * Empty set: Not wrapped. 183 /// * Full set: Not wrapped. 184 /// * [X, 0): Wrapped. 185 bool isUpperWrapped() const; 186 187 /// Return true if this set wraps around the signed domain. Special cases: 188 /// * Empty set: Not wrapped. 189 /// * Full set: Not wrapped. 190 /// * [X, SignedMin) == [X, SignedMax]: Not wrapped. 191 bool isSignWrappedSet() const; 192 193 /// Return true if the (exclusive) upper bound wraps around the signed 194 /// domain. Special cases: 195 /// * Empty set: Not wrapped. 196 /// * Full set: Not wrapped. 197 /// * [X, SignedMin): Wrapped. 198 bool isUpperSignWrapped() const; 199 200 /// Return true if the specified value is in the set. 201 bool contains(const APInt &Val) const; 202 203 /// Return true if the other range is a subset of this one. 204 bool contains(const ConstantRange &CR) const; 205 206 /// If this set contains a single element, return it, otherwise return null. getSingleElement()207 const APInt *getSingleElement() const { 208 if (Upper == Lower + 1) 209 return &Lower; 210 return nullptr; 211 } 212 213 /// If this set contains all but a single element, return it, otherwise return 214 /// null. getSingleMissingElement()215 const APInt *getSingleMissingElement() const { 216 if (Lower == Upper + 1) 217 return &Upper; 218 return nullptr; 219 } 220 221 /// Return true if this set contains exactly one member. isSingleElement()222 bool isSingleElement() const { return getSingleElement() != nullptr; } 223 224 /// Compare set size of this range with the range CR. 225 bool isSizeStrictlySmallerThan(const ConstantRange &CR) const; 226 227 /// Compare set size of this range with Value. 228 bool isSizeLargerThan(uint64_t MaxSize) const; 229 230 /// Return true if all values in this range are negative. 231 bool isAllNegative() const; 232 233 /// Return true if all values in this range are non-negative. 234 bool isAllNonNegative() const; 235 236 /// Return the largest unsigned value contained in the ConstantRange. 237 APInt getUnsignedMax() const; 238 239 /// Return the smallest unsigned value contained in the ConstantRange. 240 APInt getUnsignedMin() const; 241 242 /// Return the largest signed value contained in the ConstantRange. 243 APInt getSignedMax() const; 244 245 /// Return the smallest signed value contained in the ConstantRange. 246 APInt getSignedMin() const; 247 248 /// Return true if this range is equal to another range. 249 bool operator==(const ConstantRange &CR) const { 250 return Lower == CR.Lower && Upper == CR.Upper; 251 } 252 bool operator!=(const ConstantRange &CR) const { 253 return !operator==(CR); 254 } 255 256 /// Subtract the specified constant from the endpoints of this constant range. 257 ConstantRange subtract(const APInt &CI) const; 258 259 /// Subtract the specified range from this range (aka relative complement of 260 /// the sets). 261 ConstantRange difference(const ConstantRange &CR) const; 262 263 /// If represented precisely, the result of some range operations may consist 264 /// of multiple disjoint ranges. As only a single range may be returned, any 265 /// range covering these disjoint ranges constitutes a valid result, but some 266 /// may be more useful than others depending on context. The preferred range 267 /// type specifies whether a range that is non-wrapping in the unsigned or 268 /// signed domain, or has the smallest size, is preferred. If a signedness is 269 /// preferred but all ranges are non-wrapping or all wrapping, then the 270 /// smallest set size is preferred. If there are multiple smallest sets, any 271 /// one of them may be returned. 272 enum PreferredRangeType { Smallest, Unsigned, Signed }; 273 274 /// Return the range that results from the intersection of this range with 275 /// another range. If the intersection is disjoint, such that two results 276 /// are possible, the preferred range is determined by the PreferredRangeType. 277 ConstantRange intersectWith(const ConstantRange &CR, 278 PreferredRangeType Type = Smallest) const; 279 280 /// Return the range that results from the union of this range 281 /// with another range. The resultant range is guaranteed to include the 282 /// elements of both sets, but may contain more. For example, [3, 9) union 283 /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included 284 /// in either set before. 285 ConstantRange unionWith(const ConstantRange &CR, 286 PreferredRangeType Type = Smallest) const; 287 288 /// Return a new range representing the possible values resulting 289 /// from an application of the specified cast operator to this range. \p 290 /// BitWidth is the target bitwidth of the cast. For casts which don't 291 /// change bitwidth, it must be the same as the source bitwidth. For casts 292 /// which do change bitwidth, the bitwidth must be consistent with the 293 /// requested cast and source bitwidth. 294 ConstantRange castOp(Instruction::CastOps CastOp, 295 uint32_t BitWidth) const; 296 297 /// Return a new range in the specified integer type, which must 298 /// be strictly larger than the current type. The returned range will 299 /// correspond to the possible range of values if the source range had been 300 /// zero extended to BitWidth. 301 ConstantRange zeroExtend(uint32_t BitWidth) const; 302 303 /// Return a new range in the specified integer type, which must 304 /// be strictly larger than the current type. The returned range will 305 /// correspond to the possible range of values if the source range had been 306 /// sign extended to BitWidth. 307 ConstantRange signExtend(uint32_t BitWidth) const; 308 309 /// Return a new range in the specified integer type, which must be 310 /// strictly smaller than the current type. The returned range will 311 /// correspond to the possible range of values if the source range had been 312 /// truncated to the specified type. 313 ConstantRange truncate(uint32_t BitWidth) const; 314 315 /// Make this range have the bit width given by \p BitWidth. The 316 /// value is zero extended, truncated, or left alone to make it that width. 317 ConstantRange zextOrTrunc(uint32_t BitWidth) const; 318 319 /// Make this range have the bit width given by \p BitWidth. The 320 /// value is sign extended, truncated, or left alone to make it that width. 321 ConstantRange sextOrTrunc(uint32_t BitWidth) const; 322 323 /// Return a new range representing the possible values resulting 324 /// from an application of the specified binary operator to an left hand side 325 /// of this range and a right hand side of \p Other. 326 ConstantRange binaryOp(Instruction::BinaryOps BinOp, 327 const ConstantRange &Other) const; 328 329 /// Return a new range representing the possible values resulting 330 /// from an application of the specified overflowing binary operator to a 331 /// left hand side of this range and a right hand side of \p Other given 332 /// the provided knowledge about lack of wrapping \p NoWrapKind. 333 ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, 334 const ConstantRange &Other, 335 unsigned NoWrapKind) const; 336 337 /// Return a new range representing the possible values resulting 338 /// from an addition of a value in this range and a value in \p Other. 339 ConstantRange add(const ConstantRange &Other) const; 340 341 /// Return a new range representing the possible values resulting 342 /// from an addition with wrap type \p NoWrapKind of a value in this 343 /// range and a value in \p Other. 344 /// If the result range is disjoint, the preferred range is determined by the 345 /// \p PreferredRangeType. 346 ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, 347 PreferredRangeType RangeType = Smallest) const; 348 349 /// Return a new range representing the possible values resulting 350 /// from a subtraction of a value in this range and a value in \p Other. 351 ConstantRange sub(const ConstantRange &Other) const; 352 353 /// Return a new range representing the possible values resulting 354 /// from an subtraction with wrap type \p NoWrapKind of a value in this 355 /// range and a value in \p Other. 356 /// If the result range is disjoint, the preferred range is determined by the 357 /// \p PreferredRangeType. 358 ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, 359 PreferredRangeType RangeType = Smallest) const; 360 361 /// Return a new range representing the possible values resulting 362 /// from a multiplication of a value in this range and a value in \p Other, 363 /// treating both this and \p Other as unsigned ranges. 364 ConstantRange multiply(const ConstantRange &Other) const; 365 366 /// Return a new range representing the possible values resulting 367 /// from a signed maximum of a value in this range and a value in \p Other. 368 ConstantRange smax(const ConstantRange &Other) const; 369 370 /// Return a new range representing the possible values resulting 371 /// from an unsigned maximum of a value in this range and a value in \p Other. 372 ConstantRange umax(const ConstantRange &Other) const; 373 374 /// Return a new range representing the possible values resulting 375 /// from a signed minimum of a value in this range and a value in \p Other. 376 ConstantRange smin(const ConstantRange &Other) const; 377 378 /// Return a new range representing the possible values resulting 379 /// from an unsigned minimum of a value in this range and a value in \p Other. 380 ConstantRange umin(const ConstantRange &Other) const; 381 382 /// Return a new range representing the possible values resulting 383 /// from an unsigned division of a value in this range and a value in 384 /// \p Other. 385 ConstantRange udiv(const ConstantRange &Other) const; 386 387 /// Return a new range representing the possible values resulting 388 /// from a signed division of a value in this range and a value in 389 /// \p Other. Division by zero and division of SignedMin by -1 are considered 390 /// undefined behavior, in line with IR, and do not contribute towards the 391 /// result. 392 ConstantRange sdiv(const ConstantRange &Other) const; 393 394 /// Return a new range representing the possible values resulting 395 /// from an unsigned remainder operation of a value in this range and a 396 /// value in \p Other. 397 ConstantRange urem(const ConstantRange &Other) const; 398 399 /// Return a new range representing the possible values resulting 400 /// from a signed remainder operation of a value in this range and a 401 /// value in \p Other. 402 ConstantRange srem(const ConstantRange &Other) const; 403 404 /// Return a new range representing the possible values resulting 405 /// from a binary-and of a value in this range by a value in \p Other. 406 ConstantRange binaryAnd(const ConstantRange &Other) const; 407 408 /// Return a new range representing the possible values resulting 409 /// from a binary-or of a value in this range by a value in \p Other. 410 ConstantRange binaryOr(const ConstantRange &Other) const; 411 412 /// Return a new range representing the possible values resulting 413 /// from a left shift of a value in this range by a value in \p Other. 414 /// TODO: This isn't fully implemented yet. 415 ConstantRange shl(const ConstantRange &Other) const; 416 417 /// Return a new range representing the possible values resulting from a 418 /// logical right shift of a value in this range and a value in \p Other. 419 ConstantRange lshr(const ConstantRange &Other) const; 420 421 /// Return a new range representing the possible values resulting from a 422 /// arithmetic right shift of a value in this range and a value in \p Other. 423 ConstantRange ashr(const ConstantRange &Other) const; 424 425 /// Perform an unsigned saturating addition of two constant ranges. 426 ConstantRange uadd_sat(const ConstantRange &Other) const; 427 428 /// Perform a signed saturating addition of two constant ranges. 429 ConstantRange sadd_sat(const ConstantRange &Other) const; 430 431 /// Perform an unsigned saturating subtraction of two constant ranges. 432 ConstantRange usub_sat(const ConstantRange &Other) const; 433 434 /// Perform a signed saturating subtraction of two constant ranges. 435 ConstantRange ssub_sat(const ConstantRange &Other) const; 436 437 /// Perform an unsigned saturating multiplication of two constant ranges. 438 ConstantRange umul_sat(const ConstantRange &Other) const; 439 440 /// Perform a signed saturating multiplication of two constant ranges. 441 ConstantRange smul_sat(const ConstantRange &Other) const; 442 443 /// Perform an unsigned saturating left shift of this constant range by a 444 /// value in \p Other. 445 ConstantRange ushl_sat(const ConstantRange &Other) const; 446 447 /// Perform a signed saturating left shift of this constant range by a 448 /// value in \p Other. 449 ConstantRange sshl_sat(const ConstantRange &Other) const; 450 451 /// Return a new range that is the logical not of the current set. 452 ConstantRange inverse() const; 453 454 /// Calculate absolute value range. If the original range contains signed 455 /// min, then the resulting range will also contain signed min. 456 ConstantRange abs() const; 457 458 /// Represents whether an operation on the given constant range is known to 459 /// always or never overflow. 460 enum class OverflowResult { 461 /// Always overflows in the direction of signed/unsigned min value. 462 AlwaysOverflowsLow, 463 /// Always overflows in the direction of signed/unsigned max value. 464 AlwaysOverflowsHigh, 465 /// May or may not overflow. 466 MayOverflow, 467 /// Never overflows. 468 NeverOverflows, 469 }; 470 471 /// Return whether unsigned add of the two ranges always/never overflows. 472 OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const; 473 474 /// Return whether signed add of the two ranges always/never overflows. 475 OverflowResult signedAddMayOverflow(const ConstantRange &Other) const; 476 477 /// Return whether unsigned sub of the two ranges always/never overflows. 478 OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const; 479 480 /// Return whether signed sub of the two ranges always/never overflows. 481 OverflowResult signedSubMayOverflow(const ConstantRange &Other) const; 482 483 /// Return whether unsigned mul of the two ranges always/never overflows. 484 OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const; 485 486 /// Print out the bounds to a stream. 487 void print(raw_ostream &OS) const; 488 489 /// Allow printing from a debugger easily. 490 void dump() const; 491 }; 492 493 inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) { 494 CR.print(OS); 495 return OS; 496 } 497 498 /// Parse out a conservative ConstantRange from !range metadata. 499 /// 500 /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20). 501 ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD); 502 503 } // end namespace llvm 504 505 #endif // LLVM_IR_CONSTANTRANGE_H 506