From patchwork Sun Jul 3 06:44:22 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1651552 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=ghNX6NwB; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (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 4LbKDp5Hhdz9s07 for ; Sun, 3 Jul 2022 16:44:57 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DF4993851154 for ; Sun, 3 Jul 2022 06:44:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DF4993851154 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1656830693; bh=7bN6hKf4wn2Kt5lK+JDorrbzWIriRx6z0iyjSN/dLls=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=ghNX6NwBcQ5AoNQ8lHx1a5Rdg0N/C+Ldq6f9bhEIv5WEv0ruCqxGQ559d8IqyGqWv 2SSRq2Z7y9ecTqWBo9LEiDWDoLQ9S7rpmDi2R0/ZGTkfG3G7zTiE3zaDv4Q3/DNmcp EJ4rsmC5KVjetzTzYPdy07urM8ScUW4QB+V4NgZ4= 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 BD3113858284 for ; Sun, 3 Jul 2022 06:44:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BD3113858284 Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-425-Df_mZwIkO4611CMs9twucA-1; Sun, 03 Jul 2022 02:44:30 -0400 X-MC-Unique: Df_mZwIkO4611CMs9twucA-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id D732529AA382 for ; Sun, 3 Jul 2022 06:44:29 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.44]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 427EA1121314; Sun, 3 Jul 2022 06:44:29 +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 2636iQr2375797 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sun, 3 Jul 2022 08:44:26 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 2636iQf9375796; Sun, 3 Jul 2022 08:44:26 +0200 To: GCC patches Subject: [COMMITTED] Implement class vrange_storage to stream ranges to long term memory. Date: Sun, 3 Jul 2022 08:44:22 +0200 Message-Id: <20220703064422.375780-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.78 on 10.11.54.3 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, 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 Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch implements a storage class that will be used to stream out ranges to long term storage, initially in SSA_NAME_RANGE_INFO, but it is flexible enough to use with our obstack allocator. For instance, in the future we could use it in the ranger cache to save memory. The current size of range_info_def which is used in SSA_NAME_RANGE_INFO is 16 bytes. With this patch, the size of the slot (irange_storage_slot) will be 24 bytes. But we'll have the ability to be able to store up to 5 pairs of sub-ranges if necessary. If we ever need to save more (say for switches), we could explore a trailing_wide_ints structure with a pointer to the m_len[N] bits as Jakub has suggested. In follow-up patches I will contribute the SSA_NAME_RANGE_INFO changes as well as changes storing the nonzero bits within an irange. For reference, the main interface is rather simple: class vrange_storage { public: vrange_storage (vrange_allocator *alloc) : m_alloc (alloc) { } void *alloc_slot (const vrange &r); void free (void *slot); void get_vrange (const void *slot, vrange &r, tree type); void set_vrange (void *slot, const vrange &r); static bool fits_p (const void *slot, const vrange &r); }; The above class will have the knowledge to stream out the different ranges we support (currently only irange_storage_slot). As has been discussed, the irange storage will use trailing wide ints: class GTY ((variable_size)) irange_storage_slot { // This is the maximum number of wide_int's allowed in the trailing // ints structure, without going over 16 bytes (128 bits) in the // control word that preceeds the HOST_WIDE_INTs in // trailing_wide_ints::m_val[]. static const unsigned MAX_INTS = 12; // Maximum number of range pairs we can handle, considering the // nonzero bits take one wide_int. static const unsigned MAX_PAIRS = (MAX_INTS - 1) / 2; trailing_wide_ints m_ints; }; Tested on x86-64 Linux. gcc/ChangeLog: * Makefile.in (OBJS): Add value-range-storage.o. (GTFILES): Add value-range-storage.h. * gengtype.cc (open_base_files): Add value-range-storage.h. * value-range-storage.cc: New file. * value-range-storage.h: New file. --- gcc/Makefile.in | 2 + gcc/gengtype.cc | 1 + gcc/value-range-storage.cc | 212 +++++++++++++++++++++++++++++++++++++ gcc/value-range-storage.h | 85 +++++++++++++++ 4 files changed, 300 insertions(+) create mode 100644 gcc/value-range-storage.cc create mode 100644 gcc/value-range-storage.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 69ac81a1e45..3ae23702426 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1711,6 +1711,7 @@ OBJS = \ value-query.o \ value-range.o \ value-range-equiv.o \ + value-range-storage.o \ value-relation.o \ value-prof.o \ var-tracking.o \ @@ -2719,6 +2720,7 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/tree-ssanames.h \ $(srcdir)/tree-vrp.h \ $(srcdir)/value-range.h \ + $(srcdir)/value-range-storage.h \ $(srcdir)/ipa-prop.h \ $(srcdir)/trans-mem.cc \ $(srcdir)/lto-streamer.h \ diff --git a/gcc/gengtype.cc b/gcc/gengtype.cc index 19676251fdb..42363439bd8 100644 --- a/gcc/gengtype.cc +++ b/gcc/gengtype.cc @@ -1705,6 +1705,7 @@ open_base_files (void) "stmt.h", "expr.h", "alloc-pool.h", "cselib.h", "insn-addr.h", "optabs.h", "libfuncs.h", "debug.h", "internal-fn.h", "gimple-iterator.h", "gimple-fold.h", "value-range.h", + "value-range-storage.h", "tree-eh.h", "gimple-ssa.h", "tree-cfg.h", "tree-vrp.h", "tree-phinodes.h", "ssa-iterators.h", "stringpool.h", "tree-ssanames.h", "tree-ssa-loop.h", "tree-ssa-loop-ivopts.h", diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc new file mode 100644 index 00000000000..ea9b18f993b --- /dev/null +++ b/gcc/value-range-storage.cc @@ -0,0 +1,212 @@ +/* Support routines for vrange storage. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "tree-pretty-print.h" +#include "fold-const.h" +#include "gimple-range.h" +#include "value-range-storage.h" + +// Return a newly allocated slot holding R. + +void * +vrange_storage::alloc_slot (const vrange &r) +{ + gcc_checking_assert (m_alloc); + + if (is_a (r)) + return irange_storage_slot::alloc_slot (*m_alloc, as_a (r)); + + gcc_unreachable (); + return NULL; +} + +// Set SLOT to R. + +void +vrange_storage::set_vrange (void *slot, const vrange &r) +{ + if (is_a (r)) + { + irange_storage_slot *s = static_cast (slot); + gcc_checking_assert (s->fits_p (as_a (r))); + s->set_irange (as_a (r)); + } + else + gcc_unreachable (); +} + +// Restore R from SLOT. TYPE is the type of R. + +void +vrange_storage::get_vrange (const void *slot, vrange &r, tree type) +{ + if (is_a (r)) + { + const irange_storage_slot *s + = static_cast (slot); + s->get_irange (as_a (r), type); + } + else + gcc_unreachable (); +} + +// Return TRUE if SLOT can fit R. + +bool +vrange_storage::fits_p (const void *slot, const vrange &r) +{ + if (is_a (r)) + { + const irange_storage_slot *s + = static_cast (slot); + return s->fits_p (as_a (r)); + } + gcc_unreachable (); + return false; +} + +// Factory that creates a new irange_storage_slot object containing R. +// This is the only way to construct an irange slot as stack creation +// is disallowed. + +irange_storage_slot * +irange_storage_slot::alloc_slot (vrange_allocator &allocator, const irange &r) +{ + size_t size = irange_storage_slot::size (r); + irange_storage_slot *p + = static_cast (allocator.alloc (size)); + new (p) irange_storage_slot (r); + return p; +} + +// Initialize the current slot with R. + +irange_storage_slot::irange_storage_slot (const irange &r) +{ + gcc_checking_assert (!r.undefined_p ()); + + unsigned prec = TYPE_PRECISION (r.type ()); + unsigned n = num_wide_ints_needed (r); + if (n > MAX_INTS) + { + int_range squash (r); + m_ints.set_precision (prec, num_wide_ints_needed (squash)); + set_irange (squash); + } + else + { + m_ints.set_precision (prec, n); + set_irange (r); + } +} + +// Store R into the current slot. + +void +irange_storage_slot::set_irange (const irange &r) +{ + gcc_checking_assert (fits_p (r)); + + //m_ints[0] = r.get_nonzero_bits (); + unsigned pairs = r.num_pairs (); + for (unsigned i = 0; i < pairs; ++i) + { + m_ints[i*2 + 1] = r.lower_bound (i); + m_ints[i*2 + 2] = r.upper_bound (i); + } +} + +// Restore a range of TYPE from the current slot into R. + +void +irange_storage_slot::get_irange (irange &r, tree type) const +{ + gcc_checking_assert (TYPE_PRECISION (type) == m_ints.get_precision ()); + + r.set_undefined (); + unsigned nelements = m_ints.num_elements (); + for (unsigned i = 1; i < nelements; i += 2) + { + int_range<2> tmp (type, m_ints[i], m_ints[i + 1]); + r.union_ (tmp); + } + //r.set_nonzero_bits (get_nonzero_bits ()); +} + +// Return the size in bytes to allocate a slot that can hold R. + +size_t +irange_storage_slot::size (const irange &r) +{ + gcc_checking_assert (!r.undefined_p ()); + + unsigned prec = TYPE_PRECISION (r.type ()); + unsigned n = num_wide_ints_needed (r); + if (n > MAX_INTS) + n = MAX_INTS; + return (sizeof (irange_storage_slot) + + trailing_wide_ints::extra_size (prec, n)); +} + +// Return the number of wide ints needed to represent R. + +unsigned int +irange_storage_slot::num_wide_ints_needed (const irange &r) +{ + return r.num_pairs () * 2 + 1; +} + +// Return TRUE if R fits in the current slot. + +bool +irange_storage_slot::fits_p (const irange &r) const +{ + return m_ints.num_elements () >= num_wide_ints_needed (r); +} + +// Dump the current slot. + +void +irange_storage_slot::dump () const +{ + fprintf (stderr, "raw irange_storage_slot:\n"); + for (unsigned i = 1; i < m_ints.num_elements (); i += 2) + { + m_ints[i].dump (); + m_ints[i + 1].dump (); + } + fprintf (stderr, "NONZERO "); + wide_int nz = get_nonzero_bits (); + nz.dump (); +} + +DEBUG_FUNCTION void +debug (const irange_storage_slot &storage) +{ + storage.dump (); + fprintf (stderr, "\n"); +} diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h new file mode 100644 index 00000000000..58c5e114320 --- /dev/null +++ b/gcc/value-range-storage.h @@ -0,0 +1,85 @@ +/* Support routines for vrange storage. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_VALUE_RANGE_STORAGE_H +#define GCC_VALUE_RANGE_STORAGE_H + +// This class is used to allocate chunks of memory that can store +// ranges as memory efficiently as possible. It is meant to be used +// when long term storage of a range is needed. The class can be used +// with any vrange_allocator (i.e. alloca or GC). + +class vrange_storage +{ +public: + vrange_storage (vrange_allocator *alloc) : m_alloc (alloc) { } + void *alloc_slot (const vrange &r); + void free (void *slot) { m_alloc->free (slot); } + void get_vrange (const void *slot, vrange &r, tree type); + void set_vrange (void *slot, const vrange &r); + static bool fits_p (const void *slot, const vrange &r); +private: + DISABLE_COPY_AND_ASSIGN (vrange_storage); + vrange_allocator *m_alloc; +}; + + +// INTERNAL USE ONLY. The remaining interfaces are only exposed for +// the GTY machinery to play nice with tree_ssa_name. + +// A chunk of memory pointing to an irange storage. + +class GTY ((variable_size)) irange_storage_slot +{ +public: + static irange_storage_slot *alloc_slot (vrange_allocator &, const irange &r); + void set_irange (const irange &r); + void get_irange (irange &r, tree type) const; + wide_int get_nonzero_bits () const { return m_ints[0]; } + bool fits_p (const irange &r) const; + static size_t size (const irange &r); + void dump () const; +private: + DISABLE_COPY_AND_ASSIGN (irange_storage_slot); + friend void gt_ggc_mx_irange_storage_slot (void *); + friend void gt_pch_p_19irange_storage_slot (void *, void *, + gt_pointer_operator, void *); + friend void gt_pch_nx_irange_storage_slot (void *); + + // This is the maximum number of wide_int's allowed in the trailing + // ints structure, without going over 16 bytes (128 bits) in the + // control word that preceeds the HOST_WIDE_INTs in + // trailing_wide_ints::m_val[]. + static const unsigned MAX_INTS = 12; + + // Maximum number of range pairs we can handle, considering the + // nonzero bits take one wide_int. + static const unsigned MAX_PAIRS = (MAX_INTS - 1) / 2; + + // Constructor is private to disallow stack initialization. Use + // alloc_slot() to create objects. + irange_storage_slot (const irange &r); + + static unsigned num_wide_ints_needed (const irange &r); + + trailing_wide_ints m_ints; +}; + +#endif // GCC_VALUE_RANGE_STORAGE_H