https://github.com/jroelofs updated https://github.com/llvm/llvm-project/pull/235159
>From 38c66a29996b706aaa4bf213c035a2dd2cd64fe3 Mon Sep 17 00:00:00 2001 From: Jon Roelofs <[email protected]> Date: Fri, 23 Oct 2026 15:41:04 -0700 Subject: [PATCH] [ConstraintElim] Prove sadd/ssub.with.overflow cannot overflow from the exact sum Decompose the operands and show that the sum lies in the range of the type. This handles patterns like A + (B - A), as well as sums involving signed min/max results, which are split across their respective operands using monotonicity (for example start + smax(end - start - 1, 0) <= end). https://alive2.llvm.org/ce/z/ze8LCk --- .../Scalar/ConstraintElimination.cpp | 163 +++++- .../sadd-with-overflow.ll | 539 ++++++++++++++++++ 2 files changed, 699 insertions(+), 3 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index c58563d58bff25..0a68635af4da38 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -13,6 +13,7 @@ #include "llvm/Transforms/Scalar/ConstraintElimination.h" #include "ScalarOptions.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" @@ -345,6 +346,30 @@ struct Decomposition { return true; return false; } + + /// Merge entries that refer to the same variable, and remove any whose + /// coefficient is zero. \returns true if any operation overflows, i.e. the + /// decomposition is invalid. + [[nodiscard]] bool canonicalize() { + // Sum the coefficients of each variable. + SmallMapVector<Value *, int64_t, 4> Coefficients; + for (const DecompEntry &E : Vars) { + int64_t &Sum = Coefficients[E.Variable]; + if (AddOverflow(Sum, E.Coefficient, Sum)) + return true; + } + Vars.clear(); + for (const auto &[Variable, Coefficient] : Coefficients) + if (Coefficient != 0) + Vars.emplace_back(Coefficient, Variable); + return false; + } + + /// Returns a new decomposition with \p Variable replaced by \p Replacement. + /// Returns std::nullopt if a coefficient overflows, i.e. the decomposition is + /// invalid. + [[nodiscard]] std::optional<Decomposition> + substitute(Value *Variable, Value *Replacement, ConstraintInfo &Info); }; /// Wrapper encapsulating separate constraint systems and corresponding value @@ -393,6 +418,8 @@ class ConstraintInfo { return Signed ? SignedCS : UnsignedCS; } + const DataLayout &getDataLayout() const { return DL; } + void popLastConstraint(bool Signed) { assert(DecomposeCache.empty() && "Cache must be cleared"); getCS(Signed).popLastConstraint(); @@ -551,6 +578,129 @@ static bool doesHoldInRange(ConstraintInfo &Info, Value *Op, return true; } +std::optional<Decomposition> Decomposition::substitute(Value *Variable, + Value *Replacement, + ConstraintInfo &Info) { + Decomposition Result(Offset); + int64_t Coefficient = 0; + for (const DecompEntry &E : Vars) { + if (E.Variable != Variable) + Result.Vars.push_back(E); + else if (AddOverflow(Coefficient, E.Coefficient, Coefficient)) + return std::nullopt; + } + Decomposition ReplacementDec = + decompose(Replacement, Info, /*IsSigned=*/true, Info.getDataLayout()); + if (ReplacementDec.mul(Coefficient) || Result.add(ReplacementDec)) + return std::nullopt; + return Result; +} + +enum class SignedBound { Upper, Lower }; + +/// Returns true if \p Info implies that the value of \p D does not exceed the +/// signed maximum of \p Ty (if \p Bound is Upper) or is not below the signed +/// minimum of \p Ty (if \p Bound is Lower). +/// +/// The constraint systems do not record that every variable is within the +/// range of its type, so only decompositions that are trivially in range, or +/// that reduce to a single variable plus an offset, are handled. A min/max +/// intrinsic result in \p D is split across its respective operands, using the +/// fact that the value of \p D is monotonic in it: for an upper bound on a +/// maximum, both sides must be in range, while for a lower bound only one side +/// must be. +static bool isKnownWithinSignedRange(Decomposition D, SignedBound Bound, + Type *Ty, ConstraintInfo &Info, + unsigned Depth) { + if (D.canonicalize()) + return false; + + if (Depth != 0) { + for (const DecompEntry &E : D.Vars) { + auto *MM = dyn_cast<MinMaxIntrinsic>(E.Variable); + if (!MM || !MM->isSigned() || MM->getType() != Ty) + continue; + auto LHS = D.substitute(E.Variable, MM->getLHS(), Info); + auto RHS = D.substitute(E.Variable, MM->getRHS(), Info); + if (!LHS || !RHS) + return false; + + // D is increasing in the min/max result iff its coefficient is positive. + // Then D is a max over the respective sides iff the intrinsic is a max. + bool IsMax = + (MM->getIntrinsicID() == Intrinsic::smax) == (E.Coefficient > 0); + bool L = isKnownWithinSignedRange(*LHS, Bound, Ty, Info, Depth - 1); + if ((Bound == SignedBound::Upper) == IsMax) + return L && isKnownWithinSignedRange(*RHS, Bound, Ty, Info, Depth - 1); + return L || isKnownWithinSignedRange(*RHS, Bound, Ty, Info, Depth - 1); + } + } + + // Compare in a type wide enough for both the bounds of Ty and the int64_t + // offset, so this does not depend on the width of Ty. + unsigned BitWidth = Ty->getScalarSizeInBits(); + unsigned WideBits = std::max(BitWidth, 64u); + APInt SMax = APInt::getSignedMaxValue(BitWidth).sext(WideBits); + APInt SMin = APInt::getSignedMinValue(BitWidth).sext(WideBits); + APInt Offset(WideBits, D.Offset, /*isSigned=*/true); + if (D.Vars.empty()) + return Bound == SignedBound::Upper ? Offset.sle(SMax) : Offset.sge(SMin); + + // V + C is at most the maximum if C <= 0 and at least the minimum if C >= 0, + // since V is itself in range. + if (D.Vars.size() != 1 || D.Vars[0].Coefficient != 1) + return false; + + Value *V = D.Vars[0].Variable; + if (V->getType() != Ty) + return false; + + if (Bound == SignedBound::Upper) { + if (D.Offset <= 0) + return true; + + // V + C <= SMax iff V <= SMax - C, which is only satisfiable in range. + APInt Limit = SMax - Offset; + return Limit.sge(SMin) && + Info.doesHold(CmpInst::ICMP_SLE, V, + ConstantInt::get(Ty, Limit.trunc(BitWidth))); + } + + if (D.Offset >= 0) + return true; + + // V + C >= SMin iff V >= SMin - C, which is only satisfiable in range. + APInt Limit = SMin - Offset; + return Limit.sle(SMax) && + Info.doesHold(CmpInst::ICMP_SGE, V, + ConstantInt::get(Ty, Limit.trunc(BitWidth))); +} + +/// Returns true if the signed \p Opcode (Add or Sub) of \p Op0 and \p Op1 is +/// known to not overflow because the result is in the range of the type. +/// For example, A + (B - A) is B and therefore cannot overflow. +static bool isKnownNoSignedWrap(Instruction::BinaryOps Opcode, Value *Op0, + Value *Op1, ConstraintInfo &Info) { + if (Opcode != Instruction::Add && Opcode != Instruction::Sub) + return false; + + Type *Ty = Op0->getType(); + if (!Ty->isIntegerTy()) + return false; + + const DataLayout &DL = Info.getDataLayout(); + Decomposition LHS = decompose(Op0, Info, /*IsSigned=*/true, DL); + Decomposition RHS = decompose(Op1, Info, /*IsSigned=*/true, DL); + if (Opcode == Instruction::Add ? LHS.add(RHS) : LHS.sub(RHS)) + return false; + + constexpr unsigned MaxDepth = 2; + return isKnownWithinSignedRange(LHS, SignedBound::Upper, Ty, Info, + MaxDepth) && + isKnownWithinSignedRange(LHS, SignedBound::Lower, Ty, Info, + MaxDepth); +} + /// Returns true if \p Opcode applied to \p Op0 and \p Op1 with \p NoWrapFlags /// is known to not wrap in signed or unsigned, depending on \p Signed. static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, @@ -596,9 +746,16 @@ static bool isKnownNoWrap(Value *V, ConstraintInfo &Info, bool Signed) { if (match(V, m_DisjointOr(m_Value(), m_Value()))) return true; - if (auto *WO = dyn_cast<WithOverflowInst>(V)) - return isKnownNoWrap(WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), - /*NoWrapFlags=*/0, Info, Signed); + if (auto *WO = dyn_cast<WithOverflowInst>(V)) { + if (isKnownNoWrap(WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), + /*NoWrapFlags=*/0, Info, Signed)) + return true; + // Reasoning about the infinite precision sum is costlier than the checks + // above, so only do it for the overflow intrinsics themselves, not + // for the plain adds and subs that decompose() analyzes. + return Signed && isKnownNoSignedWrap(WO->getBinaryOp(), WO->getLHS(), + WO->getRHS(), Info); + } if (auto *Trunc = dyn_cast<TruncInst>(V)) { if (Signed) diff --git a/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll b/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll index 4194797fa5ea05..e28610764f1b01 100644 --- a/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll +++ b/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll @@ -318,3 +318,542 @@ then: else: ret i8 0 } + +define void @sadd_sum_of_difference_assume(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_assume( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %d) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_sum_of_difference_branch(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_branch( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: br i1 [[NONNEG]], label %[[B1:.*]], label %[[EXIT:.*]] +; CHECK: [[B1]]: +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: br i1 [[ORDERED]], label %[[BODY:.*]], label %[[EXIT]] +; CHECK: [[BODY]]: +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: br label %[[EXIT]] +; CHECK: [[EXIT]]: +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + br i1 %nonneg, label %b1, label %exit +b1: + %ordered = icmp sge i8 %end, %start + br i1 %ordered, label %body, label %exit +body: + %d = sub i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %d) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + br label %exit +exit: + ret void +} + +define void @sadd_sum_of_difference_commuted(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_commuted( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %d, i8 %start) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_sum_of_difference_nsw_any_sign(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_nsw_any_sign( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[D:%.*]] = sub nsw i8 [[END]], [[START]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %d = sub nsw i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %d) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_sum_of_difference_neg_start(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_neg_start( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub i8 [[END]], [[START]] +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[START]], i8 [[D]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %d) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_sum_of_difference_unordered(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_unordered( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[D:%.*]] = sub i8 [[END]], [[START]] +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[START]], i8 [[D]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %d = sub i8 %end, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %d) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smin_side(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smin_side( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[D]], i8 5) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub i8 %end, %start + %m = call i8 @llvm.smin.i8(i8 %d, i8 5) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smax_side_neg(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smax_side_neg( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[D]], i8 5) +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[START]], i8 [[M]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub i8 %end, %start + %m = call i8 @llvm.smax.i8(i8 %d, i8 5) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smax_clamp(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smax_clamp( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[NOTSTART:%.*]] = xor i8 [[START]], -1 +; CHECK-NEXT: [[X:%.*]] = add nsw i8 [[END]], [[NOTSTART]] +; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 0) +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[START]], [[M]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[LT:%.*]] = icmp slt i8 [[TMP0]], [[START]] +; CHECK-NEXT: call void @use(i1 [[LT]]) +; CHECK-NEXT: [[GT:%.*]] = icmp slt i8 [[END]], [[TMP0]] +; CHECK-NEXT: call void @use(i1 [[GT]]) +; CHECK-NEXT: ret void +; +entry: + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %notstart = xor i8 %start, -1 + %x = add nsw i8 %end, %notstart + %m = call i8 @llvm.smax.i8(i8 %x, i8 0) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + %new = extractvalue { i8, i1 } %r, 0 + %lt = icmp slt i8 %new, %start + call void @use(i1 %lt) + %gt = icmp slt i8 %end, %new + call void @use(i1 %gt) + ret void +} + +define void @sadd_smax_clamp_unordered(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smax_clamp_unordered( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NOTSTART:%.*]] = xor i8 [[START]], -1 +; CHECK-NEXT: [[X:%.*]] = add nsw i8 [[END]], [[NOTSTART]] +; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 0) +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[START]], [[M]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[LT:%.*]] = icmp slt i8 [[TMP0]], [[START]] +; CHECK-NEXT: call void @use(i1 [[LT]]) +; CHECK-NEXT: [[GT:%.*]] = icmp slt i8 [[END]], [[TMP0]] +; CHECK-NEXT: call void @use(i1 [[GT]]) +; CHECK-NEXT: ret void +; +entry: + %notstart = xor i8 %start, -1 + %x = add nsw i8 %end, %notstart + %m = call i8 @llvm.smax.i8(i8 %x, i8 0) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + %new = extractvalue { i8, i1 } %r, 0 + %lt = icmp slt i8 %new, %start + call void @use(i1 %lt) + %gt = icmp slt i8 %end, %new + call void @use(i1 %gt) + ret void +} + +define void @sadd_sum_of_difference_i128(i128 %start, i128 %end) { +; CHECK-LABEL: define void @sadd_sum_of_difference_i128( +; CHECK-SAME: i128 [[START:%.*]], i128 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[D:%.*]] = sub nsw i128 [[END]], [[START]] +; CHECK-NEXT: [[R:%.*]] = call { i128, i1 } @llvm.sadd.with.overflow.i128(i128 [[START]], i128 [[D]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i128, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %d = sub nsw i128 %end, %start + %r = call { i128, i1 } @llvm.sadd.with.overflow.i128(i128 %start, i128 %d) + %ov = extractvalue { i128, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smax_clamp_i256(i256 %start, i256 %end) { +; CHECK-LABEL: define void @sadd_smax_clamp_i256( +; CHECK-SAME: i256 [[START:%.*]], i256 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i256 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[NOTSTART:%.*]] = xor i256 [[START]], -1 +; CHECK-NEXT: [[X:%.*]] = add nsw i256 [[END]], [[NOTSTART]] +; CHECK-NEXT: [[M:%.*]] = call i256 @llvm.smax.i256(i256 [[X]], i256 0) +; CHECK-NEXT: [[R:%.*]] = call { i256, i1 } @llvm.sadd.with.overflow.i256(i256 [[START]], i256 [[M]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i256, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %ordered = icmp sge i256 %end, %start + call void @llvm.assume(i1 %ordered) + %notstart = xor i256 %start, -1 + %x = add nsw i256 %end, %notstart + %m = call i256 @llvm.smax.i256(i256 %x, i256 0) + %r = call { i256, i1 } @llvm.sadd.with.overflow.i256(i256 %start, i256 %m) + %ov = extractvalue { i256, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_repeated_variable_cancels(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_repeated_variable_cancels( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[D:%.*]] = sub nsw i8 [[END]], [[START]] +; CHECK-NEXT: [[E:%.*]] = add nsw i8 [[D]], [[START]] +; CHECK-NEXT: [[F:%.*]] = sub nsw i8 [[E]], [[START]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %d = sub nsw i8 %end, %start + %e = add nsw i8 %d, %start + %f = sub nsw i8 %e, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %f) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_repeated_variable_nonzero(i8 %start) { +; CHECK-LABEL: define void @sadd_repeated_variable_nonzero( +; CHECK-SAME: i8 [[START:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = add nsw i8 [[START]], [[START]] +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[A]], i8 [[START]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %a = add nsw i8 %start, %start + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %a, i8 %start) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_cancels_to_constant(i8 %x) { +; CHECK-LABEL: define void @sadd_cancels_to_constant( +; CHECK-SAME: i8 [[X:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[N:%.*]] = sub nsw i8 0, [[X]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %n = sub nsw i8 0, %x + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %x, i8 %n) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smin_second_operand(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smin_second_operand( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[ORDERED:%.*]] = icmp sge i8 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[ORDERED]]) +; CHECK-NEXT: [[D:%.*]] = sub nuw nsw i8 [[END]], [[START]] +; CHECK-NEXT: [[M:%.*]] = call i8 @llvm.smin.i8(i8 5, i8 [[D]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %ordered = icmp sge i8 %end, %start + call void @llvm.assume(i1 %ordered) + %d = sub nsw i8 %end, %start + %m = call i8 @llvm.smin.i8(i8 5, i8 %d) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_vector_not_folded(<2 x i8> %start, <2 x i8> %end) { +; CHECK-LABEL: define void @sadd_vector_not_folded( +; CHECK-SAME: <2 x i8> [[START:%.*]], <2 x i8> [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[D:%.*]] = sub nsw <2 x i8> [[END]], [[START]] +; CHECK-NEXT: [[R:%.*]] = call { <2 x i8>, <2 x i1> } @llvm.sadd.with.overflow.v2i8(<2 x i8> [[START]], <2 x i8> [[D]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { <2 x i8>, <2 x i1> } [[R]], 1 +; CHECK-NEXT: call void @use.vec(<2 x i1> [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %d = sub nsw <2 x i8> %end, %start + %r = call { <2 x i8>, <2 x i1> } @llvm.sadd.with.overflow.v2i8(<2 x i8> %start, <2 x i8> %d) + %ov = extractvalue { <2 x i8>, <2 x i1> } %r, 1 + call void @use.vec(<2 x i1> %ov) + ret void +} + +; Negative: the coefficients of %x add up to 4 * 2^61 = 2^63, which does not fit +; the 64-bit coefficients, so the decomposition is given up on. +define void @sadd_coefficient_overflow(i64 %x, i64 %y) { +; CHECK-LABEL: define void @sadd_coefficient_overflow( +; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = mul nsw i64 [[X]], 2305843009213693952 +; CHECK-NEXT: [[B:%.*]] = add nsw i64 [[A]], [[A]] +; CHECK-NEXT: [[C:%.*]] = add nsw i64 [[B]], [[A]] +; CHECK-NEXT: [[D:%.*]] = add nsw i64 [[C]], [[A]] +; CHECK-NEXT: [[R:%.*]] = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 [[D]], i64 [[Y]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i64, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %a = mul nsw i64 %x, 2305843009213693952 + %b = add nsw i64 %a, %a + %c = add nsw i64 %b, %a + %d = add nsw i64 %c, %a + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %d, i64 %y) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_umax_not_split(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_umax_not_split( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[START]], i8 [[END]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %m = call i8 @llvm.umax.i8(i8 %end, i8 0) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @slt_coefficient_overflow(i64 %x, i64 %y) { +; CHECK-LABEL: define void @slt_coefficient_overflow( +; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = mul nsw i64 [[X]], 2305843009213693952 +; CHECK-NEXT: [[B:%.*]] = add nsw i64 [[A]], [[A]] +; CHECK-NEXT: [[C:%.*]] = add nsw i64 [[B]], [[A]] +; CHECK-NEXT: [[D:%.*]] = add nsw i64 [[C]], [[A]] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[D]], [[Y]] +; CHECK-NEXT: call void @use(i1 [[CMP]]) +; CHECK-NEXT: ret void +; +entry: + %a = mul nsw i64 %x, 2305843009213693952 + %b = add nsw i64 %a, %a + %c = add nsw i64 %b, %a + %d = add nsw i64 %c, %a + %cmp = icmp slt i64 %d, %y + call void @use(i1 %cmp) + ret void +} + +define void @sadd_smax_three_levels(i8 %start, i8 %end) { +; CHECK-LABEL: define void @sadd_smax_three_levels( +; CHECK-SAME: i8 [[START:%.*]], i8 [[END:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[NONNEG:%.*]] = icmp sge i8 [[START]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[NONNEG]]) +; CHECK-NEXT: [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[END]], i8 0) +; CHECK-NEXT: [[M2:%.*]] = call i8 @llvm.smax.i8(i8 [[M1]], i8 1) +; CHECK-NEXT: [[M3:%.*]] = call i8 @llvm.smax.i8(i8 [[M2]], i8 2) +; CHECK-NEXT: [[R:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[START]], i8 [[M3]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i8, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %nonneg = icmp sge i8 %start, 0 + call void @llvm.assume(i1 %nonneg) + %m1 = call i8 @llvm.smax.i8(i8 %end, i8 0) + %m2 = call i8 @llvm.smax.i8(i8 %m1, i8 1) + %m3 = call i8 @llvm.smax.i8(i8 %m2, i8 2) + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %start, i8 %m3) + %ov = extractvalue { i8, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_offset_overflow(i64 %x, i64 %y) { +; CHECK-LABEL: define void @sadd_offset_overflow( +; CHECK-SAME: i64 [[X:%.*]], i64 [[Y:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = add nsw i64 [[X]], 9223372036854775806 +; CHECK-NEXT: [[B:%.*]] = add nsw i64 [[Y]], 5 +; CHECK-NEXT: [[R:%.*]] = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 [[A]], i64 [[B]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i64, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %a = add nsw i64 %x, 9223372036854775806 + %b = add nsw i64 %y, 5 + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %a, i64 %b) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smax_substitute_overflow(i64 %x, i64 %z, i64 %y) { +; CHECK-LABEL: define void @sadd_smax_substitute_overflow( +; CHECK-SAME: i64 [[X:%.*]], i64 [[Z:%.*]], i64 [[Y:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = mul nsw i64 [[X]], 1099511627776 +; CHECK-NEXT: [[M:%.*]] = call i64 @llvm.smax.i64(i64 [[A]], i64 [[Z]]) +; CHECK-NEXT: [[D:%.*]] = mul nsw i64 [[M]], 1073741824 +; CHECK-NEXT: [[R:%.*]] = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 [[D]], i64 [[Y]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i64, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %a = mul nsw i64 %x, 1099511627776 + %m = call i64 @llvm.smax.i64(i64 %a, i64 %z) + %d = mul nsw i64 %m, 1073741824 + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %d, i64 %y) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +declare void @use.vec(<2 x i1>) _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
