https://gcc.gnu.org/g:24e96a7911669fc81febcf887b443c8aef15a4cc
commit r17-5963-g24e96a7911669fc81febcf887b443c8aef15a4cc Author: Naveen <[email protected]> Date: Wed Nov 4 20:09:17 2026 -0800 tree-optimization: tighten unsigned-add range via no-overflow relation [PR127101] When lhs = op1 + op2 and the relation lhs >= op1 is known, no unsigned overflow can have occurred and so lhs >= op2. If op2's lower bound is positive this lets us tighten the computed range of lhs to [op2_lb, TYPE_MAX]. The symmetric case (lhs >= op2, op1_lb > 0) is handled analogously. Add operator_plus::fold_range to apply this intersection and thread the lhs-op1 / lhs-op2 relation_trio through the four fold_range call-sites in gori_compute::refine_using_relation so the tightening actually fires during GORI refinement. gcc/ChangeLog: PR tree-optimization/127101 * range-op-mixed.h (operator_plus): Add using declaration for range_operator::fold_range; declare fold_range override. * range-op.cc (operator_plus::fold_range): New. * gimple-range-gori.cc (gori_compute::refine_using_relation): Pass lhs_op1/lhs_op2 relation to fold_range call-sites. gcc/testsuite/ChangeLog: PR tree-optimization/127101 * gcc.dg/tree-ssa/pr127101.c: New test. Signed-off-by: Naveen <[email protected]> Diff: --- gcc/gimple-range-gori.cc | 27 ++++++++++++----- gcc/range-op-mixed.h | 4 +++ gcc/range-op.cc | 52 ++++++++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr127101.c | 46 ++++++++++++++++++++++++++++ 4 files changed, 121 insertions(+), 8 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 7d62cb184988..96c7d83f0814 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1105,11 +1105,16 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, op1_def_p ? op1_range : op2_range, other_op, relation_trio::lhs_op1 (k))) return false; + // Note: K arrives as an op1/op2 relation, and because of + // the definition chain requirement here, it is also an LHS relation on the + // defining statement, which is how it is passed to the range operators below. if (op1_def_p) { change |= op2_range.intersect (new_result); - // Recalculate op2. - if (op_handler.fold_range (new_result, type, op2_range, other_op)) + // Recalculate the LHS passing the lhs-op1 relation so that + // operator_plus::fold_range can tighten the no-overflow range. + if (op_handler.fold_range (new_result, type, op2_range, other_op, + relation_trio::lhs_op1 (k))) { change |= op1_range.intersect (new_result); } @@ -1117,8 +1122,9 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, else { change |= op1_range.intersect (new_result); - // Recalculate op1. - if (op_handler.fold_range (new_result, type, op1_range, other_op)) + // Recalculate the LHS passing the lhs-op1 relation. + if (op_handler.fold_range (new_result, type, op1_range, other_op, + relation_trio::lhs_op1 (k))) { change |= op2_range.intersect (new_result); } @@ -1137,11 +1143,15 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, op1_def_p ? op1_range : op2_range, other_op, relation_trio::lhs_op2 (k))) return false; + // Note: K arrives as an op1/op2 relation, and because of + // the definition chain requirement here, it is also an LHS relation on the + // defining statement, which is how it is passed to the range operators below. if (op1_def_p) { change |= op2_range.intersect (new_result); - // Recalculate op1. - if (op_handler.fold_range (new_result, type, other_op, op2_range)) + // Recalculate the LHS passing the lhs-op2 relation. + if (op_handler.fold_range (new_result, type, other_op, op2_range, + relation_trio::lhs_op2 (k))) { change |= op1_range.intersect (new_result); } @@ -1149,8 +1159,9 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, else { change |= op1_range.intersect (new_result); - // Recalculate op2. - if (op_handler.fold_range (new_result, type, other_op, op1_range)) + // Recalculate the LHS passing the lhs-op2 relation. + if (op_handler.fold_range (new_result, type, other_op, op1_range, + relation_trio::lhs_op2 (k))) { change |= op2_range.intersect (new_result); } diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h index a294958ce8ff..ef9c7f2d3c86 100644 --- a/gcc/range-op-mixed.h +++ b/gcc/range-op-mixed.h @@ -573,6 +573,10 @@ class operator_plus : public range_operator public: using range_operator::op1_range; using range_operator::op2_range; + using range_operator::fold_range; + bool fold_range (irange &r, tree type, + const irange &lh, const irange &rh, + relation_trio = TRIO_VARYING) const final override; using range_operator::lhs_op1_relation; using range_operator::lhs_op2_relation; using range_operator::update_bitmask; diff --git a/gcc/range-op.cc b/gcc/range-op.cc index beecea6a8e70..d08193ce41da 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1716,6 +1716,58 @@ operator_plus::update_bitmask (irange &r, const irange &lh, update_known_bitmask (r, PLUS_EXPR, lh, rh); } +// For unsigned wrapping addition lhs = op1 + op2, if the relation +// lhs >= op1 (or lhs > op1) holds and op2 has a positive lower bound, +// the addition could not have wrapped and therefore lhs >= op2_lb >= 1. +// Tighten the computed range accordingly. The symmetric case (lhs >= op2 +// with op1_lb > 0) is handled for completeness. +// +// Note: this override is only applicable during GORI recomputations and +// refinements, where the LHS is an already-known value being intersected +// against. Under normal fold_range use the LHS is being freshly computed, +// and an LHS/operand relation would be circular. + +bool +operator_plus::fold_range (irange &r, tree type, + const irange &lh, const irange &rh, + relation_trio rel) const +{ + if (!range_operator::fold_range (r, type, lh, rh, rel)) + return false; + + if (r.undefined_p () + || !TYPE_UNSIGNED (type) + || !TYPE_OVERFLOW_WRAPS (type) + || (rel.lhs_op1 () == VREL_VARYING && rel.lhs_op2 () == VREL_VARYING)) + return true; + + const unsigned prec = TYPE_PRECISION (type); + const wide_int zero = wi::zero (prec); + const wide_int max = irange_val_max (type); + + // lhs >= op1 with op2 > 0 => no unsigned wrap => lhs >= op2_lb. + relation_kind lhs_op1 = rel.lhs_op1 (); + if ((lhs_op1 == VREL_GE || lhs_op1 == VREL_GT) + && !rh.undefined_p () + && wi::gt_p (rh.lower_bound (), zero, UNSIGNED)) + { + int_range<1> lb (type, rh.lower_bound (), max); + r.intersect (lb); + } + + // lhs >= op2 with op1 > 0 => no unsigned wrap => lhs >= op1_lb. + relation_kind lhs_op2 = rel.lhs_op2 (); + if ((lhs_op2 == VREL_GE || lhs_op2 == VREL_GT) + && !lh.undefined_p () + && wi::gt_p (lh.lower_bound (), zero, UNSIGNED)) + { + int_range<1> lb (type, lh.lower_bound (), max); + r.intersect (lb); + } + + return true; +} + // Check to see if the range of OP2 indicates anything about the relation // between LHS and OP1. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr127101.c b/gcc/testsuite/gcc.dg/tree-ssa/pr127101.c new file mode 100644 index 000000000000..1211da9b1a32 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr127101.c @@ -0,0 +1,46 @@ +/* PR tree-optimization/127101 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* Both functions should reduce to return 1. + Chain of reasoning: + a != 0 => a >= 1 + c != 0 => c >= 1 + l0 = l1 + a, l0 >= l1 => no unsigned overflow => l0 >= a >= 1 + min(l0, c) != 0 [PR127102 pattern] => l0 != 0 (c > 0) + l0 >= 1 => l0 != 0 => 1 */ + +unsigned +f (unsigned l1, unsigned a, unsigned c) +{ + if (a == 0) + return 1; + if (c == 0) + return 1; + unsigned l0 = l1 + a; + if (l0 >= l1) + { + unsigned m = l0 > c ? c : l0; + return m != 0; + } + return 1; +} + +/* m is computed before the overflow check; range must be re-evaluated + in the no-overflow branch context. */ +unsigned +f1 (unsigned l1, unsigned a, unsigned c) +{ + if (a == 0) + return 1; + if (c == 0) + return 1; + unsigned l0 = l1 + a; + unsigned m = l0 > c ? c : l0; + if (l0 >= l1) + return m != 0; + return 1; +} + +/* { dg-final { scan-tree-dump-times "return 1" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "optimized" } } */
