diff options
Diffstat (limited to 'include/llvm/IR/ConstantRange.h')
| -rw-r--r-- | include/llvm/IR/ConstantRange.h | 191 |
1 files changed, 158 insertions, 33 deletions
diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h index 1adda3269abc..91f3f31abe17 100644 --- a/include/llvm/IR/ConstantRange.h +++ b/include/llvm/IR/ConstantRange.h @@ -1,9 +1,8 @@ //===- ConstantRange.h - Represent a range ----------------------*- C++ -*-===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // @@ -42,14 +41,25 @@ namespace llvm { class MDNode; class raw_ostream; +struct KnownBits; /// This class represents a range of values. class LLVM_NODISCARD ConstantRange { APInt Lower, Upper; + /// Create empty constant range with same bitwidth. + ConstantRange getEmpty() const { + return ConstantRange(getBitWidth(), false); + } + + /// Create full constant range with same bitwidth. + ConstantRange getFull() const { + return ConstantRange(getBitWidth(), true); + } + public: - /// Initialize a full (the default) or empty set for the specified bit width. - explicit ConstantRange(uint32_t BitWidth, bool isFullSet = true); + /// Initialize a full or empty set for the specified bit width. + explicit ConstantRange(uint32_t BitWidth, bool isFullSet); /// Initialize a range to hold the single specified value. ConstantRange(APInt Value); @@ -59,6 +69,29 @@ public: /// assert out if the two APInt's are not the same bit width. ConstantRange(APInt Lower, APInt Upper); + /// Create empty constant range with the given bit width. + static ConstantRange getEmpty(uint32_t BitWidth) { + return ConstantRange(BitWidth, false); + } + + /// Create full constant range with the given bit width. + static ConstantRange getFull(uint32_t BitWidth) { + return ConstantRange(BitWidth, true); + } + + /// Create non-empty constant range with the given bounds. If Lower and + /// Upper are the same, a full range is returned. + static ConstantRange getNonEmpty(APInt Lower, APInt Upper) { + if (Lower == Upper) + return getFull(Lower.getBitWidth()); + return ConstantRange(std::move(Lower), std::move(Upper)); + } + + /// Initialize a range based on a known bits constraint. The IsSigned flag + /// indicates whether the constant range should not wrap in the signed or + /// unsigned domain. + static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned); + /// Produce the smallest range such that all values that may satisfy the given /// predicate with any value contained within Other is contained in the /// returned range. Formally, this returns a superset of @@ -91,14 +124,12 @@ public: static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other); - /// Return the largest range containing all X such that "X BinOpC Y" is - /// guaranteed not to wrap (overflow) for all Y in Other. + /// Produce the largest range containing all X such that "X BinOp Y" is + /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may + /// be *some* Y in Other for which additional X not contained in the result + /// also do not overflow. /// - /// NB! The returned set does *not* contain **all** possible values of X for - /// which "X BinOpC Y" does not wrap -- some viable values of X may be - /// missing, so you cannot use this to constrain X's range. E.g. in the - /// fourth example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2), - /// but (-2) is not in the set returned. + /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap. /// /// Examples: /// typedef OverflowingBinaryOperator OBO; @@ -106,17 +137,19 @@ public: /// MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127) /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1) /// MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set - /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap) - /// == [0,INT_MAX) /// MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4) /// MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128) /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0) - /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap) - /// == [1,INT_MAX) static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind); + /// Produce the range that contains X if and only if "X BinOp Other" does + /// not wrap. + static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, + const APInt &Other, + unsigned NoWrapKind); + /// Set up \p Pred and \p RHS such that /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this. Return true if /// successful. @@ -138,14 +171,32 @@ public: /// Return true if this set contains no members. bool isEmptySet() const; - /// Return true if this set wraps around the top of the range. - /// For example: [100, 8). + /// Return true if this set wraps around the unsigned domain. Special cases: + /// * Empty set: Not wrapped. + /// * Full set: Not wrapped. + /// * [X, 0) == [X, Max]: Not wrapped. bool isWrappedSet() const; - /// Return true if this set wraps around the INT_MIN of - /// its bitwidth. For example: i8 [120, 140). + /// Return true if the exclusive upper bound wraps around the unsigned + /// domain. Special cases: + /// * Empty set: Not wrapped. + /// * Full set: Not wrapped. + /// * [X, 0): Wrapped. + bool isUpperWrapped() const; + + /// Return true if this set wraps around the signed domain. Special cases: + /// * Empty set: Not wrapped. + /// * Full set: Not wrapped. + /// * [X, SignedMin) == [X, SignedMax]: Not wrapped. bool isSignWrappedSet() const; + /// Return true if the (exclusive) upper bound wraps around the signed + /// domain. Special cases: + /// * Empty set: Not wrapped. + /// * Full set: Not wrapped. + /// * [X, SignedMin): Wrapped. + bool isUpperSignWrapped() const; + /// Return true if the specified value is in the set. bool contains(const APInt &Val) const; @@ -170,15 +221,18 @@ public: /// Return true if this set contains exactly one member. bool isSingleElement() const { return getSingleElement() != nullptr; } - /// Return the number of elements in this set. - APInt getSetSize() const; - /// Compare set size of this range with the range CR. bool isSizeStrictlySmallerThan(const ConstantRange &CR) const; - // Compare set size of this range with Value. + /// Compare set size of this range with Value. bool isSizeLargerThan(uint64_t MaxSize) const; + /// Return true if all values in this range are negative. + bool isAllNegative() const; + + /// Return true if all values in this range are non-negative. + bool isAllNonNegative() const; + /// Return the largest unsigned value contained in the ConstantRange. APInt getUnsignedMax() const; @@ -206,20 +260,30 @@ public: /// the sets). ConstantRange difference(const ConstantRange &CR) const; - /// Return the range that results from the intersection of - /// this range with another range. The resultant range is guaranteed to - /// include all elements contained in both input ranges, and to have the - /// smallest possible set size that does so. Because there may be two - /// intersections with the same set size, A.intersectWith(B) might not - /// be equal to B.intersectWith(A). - ConstantRange intersectWith(const ConstantRange &CR) const; + /// If represented precisely, the result of some range operations may consist + /// of multiple disjoint ranges. As only a single range may be returned, any + /// range covering these disjoint ranges constitutes a valid result, but some + /// may be more useful than others depending on context. The preferred range + /// type specifies whether a range that is non-wrapping in the unsigned or + /// signed domain, or has the smallest size, is preferred. If a signedness is + /// preferred but all ranges are non-wrapping or all wrapping, then the + /// smallest set size is preferred. If there are multiple smallest sets, any + /// one of them may be returned. + enum PreferredRangeType { Smallest, Unsigned, Signed }; + + /// Return the range that results from the intersection of this range with + /// another range. If the intersection is disjoint, such that two results + /// are possible, the preferred range is determined by the PreferredRangeType. + ConstantRange intersectWith(const ConstantRange &CR, + PreferredRangeType Type = Smallest) const; /// Return the range that results from the union of this range /// with another range. The resultant range is guaranteed to include the /// elements of both sets, but may contain more. For example, [3, 9) union /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included /// in either set before. - ConstantRange unionWith(const ConstantRange &CR) const; + ConstantRange unionWith(const ConstantRange &CR, + PreferredRangeType Type = Smallest) const; /// Return a new range representing the possible values resulting /// from an application of the specified cast operator to this range. \p @@ -301,6 +365,23 @@ public: ConstantRange udiv(const ConstantRange &Other) const; /// Return a new range representing the possible values resulting + /// from a signed division of a value in this range and a value in + /// \p Other. Division by zero and division of SignedMin by -1 are considered + /// undefined behavior, in line with IR, and do not contribute towards the + /// result. + ConstantRange sdiv(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting + /// from an unsigned remainder operation of a value in this range and a + /// value in \p Other. + ConstantRange urem(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting + /// from a signed remainder operation of a value in this range and a + /// value in \p Other. + ConstantRange srem(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting /// from a binary-and of a value in this range by a value in \p Other. ConstantRange binaryAnd(const ConstantRange &Other) const; @@ -321,9 +402,53 @@ public: /// arithmetic right shift of a value in this range and a value in \p Other. ConstantRange ashr(const ConstantRange &Other) const; + /// Perform an unsigned saturating addition of two constant ranges. + ConstantRange uadd_sat(const ConstantRange &Other) const; + + /// Perform a signed saturating addition of two constant ranges. + ConstantRange sadd_sat(const ConstantRange &Other) const; + + /// Perform an unsigned saturating subtraction of two constant ranges. + ConstantRange usub_sat(const ConstantRange &Other) const; + + /// Perform a signed saturating subtraction of two constant ranges. + ConstantRange ssub_sat(const ConstantRange &Other) const; + /// Return a new range that is the logical not of the current set. ConstantRange inverse() const; + /// Calculate absolute value range. If the original range contains signed + /// min, then the resulting range will also contain signed min. + ConstantRange abs() const; + + /// Represents whether an operation on the given constant range is known to + /// always or never overflow. + enum class OverflowResult { + /// Always overflows in the direction of signed/unsigned min value. + AlwaysOverflowsLow, + /// Always overflows in the direction of signed/unsigned max value. + AlwaysOverflowsHigh, + /// May or may not overflow. + MayOverflow, + /// Never overflows. + NeverOverflows, + }; + + /// Return whether unsigned add of the two ranges always/never overflows. + OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const; + + /// Return whether signed add of the two ranges always/never overflows. + OverflowResult signedAddMayOverflow(const ConstantRange &Other) const; + + /// Return whether unsigned sub of the two ranges always/never overflows. + OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const; + + /// Return whether signed sub of the two ranges always/never overflows. + OverflowResult signedSubMayOverflow(const ConstantRange &Other) const; + + /// Return whether unsigned mul of the two ranges always/never overflows. + OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const; + /// Print out the bounds to a stream. void print(raw_ostream &OS) const; |