From patchwork Mon Jul 24 14:39:27 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1811864 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.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=GCgyU1YV; dkim-atps=neutral Received: from server2.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 ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4R8jVj65WWz1yYc for ; Tue, 25 Jul 2023 00:39:57 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8FB4E385770D for ; Mon, 24 Jul 2023 14:39:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8FB4E385770D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690209595; bh=SsMjbONER+lXBHENNVxXPkNaOhmtAClcS8gwiXI6OEE=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=GCgyU1YVx96+dGGIWY0lJ5D0vQ69nuTL4yxzepukN9yNOHNlKuUD8L3Yh28FnmAA1 x82YKywbjq2QpVck83r6nrF+t9n14zyWeAhTRnVj5JZd8VUvweN5URyomOenMKH01S IuMa93dw3LUtg+0onB+vwIjm6UD573g9UCmJ+u1A= 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 1DA5B3858C5E for ; Mon, 24 Jul 2023 14:39:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1DA5B3858C5E Received: from mail-vs1-f71.google.com (mail-vs1-f71.google.com [209.85.217.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-501-B5P_1WbCPmWU_ZcRWzTQyQ-1; Mon, 24 Jul 2023 10:39:30 -0400 X-MC-Unique: B5P_1WbCPmWU_ZcRWzTQyQ-1 Received: by mail-vs1-f71.google.com with SMTP id ada2fe7eead31-440d57c812bso643007137.0 for ; Mon, 24 Jul 2023 07:39:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690209570; x=1690814370; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=TZM59dDu4fPFTKD8PaAakTkGj6EOVdogrQMwSdjFYEw=; b=War6zWS72bdezvNoU3jrnikgV4XzSrHVJeLyrQytT/1MB8uvLWbk/qjKcRVyMB0R03 X7gydhR3PXWTsdUt8zIwcqIPOKViWpLFBDRP7kfuIB03S0lkrIW6wkMgPc6A9VVwPbLc FJj1QUvnbWju6jZm17XuF/o5aM2YMqkOfUVVP8VGNtwnIm6lhKMFJ1jhLA2Nwu6uoLpS xoK7VIMsiFjvURc67ZaAjoxXwniMYAfDKm8iL+GqgxugdWvLGzUeBlJ2mjbxva6lHQgZ HmI47Spbjdw8rwU3o2qnkvL6CPi1pdF8ZdSv5Z/lDXjG4wWSJWPQTQqcZtNZvDsQpt7i L+Vg== X-Gm-Message-State: ABy/qLbrlMhFbRLWih7BBvI9KlDb7RcNoM2Z8BG2CNAD2JJsrg3OCVnc spM/Hr9ENJXeRGCFSM9u/aEvpaI/GeY8tf0tkxO0I526Qh1NmECC9MmbkjkEZmVchqTc96BDvfE 1xjTGKssqinTfVJpHTBp7MRv/+hXg6unqmHziy/0rXrip7yDwmEOGPPBMTL2le6GLhu14GSOzUB kwvw== X-Received: by 2002:a67:fb4a:0:b0:443:5aca:d2dc with SMTP id e10-20020a67fb4a000000b004435acad2dcmr2747552vsr.6.1690209570039; Mon, 24 Jul 2023 07:39:30 -0700 (PDT) X-Google-Smtp-Source: APBJJlHipiM3UjiQqGzB7y6cbGdpEPO9+HvscAJu8BGTRHUkH+dHX218c458ohST+NfTlJ0ZsiFsYA== X-Received: by 2002:a67:fb4a:0:b0:443:5aca:d2dc with SMTP id e10-20020a67fb4a000000b004435acad2dcmr2747536vsr.6.1690209569619; Mon, 24 Jul 2023 07:39:29 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::bdd9? ([2607:fea8:51df:4200::bdd9]) by smtp.gmail.com with ESMTPSA id h9-20020a05620a13e900b00767ce8e6d7fsm2983676qkl.57.2023.07.24.07.39.28 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 24 Jul 2023 07:39:29 -0700 (PDT) Message-ID: <8b98831c-23cd-0c27-58f3-62bbcb4b3347@redhat.com> Date: Mon, 24 Jul 2023 10:39:27 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [PATCH] [GCC13] PR tree-optimization/110315 - Add auto-resizing capability to irange's X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.4 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_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Aldy has ported his irange reduction patch to GCC 13.  It resolves this PR. I have bootstrapped it and it passes regression tests. Do we want to check it into the GCC 13 branch?  The patch has all his comments in it. Andrew From 777aa930b106fea2dd6ed9fe22b42a2717f1472d Mon Sep 17 00:00:00 2001 From: Aldy Hernandez Date: Mon, 15 May 2023 12:25:58 +0200 Subject: [PATCH] [GCC13] Add auto-resizing capability to irange's [PR109695] Backport the following from trunk. Note that the patch has been adapted to trees. The numbers for various sub-ranges on GCC13 are: < 2> = 64 bytes, -3.02% for VRP. < 3> = 80 bytes, -2.67% for VRP. < 8> = 160 bytes, -2.46% for VRP. <16> = 288 bytes, -2.40% for VRP. We can now have int_range for automatically resizable ranges. int_range_max is now int_range<3, true> for a 69X reduction in size from current trunk, and 6.9X reduction from GCC12. This incurs a 5% performance penalty for VRP that is more than covered by our > 13% improvements recently. int_range_max is the temporary range object we use in the ranger for integers. With the conversion to wide_int, this structure bloated up significantly because wide_ints are huge (80 bytes a piece) and are about 10 times as big as a plain tree. Since the temporary object requires 255 sub-ranges, that's 255 * 80 * 2, plus the control word. This means the structure grew from 4112 bytes to 40912 bytes. This patch adds the ability to resize ranges as needed, defaulting to no resizing, while int_range_max now defaults to 3 sub-ranges (instead of 255) and grows to 255 when the range being calculated does not fit. For example: int_range<1> foo; // 1 sub-range with no resizing. int_range<5> foo; // 5 sub-ranges with no resizing. int_range<5, true> foo; // 5 sub-ranges with resizing. I ran some tests and found that 3 sub-ranges cover 99% of cases, so I've set the int_range_max default to that: typedef int_range<3, /*RESIZABLE=*/true> int_range_max; We don't bother growing incrementally, since the default covers most cases and we have a 255 hard-limit. This hard limit could be reduced to 128, since my tests never saw a range needing more than 124, but we could do that as a follow-up if needed. With 3-subranges, int_range_max is now 592 bytes versus 40912 for trunk, and versus 4112 bytes for GCC12! The penalty is 5.04% for VRP and 3.02% for threading, with no noticeable change in overall compilation (0.27%). This is more than covered by our 13.26% improvements for the legacy removal + wide_int conversion. I think this approach is a good alternative, while providing us with flexibility going forward. For example, we could try defaulting to a 8 sub-ranges for a noticeable improvement in VRP. We could also use large sub-ranges for switch analysis to avoid resizing. Another approach I tried was always resizing. With this, we could drop the whole int_range nonsense, and have irange just hold a resizable range. This simplified things, but incurred a 7% penalty on ipa_cp. This was hard to pinpoint, and I'm not entirely convinced this wasn't some artifact of valgrind. However, until we're sure, let's avoid massive changes, especially since IPA changes are coming up. For the curious, a particular hot spot for IPA in this area was: ipcp_vr_lattice::meet_with_1 (const value_range *other_vr) { ... ... value_range save (m_vr); m_vr.union_ (*other_vr); return m_vr != save; } The problem isn't the resizing (since we do that at most once) but the fact that for some functions with lots of callers we end up a huge range that gets copied and compared for every meet operation. Maybe the IPA algorithm could be adjusted somehow??. Anywhooo... for now there is nothing to worry about, since value_range still has 2 subranges and is not resizable. But we should probably think what if anything we want to do here, as I envision IPA using infinite ranges here (well, int_range_max) and handling frange's, etc. gcc/ChangeLog: PR tree-optimization/109695 * value-range.cc (irange::operator=): Resize range. (irange::union_): Same. (irange::intersect): Same. (irange::invert): Same. (int_range_max): Default to 3 sub-ranges and resize as needed. * value-range.h (irange::maybe_resize): New. (~int_range): New. (int_range::int_range): Adjust for resizing. (int_range::operator=): Same. --- gcc/value-range-storage.h | 2 +- gcc/value-range.cc | 15 ++++++ gcc/value-range.h | 96 +++++++++++++++++++++++++++------------ 3 files changed, 83 insertions(+), 30 deletions(-) diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h index 6da377ebd2e..1ed6f1ccd61 100644 --- a/gcc/value-range-storage.h +++ b/gcc/value-range-storage.h @@ -184,7 +184,7 @@ vrange_allocator::alloc_irange (unsigned num_pairs) // Allocate the irange and required memory for the vector. void *r = alloc (sizeof (irange)); tree *mem = static_cast (alloc (nbytes)); - return new (r) irange (mem, num_pairs); + return new (r) irange (mem, num_pairs, /*resizable=*/false); } inline frange * diff --git a/gcc/value-range.cc b/gcc/value-range.cc index ec826c2fe1b..753f5e8cc76 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -831,6 +831,10 @@ irange::operator= (const irange &src) copy_to_legacy (src); return *this; } + + int needed = src.num_pairs (); + maybe_resize (needed); + if (src.legacy_mode_p ()) { copy_legacy_to_multi_range (src); @@ -2506,6 +2510,7 @@ irange::irange_union (const irange &r) // Now it simply needs to be copied, and if there are too many // ranges, merge some. We wont do any analysis as to what the // "best" merges are, simply combine the final ranges into one. + maybe_resize (i / 2); if (i > m_max_ranges * 2) { res[m_max_ranges * 2 - 1] = res[i - 1]; @@ -2605,6 +2610,11 @@ irange::irange_intersect (const irange &r) if (r.irange_contains_p (*this)) return intersect_nonzero_bits (r); + // ?? We could probably come up with something smarter than the + // worst case scenario here. + int needed = num_pairs () + r.num_pairs (); + maybe_resize (needed); + signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); unsigned bld_pair = 0; unsigned bld_lim = m_max_ranges; @@ -2831,6 +2841,11 @@ irange::invert () m_num_ranges = 1; return; } + + // At this point, we need one extra sub-range to represent the + // inverse. + maybe_resize (m_num_ranges + 1); + // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. // diff --git a/gcc/value-range.h b/gcc/value-range.h index 969b2b68418..96e59ecfa72 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -172,7 +172,8 @@ public: bool legacy_verbose_intersect (const irange *); // DEPRECATED protected: - irange (tree *, unsigned); + void maybe_resize (int needed); + irange (tree *, unsigned nranges, bool resizable); // potential promotion to public? tree tree_lower_bound (unsigned = 0) const; tree tree_upper_bound (unsigned) const; @@ -200,6 +201,8 @@ protected: void copy_to_legacy (const irange &); void copy_legacy_to_multi_range (const irange &); + // Hard limit on max ranges allowed. + static const int HARD_MAX_RANGES = 255; private: friend void gt_ggc_mx (irange *); friend void gt_pch_nx (irange *); @@ -214,15 +217,21 @@ private: bool intersect (const wide_int& lb, const wide_int& ub); unsigned char m_num_ranges; + bool m_resizable; unsigned char m_max_ranges; tree m_nonzero_mask; +protected: tree *m_base; }; // Here we describe an irange with N pairs of ranges. The storage for // the pairs is embedded in the class as an array. +// +// If RESIZABLE is true, the storage will be resized on the heap when +// the number of ranges needed goes past N up to a max of +// HARD_MAX_RANGES. This new storage is freed upon destruction. -template +template class GTY((user)) int_range : public irange { public: @@ -233,7 +242,7 @@ public: int_range (tree type); int_range (const int_range &); int_range (const irange &); - virtual ~int_range () = default; + virtual ~int_range (); int_range& operator= (const int_range &); private: template friend void gt_ggc_mx (int_range *); @@ -472,6 +481,38 @@ is_a (vrange &v) return v.m_discriminator == VR_FRANGE; } +// For resizable ranges, resize the range up to HARD_MAX_RANGES if the +// NEEDED pairs is greater than the current capacity of the range. + +inline void +irange::maybe_resize (int needed) +{ + if (!m_resizable || m_max_ranges == HARD_MAX_RANGES) + return; + + if (needed > m_max_ranges) + { + m_max_ranges = HARD_MAX_RANGES; + tree *newmem = new tree[m_max_ranges * 2]; + memcpy (newmem, m_base, sizeof (tree) * num_pairs () * 2); + m_base = newmem; + } +} + +template +inline +int_range::~int_range () +{ + if (RESIZABLE && m_base != m_ranges) + delete m_base; +} + +// This is an "infinite" precision irange for use in temporary +// calculations. It starts with a sensible default covering 99% of +// uses, and goes up to HARD_MAX_RANGES when needed. Any allocated +// storage is freed upon destruction. +typedef int_range<3, /*RESIZABLE=*/true> int_range_max; + class vrange_visitor { public: @@ -490,10 +531,6 @@ public: // There are copy operators to seamlessly copy to/fro multi-ranges. typedef int_range<1> value_range; -// This is an "infinite" precision irange for use in temporary -// calculations. -typedef int_range<255> int_range_max; - // This is an "infinite" precision range object for use in temporary // calculations for any of the handled types. The object can be // transparently used as a vrange. @@ -872,64 +909,65 @@ gt_pch_nx (int_range *x, gt_pointer_operator op, void *cookie) // Constructors for irange inline -irange::irange (tree *base, unsigned nranges) +irange::irange (tree *base, unsigned nranges, bool resizable) { m_discriminator = VR_IRANGE; m_base = base; m_max_ranges = nranges; + m_resizable = resizable; set_undefined (); } // Constructors for int_range<>. -template +template inline -int_range::int_range () - : irange (m_ranges, N) +int_range::int_range () + : irange (m_ranges, N, RESIZABLE) { } -template -int_range::int_range (const int_range &other) - : irange (m_ranges, N) +template +int_range::int_range (const int_range &other) + : irange (m_ranges, N, RESIZABLE) { irange::operator= (other); } -template -int_range::int_range (tree min, tree max, value_range_kind kind) - : irange (m_ranges, N) +template +int_range::int_range (tree min, tree max, value_range_kind kind) + : irange (m_ranges, N, RESIZABLE) { irange::set (min, max, kind); } -template -int_range::int_range (tree type) - : irange (m_ranges, N) +template +int_range::int_range (tree type) + : irange (m_ranges, N, RESIZABLE) { set_varying (type); } -template -int_range::int_range (tree type, const wide_int &wmin, const wide_int &wmax, +template +int_range::int_range (tree type, const wide_int &wmin, const wide_int &wmax, value_range_kind kind) - : irange (m_ranges, N) + : irange (m_ranges, N, RESIZABLE) { tree min = wide_int_to_tree (type, wmin); tree max = wide_int_to_tree (type, wmax); set (min, max, kind); } -template -int_range::int_range (const irange &other) - : irange (m_ranges, N) +template +int_range::int_range (const irange &other) + : irange (m_ranges, N, RESIZABLE) { irange::operator= (other); } -template -int_range& -int_range::operator= (const int_range &src) +template +int_range& +int_range::operator= (const int_range &src) { irange::operator= (src); return *this; -- 2.40.0