From patchwork Sun Jul 10 07:53:18 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1654498 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=vMe+t5wT; 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 4LgfR64lrBz9s07 for ; Sun, 10 Jul 2022 17:53:52 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 10229385C327 for ; Sun, 10 Jul 2022 07:53:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 10229385C327 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1657439628; bh=VrI0tTj//+e36lGANM3IptaSeS3N1DxepB+XASEgTe4=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=vMe+t5wT/D9EfsSctuTO7jHpCEEfUKWsBEClUxRN1gZlvxUKaOjnd5sN65zx+HNaD Ejc31Xj6VunhexdLHBnrP5DgM0xx+dThEXHum5/TR80D0w/V4LITLbmk9O9DTPH30Z E56D8WYRzwLyRvblJ25r9ie5RHHNSC9oBnoBQkYY= 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 CBE123858C2F for ; Sun, 10 Jul 2022 07:53:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CBE123858C2F 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-487-gd2jK-fwO9alWYllcDcGuw-1; Sun, 10 Jul 2022 03:53:26 -0400 X-MC-Unique: gd2jK-fwO9alWYllcDcGuw-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id AB066185A79C for ; Sun, 10 Jul 2022 07:53:25 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.6]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 46E78492CA2; Sun, 10 Jul 2022 07:53:25 +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 26A7rMGU375295 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sun, 10 Jul 2022 09:53:22 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 26A7rML9375290; Sun, 10 Jul 2022 09:53:22 +0200 To: GCC patches Subject: [COMMITTED] Cleanups to irange::nonzero bit code. Date: Sun, 10 Jul 2022 09:53:18 +0200 Message-Id: <20220710075318.375267-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.85 on 10.11.54.9 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" In discussions with Andrew we realized varying_p() was returning true for a range of the entire domain with a non-empty nonzero mask. This is confusing as varying_p() should only return true when absolutely no information is available. A nonzero mask that has any cleared bits is extra information and must return false for varying_p(). This patch fixes this oversight. Now a range of the entire domain with nonzero bits, is internally set to VR_RANGE (with the appropriate end points set). VR_VARYING ranges must have a null nonzero mask. Also, the union and intersect code were not quite right in the presence of nonzero masks. Sometimes we would drop masks to -1 unnecessarily. I was trying to be too smart in avoiding extra work when the mask was NULL, but there's also an implicit mask in the range that must be taken into account. For example, [0,0] may have no nonzero bits set explicitly, but the mask is really 0x0. This will all be simpler when we drop trees, because the nonzero bits will always be set, even if -1. Finally, I've added unit tests to the nonzero mask code. This should help us maintain sanity going forward. There should be no visible changes, as the main consumer of this code is the SSA_NAME_RANGE_INFO patchset which has yet to be committed. Tested on x86-64 Linux. gcc/ChangeLog: * value-range.cc (irange::operator=): Call verify_range. (irange::irange_set): Normalize kind after everything else has been set. (irange::irange_set_anti_range): Same. (irange::set): Same. (irange::verify_range): Disallow nonzero masks for VARYING. (irange::irange_union): Call verify_range. Handle nonzero masks better. (irange::irange_intersect): Same. (irange::set_nonzero_bits): Calculate mask if either range has an explicit mask. (irange::intersect_nonzero_bits): Same. (irange::union_nonzero_bits): Same. (range_tests_nonzero_bits): New. (range_tests): Call range_tests_nonzero_bits. * value-range.h (class irange): Remove set_nonzero_bits method with trees. (irange::varying_compatible_p): Set nonzero mask. --- gcc/value-range.cc | 167 +++++++++++++++++++++++++++++++++++---------- gcc/value-range.h | 5 +- 2 files changed, 133 insertions(+), 39 deletions(-) diff --git a/gcc/value-range.cc b/gcc/value-range.cc index fd549b9ca59..a02fab47fc4 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -275,6 +275,8 @@ irange::operator= (const irange &src) m_num_ranges = lim; m_kind = src.m_kind; m_nonzero_mask = src.m_nonzero_mask; + if (flag_checking) + verify_range (); return *this; } @@ -393,8 +395,8 @@ irange::irange_set (tree min, tree max) m_base[1] = max; m_num_ranges = 1; m_kind = VR_RANGE; - normalize_kind (); m_nonzero_mask = NULL; + normalize_kind (); if (flag_checking) verify_range (); @@ -467,8 +469,8 @@ irange::irange_set_anti_range (tree min, tree max) } m_kind = VR_RANGE; - normalize_kind (); m_nonzero_mask = NULL; + normalize_kind (); if (flag_checking) verify_range (); @@ -577,8 +579,8 @@ irange::set (tree min, tree max, value_range_kind kind) m_base[0] = min; m_base[1] = max; m_num_ranges = 1; - normalize_kind (); m_nonzero_mask = NULL; + normalize_kind (); if (flag_checking) verify_range (); } @@ -599,6 +601,7 @@ irange::verify_range () gcc_checking_assert (wi::to_wide (m_nonzero_mask) != -1); if (m_kind == VR_VARYING) { + gcc_checking_assert (!m_nonzero_mask); gcc_checking_assert (m_num_ranges == 1); gcc_checking_assert (varying_compatible_p ()); return; @@ -1759,6 +1762,8 @@ irange::legacy_verbose_intersect (const irange *other) // Perform an efficient union with R when both ranges have only a single pair. // Excluded are VARYING and UNDEFINED ranges. +// +// NOTE: It is the caller's responsibility to set the nonzero mask. bool irange::irange_single_pair_union (const irange &r) @@ -1831,23 +1836,28 @@ irange::irange_union (const irange &r) if (undefined_p ()) { operator= (r); + if (flag_checking) + verify_range (); 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; + return false; if (r.varying_p ()) { - set_varying (r.type ()); - set_nonzero_bits (saved_nz); + set_varying (type ()); 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; + + // The union_nonzero_bits may have turned things into a varying. + if (varying_p ()) + return true; + // Special case one range union one range. if (m_num_ranges == 1 && r.m_num_ranges == 1) { @@ -1948,8 +1958,8 @@ irange::irange_union (const irange &r) m_num_ranges = i / 2; m_kind = VR_RANGE; + m_nonzero_mask = saved_nz; normalize_kind (); - set_nonzero_bits (saved_nz); if (flag_checking) verify_range (); @@ -2029,13 +2039,19 @@ irange::irange_intersect (const irange &r) if (varying_p ()) { operator= (r); - set_nonzero_bits (saved_nz); + if (saved_nz) + set_nonzero_bits (saved_nz); + if (flag_checking) + verify_range (); return true; } if (r.num_pairs () == 1) { bool res = intersect (r.lower_bound (), r.upper_bound ()); + if (undefined_p ()) + return true; + set_nonzero_bits (saved_nz); return res || saved_nz; } @@ -2113,9 +2129,9 @@ irange::irange_intersect (const irange &r) m_num_ranges = bld_pair; m_kind = VR_RANGE; - normalize_kind (); if (!undefined_p ()) - set_nonzero_bits (saved_nz); + m_nonzero_mask = saved_nz; + normalize_kind (); if (flag_checking) verify_range (); @@ -2331,6 +2347,30 @@ irange::invert () verify_range (); } +void +irange::set_nonzero_bits (tree mask) +{ + gcc_checking_assert (!undefined_p ()); + + if (!mask) + { + if (m_nonzero_mask) + { + m_nonzero_mask = NULL; + // Clearing the mask may have turned a range into VARYING. + normalize_kind (); + } + return; + } + m_nonzero_mask = mask; + // Setting the mask may have turned a VARYING into a range. + if (m_kind == VR_VARYING) + m_kind = VR_RANGE; + + if (flag_checking) + verify_range (); +} + void irange::set_nonzero_bits (const wide_int_ref &bits) { @@ -2338,10 +2378,10 @@ irange::set_nonzero_bits (const wide_int_ref &bits) if (bits == -1) { - m_nonzero_mask = NULL; + set_nonzero_bits (NULL); return; } - m_nonzero_mask = wide_int_to_tree (type (), bits); + set_nonzero_bits (wide_int_to_tree (type (), bits)); } wide_int @@ -2378,17 +2418,14 @@ 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) + if (m_nonzero_mask || r.m_nonzero_mask) { - m_nonzero_mask = r.m_nonzero_mask; + wide_int nz = wi::bit_and (get_nonzero_bits (), + r.get_nonzero_bits ()); + set_nonzero_bits (nz); 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; + return false; } // Union the nonzero bits in R into THIS. @@ -2398,21 +2435,14 @@ 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 || r.m_nonzero_mask) { - if (m_nonzero_mask) - { - m_nonzero_mask = NULL; - return true; - } - return false; + wide_int nz = wi::bit_or (get_nonzero_bits (), + r.get_nonzero_bits ()); + set_nonzero_bits (nz); + return true; } - 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; + return false; } static void @@ -3054,6 +3084,68 @@ range_tests_misc () ASSERT_TRUE (r0.contains_p (UINT (2))); } +static void +range_tests_nonzero_bits () +{ + int_range<2> r0, r1; + + // Adding nonzero bits to a varying drops the varying. + r0.set_varying (integer_type_node); + r0.set_nonzero_bits (255); + ASSERT_TRUE (!r0.varying_p ()); + // Dropping the nonzero bits brings us back to varying. + r0.set_nonzero_bits (-1); + ASSERT_TRUE (r0.varying_p ()); + + // Test contains_p with nonzero bits. + r0.set_zero (integer_type_node); + ASSERT_TRUE (r0.contains_p (INT (0))); + ASSERT_FALSE (r0.contains_p (INT (1))); + r0.set_nonzero_bits (0xfe); + ASSERT_FALSE (r0.contains_p (INT (0x100))); + ASSERT_FALSE (r0.contains_p (INT (0x3))); + + // Union of nonzero bits. + r0.set_varying (integer_type_node); + r0.set_nonzero_bits (0xf0); + r1.set_varying (integer_type_node); + r1.set_nonzero_bits (0xf); + r0.union_ (r1); + ASSERT_TRUE (r0.get_nonzero_bits () == 0xff); + + // Union where the mask of nonzero bits is implicit from the range. + r0.set_varying (integer_type_node); + r0.set_nonzero_bits (0xf00); + r1.set_zero (integer_type_node); // nonzero mask is implicitly 0 + r0.union_ (r1); + ASSERT_TRUE (r0.get_nonzero_bits () == 0xf00); + + // Intersect of nonzero bits. + r0.set (INT (0), INT (255)); + r0.set_nonzero_bits (0xfe); + r1.set_varying (integer_type_node); + r1.set_nonzero_bits (0xf0); + r0.intersect (r1); + ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0); + + // Intersect where the mask of nonzero bits is implicit from the range. + r0.set_varying (integer_type_node); + r1.set (INT (0), INT (255)); + r0.intersect (r1); + ASSERT_TRUE (r0.get_nonzero_bits () == 0xff); + + // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the + // entire domain, and makes the range a varying. + r0.set_varying (integer_type_node); + wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node)); + x = wi::bit_not (x); + r0.set_nonzero_bits (x); // 0xff..ff00 + r1.set_varying (integer_type_node); + r1.set_nonzero_bits (0xff); + r0.union_ (r1); + ASSERT_TRUE (r0.varying_p ()); +} + void range_tests () { @@ -3061,6 +3153,7 @@ range_tests () range_tests_irange3 (); range_tests_int_range_max (); range_tests_strict_enum (); + range_tests_nonzero_bits (); range_tests_misc (); } diff --git a/gcc/value-range.h b/gcc/value-range.h index 2e48d92d189..0e341185f69 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -201,7 +201,7 @@ private: void irange_set_1bit_anti_range (tree, tree); bool varying_compatible_p () const; - void set_nonzero_bits (tree bits) { m_nonzero_mask = bits; } + void set_nonzero_bits (tree mask); bool intersect_nonzero_bits (const irange &r); bool union_nonzero_bits (const irange &r); void dump_bitmasks (FILE *) const; @@ -555,7 +555,8 @@ irange::varying_compatible_p () const signop sign = TYPE_SIGN (t); if (INTEGRAL_TYPE_P (t)) return (wi::to_wide (l) == wi::min_value (prec, sign) - && wi::to_wide (u) == wi::max_value (prec, sign)); + && wi::to_wide (u) == wi::max_value (prec, sign) + && !m_nonzero_mask); if (POINTER_TYPE_P (t)) return (wi::to_wide (l) == 0 && wi::to_wide (u) == wi::max_value (prec, sign));