From patchwork Mon Aug 23 15:58:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1519807 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 (server2.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 (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GtcNr48mFz9s1l for ; Tue, 24 Aug 2021 01:58:52 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 113AC3853C2F for ; Mon, 23 Aug 2021 15:58:49 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 2FA723858C2C for ; Mon, 23 Aug 2021 15:58:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2FA723858C2C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: sourceware.org; spf=none smtp.mailfrom=kam.mff.cuni.cz Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id B251D2808BE; Mon, 23 Aug 2021 17:58:22 +0200 (CEST) Date: Mon, 23 Aug 2021 17:58:22 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Avoid redundant entries in modref's access lists Message-ID: <20210823155822.GA75373@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Status: No, score=-14.0 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, in PR101296 Richard noticed that modref is giving up on analysis in milc by hitting --param=modref-max-accesses limit. While cleaning up original modref patch I removed code that tried to do smart things while merging accesses because it had bugs and wanted to reimplement it later which I later forgot. This patch adds logic that avoids adding access and its subaccess to the list which is just waste of memory and compile time. Incrementally I will add logic merging the ranges. Bootstrapped/regtested x86_64-linux, comitted. Current cc1plus stats are Alias oracle query stats: refs_may_alias_p: 72546769 disambiguations, 82870545 queries ref_maybe_used_by_call_p: 497089 disambiguations, 73535250 queries call_may_clobber_ref_p: 259485 disambiguations, 263258 queries nonoverlapping_component_refs_p: 0 disambiguations, 38042 queries nonoverlapping_refs_since_match_p: 21125 disambiguations, 65780 must overlaps, 87810 queries aliasing_component_refs_p: 63132 disambiguations, 2186210 queries TBAA oracle: 26058958 disambiguations 61665515 queries 12157742 are in alias set 0 11350680 queries asked about the same object 144 queries asked about the same alias set 0 access volatile 10552147 are dependent in the DAG 1545844 are aritificially in conflict with void * Modref stats: modref use: 24018 disambiguations, 713486 queries modref clobber: 1400403 disambiguations, 17119339 queries 3473726 tbaa queries (0.202912 per modref query) 535259 base compares (0.031266 per modref query) PTA query stats: pt_solution_includes: 12436890 disambiguations, 20321783 queries pt_solutions_intersect: 1390457 disambiguations, 14654884 queries This is pretty much the same as last time I measured. This is bit of expected since we do not hit the limit on GCC very often. It is 43 times during cc1plus LTO build (release checking), however code that does a lot of array/fields initialization may hit the limit easily. gcc/ChangeLog: 2021-08-23 Jan Hubicka * ipa-modref-tree.h (modref_access_node::range_info_useful_p): Improve range compare. (modref_access_node::contains): New member function. (modref_access_node::search): Remove. (modref_access_node::insert): Be smarter about subaccesses. gcc/testsuite/ChangeLog: 2021-08-23 Jan Hubicka * gcc.dg/tree-ssa/modref-7.c: New test. diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h index d36c28c0470..2e26b75e21f 100644 --- a/gcc/ipa-modref-tree.h +++ b/gcc/ipa-modref-tree.h @@ -66,7 +66,10 @@ struct GTY(()) modref_access_node /* Return true if range info is useful. */ bool range_info_useful_p () const { - return parm_index != -1 && parm_offset_known; + return parm_index != -1 && parm_offset_known + && (known_size_p (size) + || known_size_p (max_size) + || known_ge (offset, 0)); } /* Return true if both accesses are the same. */ bool operator == (modref_access_node &a) const @@ -88,6 +91,35 @@ struct GTY(()) modref_access_node return false; return true; } + /* Return true A is a subaccess. */ + bool contains (modref_access_node &a) const + { + if (parm_index != a.parm_index) + return false; + if (parm_index >= 0) + { + if (parm_offset_known + && (!a.parm_offset_known + || !known_eq (parm_offset, a.parm_offset))) + return false; + } + if (range_info_useful_p ()) + { + if (!a.range_info_useful_p ()) + return false; + /* Sizes of stores are used to check that object is big enough + to fit the store, so smaller or unknown sotre is more general + than large store. */ + if (known_size_p (size) + && !known_le (size, a.size)) + return false; + if (known_size_p (max_size)) + return known_subrange_p (a.offset, a.max_size, offset, max_size); + else + return known_le (offset, a.offset); + } + return true; + } }; /* Access node specifying no useful info. */ @@ -107,17 +139,6 @@ struct GTY((user)) modref_ref_node accesses (NULL) {} - /* Search REF; return NULL if failed. */ - modref_access_node *search (modref_access_node access) - { - size_t i; - modref_access_node *a; - FOR_EACH_VEC_SAFE_ELT (accesses, i, a) - if (*a == access) - return a; - return NULL; - } - /* Collapse the tree. */ void collapse () { @@ -136,16 +157,36 @@ struct GTY((user)) modref_ref_node return false; /* Otherwise, insert a node for the ref of the access under the base. */ - modref_access_node *access_node = search (a); - if (access_node) - return false; + size_t i; + modref_access_node *a2; + + if (!a.useful_p ()) + { + if (!every_access) + { + collapse (); + return true; + } + return false; + } + + FOR_EACH_VEC_SAFE_ELT (accesses, i, a2) + { + if (a2->contains (a)) + return false; + if (a.contains (*a2)) + { + *a2 = a; + return true; + } + gcc_checking_assert (!(a == *a2)); + } /* If this base->ref pair has too many accesses stored, we will clear all accesses and bail out. */ - if ((accesses && accesses->length () >= max_accesses) - || !a.useful_p ()) + if (accesses && accesses->length () >= max_accesses) { - if (dump_file && a.useful_p ()) + if (dump_file) fprintf (dump_file, "--param param=modref-max-accesses limit reached\n"); collapse (); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modref-7.c b/gcc/testsuite/gcc.dg/tree-ssa/modref-7.c new file mode 100644 index 00000000000..53ffa1c394c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/modref-7.c @@ -0,0 +1,13 @@ +/* { dg-options "-O2 --param modref-max-accesses=1 -fdump-tree-modref1" } */ +/* { dg-do compile } */ +struct a { + int array[10]; + int tail; +}; +int test(struct a *a, int p) +{ + a->array[p] = 0; + a->array[0] = 1; +} +/* All three accesses combine to one bigger access. */ +/* { dg-final { scan-tree-dump-not "param=modref-max-accesses" "modref1" } } */