From patchwork Tue Sep 21 16:53:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1530811 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: 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=tDn0mNFY; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HDSHm72Vsz9shn for ; Wed, 22 Sep 2021 02:56:20 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2CF17385843A for ; Tue, 21 Sep 2021 16:56:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2CF17385843A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632243378; bh=DrTA6A1HiS6fZ2jg1CN8XeMzCSbMKPqQAo6bBcfcDF4=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=tDn0mNFY88I1ZYTqirPf2jFT1oL6NLOias5qeb8wVfl/77jWxkDbG0RsjzJzeJneo 826TzjZOZoB3JTrwEwgzN7sapplWNmNiQ1pmRcyJgO5Y/Fi2iv50h9YcR67h5Ms2YO 7+67vzpmFroGiA07Cn6J7PVsHPupMz2GyUBLK9NU= 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 ESMTP id 674A73858020 for ; Tue, 21 Sep 2021 16:54:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 674A73858020 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-192-SM5Y96_LNdqNafLmUzITZg-1; Tue, 21 Sep 2021 12:54:09 -0400 X-MC-Unique: SM5Y96_LNdqNafLmUzITZg-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 362FF1007249; Tue, 21 Sep 2021 16:54:08 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.248]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C0C201024888; Tue, 21 Sep 2021 16:54:07 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18LGs5aG414683 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 21 Sep 2021 18:54:05 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18LGs5Jr414682; Tue, 21 Sep 2021 18:54:05 +0200 To: Andrew MacLeod Subject: [PATCH 6/7] path solver: Add related SSAs to solvable set. Date: Tue, 21 Sep 2021 18:53:49 +0200 Message-Id: <20210921165350.414593-7-aldyh@redhat.com> In-Reply-To: <20210921165350.414593-1-aldyh@redhat.com> References: <20210921165350.414593-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 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_LOW, RCVD_IN_MSPIKE_H2, 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: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: GCC patches Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The path solver takes an initial set of SSA names which are deemed interesting. These are then solved along the path. Adding any copies of said SSA names to the list of interesting names yields significantly better results. This patch adds said copies to the already provided list. Currently this code is guarded by "m_resolve", which is the more expensive mode, but it would be reasonable to make it available always, especially since adding more imports usually has minimal impact on the processing time. I will investigate and make it universally available if this is indeed the case. Committed. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::add_to_imports): New. (path_range_query::add_copies_to_imports): New. (path_range_query::precompute_ranges): Call add_copies_to_imports. * gimple-range-path.h (class path_range_query): Add prototypes for add_copies_to_imports and add_to_imports. --- gcc/gimple-range-path.cc | 80 +++++++++++++++++++++++++++++++++++++++- gcc/gimple-range-path.h | 4 +- 2 files changed, 82 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index b86a76fa74b..a8ead3da4dc 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -343,6 +343,71 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) } } +// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS. + +bool +path_range_query::add_to_imports (tree name, bitmap imports) +{ + if (TREE_CODE (name) == SSA_NAME + && irange::supports_type_p (TREE_TYPE (name))) + return bitmap_set_bit (imports, SSA_NAME_VERSION (name)); + return false; +} + +// Add the copies of any SSA names in IMPORTS to IMPORTS. +// +// These are hints for the solver. Adding more elements (within +// reason) doesn't slow us down, because we don't solve anything that +// doesn't appear in the path. On the other hand, not having enough +// imports will limit what we can solve. + +void +path_range_query::add_copies_to_imports () +{ + auto_vec worklist (bitmap_count_bits (m_imports)); + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) + { + tree name = ssa_name (i); + worklist.quick_push (name); + } + + while (!worklist.is_empty ()) + { + tree name = worklist.pop (); + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + + if (is_gimple_assign (def_stmt)) + { + // ?? Adding assignment copies doesn't get us much. At the + // time of writing, we got 63 more threaded paths across the + // .ii files from a bootstrap. + add_to_imports (gimple_assign_rhs1 (def_stmt), m_imports); + tree rhs = gimple_assign_rhs2 (def_stmt); + if (rhs && add_to_imports (rhs, m_imports)) + worklist.safe_push (rhs); + rhs = gimple_assign_rhs3 (def_stmt); + if (rhs && add_to_imports (rhs, m_imports)) + worklist.safe_push (rhs); + } + else if (gphi *phi = dyn_cast (def_stmt)) + { + for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) + { + edge e = gimple_phi_arg_edge (phi, i); + tree arg = gimple_phi_arg (phi, i)->def; + + if (TREE_CODE (arg) == SSA_NAME + && m_path->contains (e->src) + && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg))) + worklist.safe_push (arg); + } + } + } +} + // Precompute the ranges for IMPORTS along PATH. // // IMPORTS are the set of SSA names, any of which could potentially @@ -353,11 +418,12 @@ path_range_query::precompute_ranges (const vec &path, const bitmap_head *imports) { set_path (path); - m_imports = imports; + bitmap_copy (m_imports, imports); m_undefined_path = false; if (m_resolve) { + add_copies_to_imports (); m_oracle->reset_path (); precompute_relations (path); } @@ -379,6 +445,18 @@ path_range_query::precompute_ranges (const vec &path, { basic_block bb = curr_bb (); + if (m_resolve) + { + gori_compute &gori = m_ranger.gori (); + tree name; + + // Exported booleans along the path, may help conditionals. + // Add them as interesting imports. + FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) + if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) + bitmap_set_bit (m_imports, SSA_NAME_VERSION (name)); + } + precompute_ranges_in_block (bb); adjust_for_non_null_uses (bb); diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index d12fd7743ca..f23cce18391 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -61,6 +61,8 @@ private: void ssa_range_in_phi (irange &r, gphi *phi); void precompute_relations (const vec &); void precompute_phi_relations (basic_block bb, basic_block prev); + void add_copies_to_imports (); + bool add_to_imports (tree name, bitmap imports); // Path navigation. void set_path (const vec &); @@ -82,7 +84,7 @@ private: // Path being analyzed. const vec *m_path; - const bitmap_head *m_imports; + auto_bitmap m_imports; gimple_ranger &m_ranger; non_null_ref m_non_null; path_oracle *m_oracle;