From patchwork Mon Jul 4 09:34:02 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1651880 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=t/vZgfsC; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4Lc0yF6BqPz9sFr for ; Mon, 4 Jul 2022 19:34:44 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E31383856DE0 for ; Mon, 4 Jul 2022 09:34:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E31383856DE0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1656927277; bh=siXYOHBDq1y8JBH0SuNKMusXVf1UIQA+bHUHLyG5EmQ=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=t/vZgfsCxeCuQ287lLW1Nox5RIwkVmefHnXW38GlpQI4Q91/FXeJ8S1DDyT2gX9LL TftMnEZIzM0mmGyjsSUL8eusGxoqkKTWh4HyR0B+qYbTxznrzQJAEOl1eDKY61RWSY o97IJ6rFRuWmYftEscRbGH3l6+R8My7PzP6npbvQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 7D7683858C52 for ; Mon, 4 Jul 2022 09:34:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7D7683858C52 Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-639-_Zti6-fbNO-fPsrCasD7lg-1; Mon, 04 Jul 2022 05:34:14 -0400 X-MC-Unique: _Zti6-fbNO-fPsrCasD7lg-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 22017833975 for ; Mon, 4 Jul 2022 09:34:10 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.61]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 875FDC53360; Mon, 4 Jul 2022 09:34:09 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 2649Y7m3532473 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 4 Jul 2022 11:34:07 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 2649Y6XR532472; Mon, 4 Jul 2022 11:34:06 +0200 To: GCC patches Subject: [COMMITTED] Integrate nonzero bits with irange. Date: Mon, 4 Jul 2022 11:34:02 +0200 Message-Id: <20220704093402.532456-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.85 on 10.11.54.8 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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. --- 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)