PR tree-optimization/127101
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.
Bootstrapped and regression-tested on x86_64 and Aarch64 with no new failures.
Signed-off-by: Naveen <[email protected]>
---
gcc/gimple-range-gori.cc | 21 ++++++-----
gcc/range-op-mixed.h | 4 +++
gcc/range-op.cc | 44 ++++++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/pr127101.c | 44 ++++++++++++++++++++++++
4 files changed, 105 insertions(+), 8 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr127101.c
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index d34c2b79a7c..c68b9185d1a 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -1108,8 +1108,10 @@ gori_compute::refine_using_relation (tree op1, vrange
&op1_range,
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 +1119,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);
}
@@ -1140,8 +1143,9 @@ gori_compute::refine_using_relation (tree op1, vrange
&op1_range,
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 +1153,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 0e97fb11688..f292d1b2440 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 76c52bf897e..8004b6c1d8d 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1716,6 +1716,50 @@ 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.
+
+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))
+ 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 00000000000..fa7416423e1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr127101.c
@@ -0,0 +1,44 @@
+/* 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;
+}
+
--
2.34.1
