From patchwork Thu Nov 11 14:41:18 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 47475 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 615983857C66 for ; Thu, 11 Nov 2021 14:42:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 615983857C66 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1636641725; bh=P3OVZgzEIpVLJjjgLvxbcw3zILZBkJJiS/GUGnpBOSE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=DX+jCiaFWpGl+EO7t5aPk3Te7WW3+q9c5TrrACOAZhP8Rk3rVUmjF14pNEPmfuHkW Sg/M7LhB8nMbtFW3AGrJBRUlKWoOdwW7eAFaTv/rxJ4Y+nY5ck/AVYnQZQWEWOhp3d fovB2A/BtvAokINAmuI13ug8/8zZVavoVu3FgDzI= 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 2C00C385840A for ; Thu, 11 Nov 2021 14:41:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2C00C385840A 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-310-F0WD8EYfN0CJ2_olc2PWKg-1; Thu, 11 Nov 2021 09:41:32 -0500 X-MC-Unique: F0WD8EYfN0CJ2_olc2PWKg-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 8E20B1966325; Thu, 11 Nov 2021 14:41:31 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.226]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 1E88D18A8F; Thu, 11 Nov 2021 14:41:30 +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 1ABEfS26812869 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Thu, 11 Nov 2021 15:41:28 +0100 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 1ABEfRjD812868; Thu, 11 Nov 2021 15:41:27 +0100 To: GCC patches Subject: [COMMITTED] Move import population from threader to path solver. Date: Thu, 11 Nov 2021 15:41:18 +0100 Message-Id: <20211111144118.812688-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.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_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 Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Imports are our nomenclature for external SSA names to a block that are used to calculate the outgoing edges for said block. For example, in the following snippet: : _1 = b_10 == block_11; _2 = b_10 != -1; _3 = _1 & _2; if (_3 != 0) goto ; [INV] else goto ; [INV] ...the imports to the block are b_10 and block_11 since they are both needed to calculate _3. The path solver takes a bitmap of imports in addition to the path itself. This sets up the number of SSA names to be on the lookout for, while resolving the final conditional. Calculating these imports was initially done in the threader, since it was the only user of the path solver. With new clients, it has become obvious that populating the imports should be a task for the path solver, so it can be shared among the clients. This patch moves the import code to the solver, making both the solver and the threader simpler in the process. This is because intent is clearer and some duplicate code was removed. This reshuffling had the net effect of giving us a handful of new threads through my suite of .ii files (125). This was unexpected, but welcome nevertheless. There is no performance difference in callgrind over the same suite. Regstrapped on x86-64 Linux. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::add_copies_to_imports): Rename to... (path_range_query::compute_imports): ...this. Adapt it so it can be passed the imports bitmap instead of working on m_imports. (path_range_query::compute_ranges): Call compute_imports in all cases unless an imports bitmap is passed. * gimple-range-path.h (path_range_query::compute_imports): New. (path_range_query::add_copies_to_imports): Remove. * tree-ssa-threadbackward.c (back_threader::resolve_def): Remove. (back_threader::find_paths_to_names): Inline resolve_def. (back_threader::find_paths): Call compute_imports. (back_threader::resolve_phi): Adjust comment. --- gcc/gimple-range-path.cc | 45 ++++++++++++++++----------------- gcc/gimple-range-path.h | 2 +- gcc/tree-ssa-threadbackward.c | 47 ++++++----------------------------- 3 files changed, 30 insertions(+), 64 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 6da01c7067f..4843c133e62 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -439,26 +439,32 @@ path_range_query::add_to_imports (tree name, bitmap imports) return false; } -// Add the copies of any SSA names in IMPORTS to IMPORTS. +// Compute the imports to the path ending in EXIT. These are +// essentially the SSA names used to calculate the final conditional +// along the path. // -// 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. +// They are hints for the solver. Adding more elements 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 () +path_range_query::compute_imports (bitmap imports, basic_block exit) { - auto_vec worklist (bitmap_count_bits (m_imports)); + // Start with the imports from the exit block... + bitmap r_imports = m_ranger.gori ().imports (exit); + bitmap_copy (imports, r_imports); + + auto_vec worklist (bitmap_count_bits (imports)); bitmap_iterator bi; unsigned i; - - EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) + EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi) { tree name = ssa_name (i); worklist.quick_push (name); } + // ...and add any operands used to define these imports. while (!worklist.is_empty ()) { tree name = worklist.pop (); @@ -466,15 +472,12 @@ path_range_query::add_copies_to_imports () 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); + add_to_imports (gimple_assign_rhs1 (def_stmt), imports); tree rhs = gimple_assign_rhs2 (def_stmt); - if (rhs && add_to_imports (rhs, m_imports)) + if (rhs && add_to_imports (rhs, imports)) worklist.safe_push (rhs); rhs = gimple_assign_rhs3 (def_stmt); - if (rhs && add_to_imports (rhs, m_imports)) + if (rhs && add_to_imports (rhs, imports)) worklist.safe_push (rhs); } else if (gphi *phi = dyn_cast (def_stmt)) @@ -486,7 +489,7 @@ path_range_query::add_copies_to_imports () if (TREE_CODE (arg) == SSA_NAME && m_path.contains (e->src) - && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg))) + && bitmap_set_bit (imports, SSA_NAME_VERSION (arg))) worklist.safe_push (arg); } } @@ -512,16 +515,10 @@ path_range_query::compute_ranges (const vec &path, if (imports) bitmap_copy (m_imports, imports); else - { - bitmap imports = m_ranger.gori ().imports (exit_bb ()); - bitmap_copy (m_imports, imports); - } + compute_imports (m_imports, exit_bb ()); if (m_resolve) - { - add_copies_to_imports (); - get_path_oracle ()->reset_path (); - } + get_path_oracle ()->reset_path (); if (DEBUG_SOLVER) { diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index b73549f01a5..b5a054359ad 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -36,6 +36,7 @@ public: virtual ~path_range_query (); void compute_ranges (const vec &, const bitmap_head *imports = NULL); void compute_ranges (edge e); + void compute_imports (bitmap imports, basic_block exit); bool range_of_expr (irange &r, tree name, gimple * = NULL) override; bool range_of_stmt (irange &r, gimple *, tree name = NULL) override; bool unreachable_path_p (); @@ -61,7 +62,6 @@ private: void compute_outgoing_relations (basic_block bb, basic_block next); void compute_phi_relations (basic_block bb, basic_block prev); void maybe_register_phi_relation (gphi *, tree arg); - void add_copies_to_imports (); bool add_to_imports (tree name, bitmap imports); inline bool import_p (tree name); diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 0f7b4a732eb..d067c470c38 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -91,7 +91,6 @@ private: edge maybe_register_path (); void maybe_register_path_dump (edge taken_edge); void find_paths_to_names (basic_block bb, bitmap imports); - bool resolve_def (tree name, bitmap interesting, vec &worklist); void resolve_phi (gphi *phi, bitmap imports); edge find_taken_edge (const vec &path); edge find_taken_edge_cond (const vec &path, gcond *); @@ -363,12 +362,8 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting) edge e = gimple_phi_arg_edge (phi, i); // This is like path_crosses_loops in profitable_path_p but more - // restrictive, since profitable_path_p allows threading the - // first block because it would be redirected anyhow. - // - // If we loosened the restriction and used profitable_path_p() - // here instead, we would peel off the first iterations of loops - // in places like tree-ssa/pr14341.c. + // restrictive to avoid peeling off loop iterations (see + // tree-ssa/pr14341.c for an example). bool profitable_p = m_path[0]->loop_father == e->src->loop_father; if (!profitable_p) { @@ -404,33 +399,6 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting) } } -// If the definition of NAME causes the final conditional of the -// current path to be constant, register the path, and return TRUE. - -bool -back_threader::resolve_def (tree name, bitmap interesting, vec &worklist) -{ - gimple *def_stmt = SSA_NAME_DEF_STMT (name); - - // Handle PHIs. - if (is_a (def_stmt)) - { - resolve_phi (as_a (def_stmt), interesting); - return true; - } - - // Defer copies of SSAs by adding the source to the worklist. - if (gimple_assign_single_p (def_stmt) - && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME) - { - tree rhs = gimple_assign_rhs1 (def_stmt); - bitmap_set_bit (m_imports, SSA_NAME_VERSION (rhs)); - bitmap_set_bit (interesting, SSA_NAME_VERSION (rhs)); - worklist.safe_push (rhs); - } - return false; -} - // Find jump threading paths to any of the SSA names in the // INTERESTING bitmap, and register any such paths. // @@ -464,13 +432,15 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting) { tree name = worklist.pop (); unsigned i = SSA_NAME_VERSION (name); - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + gimple *def_stmt = SSA_NAME_DEF_STMT (name); + basic_block def_bb = gimple_bb (def_stmt); - // Process any names defined in this block. + // Process any PHIs defined in this block. if (def_bb == bb && bitmap_set_bit (processed, i) - && resolve_def (name, interesting, worklist)) + && gimple_code (def_stmt) == GIMPLE_PHI) { + resolve_phi (as_a (def_stmt), interesting); done = true; break; } @@ -515,10 +485,9 @@ back_threader::find_paths (basic_block bb, tree name) m_visited_bbs.empty (); m_path.truncate (0); m_name = name; - bitmap_clear (m_imports); + m_solver->compute_imports (m_imports, bb); auto_bitmap interesting; - bitmap_copy (m_imports, m_ranger->gori ().imports (bb)); bitmap_copy (interesting, m_imports); find_paths_to_names (bb, interesting); }