https://github.com/jroelofs updated https://github.com/llvm/llvm-project/pull/235159
>From 3294c71414f6dac5c31b70fffde33ba00d5af711 Mon Sep 17 00:00:00 2001 From: Jon Roelofs <[email protected]> Date: Thu, 5 Nov 2026 13:39:08 -0800 Subject: [PATCH 1/2] [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 | 62 +++++++++++++++++++ 3 files changed, 84 insertions(+), 6 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index dfb16aaed655b7..bbf0c828a0dbc2 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -419,6 +419,10 @@ class ConstraintInfo { /// system implies it or because ValueTracking can prove it. bool isKnownPositive(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(Value *V); + /// Returns true if \p V is known to be negative, false if \p V is known to be /// nonnegative, or std::nullopt if neither the signed system nor /// ValueTracking can prove it. @@ -628,6 +632,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)) @@ -1165,6 +1177,13 @@ bool ConstraintInfo::isKnownPositive(Value *V) { doesHold(CmpInst::ICMP_SGT, V, ConstantInt::get(V->getType(), 0)); } +bool ConstraintInfo::isKnownNonPositive(Value *V) { + if (auto *CI = dyn_cast<ConstantInt>(V)) + return CI->getValue().isNonPositive(); + return ::isKnownNegative(V, DL) || + doesHold(CmpInst::ICMP_SLE, V, ConstantInt::get(V->getType(), 0)); +} + std::optional<bool> ConstraintInfo::getKnownSign(Value *V) { KnownBits Known = computeKnownBits(V, DL); if (Known.isNonNegative()) 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 4194797fa5ea05..df7d867003d68c 100644 --- a/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll +++ b/llvm/test/Transforms/ConstraintElimination/sadd-with-overflow.ll @@ -318,3 +318,65 @@ then: else: ret i8 0 } + +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_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 +} >From 53fccf605baa227d289dcb3f1e7411b160552088 Mon Sep 17 00:00:00 2001 From: Jon Roelofs <[email protected]> Date: Mon, 9 Nov 2026 11:06:56 -0800 Subject: [PATCH 2/2] cache known bits for opposite signs check --- .../Scalar/ConstraintElimination.cpp | 23 +++++++++++-------- 1 file changed, 13 insertions(+), 10 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index bbf0c828a0dbc2..482a86cecce488 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -413,7 +413,7 @@ class ConstraintInfo { /// Returns true if \p V is known to be non-negative, either because the /// signed system implies it or because ValueTracking can prove it. - bool isKnownNonNegative(Value *V); + bool isKnownNonNegative(const WithCache<const Value *> &V); /// Returns true if \p V is known to be positive, either because the signed /// system implies it or because ValueTracking can prove it. @@ -421,7 +421,7 @@ class ConstraintInfo { /// 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(Value *V); + bool isKnownNonPositive(const WithCache<const Value *> &V); /// Returns true if \p V is known to be negative, false if \p V is known to be /// nonnegative, or std::nullopt if neither the signed system nor @@ -634,9 +634,10 @@ static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, // A signed sum of operands with opposite signs cannot wrap. if (Signed && Opcode == Instruction::Add) { - if (Info.isKnownNonNegative(Op0) && Info.isKnownNonPositive(Op1)) + WithCache<const Value *> KnownOp0{Op0}, KnownOp1{Op1}; + if (Info.isKnownNonNegative(KnownOp0) && Info.isKnownNonPositive(KnownOp1)) return true; - if (Info.isKnownNonPositive(Op0) && Info.isKnownNonNegative(Op1)) + if (Info.isKnownNonPositive(KnownOp0) && Info.isKnownNonNegative(KnownOp1)) return true; } @@ -1163,11 +1164,12 @@ bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, Value *B) { .value_or(false); } -bool ConstraintInfo::isKnownNonNegative(Value *V) { - if (auto *CI = dyn_cast<ConstantInt>(V)) +bool ConstraintInfo::isKnownNonNegative(const WithCache<const Value *> &V) { + if (auto *CI = dyn_cast<ConstantInt>(V.getValue())) return !CI->isNegative(); return ::isKnownNonNegative(V, DL) || - doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0)); + doesHold(CmpInst::ICMP_SGE, const_cast<Value *>(V.getValue()), + ConstantInt::get(V->getType(), 0)); } bool ConstraintInfo::isKnownPositive(Value *V) { @@ -1177,11 +1179,12 @@ bool ConstraintInfo::isKnownPositive(Value *V) { doesHold(CmpInst::ICMP_SGT, V, ConstantInt::get(V->getType(), 0)); } -bool ConstraintInfo::isKnownNonPositive(Value *V) { - if (auto *CI = dyn_cast<ConstantInt>(V)) +bool ConstraintInfo::isKnownNonPositive(const WithCache<const 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)); + doesHold(CmpInst::ICMP_SLE, const_cast<Value *>(V.getValue()), + ConstantInt::get(V->getType(), 0)); } std::optional<bool> ConstraintInfo::getKnownSign(Value *V) { _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
