From patchwork Tue Sep 26 18:06:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1839878 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=SVMDwR7y; dkim-atps=neutral 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=patchwork.ozlabs.org) 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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Rw73Q2f1fz1yp0 for ; Wed, 27 Sep 2023 04:06:26 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CDFCA3860769 for ; Tue, 26 Sep 2023 18:06:23 +0000 (GMT) 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.133.124]) by sourceware.org (Postfix) with ESMTPS id 02650385B530 for ; Tue, 26 Sep 2023 18:06:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 02650385B530 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1695751568; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=Bu7pBZVv5tU4925QfVhLCbsUAbcHedT7J/Y5I+6w8wo=; b=SVMDwR7yICYpOEMjwm/7g+CFFOM+42yTqJqsK3Do/aa8I+v6wJbDFMWyhSQiE2Zjn8MB6M i+eivC267EGHzfVdzdbborcGAYQjn1wgzUqmEqo7zqP8dOE0BW81qLGGi3t7o8EOAeQfz0 Y9YmuCooedmZOCx/pkfYVqDy1SUEbac= Received: from mail-oa1-f71.google.com (mail-oa1-f71.google.com [209.85.160.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-692-gs9Q-Ub8OSmX9ryZzfM7Yg-1; Tue, 26 Sep 2023 14:06:07 -0400 X-MC-Unique: gs9Q-Ub8OSmX9ryZzfM7Yg-1 Received: by mail-oa1-f71.google.com with SMTP id 586e51a60fabf-1dd31b52af3so10104345fac.3 for ; Tue, 26 Sep 2023 11:06:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695751566; x=1696356366; 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=xZjAy4VJuoFPZQXJIUqoTYdxOuqHp/IFpL7dMtCJwSI=; b=Eo0aqnj3hbFny84gbtn5c95nFOxx8nHlZftSMe2HtaEJLxuClTeUDPdXi1Y8XG0VS0 VpycEN8S9FMK2HVhFUS3h0ZZuoLx19+ugQpz2yN2KsOZcTRFEry4GpUjTlJB/hrjfx/p lkglccpf+0AlduCN2o8zxdBRUXH4UYLLc5FS0LZ6pMLtOxmXcMm6qacyubFWT2gjduRg 5OCjgNtIaqQusZ1Lt6NmftY5moZF5KhMjJjUqxB/s49FmPHGew2yYT8oPtFE9Bwp3bc1 DQ9fwR+gyqwnulKlTvJZ1SgbaKwH9NjCFh/HyvCaebIB/JSm3VD0OUUnQFuHzHREyx6c SiEg== X-Gm-Message-State: AOJu0YxetvZ6mzb6tscGyZYz2aH5JoV4/p+/kG3yt45VY6/N0prs8lhP oU8bRgs8GxTZfGzRslL5HBBuxiU2fKe+xvcuTA251fmQFEdiOVlBcBgjoFcAM5sYQARau+LkpzY 6kWuq8NzPF1RZmAYdlMM+3QtVDwDihxWDQVj+ASczdANFsGdwXGNqPlPHZG8vdLcVdYbXA+Tgtp 4xOw== X-Received: by 2002:a05:6870:7811:b0:1dd:67b7:2ce6 with SMTP id hb17-20020a056870781100b001dd67b72ce6mr2869937oab.58.1695751565800; Tue, 26 Sep 2023 11:06:05 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFGP5GW57mW4X9iTS1AH/AtkUrxF/zdlzFgCRx491mD8Y6QwTKT4F6PgHEGoEu0Wp7T/6EXPg== X-Received: by 2002:a05:6870:7811:b0:1dd:67b7:2ce6 with SMTP id hb17-20020a056870781100b001dd67b72ce6mr2869909oab.58.1695751565413; Tue, 26 Sep 2023 11:06:05 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id ph7-20020a0562144a4700b00655ebd053dcsm4126012qvb.82.2023.09.26.11.06.04 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 26 Sep 2023 11:06:04 -0700 (PDT) Message-ID: <1a8e843d-3289-3319-1dd1-53e790ba60d9@redhat.com> Date: Tue, 26 Sep 2023 14:06:07 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: gcc-patches Cc: "hernandez, aldy" From: Andrew MacLeod Subject: [COMMITTED][GCC13] PR tree-optimization/110315 - Reduce the initial size of int_range_max. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.3 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_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org This patch adds the ability to resize ranges as needed, defaulting to no resizing.  int_range_max now defaults to 3 sub-ranges (instead of 255) and grows to 255 when the range being calculated does not fit. Bootstraps on x86_64-pc-linux-gnu with no regressions.   Pushed. Andrew From 70639014a69cf50fe11dc1adbfe1db4c7760ce69 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 26 Sep 2023 09:44:39 -0400 Subject: [PATCH] Reduce the initial size of int_range_max. This patch adds the ability to resize ranges as needed, defaulting to no resizing. int_range_max now defaults to 3 sub-ranges (instead of 255) and grows to 255 when the range being calculated does not fit. PR tree-optimization/110315 * value-range-storage.h (vrange_allocator::alloc_irange): Adjust new params. * value-range.cc (irange::operator=): Resize range. (irange::irange_union): Same. (irange::irange_intersect): Same. (irange::invert): Same. * value-range.h (irange::maybe_resize): New. (~int_range): New. (int_range_max): Default to 3 sub-ranges and resize as needed. (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.41.0