From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id BC169385841A; Tue, 31 Jan 2023 14:58:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BC169385841A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1675177085; bh=yQ9F8FsQI/eC7BlcCuIZ0jiC1YNJ4+utiubj1fTtROo=; h=From:To:Subject:Date:From; b=ZrwZFJpPIbNy1x8SaCgyvfkEQJcJysw7jLZgmFztaBMRjes+U4b6LMQPnbq2g0I28 dHM8UHMPy7KfM4yrcfHQheUraZRxwn13JmoXGEi/BVPo/yzi2DweT7G84pqpZZR5ki iQXI+Dwk3PVr1d6YmfiyCrGL+OG067L87Na+pivA= 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-5578] Utilize op1 == op2 when invoking range-ops folding. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 99fda5de368d84d97eb29a9f03e0d6039068f8b9 X-Git-Newrev: 809d661aff99ae0287baf4a52269425de62381e6 Message-Id: <20230131145805.BC169385841A@sourceware.org> Date: Tue, 31 Jan 2023 14:58:05 +0000 (GMT) List-Id: https://gcc.gnu.org/g:809d661aff99ae0287baf4a52269425de62381e6 commit r13-5578-g809d661aff99ae0287baf4a52269425de62381e6 Author: Andrew MacLeod Date: Tue Jan 17 11:14:41 2023 -0500 Utilize op1 == op2 when invoking range-ops folding. If there exists an equivalence relationship between op1 and op2, any binary operation can be broken into individual operations and unioned if there are sufficently few elements in the set. PR tree-optimization/108359 gcc/ * range-op.cc (range_operator::wi_fold_in_parts_equiv): New. (range_operator::fold_range): If op1 is equivalent to op2 then invoke new fold_in_parts_equiv to operate on sub-components. * range-op.h (wi_fold_in_parts_equiv): New prototype. gcc/testsuite/ * gcc.dg/pr108359.c: New. Diff: --- gcc/range-op.cc | 54 +++++++++++++++++++++++++++++++++++++++++ gcc/range-op.h | 6 +++++ gcc/testsuite/gcc.dg/pr108359.c | 52 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 112 insertions(+) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index ed2dd1eb99c..f7c1e84e0bd 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -160,6 +160,38 @@ range_operator::wi_fold (irange &r, tree type, r.set_varying (type); } +// Call wi_fold when both op1 and op2 are equivalent. Further split small +// subranges into constants. This can provide better precision. +// For x + y, when x == y with a range of [0,4] instead of [0, 8] produce +// [0,0][2, 2][4,4][6, 6][8, 8] +// LIMIT is the maximum number of elements in range allowed before we +// do not processs them individually. + +void +range_operator::wi_fold_in_parts_equiv (irange &r, tree type, + const wide_int &lh_lb, + const wide_int &lh_ub, + unsigned limit) const +{ + int_range_max tmp; + widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)), + widest_int::from (lh_lb, TYPE_SIGN (type))); + // if there are 1 to 8 values in the LH range, split them up. + r.set_undefined (); + if (lh_range >= 0 && lh_range < limit) + { + for (unsigned x = 0; x <= lh_range; x++) + { + wide_int val = lh_lb + x; + wi_fold (tmp, type, val, val, val, val); + r.union_ (tmp); + } + } + // Otherwise just call wi_fold. + else + wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub); +} + // Call wi_fold, except further split small subranges into constants. // This can provide better precision. For something 8 >> [0,1] // Instead of [8, 16], we will produce [8,8][16,16] @@ -234,6 +266,28 @@ range_operator::fold_range (irange &r, tree type, unsigned num_lh = lh.num_pairs (); unsigned num_rh = rh.num_pairs (); + // If op1 and op2 are equivalences, then we don't need a complete cross + // product, just pairs of matching elements. + if (relation_equiv_p (rel) && lh == rh) + { + int_range_max tmp; + r.set_undefined (); + for (unsigned x = 0; x < num_lh; ++x) + { + // If the number of subranges is too high, limit subrange creation. + unsigned limit = (r.num_pairs () > 32) ? 0 : 8; + wide_int lh_lb = lh.lower_bound (x); + wide_int lh_ub = lh.upper_bound (x); + wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit); + r.union_ (tmp); + if (r.varying_p ()) + break; + } + op1_op2_relation_effect (r, type, lh, rh, rel); + update_known_bitmask (r, m_code, lh, rh); + return true; + } + // If both ranges are single pairs, fold directly into the result range. // If the number of subranges grows too high, produce a summary result as the // loop becomes exponential with little benefit. See PR 103821. diff --git a/gcc/range-op.h b/gcc/range-op.h index b7b8a3b9473..f00b747f08a 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -109,6 +109,12 @@ protected: const wide_int &rh_lb, const wide_int &rh_ub) const; + // Called by fold range to split small subranges into parts when op1 == op2 + void wi_fold_in_parts_equiv (irange &r, tree type, + const wide_int &lb, + const wide_int &ub, + unsigned limit) const; + // Tree code of the range operator or ERROR_MARK if unknown. tree_code m_code; }; diff --git a/gcc/testsuite/gcc.dg/pr108359.c b/gcc/testsuite/gcc.dg/pr108359.c new file mode 100644 index 00000000000..7cf04f74132 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr108359.c @@ -0,0 +1,52 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* PR test case. */ +int b = 10; +int c; +char e; +void foo(); +static char(a)(char f, char g) { return f && g == 1 ? 0 : f % g; } +short(d)(short f, short g) { return f * g; } +int main() { + short h; + int i; + unsigned j; + h = d(b && c, 5); + j = h; + i = a(h, 237); + unsigned k = i; + e = i < 0 || k >= 32 ? 0 : i >> k; + if (e) { + c = 0; + foo(); + } +} + + +/* Also Check that small ranges are broken down and optimized properly + This function should never call foo (). */ + +int otherfunc (int x, int z) { + if (x < 1 || x > 6 ) + return 0; + + if (x == z) + { + if (x >> z > 0) + foo (); + if (x * z > 26 && x * z < 35) + foo (); + if (x + z == 5) + foo (); + if ((x + z) % 2 == 1) + foo (); + if (x / z != 1) + foo (); + + } + return 0; +} + + +/* { dg-final { scan-tree-dump-not "foo" "optimized" } } */