From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 9FF283860776; Thu, 29 Sep 2022 22:34:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9FF283860776 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1664490899; bh=PAuhU0DEac8UfSHeb+3QmN6A0T3Pe06Q+Ix28fj3xIo=; h=From:To:Subject:Date:From; b=q1i1UKFqlD3DtyeaEVZp8gPrQm39B+cace6sZQnm7lqRnw4o6BJOe9t4rJTSsq/Ex zwir9ZJhUDMaEvazOZ+ncae059lU/o6UULcmPQfer28qf9KLeTxIkCIWm59nMo5QVH dsnCt+a1SK+dPW6VTP2D7RB18RHNmuI1rMENb0WQ= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2975] Process unsigned overflow relations for plus and minus is range-ops. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 67166c9ec35d58efd0225b74730983aa480a88f1 X-Git-Newrev: 7ea258a13a115e9e73d60f59369d16892ed07435 Message-Id: <20220929223459.9FF283860776@sourceware.org> Date: Thu, 29 Sep 2022 22:34:59 +0000 (GMT) List-Id: https://gcc.gnu.org/g:7ea258a13a115e9e73d60f59369d16892ed07435 commit r13-2975-g7ea258a13a115e9e73d60f59369d16892ed07435 Author: Andrew MacLeod Date: Tue Aug 23 10:17:02 2022 -0400 Process unsigned overflow relations for plus and minus is range-ops. If a relation is available, calculate overflow and normal ranges. Then apply as appropriate. gcc/ * range-op.cc (plus_minus_ranges): New. (adjust_op1_for_overflow): New. (operator_plus::op1_range): Use new adjustment. (operator_plus::op2_range): Ditto. (operator_minus::op1_range): Ditto. * value-relation.h (relation_lt_le_gt_ge_p): New. gcc/testsuite/ * gcc.dg/tree-ssa/pr79095.c: Test evrp pass rather than vrp1. Diff: --- gcc/range-op.cc | 121 ++++++++++++++++++++++++++++++-- gcc/testsuite/gcc.dg/tree-ssa/pr79095.c | 6 +- gcc/value-relation.h | 2 + 3 files changed, 121 insertions(+), 8 deletions(-) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 6b75c365147..7ef980315b6 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1305,22 +1305,123 @@ operator_plus::wi_fold (irange &r, tree type, value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); } +// Given addition or subtraction, determine the possible NORMAL ranges and +// OVERFLOW ranges given an OFFSET range. ADD_P is true for addition. +// Return the relation that exists between the LHS and OP1 in order for the +// NORMAL range to apply. +// a return value of VREL_VARYING means no ranges were applicable. + +static relation_kind +plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset, + bool add_p) +{ + relation_kind kind = VREL_VARYING; + // For now, only deal with constant adds. This could be extended to ranges + // when someone is so motivated. + if (!offset.singleton_p () || offset.zero_p ()) + return kind; + + // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2 + wide_int off = offset.lower_bound (); + if (wi::neg_p (off, SIGNED)) + { + add_p = !add_p; + off = wi::neg (off); + } + + wi::overflow_type ov; + tree type = offset.type (); + unsigned prec = TYPE_PRECISION (type); + wide_int ub; + wide_int lb; + // calculate the normal range and relation for the operation. + if (add_p) + { + // [ 0 , INF - OFF] + lb = wi::zero (prec); + ub = wi::sub (wi::to_wide (vrp_val_max (type)), off, UNSIGNED, &ov); + kind = VREL_GT; + } + else + { + // [ OFF, INF ] + lb = off; + ub = wi::to_wide (vrp_val_max (type)); + kind = VREL_LT; + } + int_range<2> normal_range (type, lb, ub); + int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE); + + r_ov = ov_range; + r_normal = normal_range; + return kind; +} + +// Once op1 has been calculated by operator_plus or operator_minus, check +// to see if the relation passed causes any part of the calculation to +// be not possible. ie +// a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF] +// and that further refines a_2 to [0, 0]. +// R is the value of op1, OP2 is the offset being added/subtracted, REL is the +// relation between LHS relatoin OP1 and ADD_P is true for PLUS, false for +// MINUS. IF any adjustment can be made, R will reflect it. + +static void +adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel, + bool add_p) +{ + tree type = r.type (); + // Check for unsigned overflow and calculate the overflow part. + signop s = TYPE_SIGN (type); + if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED) + return; + + // Only work with <, <=, >, >= relations. + if (!relation_lt_le_gt_ge_p (rel)) + return; + + // Get the ranges for this offset. + int_range_max normal, overflow; + relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p); + + // VREL_VARYING means there are no adjustments. + if (k == VREL_VARYING) + return; + + // If the relations match use the normal range, otherwise use overflow range. + if (relation_intersect (k, rel) == k) + r.intersect (normal); + else + r.intersect (overflow); + return; +} + bool operator_plus::op1_range (irange &r, tree type, const irange &lhs, const irange &op2, - relation_kind rel ATTRIBUTE_UNUSED) const + relation_kind rel) const { - return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op2); + if (lhs.undefined_p ()) + return false; + // Start with the default operation. + range_op_handler minus (MINUS_EXPR, type); + if (!minus) + return false; + bool res = minus.fold_range (r, type, lhs, op2); + // Check for a relation refinement. + if (res) + adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */); + return res; } bool operator_plus::op2_range (irange &r, tree type, const irange &lhs, const irange &op1, - relation_kind rel ATTRIBUTE_UNUSED) const + relation_kind rel) const { - return range_op_handler (MINUS_EXPR, type).fold_range (r, type, lhs, op1); + return op1_range (r, type, lhs, op1, rel); } @@ -1472,7 +1573,17 @@ operator_minus::op1_range (irange &r, tree type, const irange &op2, relation_kind rel ATTRIBUTE_UNUSED) const { - return range_op_handler (PLUS_EXPR, type).fold_range (r, type, lhs, op2); + if (lhs.undefined_p ()) + return false; + // Start with the default operation. + range_op_handler minus (PLUS_EXPR, type); + if (!minus) + return false; + bool res = minus.fold_range (r, type, lhs, op2); + if (res) + adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */); + return res; + } bool diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c index f635fcafe4f..b1751877756 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79095.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-evrp" } */ extern void arf (unsigned x, unsigned y); extern void baz (unsigned x, unsigned y); @@ -429,8 +429,8 @@ f4nro (unsigned a, unsigned b) } /* All calls to baz should still reference a & b as arguments. */ -/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "baz \\(a_\[0-9\]+\\(D\\), b_\[0-9\]+\\)" 32 "evrp"} } */ /* All calls to arf should have constant arguments. */ -/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "arf \\(\[0-9\]+, \[0-9\]+\\)" 32 "evrp"} } */ diff --git a/gcc/value-relation.h b/gcc/value-relation.h index f3b18ac62ef..e1347ea8ad8 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -78,6 +78,8 @@ relation_kind relation_union (relation_kind r1, relation_kind r2); relation_kind relation_intersect (relation_kind r1, relation_kind r2); relation_kind relation_negate (relation_kind r); relation_kind relation_swap (relation_kind r); +inline bool relation_lt_le_gt_ge_p (relation_kind r) + { return (r >= VREL_LT && r <= VREL_GE); } void print_relation (FILE *f, relation_kind rel); class relation_oracle