From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2136) id 6CE003856DE8; Mon, 4 Jul 2022 09:34:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6CE003856DE8 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Aldy Hernandez To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-1451] Integrate nonzero bits with irange. X-Act-Checkin: gcc X-Git-Author: Aldy Hernandez X-Git-Refname: refs/heads/master X-Git-Oldrev: d2a898666609452ef79a14feae1cadc3538e4b45 X-Git-Newrev: 4e82205b68024f5c1a9006fe2b62e1a0fa7f1245 Message-Id: <20220704093427.6CE003856DE8@sourceware.org> Date: Mon, 4 Jul 2022 09:34:27 +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: Mon, 04 Jul 2022 09:34:27 -0000 https://gcc.gnu.org/g:4e82205b68024f5c1a9006fe2b62e1a0fa7f1245 commit r13-1451-g4e82205b68024f5c1a9006fe2b62e1a0fa7f1245 Author: Aldy Hernandez Date: Fri Jul 1 13:20:42 2022 +0200 Integrate nonzero bits with irange. The nonzero bits and integer ranges compliment each other quite well, and it only makes sense to make the mask a first class citizen in the irange. We do a half assed job of keeping ranges and nonzero bits somewhat in sync in SSA_NAME_RANGE_INFO, and the goal has always been to integrate them properly. This patch does that, in preparation for streaming out full-resolution iranges between passes (think SSA_NAME_RANGE_INFO). Having nonzero bits in the irange allows us to get better results from things like irange::contains_p() and keeping them in the irange allows us to propagate the bits throughout with the ranger. This patch provides the bare infrastructure, without any optimizations to range-ops, etc. Those will come as follow-ups. A few notes: Legacy SSA_NAME_RANGE_INFO updates the nonzero bits every time a range is set. Here instead, we don't update the nonzero bits on a new range, but calculate it on the fly when irange::get_nonzero_bits() is called. The goal is to only store nonzero bits that provide meaningful information that can't be gleaned from the range itself. But you can always call get_nonzero_bits() and get the full information. Nonzero bits are not supported in legacy mode. The mask may be set as a consequence of propagation or reading global ranges, but no one from legacy land should be querying irange::get_nonzero_bits. There is an assert enforcing this. However, legacy/global set_nonzero_bits() continue to work as before. There is no change to legacy behavior. There is virtually no performance change with this patch, as there are no consumers. The next patch I post will be the SSA_NAME_RANGE_INFO conversion to the new world, in which I will discuss performance proper. Hint: I'll be chewing up the time budget we gained with the vrange conversion. Tested and benchmarked on x86-64 Linux. gcc/ChangeLog: * value-range-storage.cc (irange_storage_slot::set_irange): Set nonzero bits in irange. (irange_storage_slot::get_irange): Get nonzero bits from irange. * value-range.cc (irange::operator=): Set nonzero bits. (irange::irange_set): Same. (irange::irange_set_anti_range): Same. (irange::set): Same. (irange::verify_range): Same. (irange::legacy_equal_p): Check nonzero bits. (irange::equal_p): Same. (irange::contains_p): Handle nonzero bits. (irange::irange_union): Same. (irange::irange_intersect): Same. (irange::dump): Same. (irange::set_nonzero_bits): New. (irange::get_nonzero_bits): New. (irange::intersect_nonzero_bits): New. (irange::union_nonzero_bits): New. (irange::dump_bitmasks): New. * value-range.h (class irange): Add m_nonzero_mask. (gt_ggc_mx): Handle nonzero bits. (gt_pch_nx): Same. (irange::set_undefined): Set nonzero bits. (irange::set_varying): Same. (irange::normalize_kind): Call set_undefined. Diff: --- gcc/value-range-storage.cc | 9 ++- gcc/value-range.cc | 177 ++++++++++++++++++++++++++++++++++++++++++--- gcc/value-range.h | 20 ++++- 3 files changed, 193 insertions(+), 13 deletions(-) diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc index ea9b18f993b..ac62bfaa638 100644 --- a/gcc/value-range-storage.cc +++ b/gcc/value-range-storage.cc @@ -131,7 +131,12 @@ irange_storage_slot::set_irange (const irange &r) { gcc_checking_assert (fits_p (r)); - //m_ints[0] = r.get_nonzero_bits (); + // Avoid calling unsupported get_nonzero_bits on legacy. + if (r.legacy_mode_p ()) + m_ints[0] = -1; + else + m_ints[0] = r.get_nonzero_bits (); + unsigned pairs = r.num_pairs (); for (unsigned i = 0; i < pairs; ++i) { @@ -154,7 +159,7 @@ irange_storage_slot::get_irange (irange &r, tree type) const int_range<2> tmp (type, m_ints[i], m_ints[i + 1]); r.union_ (tmp); } - //r.set_nonzero_bits (get_nonzero_bits ()); + r.set_nonzero_bits (get_nonzero_bits ()); } // Return the size in bytes to allocate a slot that can hold R. diff --git a/gcc/value-range.cc b/gcc/value-range.cc index 574c51002b5..25f1acff4a3 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -274,6 +274,7 @@ irange::operator= (const irange &src) m_num_ranges = lim; m_kind = src.m_kind; + m_nonzero_mask = src.m_nonzero_mask; return *this; } @@ -393,6 +394,7 @@ irange::irange_set (tree min, tree max) m_num_ranges = 1; m_kind = VR_RANGE; normalize_kind (); + m_nonzero_mask = NULL; if (flag_checking) verify_range (); @@ -466,6 +468,7 @@ irange::irange_set_anti_range (tree min, tree max) m_kind = VR_RANGE; normalize_kind (); + m_nonzero_mask = NULL; if (flag_checking) verify_range (); @@ -524,6 +527,7 @@ irange::set (tree min, tree max, value_range_kind kind) m_base[0] = min; m_base[1] = max; m_num_ranges = 1; + m_nonzero_mask = NULL; return; } @@ -574,6 +578,7 @@ irange::set (tree min, tree max, value_range_kind kind) m_base[1] = max; m_num_ranges = 1; normalize_kind (); + m_nonzero_mask = NULL; if (flag_checking) verify_range (); } @@ -587,8 +592,11 @@ irange::verify_range () if (m_kind == VR_UNDEFINED) { gcc_checking_assert (m_num_ranges == 0); + gcc_checking_assert (!m_nonzero_mask); return; } + if (m_nonzero_mask) + gcc_checking_assert (wi::to_wide (m_nonzero_mask) != -1); if (m_kind == VR_VARYING) { gcc_checking_assert (m_num_ranges == 1); @@ -680,11 +688,15 @@ irange::legacy_equal_p (const irange &other) const if (m_kind == VR_UNDEFINED) return true; if (m_kind == VR_VARYING) - return range_compatible_p (type (), other.type ()); + { + return (range_compatible_p (type (), other.type ()) + && vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask)); + } return (vrp_operand_equal_p (tree_lower_bound (0), other.tree_lower_bound (0)) && vrp_operand_equal_p (tree_upper_bound (0), - other.tree_upper_bound (0))); + other.tree_upper_bound (0)) + && vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask)); } bool @@ -716,7 +728,7 @@ irange::operator== (const irange &other) const || !operand_equal_p (ub, ub_other, 0)) return false; } - return true; + return vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask); } /* Return TRUE if this is a symbolic range. */ @@ -858,6 +870,14 @@ irange::contains_p (tree cst) const } gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); + + if (m_nonzero_mask) + { + wide_int cstw = wi::to_wide (cst); + if (cstw != 0 && wi::bit_and (wi::to_wide (m_nonzero_mask), cstw) == 0) + return false; + } + signop sign = TYPE_SIGN (TREE_TYPE (cst)); wide_int v = wi::to_wide (cst); for (unsigned r = 0; r < m_num_ranges; ++r) @@ -1809,22 +1829,40 @@ irange::irange_union (const irange &r) { gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); - if (r.undefined_p () || varying_p ()) + if (r.undefined_p ()) return false; - if (undefined_p () || r.varying_p ()) + if (undefined_p ()) { operator= (r); return true; } + // Save the nonzero mask in case the set operations below clobber it. + bool ret_nz = union_nonzero_bits (r); + tree saved_nz = m_nonzero_mask; + + if (varying_p ()) + return ret_nz; + + if (r.varying_p ()) + { + set_varying (r.type ()); + set_nonzero_bits (saved_nz); + return true; + } + // Special case one range union one range. if (m_num_ranges == 1 && r.m_num_ranges == 1) - return irange_single_pair_union (r); + { + bool ret = irange_single_pair_union (r); + set_nonzero_bits (saved_nz); + return ret || ret_nz; + } // If this ranges fully contains R, then we need do nothing. if (irange_contains_p (r)) - return false; + return ret_nz; // Do not worry about merging and such by reserving twice as many // pairs as needed, and then simply sort the 2 ranges into this @@ -1913,6 +1951,7 @@ irange::irange_union (const irange &r) m_kind = VR_RANGE; normalize_kind (); + set_nonzero_bits (saved_nz); if (flag_checking) verify_range (); @@ -1974,25 +2013,38 @@ irange::irange_intersect (const irange &r) gcc_checking_assert (undefined_p () || r.undefined_p () || range_compatible_p (type (), r.type ())); - if (undefined_p () || r.varying_p ()) + if (undefined_p ()) return false; if (r.undefined_p ()) { set_undefined (); return true; } + + // Save the nonzero mask in case the set operations below clobber it. + bool ret_nz = intersect_nonzero_bits (r); + tree saved_nz = m_nonzero_mask; + + if (r.varying_p ()) + return ret_nz; + if (varying_p ()) { operator= (r); + set_nonzero_bits (saved_nz); return true; } if (r.num_pairs () == 1) - return intersect (r.lower_bound (), r.upper_bound ()); + { + bool res = intersect (r.lower_bound (), r.upper_bound ()); + set_nonzero_bits (saved_nz); + return res || saved_nz; + } // If R fully contains this, then intersection will change nothing. if (r.irange_contains_p (*this)) - return false; + return ret_nz; signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); unsigned bld_pair = 0; @@ -2064,6 +2116,8 @@ irange::irange_intersect (const irange &r) m_kind = VR_RANGE; normalize_kind (); + if (!undefined_p ()) + set_nonzero_bits (saved_nz); if (flag_checking) verify_range (); @@ -2074,6 +2128,8 @@ irange::irange_intersect (const irange &r) // Multirange intersect for a specified wide_int [lb, ub] range. // Return TRUE if intersect changed anything. +// +// NOTE: It is the caller's responsibility to intersect the nonzero masks. bool irange::intersect (const wide_int& lb, const wide_int& ub) @@ -2277,6 +2333,90 @@ irange::invert () verify_range (); } +void +irange::set_nonzero_bits (const wide_int_ref &bits) +{ + gcc_checking_assert (!undefined_p ()); + + if (bits == -1) + { + m_nonzero_mask = NULL; + return; + } + m_nonzero_mask = wide_int_to_tree (type (), bits); +} + +wide_int +irange::get_nonzero_bits () const +{ + gcc_checking_assert (!undefined_p ()); + // Nonzero bits are unsupported in legacy mode. The mask may be set + // as a consequence of propagation or reading global ranges, but no + // one from legacy land should be querying this. + gcc_checking_assert (!legacy_mode_p ()); + + // Calculate the nonzero bits inherent in the range. + wide_int min = lower_bound (); + wide_int max = upper_bound (); + wide_int xorv = min ^ max; + if (xorv != 0) + { + unsigned prec = TYPE_PRECISION (type ()); + xorv = wi::mask (prec - wi::clz (xorv), false, prec); + } + wide_int mask = min | xorv; + + // Return the nonzero bits augmented by the range. + if (m_nonzero_mask) + return mask & wi::to_wide (m_nonzero_mask); + + return mask; +} + +// Intersect the nonzero bits in R into THIS. + +bool +irange::intersect_nonzero_bits (const irange &r) +{ + gcc_checking_assert (!undefined_p () && !r.undefined_p ()); + + if (!r.m_nonzero_mask) + return false; + if (!m_nonzero_mask) + { + m_nonzero_mask = r.m_nonzero_mask; + return true; + } + wide_int i = wi::bit_and (wi::to_wide (m_nonzero_mask), + wi::to_wide (r.m_nonzero_mask)); + set_nonzero_bits (i); + return true; +} + +// Union the nonzero bits in R into THIS. + +bool +irange::union_nonzero_bits (const irange &r) +{ + gcc_checking_assert (!undefined_p () && !r.undefined_p ()); + + if (!m_nonzero_mask) + return false; + if (!r.m_nonzero_mask) + { + if (m_nonzero_mask) + { + m_nonzero_mask = NULL; + return true; + } + return false; + } + wide_int i = wi::bit_or (wi::to_wide (m_nonzero_mask), + wi::to_wide (r.m_nonzero_mask)); + set_nonzero_bits (i); + return true; +} + static void dump_bound_with_infinite_markers (FILE *file, tree bound) { @@ -2312,6 +2452,7 @@ irange::dump (FILE *file) const if (varying_p ()) { fprintf (file, "VARYING"); + dump_bitmasks (file); return; } if (legacy_mode_p ()) @@ -2321,6 +2462,7 @@ irange::dump (FILE *file) const fprintf (file, ", "); dump_bound_with_infinite_markers (file, max ()); fprintf (file, "]"); + dump_bitmasks (file); return; } for (unsigned i = 0; i < m_num_ranges; ++i) @@ -2333,6 +2475,21 @@ irange::dump (FILE *file) const dump_bound_with_infinite_markers (file, ub); fprintf (file, "]"); } + dump_bitmasks (file); +} + +void +irange::dump_bitmasks (FILE *file) const +{ + if (m_nonzero_mask && !legacy_mode_p ()) + { + wide_int nz = get_nonzero_bits (); + if (nz != -1) + { + fprintf (file, " NONZERO "); + print_hex (nz, file); + } + } } void diff --git a/gcc/value-range.h b/gcc/value-range.h index fd6703138ac..2e48d92d189 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -109,6 +109,7 @@ protected: class GTY((user)) irange : public vrange { friend class vrange_allocator; + friend class irange_storage_slot; // For legacy_mode_p checks. public: // In-place setters. virtual void set (tree, tree, value_range_kind = VR_RANGE) override; @@ -149,6 +150,10 @@ public: virtual bool fits_p (const vrange &r) const override; virtual void dump (FILE * = stderr) const override; + // Nonzero masks. + wide_int get_nonzero_bits () const; + void set_nonzero_bits (const wide_int_ref &bits); + // Deprecated legacy public methods. tree min () const; // DEPRECATED tree max () const; // DEPRECATED @@ -196,10 +201,15 @@ private: void irange_set_1bit_anti_range (tree, tree); bool varying_compatible_p () const; + void set_nonzero_bits (tree bits) { m_nonzero_mask = bits; } + bool intersect_nonzero_bits (const irange &r); + bool union_nonzero_bits (const irange &r); + void dump_bitmasks (FILE *) const; bool intersect (const wide_int& lb, const wide_int& ub); unsigned char m_num_ranges; unsigned char m_max_ranges; + tree m_nonzero_mask; tree *m_base; }; @@ -608,6 +618,8 @@ gt_ggc_mx (irange *x) gt_ggc_mx (x->m_base[i * 2]); gt_ggc_mx (x->m_base[i * 2 + 1]); } + if (x->m_nonzero_mask) + gt_ggc_mx (x->m_nonzero_mask); } inline void @@ -618,6 +630,8 @@ gt_pch_nx (irange *x) gt_pch_nx (x->m_base[i * 2]); gt_pch_nx (x->m_base[i * 2 + 1]); } + if (x->m_nonzero_mask) + gt_pch_nx (x->m_nonzero_mask); } inline void @@ -628,6 +642,8 @@ gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie) op (&x->m_base[i * 2], NULL, cookie); op (&x->m_base[i * 2 + 1], NULL, cookie); } + if (x->m_nonzero_mask) + op (&x->m_nonzero_mask, NULL, cookie); } template @@ -722,6 +738,7 @@ irange::set_undefined () { m_kind = VR_UNDEFINED; m_num_ranges = 0; + m_nonzero_mask = NULL; } inline void @@ -729,6 +746,7 @@ irange::set_varying (tree type) { m_kind = VR_VARYING; m_num_ranges = 1; + m_nonzero_mask = NULL; if (INTEGRAL_TYPE_P (type)) { @@ -843,7 +861,7 @@ inline void irange::normalize_kind () { if (m_num_ranges == 0) - m_kind = VR_UNDEFINED; + set_undefined (); else if (varying_compatible_p ()) { if (m_kind == VR_RANGE)