From 3547a7e64e67c7283558a9812b6cf7cda9507bd0 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sun, 28 Apr 2019 15:40:56 +0000 Subject: [PATCH] [ConstantRange] Add makeExactNoWrapRegion() I got confused on the terminology, and the change in D60598 was not correct. I was thinking of "exact" in terms of the result being non-approximate. However, the relevant distinction here is whether the result is * Largest range such that: Forall Y in Other: Forall X in Result: X BinOp Y does not wrap. (makeGuaranteedNoWrapRegion) * Smallest range such that: Forall Y in Other: Forall X not in Result: X BinOp Y wraps. (A hypothetical makeAllowedNoWrapRegion) * Both. (makeExactNoWrapRegion) I'm adding a separate makeExactNoWrapRegion method accepting a single APInt (same as makeExactICmpRegion) and using it in the places where the guarantee is relevant. Differential Revision: https://reviews.llvm.org/D60960 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@359402 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/ConstantRange.h | 12 ++++++++++-- lib/Analysis/LazyValueInfo.cpp | 4 ++-- lib/IR/ConstantRange.cpp | 14 ++++++++++---- unittests/IR/ConstantRangeTest.cpp | 12 ++++++++++-- 4 files changed, 32 insertions(+), 10 deletions(-) diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h index 5b9e8a6555b..0aac24ff8f7 100644 --- a/include/llvm/IR/ConstantRange.h +++ b/include/llvm/IR/ConstantRange.h @@ -124,8 +124,10 @@ public: static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other); - /// Return the exact 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. /// /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap. /// @@ -142,6 +144,12 @@ public: 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. diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 02a829f500b..e7ca69150c0 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -1146,8 +1146,8 @@ static ValueLatticeElement getValueFromOverflowCondition( return ValueLatticeElement::getOverdefined(); // Calculate the possible values of %x for which no overflow occurs. - ConstantRange NWR = ConstantRange::makeGuaranteedNoWrapRegion( - WO->getBinaryOp(), ConstantRange(*C), WO->getNoWrapKind()); + ConstantRange NWR = ConstantRange::makeExactNoWrapRegion( + WO->getBinaryOp(), *C, WO->getNoWrapKind()); // If overflow is false, %x is constrained to NWR. If overflow is true, %x is // constrained to it's inverse (all values that might cause overflow). diff --git a/lib/IR/ConstantRange.cpp b/lib/IR/ConstantRange.cpp index 76e0b0ca5b3..e40bbbb7e9a 100644 --- a/lib/IR/ConstantRange.cpp +++ b/lib/IR/ConstantRange.cpp @@ -309,6 +309,14 @@ ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, } } +ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp, + const APInt &Other, + unsigned NoWrapKind) { + // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as + // "for all" and "for any" coincide in this case. + return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind); +} + bool ConstantRange::isFullSet() const { return Lower == Upper && Lower.isMaxValue(); } @@ -843,10 +851,8 @@ ConstantRange::add(const ConstantRange &Other) const { ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const { // Calculate the subset of this range such that "X + Other" is // guaranteed not to wrap (overflow) for all X in this subset. - // makeGuaranteedNoWrapRegion will produce an exact NSW range. - auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add, - ConstantRange(Other), - OverflowingBinaryOperator::NoSignedWrap); + auto NSWRange = ConstantRange::makeExactNoWrapRegion( + BinaryOperator::Add, Other, OverflowingBinaryOperator::NoSignedWrap); auto NSWConstrainedRange = intersectWith(NSWRange); return NSWConstrainedRange.add(ConstantRange(Other)); diff --git a/unittests/IR/ConstantRangeTest.cpp b/unittests/IR/ConstantRangeTest.cpp index fdd1e6a47a6..a1c66f33abb 100644 --- a/unittests/IR/ConstantRangeTest.cpp +++ b/unittests/IR/ConstantRangeTest.cpp @@ -1176,17 +1176,25 @@ void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp, ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind); ForeachNumInConstantRange(CR1, [&](const APInt &N1) { bool NoOverflow = true; + bool Overflow = true; ForeachNumInConstantRange(CR2, [&](const APInt &N2) { if (OverflowFn(N1, N2)) NoOverflow = false; + else + Overflow = false; }); EXPECT_EQ(NoOverflow, NoWrap.contains(N1)); + + // The no-wrap range is exact for single-element ranges. + if (CR2.isSingleElement()) { + EXPECT_EQ(Overflow, !NoWrap.contains(N1)); + } }); }); } -// Show that makeGuaranteedNoWrapRegion is precise if only one of -// NoUnsignedWrap or NoSignedWrap is used. +// Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element +// ranges also exact. TEST(ConstantRange, NoWrapRegionExhaustive) { TestNoWrapRegionExhaustive( Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap, -- 2.11.0