From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id ADCDF385EC54; Sat, 17 Jul 2021 02:31:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ADCDF385EC54 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 r12-2381] Add wi_fold_in_parts. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 87277b6a04486b606761b86dbcfbc9a4b6871f4c X-Git-Newrev: 704e8a825c78b9a8424c291509413bbb48e602c7 Message-Id: <20210717023105.ADCDF385EC54@sourceware.org> Date: Sat, 17 Jul 2021 02:31:05 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 17 Jul 2021 02:31:05 -0000 https://gcc.gnu.org/g:704e8a825c78b9a8424c291509413bbb48e602c7 commit r12-2381-g704e8a825c78b9a8424c291509413bbb48e602c7 Author: Andrew MacLeod Date: Fri Jul 16 11:42:14 2021 -0400 Add wi_fold_in_parts. range-ops uses wi_fold to individually fold subranges one at a time and then combined them. This patch first calls wi_fold_in_parts which checks if one of the subranges is small, and if so, further splits that subrange into constants. gcc/ PR tree-optimization/96542 * range-op.cc (range_operator::wi_fold_in_parts): New. (range_operator::fold_range): Call wi_fold_in_parts. (operator_lshift::wi_fold): Fix broken lshift by [0,0]. * range-op.h (wi_fold_in_parts): Add prototype. gcc/testsuite * gcc.dg/pr96542.c: New. Diff: --- gcc/range-op.cc | 75 +++++++++++++++++++++++++++++++++++++++--- gcc/range-op.h | 6 ++++ gcc/testsuite/gcc.dg/pr96542.c | 27 +++++++++++++++ 3 files changed, 103 insertions(+), 5 deletions(-) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 08000465fd9..e0be51dbc90 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -133,6 +133,65 @@ range_operator::wi_fold (irange &r, tree type, r.set_varying (type); } +// 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] + +void +range_operator::wi_fold_in_parts (irange &r, tree type, + const wide_int &lh_lb, + const wide_int &lh_ub, + const wide_int &rh_lb, + const wide_int &rh_ub) const +{ + wi::overflow_type ov_rh, ov_lh; + int_range_max tmp; + wide_int rh_range = wi::sub (rh_ub, rh_lb, TYPE_SIGN (type), &ov_rh); + wide_int lh_range = wi::sub (lh_ub, lh_lb, TYPE_SIGN (type), &ov_lh); + signop sign = TYPE_SIGN (type);; + // If there are 2, 3, or 4 values in the RH range, do them separately. + // Call wi_fold_in_parts to check the RH side. + if (wi::gt_p (rh_range, 0, sign) && wi::lt_p (rh_range, 4, sign) + && ov_rh == wi::OVF_NONE) + { + wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb); + if (wi::gt_p (rh_range, 1, sign)) + { + wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1); + r.union_ (tmp); + if (wi::eq_p (rh_range, 3)) + { + wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2); + r.union_ (tmp); + } + } + wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub); + r.union_ (tmp); + } + // Otherise check for 2, 3, or 4 values in the LH range and split them up. + // The RH side has been checked, so no recursion needed. + else if (wi::gt_p (lh_range, 0, sign) && wi::lt_p (lh_range, 4, sign) + && ov_lh == wi::OVF_NONE) + { + wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub); + if (wi::gt_p (lh_range, 1, sign)) + { + wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub); + r.union_ (tmp); + if (wi::eq_p (lh_range, 3)) + { + wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub); + r.union_ (tmp); + } + } + wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub); + r.union_ (tmp); + } + // Otherwise just call wi_fold. + else + wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); +} + // The default for fold is to break all ranges into sub-ranges and // invoke the wi_fold method on each sub-range pair. @@ -152,8 +211,8 @@ range_operator::fold_range (irange &r, tree type, // If both ranges are single pairs, fold directly into the result range. if (num_lh == 1 && num_rh == 1) { - wi_fold (r, type, lh.lower_bound (0), lh.upper_bound (0), - rh.lower_bound (0), rh.upper_bound (0)); + wi_fold_in_parts (r, type, lh.lower_bound (0), lh.upper_bound (0), + rh.lower_bound (0), rh.upper_bound (0)); op1_op2_relation_effect (r, type, lh, rh, rel); return true; } @@ -167,7 +226,7 @@ range_operator::fold_range (irange &r, tree type, wide_int lh_ub = lh.upper_bound (x); wide_int rh_lb = rh.lower_bound (y); wide_int rh_ub = rh.upper_bound (y); - wi_fold (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub); + wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub); r.union_ (tmp); if (r.varying_p ()) { @@ -1915,8 +1974,14 @@ operator_lshift::wi_fold (irange &r, tree type, int bound_shift = overflow_pos - rh_ub.to_shwi (); // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can // overflow. However, for that to happen, rh.max needs to be zero, - // which means rh is a singleton range of zero, which means it - // should be handled by the lshift fold_range above. + // which means rh is a singleton range of zero, which means we simply return + // [lh_lb, lh_ub] as the range. + if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0)) + { + r = int_range<2> (type, lh_lb, lh_ub); + return; + } + wide_int bound = wi::set_bit_in_zero (bound_shift, prec); wide_int complement = ~(bound - 1); wide_int low_bound, high_bound; diff --git a/gcc/range-op.h b/gcc/range-op.h index 2b5db64bb98..17be9e00c08 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -97,6 +97,12 @@ protected: const irange &op1_range, const irange &op2_range, relation_kind rel) const; + // Called by fold range to split small subranges into parts. + void wi_fold_in_parts (irange &r, tree type, + const wide_int &lh_lb, + const wide_int &lh_ub, + const wide_int &rh_lb, + const wide_int &rh_ub) const; }; extern range_operator *range_op_handler (enum tree_code code, tree type); diff --git a/gcc/testsuite/gcc.dg/pr96542.c b/gcc/testsuite/gcc.dg/pr96542.c new file mode 100644 index 00000000000..5014f2acad8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr96542.c @@ -0,0 +1,27 @@ +/* { dg-do compile} */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + + +unsigned char +foo (unsigned int x) +{ + _Bool y = x; + return (((unsigned char) ~0) >> y) * 2; +} + +unsigned char +bar (unsigned int x) +{ + return (((unsigned char) ~0) >> (_Bool) x) * 2; +} + +unsigned +baz (unsigned int x) +{ + if (x >= 4) return 32; + return (-1U >> x) * 16; +} + +/* { dg-final { scan-tree-dump-times "254" 2 "evrp" } } */ +/* { dg-final { scan-tree-dump "= PHI <32.*, 4294967280" "evrp" } } */ +