public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Andrew Macleod <amacleod@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-4212] Add range intersect with 2 wide-ints. Date: Wed, 6 Oct 2021 14:52:31 +0000 (GMT) [thread overview] Message-ID: <20211006145231.B1118385B83C@sourceware.org> (raw) https://gcc.gnu.org/g:ad451b020a24fe7111e668f8c41a3ba648104569 commit r12-4212-gad451b020a24fe7111e668f8c41a3ba648104569 Author: Andrew MacLeod <amacleod@redhat.com> Date: Mon Oct 4 15:30:44 2021 -0400 Add range intersect with 2 wide-ints. Add a more efficent intersect using a lower/upper bound single pair of wide_ints. * gimple-range-cache.cc (non_null_ref::adjust_range): Call new intersect routine. * gimple-range-fold.cc (adjust_pointer_diff_expr): Ditto. (adjust_imagpart_expr): Ditto. * value-range.cc (irange::irange_intersect): Call new routine if RHS is a single pair. (irange::intersect): New wide_int version. * value-range.h (class irange): New prototype. Diff: --- gcc/gimple-range-cache.cc | 6 ++--- gcc/gimple-range-fold.cc | 14 ++++------ gcc/value-range.cc | 69 +++++++++++++++++++++++++++++++++++++++++++++++ gcc/value-range.h | 1 + 4 files changed, 78 insertions(+), 12 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 91dd5a5c087..7d994798e52 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -105,9 +105,9 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb, // Check if pointers have any non-null dereferences. if (non_null_deref_p (name, bb, search_dom)) { - int_range<2> nz; - nz.set_nonzero (TREE_TYPE (name)); - r.intersect (nz); + // Remove zero from the range. + unsigned prec = TYPE_PRECISION (TREE_TYPE (name)); + r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED)); return true; } return false; diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index bb09b751a4e..ed2fbe121cf 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -360,12 +360,9 @@ adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) && integer_zerop (gimple_call_arg (call, 1))) { tree max = vrp_val_max (ptrdiff_type_node); - wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); - tree expr_type = gimple_range_type (diff_stmt); - tree range_min = build_zero_cst (expr_type); - tree range_max = wide_int_to_tree (expr_type, wmax - 1); - int_range<2> r (range_min, range_max); - res.intersect (r); + unsigned prec = TYPE_PRECISION (TREE_TYPE (max)); + wide_int wmaxm1 = wi::to_wide (max, prec) - 1; + res.intersect (wi::zero (prec), wmaxm1); } } @@ -405,9 +402,8 @@ adjust_imagpart_expr (irange &res, const gimple *stmt) tree cst = gimple_assign_rhs1 (def_stmt); if (TREE_CODE (cst) == COMPLEX_CST) { - tree imag = TREE_IMAGPART (cst); - int_range<2> tmp (imag, imag); - res.intersect (tmp); + wide_int imag = wi::to_wide (TREE_IMAGPART (cst)); + res.intersect (imag, imag); } } } diff --git a/gcc/value-range.cc b/gcc/value-range.cc index f113fd7c905..147c4b04c1d 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1648,6 +1648,8 @@ void irange::irange_intersect (const irange &r) { gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); + gcc_checking_assert (undefined_p () || r.undefined_p () + || range_compatible_p (type (), r.type ())); if (undefined_p () || r.varying_p ()) return; @@ -1662,6 +1664,13 @@ irange::irange_intersect (const irange &r) return; } + if (r.num_pairs () == 1) + { + // R cannot be undefined, use more efficent pair routine. + intersect (r.lower_bound(), r.upper_bound ()); + return; + } + signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); unsigned bld_pair = 0; unsigned bld_lim = m_max_ranges; @@ -1737,6 +1746,66 @@ irange::irange_intersect (const irange &r) verify_range (); } +// Multirange intersect for a specified wide_int [lb, ub] range. + +void +irange::intersect (const wide_int& lb, const wide_int& ub) +{ + // Undefined remains undefined. + if (undefined_p ()) + return; + + if (legacy_mode_p ()) + { + intersect (int_range<1> (type (), lb, ub)); + return; + } + + tree range_type = type(); + signop sign = TYPE_SIGN (range_type); + + gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb)); + gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub)); + + unsigned bld_index = 0; + unsigned pair_lim = num_pairs (); + for (unsigned i = 0; i < pair_lim; i++) + { + tree pairl = m_base[i * 2]; + tree pairu = m_base[i * 2 + 1]; + // Once UB is less than a pairs lower bound, we're done. + if (wi::lt_p (ub, wi::to_wide (pairl), sign)) + break; + // if LB is greater than this pairs upper, this pair is excluded. + if (wi::lt_p (wi::to_wide (pairu), lb, sign)) + continue; + + // Must be some overlap. Find the highest of the lower bounds, + // and set it + if (wi::gt_p (lb, wi::to_wide (pairl), sign)) + m_base[bld_index * 2] = wide_int_to_tree (range_type, lb); + else + m_base[bld_index * 2] = pairl; + + // ...and choose the lower of the upper bounds and if the base pair + // has the lower upper bound, need to check next pair too. + if (wi::lt_p (ub, wi::to_wide (pairu), sign)) + { + m_base[bld_index++ * 2 + 1] = wide_int_to_tree (range_type, ub); + break; + } + else + m_base[bld_index++ * 2 + 1] = pairu; + } + + m_num_ranges = bld_index; + + m_kind = VR_RANGE; + normalize_kind (); + + if (flag_checking) + verify_range (); +} // Signed 1-bits are strange. You can't subtract 1, because you can't // represent the number 1. This works around that for the invert routine. diff --git a/gcc/value-range.h b/gcc/value-range.h index 39e8f3bcdee..ff6c0a6176d 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -73,6 +73,7 @@ public: // In-place operators. void union_ (const irange &); void intersect (const irange &); + void intersect (const wide_int& lb, const wide_int& ub); void invert (); // Operator overloads.
reply other threads:[~2021-10-06 14:52 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20211006145231.B1118385B83C@sourceware.org \ --to=amacleod@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).