From bf8c7f0adf90c8271c790be9922a2f97d19d4c01 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Sat, 11 Jul 2009 06:15:39 +0000 Subject: [PATCH] Move a method that creates constant ranges relative to another constant range per icmp predicate out of predsimplify and into ConstantRange. Add another utility method that determines whether one range is a subset of another. Combine with the former to determine whether icmp pred range, range is known to be true or not. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75357 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/ConstantRange.h | 10 +++ lib/Support/ConstantRange.cpp | 72 +++++++++++++++++++ lib/Transforms/Scalar/PredicateSimplifier.cpp | 59 ++------------- 3 files changed, 87 insertions(+), 54 deletions(-) diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h index fa4235b0cb3..27585491b38 100644 --- a/include/llvm/Support/ConstantRange.h +++ b/include/llvm/Support/ConstantRange.h @@ -58,6 +58,12 @@ public: /// assert out if the two APInt's are not the same bit width. ConstantRange(const APInt& Lower, const APInt& Upper); + /// makeICmpRegion - Return the range of values that a value must be within + /// in order for the comparison specified by the predicate against range + /// Other to be true. + static ConstantRange makeICmpRegion(unsigned Pred, + const ConstantRange &Other); + /// getLower - Return the lower value for this range... /// const APInt &getLower() const { return Lower; } @@ -88,6 +94,10 @@ public: /// bool contains(const APInt &Val) const; + /// contains - Return true if the other range is a subset of this one. + /// + bool contains(const ConstantRange &CR) const; + /// getSingleElement - If this set contains a single element, return it, /// otherwise return null. /// diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index 809a0241156..e04272348d9 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -23,6 +23,7 @@ #include "llvm/Support/ConstantRange.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Instructions.h" using namespace llvm; /// Initialize a full (the default) or empty set for the specified type. @@ -46,6 +47,53 @@ ConstantRange::ConstantRange(const APInt &L, const APInt &U) : "Lower == Upper, but they aren't min or max value!"); } +ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, + const ConstantRange &CR) { + uint32_t W = CR.getBitWidth(); + switch (Pred) { + default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); + case ICmpInst::ICMP_EQ: + return ConstantRange(CR.getLower(), CR.getUpper()); + case ICmpInst::ICMP_NE: + if (CR.isSingleElement()) + return ConstantRange(CR.getUpper(), CR.getLower()); + return ConstantRange(W); + case ICmpInst::ICMP_ULT: + return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); + case ICmpInst::ICMP_SLT: + return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); + case ICmpInst::ICMP_ULE: { + APInt UMax(CR.getUnsignedMax()); + if (UMax.isMaxValue()) + return ConstantRange(W); + return ConstantRange(APInt::getMinValue(W), UMax + 1); + } + case ICmpInst::ICMP_SLE: { + APInt SMax(CR.getSignedMax()); + if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) + return ConstantRange(W); + return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); + } + case ICmpInst::ICMP_UGT: + return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); + case ICmpInst::ICMP_SGT: + return ConstantRange(CR.getSignedMin() + 1, + APInt::getSignedMinValue(W)); + case ICmpInst::ICMP_UGE: { + APInt UMin(CR.getUnsignedMin()); + if (UMin.isMinValue()) + return ConstantRange(W); + return ConstantRange(UMin, APInt::getNullValue(W)); + } + case ICmpInst::ICMP_SGE: { + APInt SMin(CR.getSignedMin()); + if (SMin.isMinSignedValue()) + return ConstantRange(W); + return ConstantRange(SMin, APInt::getSignedMinValue(W)); + } + } +} + /// isFullSet - Return true if this set contains all of the elements possible /// for this data-type bool ConstantRange::isFullSet() const { @@ -156,6 +204,30 @@ bool ConstantRange::contains(const APInt &V) const { return Lower.ule(V) || V.ult(Upper); } +/// contains - Return true if the argument is a subset of this range. +/// Two equal set contain each other. The empty set is considered to be +/// contained by all other sets. +/// +bool ConstantRange::contains(const ConstantRange &Other) const { + if (isFullSet()) return true; + if (Other.isFullSet()) return false; + if (Other.isEmptySet()) return true; + if (isEmptySet()) return false; + + if (!isWrappedSet()) { + if (Other.isWrappedSet()) + return false; + + return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); + } + + if (!Other.isWrappedSet()) + return Other.getUpper().ule(Upper) || + Lower.ule(Other.getLower()); + + return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); +} + /// subtract - Subtract the specified constant from the endpoints of this /// constant range. ConstantRange ConstantRange::subtract(const APInt &Val) const { diff --git a/lib/Transforms/Scalar/PredicateSimplifier.cpp b/lib/Transforms/Scalar/PredicateSimplifier.cpp index 24707bd4d86..c82c4ff3bfb 100644 --- a/lib/Transforms/Scalar/PredicateSimplifier.cpp +++ b/lib/Transforms/Scalar/PredicateSimplifier.cpp @@ -990,7 +990,7 @@ namespace { assert(!CR.isEmptySet() && "Can't deal with empty set."); if (LV == NE) - return makeConstantRange(ICmpInst::ICMP_NE, CR); + return ConstantRange::makeICmpRegion(ICmpInst::ICMP_NE, CR); unsigned LV_s = LV & (SGT_BIT|SLT_BIT); unsigned LV_u = LV & (UGT_BIT|ULT_BIT); @@ -999,73 +999,24 @@ namespace { ConstantRange Range(CR.getBitWidth()); if (LV_s == SGT_BIT) { - Range = Range.maximalIntersectWith(makeConstantRange( + Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion( hasEQ ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SGT, CR)); } else if (LV_s == SLT_BIT) { - Range = Range.maximalIntersectWith(makeConstantRange( + Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion( hasEQ ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SLT, CR)); } if (LV_u == UGT_BIT) { - Range = Range.maximalIntersectWith(makeConstantRange( + Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion( hasEQ ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_UGT, CR)); } else if (LV_u == ULT_BIT) { - Range = Range.maximalIntersectWith(makeConstantRange( + Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion( hasEQ ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT, CR)); } return Range; } - /// makeConstantRange - Creates a ConstantRange representing the set of all - /// value that match the ICmpInst::Predicate with any of the values in CR. - ConstantRange makeConstantRange(ICmpInst::Predicate ICmpOpcode, - const ConstantRange &CR) { - uint32_t W = CR.getBitWidth(); - switch (ICmpOpcode) { - default: assert(!"Invalid ICmp opcode to makeConstantRange()"); - case ICmpInst::ICMP_EQ: - return ConstantRange(CR.getLower(), CR.getUpper()); - case ICmpInst::ICMP_NE: - if (CR.isSingleElement()) - return ConstantRange(CR.getUpper(), CR.getLower()); - return ConstantRange(W); - case ICmpInst::ICMP_ULT: - return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); - case ICmpInst::ICMP_SLT: - return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); - case ICmpInst::ICMP_ULE: { - APInt UMax(CR.getUnsignedMax()); - if (UMax.isMaxValue()) - return ConstantRange(W); - return ConstantRange(APInt::getMinValue(W), UMax + 1); - } - case ICmpInst::ICMP_SLE: { - APInt SMax(CR.getSignedMax()); - if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) - return ConstantRange(W); - return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); - } - case ICmpInst::ICMP_UGT: - return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); - case ICmpInst::ICMP_SGT: - return ConstantRange(CR.getSignedMin() + 1, - APInt::getSignedMinValue(W)); - case ICmpInst::ICMP_UGE: { - APInt UMin(CR.getUnsignedMin()); - if (UMin.isMinValue()) - return ConstantRange(W); - return ConstantRange(UMin, APInt::getNullValue(W)); - } - case ICmpInst::ICMP_SGE: { - APInt SMin(CR.getSignedMin()); - if (SMin.isMinSignedValue()) - return ConstantRange(W); - return ConstantRange(SMin, APInt::getSignedMinValue(W)); - } - } - } - #ifndef NDEBUG bool isCanonical(Value *V, DomTreeDFS::Node *Subtree) { return V == VN.canonicalize(V, Subtree); -- 2.34.1