https://github.com/jroelofs updated https://github.com/llvm/llvm-project/pull/235160
>From fe3522682ab52fa8e7046044162e97bc9be1c070 Mon Sep 17 00:00:00 2001 From: Jon Roelofs <[email protected]> Date: Thu, 5 Nov 2026 13:39:08 -0800 Subject: [PATCH] [ConstraintElim] A signed sum of operands with opposite signs cannot wrap If one operand is known non-negative and the other non-positive, the signed sum is between them, so it cannot overflow. https://alive2.llvm.org/ce/z/ZF5Yqr --- .../Scalar/ConstraintElimination.cpp | 19 ++++ .../ConstraintElimination/add-nsw.ll | 9 +- .../sadd-with-overflow.ll | 99 ++++++++++++++++++- 3 files changed, 119 insertions(+), 8 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index ecda1676aa35b0..029e62468cd2f6 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -450,6 +450,10 @@ class ConstraintInfo { /// system implies it or because ValueTracking can prove it. bool isKnownPositive(const WithCache<Value *> &V); + /// Returns true if \p V is known to be non-positive, either because the + /// signed system implies it or because ValueTracking can prove it. + bool isKnownNonPositive(const WithCache<Value *> &V); + void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn, unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack); @@ -776,6 +780,14 @@ static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, return true; } + // A signed sum of operands with opposite signs cannot wrap. + if (Signed && Opcode == Instruction::Add) { + if (Info.isKnownNonNegative(Op0) && Info.isKnownNonPositive(Op1)) + return true; + if (Info.isKnownNonPositive(Op0) && Info.isKnownNonNegative(Op1)) + return true; + } + if (!Signed && (NoWrapFlags & OBO::NoSignedWrap) && (Opcode == Instruction::Shl || Info.isKnownNonNegative(Op1)) && Info.isKnownNonNegative(Op0)) @@ -1320,6 +1332,13 @@ bool ConstraintInfo::isKnownNegative(const WithCache<Value *> &V) { doesHold(CmpInst::ICMP_SLT, V, ConstantInt::get(V->getType(), 0)); } +bool ConstraintInfo::isKnownNonPositive(const WithCache<Value *> &V) { + if (auto *CI = dyn_cast<ConstantInt>(V.getValue())) + return CI->getValue().isNonPositive(); + return ::isKnownNegative(V, DL) || + doesHold(CmpInst::ICMP_SLE, V, ConstantInt::get(V->getType(), 0)); +} + bool ConstraintInfo::isKnownPositive(const WithCache<Value *> &V) { if (auto *CI = dyn_cast<ConstantInt>(V.getValue())) return CI->getValue().isStrictlyPositive(); diff --git a/llvm/test/Transforms/ConstraintElimination/add-nsw.ll b/llvm/test/Transforms/ConstraintElimination/add-nsw.ll index 07ad9a51f1912d..757ed12e167308 100644 --- a/llvm/test/Transforms/ConstraintElimination/add-nsw.ll +++ b/llvm/test/Transforms/ConstraintElimination/add-nsw.ll @@ -978,8 +978,7 @@ define i1 @add_non_positive_slt(i64 %x, i64 %y, i64 %b) { ; CHECK-NEXT: [[C:%.*]] = icmp slt i64 [[X]], [[B:%.*]] ; CHECK-NEXT: call void @llvm.assume(i1 [[C]]) ; CHECK-NEXT: [[SUB:%.*]] = add i64 [[X]], [[Y]] -; CHECK-NEXT: [[T:%.*]] = icmp slt i64 [[SUB]], [[B]] -; CHECK-NEXT: ret i1 [[T]] +; CHECK-NEXT: ret i1 true ; %x.non.neg = icmp sge i64 %x, 0 call void @llvm.assume(i1 %x.non.neg) @@ -1001,8 +1000,7 @@ define i1 @add_non_positive_slt_commuted(i64 %x, i64 %y, i64 %b) { ; CHECK-NEXT: [[C:%.*]] = icmp slt i64 [[X]], [[B:%.*]] ; CHECK-NEXT: call void @llvm.assume(i1 [[C]]) ; CHECK-NEXT: [[SUB:%.*]] = add i64 [[Y]], [[X]] -; CHECK-NEXT: [[T:%.*]] = icmp slt i64 [[SUB]], [[B]] -; CHECK-NEXT: ret i1 [[T]] +; CHECK-NEXT: ret i1 true ; %x.non.neg = icmp sge i64 %x, 0 call void @llvm.assume(i1 %x.non.neg) @@ -1026,8 +1024,7 @@ define i1 @add_non_positive_slt_hoisted(i64 %x, i64 %y, i64 %b) { ; CHECK-NEXT: [[SUB:%.*]] = add i64 [[X]], [[Y]] ; CHECK-NEXT: br i1 [[AND_2]], label [[IF_END:%.*]], label [[EXIT:%.*]] ; CHECK: if.end: -; CHECK-NEXT: [[T:%.*]] = icmp slt i64 [[SUB]], [[B]] -; CHECK-NEXT: ret i1 [[T]] +; CHECK-NEXT: ret i1 true ; CHECK: exit: ; CHECK-NEXT: ret i1 false ; diff --git a/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll b/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll index e28610764f1b01..08dee4ca907156 100644 --- a/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll +++ b/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll @@ -577,6 +577,85 @@ entry: ret void } +define void @sadd_opposite_signs(i64 %v, i64 %s) { +; CHECK-LABEL: define void @sadd_opposite_signs( +; CHECK-SAME: i64 [[V:%.*]], i64 [[S:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = lshr i64 [[V]], 1 +; CHECK-NEXT: [[C:%.*]] = icmp sge i64 [[S]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[C]]) +; CHECK-NEXT: [[N:%.*]] = xor i64 [[S]], -1 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %a = lshr i64 %v, 1 + %c = icmp sge i64 %s, 0 + call void @llvm.assume(i1 %c) + %n = xor i64 %s, -1 + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %a, i64 %n) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_same_signs(i64 %v, i64 %s) { +; CHECK-LABEL: define void @sadd_same_signs( +; CHECK-SAME: i64 [[V:%.*]], i64 [[S:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = lshr i64 [[V]], 1 +; CHECK-NEXT: [[C:%.*]] = icmp sge i64 [[S]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[C]]) +; CHECK-NEXT: [[R:%.*]] = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 [[A]], i64 [[S]]) +; CHECK-NEXT: [[OV:%.*]] = extractvalue { i64, i1 } [[R]], 1 +; CHECK-NEXT: call void @use(i1 [[OV]]) +; CHECK-NEXT: ret void +; +entry: + %a = lshr i64 %v, 1 + %c = icmp sge i64 %s, 0 + call void @llvm.assume(i1 %c) + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %a, i64 %s) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + ret void +} + +define void @sadd_smax_clamp_samesign(i64 %v, i64 %start) { +; CHECK-LABEL: define void @sadd_smax_clamp_samesign( +; CHECK-SAME: i64 [[V:%.*]], i64 [[START:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[END:%.*]] = lshr i64 [[V]], 1 +; CHECK-NEXT: [[C:%.*]] = icmp samesign uge i64 [[END]], [[START]] +; CHECK-NEXT: call void @llvm.assume(i1 [[C]]) +; CHECK-NEXT: [[NOTSTART:%.*]] = xor i64 [[START]], -1 +; CHECK-NEXT: [[X:%.*]] = add i64 [[END]], [[NOTSTART]] +; CHECK-NEXT: [[M:%.*]] = call i64 @llvm.smax.i64(i64 [[X]], i64 0) +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[START]], [[M]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[GT:%.*]] = icmp slt i64 [[END]], [[TMP0]] +; CHECK-NEXT: call void @use(i1 [[GT]]) +; CHECK-NEXT: ret void +; +entry: + %end = lshr i64 %v, 1 + %c = icmp samesign uge i64 %end, %start + call void @llvm.assume(i1 %c) + %notstart = xor i64 %start, -1 + %x = add i64 %end, %notstart + %m = call i64 @llvm.smax.i64(i64 %x, i64 0) + %r = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %start, i64 %m) + %ov = extractvalue { i64, i1 } %r, 1 + call void @use(i1 %ov) + %new = extractvalue { i64, i1 } %r, 0 + %lt = icmp slt i64 %new, %start + call void @use(i1 %lt) + %gt = icmp slt i64 %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:%.*]]) { @@ -701,6 +780,24 @@ entry: ret void } +define void @sadd_opposite_signs_known_negative(i8 %v, i8 %w) { +; CHECK-LABEL: define void @sadd_opposite_signs_known_negative( +; CHECK-SAME: i8 [[V:%.*]], i8 [[W:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[A:%.*]] = lshr i8 [[V]], 1 +; CHECK-NEXT: [[B:%.*]] = or i8 [[W]], -128 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: ret void +; +entry: + %a = lshr i8 %v, 1 + %b = or i8 %w, -128 + %r = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 %a, i8 %b) + %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:%.*]]) { @@ -719,8 +816,6 @@ entry: 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:%.*]]) { _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
