From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 3DBB73858410 for ; Thu, 9 May 2024 17:42:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3DBB73858410 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 3DBB73858410 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1715276571; cv=none; b=uy5amUvyEQbA0SwVopKICFPzPJayfTwqM9p7LVkG5j7h+qgIyDtxAjQ605ka550sz3dq15vuHbID/5U/ITLJARHtVx8pSnBjqEsc+mrthi9Mwsi5bPTj9gaWjrqp85D4zH4NpS4bB8+4+2ZQhY+ETo4DVV4Aq4But57VUs3zXFA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1715276571; c=relaxed/simple; bh=YrrBkwut7CPAx5dnVJ1VzQBFOXeD/NHUxdB7z0KD0gU=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=vxMEZBOmV05LVtDR20foziH/v0WRBbJdqHnk/UgkBmfLqTb2tYb2DxgeE9RnARVWKyP8EBb0fu3gTeh+Hqv928UIXejM6m/WKFDO6cDRhuPw7gmisrCTbuSYLlIFfHNXsS2ECUau1++y6qlP75WsyJuPa7tJ0ln0hFjsPvjvzWk= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1715276568; 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: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=g5uDvxM7qLh7vWUX04xYfqN85MQud5bQXFwoSmGxuiI=; b=MIPVYg0arEzI/vBFHz2hECRfHwMOLfGX3rNXbsYqF2akFPi+PD3jp6+pPtdS5iZNnQ/m3h UD4dUA5mVl2fKzXCioDAIsIKMc7oMnzyKJcPcvo0XZq1lgAyTt6/bcC6D25CrHqdESRJDX LhPyMpZMRS1galwcrRpuQhpi7q24hnw= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-683-J3rd4MrNNIS_gcrnaAMJEg-1; Thu, 09 May 2024 13:42:47 -0400 X-MC-Unique: J3rd4MrNNIS_gcrnaAMJEg-1 Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (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 mimecast-mx02.redhat.com (Postfix) with ESMTPS id 49681101A551 for ; Thu, 9 May 2024 17:42:47 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.22.18.2]) by smtp.corp.redhat.com (Postfix) with ESMTP id 2019F746821; Thu, 9 May 2024 17:42:47 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 01/21] analyzer: add caching to globals with initializers [PR110112] Date: Thu, 9 May 2024 13:42:16 -0400 Message-Id: <20240509174236.2278921-2-dmalcolm@redhat.com> In-Reply-To: <20240509174236.2278921-1-dmalcolm@redhat.com> References: <20240509174236.2278921-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-11.7 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 autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: PR analyzer/110112 notes that -fanalyzer is extremely slow on a source file with large read-only static arrays, repeatedly building the same compound_svalue representing the full initializer, and repeatedly building svalues representing parts of the the full initialiazer. This patch adds caches for both of these; together they reduce the time taken by -fanalyzer -O2 on the testcase in the bug for an optimized build: 91.2s : no caches (status quo) 32.4s : cache in decl_region::get_svalue_for_constructor 3.7s : cache in region::get_initial_value_at_main 3.1s : both caches (this patch) gcc/analyzer/ChangeLog: PR analyzer/110112 * region-model.cc (region_model::get_initial_value_for_global): Move code to region::calc_initial_value_at_main. * region.cc (region::get_initial_value_at_main): New function. (region::calc_initial_value_at_main): New function, based on code in region_model::get_initial_value_for_global. (region::region): Initialize m_cached_init_sval_at_main. (decl_region::get_svalue_for_constructor): Add a cache, splitting out body to... (decl_region::calc_svalue_for_constructor): ...this new function. * region.h (region::get_initial_value_at_main): New decl. (region::calc_initial_value_at_main): New decl. (region::m_cached_init_sval_at_main): New field. (decl_region::decl_region): Initialize m_ctor_svalue. (decl_region::calc_svalue_for_constructor): New decl. (decl_region::m_ctor_svalue): New field. (cherry picked from commit r14-1664-gfe9771b59f576f) Signed-off-by: David Malcolm --- gcc/analyzer/region-model.cc | 25 +------------ gcc/analyzer/region.cc | 71 +++++++++++++++++++++++++++++++++--- gcc/analyzer/region.h | 14 ++++++- 3 files changed, 79 insertions(+), 31 deletions(-) diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index fb81d43f91b..18996c5e5e8 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -2355,30 +2355,7 @@ region_model::get_initial_value_for_global (const region *reg) const the initial value of REG can be taken from the initialization value of the decl. */ if (called_from_main_p () || TREE_READONLY (decl)) - { - /* Attempt to get the initializer value for base_reg. */ - if (const svalue *base_reg_init - = base_reg->get_svalue_for_initializer (m_mgr)) - { - if (reg == base_reg) - return base_reg_init; - else - { - /* Get the value for REG within base_reg_init. */ - binding_cluster c (base_reg); - c.bind (m_mgr->get_store_manager (), base_reg, base_reg_init); - const svalue *sval - = c.get_any_binding (m_mgr->get_store_manager (), reg); - if (sval) - { - if (reg->get_type ()) - sval = m_mgr->get_or_create_cast (reg->get_type (), - sval); - return sval; - } - } - } - } + return reg->get_initial_value_at_main (m_mgr); /* Otherwise, return INIT_VAL(REG). */ return m_mgr->get_or_create_initial_value (reg); diff --git a/gcc/analyzer/region.cc b/gcc/analyzer/region.cc index a18bfa50d09..f982ce67509 100644 --- a/gcc/analyzer/region.cc +++ b/gcc/analyzer/region.cc @@ -272,6 +272,51 @@ region::can_have_initial_svalue_p () const } } +/* For regions within a global decl, get the svalue for the initial + value of this region when the program starts, caching the result. */ + +const svalue * +region::get_initial_value_at_main (region_model_manager *mgr) const +{ + if (!m_cached_init_sval_at_main) + m_cached_init_sval_at_main = calc_initial_value_at_main (mgr); + return m_cached_init_sval_at_main; +} + +/* Implementation of region::get_initial_value_at_main. */ + +const svalue * +region::calc_initial_value_at_main (region_model_manager *mgr) const +{ + const decl_region *base_reg = get_base_region ()->dyn_cast_decl_region (); + gcc_assert (base_reg); + + /* Attempt to get the initializer value for base_reg. */ + if (const svalue *base_reg_init + = base_reg->get_svalue_for_initializer (mgr)) + { + if (this == base_reg) + return base_reg_init; + else + { + /* Get the value for REG within base_reg_init. */ + binding_cluster c (base_reg); + c.bind (mgr->get_store_manager (), base_reg, base_reg_init); + const svalue *sval + = c.get_any_binding (mgr->get_store_manager (), this); + if (sval) + { + if (get_type ()) + sval = mgr->get_or_create_cast (get_type (), sval); + return sval; + } + } + } + + /* Otherwise, return INIT_VAL(REG). */ + return mgr->get_or_create_initial_value (this); +} + /* If this region is a decl_region, return the decl. Otherwise return NULL. */ @@ -701,7 +746,7 @@ region::is_named_decl_p (const char *decl_name) const region::region (complexity c, unsigned id, const region *parent, tree type) : m_complexity (c), m_id (id), m_parent (parent), m_type (type), - m_cached_offset (NULL) + m_cached_offset (NULL), m_cached_init_sval_at_main (NULL) { gcc_assert (type == NULL_TREE || TYPE_P (type)); } @@ -1170,14 +1215,13 @@ decl_region::maybe_get_constant_value (region_model_manager *mgr) const return NULL; } -/* Get an svalue for CTOR, a CONSTRUCTOR for this region's decl. */ +/* Implementation of decl_region::get_svalue_for_constructor + for when the cached value hasn't yet been calculated. */ const svalue * -decl_region::get_svalue_for_constructor (tree ctor, - region_model_manager *mgr) const +decl_region::calc_svalue_for_constructor (tree ctor, + region_model_manager *mgr) const { - gcc_assert (!TREE_CLOBBER_P (ctor)); - /* Create a binding map, applying ctor to it, using this decl_region as the base region when building child regions for offset calculations. */ @@ -1189,6 +1233,21 @@ decl_region::get_svalue_for_constructor (tree ctor, return mgr->get_or_create_compound_svalue (get_type (), map); } +/* Get an svalue for CTOR, a CONSTRUCTOR for this region's decl. */ + +const svalue * +decl_region::get_svalue_for_constructor (tree ctor, + region_model_manager *mgr) const +{ + gcc_assert (!TREE_CLOBBER_P (ctor)); + gcc_assert (ctor == DECL_INITIAL (m_decl)); + + if (!m_ctor_svalue) + m_ctor_svalue = calc_svalue_for_constructor (ctor, mgr); + + return m_ctor_svalue; +} + /* For use on decl_regions for global variables. Get an svalue for the initial value of this region at entry to diff --git a/gcc/analyzer/region.h b/gcc/analyzer/region.h index 5df0ae7487b..270e5042eeb 100644 --- a/gcc/analyzer/region.h +++ b/gcc/analyzer/region.h @@ -161,6 +161,7 @@ public: const frame_region *maybe_get_frame_region () const; enum memory_space get_memory_space () const; bool can_have_initial_svalue_p () const; + const svalue *get_initial_value_at_main (region_model_manager *mgr) const; tree maybe_get_decl () const; @@ -240,6 +241,7 @@ public: private: region_offset calc_offset (region_model_manager *mgr) const; + const svalue *calc_initial_value_at_main (region_model_manager *mgr) const; complexity m_complexity; unsigned m_id; // purely for deterministic sorting at this stage, for dumps @@ -247,6 +249,10 @@ public: tree m_type; mutable region_offset *m_cached_offset; + + /* For regions within a global decl, a cache of the svalue for the initial + value of this region when the program starts. */ + mutable const svalue *m_cached_init_sval_at_main; }; } // namespace ana @@ -696,7 +702,8 @@ class decl_region : public region public: decl_region (unsigned id, const region *parent, tree decl) : region (complexity (parent), id, parent, TREE_TYPE (decl)), m_decl (decl), - m_tracked (calc_tracked_p (decl)) + m_tracked (calc_tracked_p (decl)), + m_ctor_svalue (NULL) {} enum region_kind get_kind () const final override { return RK_DECL; } @@ -716,6 +723,8 @@ public: const svalue *get_svalue_for_initializer (region_model_manager *mgr) const; private: + const svalue *calc_svalue_for_constructor (tree ctor, + region_model_manager *mgr) const; static bool calc_tracked_p (tree decl); tree m_decl; @@ -725,6 +734,9 @@ private: store objects). This can be debugged using -fdump-analyzer-untracked. */ bool m_tracked; + + /* Cached result of get_svalue_for_constructor. */ + mutable const svalue *m_ctor_svalue; }; } // namespace ana -- 2.26.3