From patchwork Wed Oct 27 18:13:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 46707 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 5F667385841A for ; Wed, 27 Oct 2021 18:14:23 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5F667385841A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1635358463; bh=LfWVJ94mgutqlz2Ixbhh9j/Qn2bTCzaoUU+yOnwWmgM=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=sAUGELU+qDm1oeKzmQK6XBi1v68O0GEABccx/UQDHQo06FQ3Z4wJhfnJ1sJE1opPJ ydI/lqsqIhvG9/fcSJWj0nPdN8XvxuxMAm+DqD4X+nSBVGqgOQyGhBRERVzbgt7QqR Syl4yJX00Si8/6sj/Zg6y7OBjOsTiSAvmypHN2lo= 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 712023858C27 for ; Wed, 27 Oct 2021 18:13:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 712023858C27 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-104-QB91loG-PueSLGosSuYJ1g-1; Wed, 27 Oct 2021 14:13:51 -0400 X-MC-Unique: QB91loG-PueSLGosSuYJ1g-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 2D77DA0BC4 for ; Wed, 27 Oct 2021 18:13:50 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.193]) by smtp.corp.redhat.com (Postfix) with ESMTPS id B7E0813ABD; Wed, 27 Oct 2021 18:13:49 +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 19RIDlxh395816 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 27 Oct 2021 20:13:47 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 19RIDlP4395815; Wed, 27 Oct 2021 20:13:47 +0200 To: GCC patches Subject: [COMMITTED] Reorder relation calculating code in the path solver. Date: Wed, 27 Oct 2021 20:13:22 +0200 Message-Id: <20211027181323.395724-2-aldyh@redhat.com> In-Reply-To: <20211027181323.395724-1-aldyh@redhat.com> References: <20211027181323.395724-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.0 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" Enabling the fully resolving threader triggers various relation ordering issues that have previously been dormant because the VRP hybrid threader (forward threader based) never gives us long enough paths for this to matter. The new threader spares no punches in finding non-obvious paths, so getting the relations right is paramount. This patch fixes a couple oversights that have gone undetected. First, some background. There are 3 types of relations along a path: a) Relations inherent in a PHI. b) Relations as a side-effect of evaluating a statement. c) Outgoing relations between blocks in a path. We must calculate these in their proper order, otherwise we can run into ordering issues. The current ordering is wrong, as we precalculate PHIs for _all_ blocks before anything else, and then proceed to register the relations throughout the path. Also, we fail to realize that a PHI whose argument is also defined in the PHIs block cannot be registered as an equivalence without causing more ordering issues. This patch fixes all the problems described above. With it we get a handful more net threads, but most importantly, we disallow some threads that were wrong. Tested on x86-64 and ppc64le Linux on the usual regstrap, plus by comparing the different thread counts before and after this patch. gcc/ChangeLog: * gimple-range-fold.cc (fold_using_range::range_of_range_op): Dump operands as well as relation. * gimple-range-path.cc (path_range_query::compute_ranges_in_block): Compute PHI relations first. Compute outgoing relations at the end. (path_range_query::compute_ranges): Remove call to compute_relations. (path_range_query::compute_relations): Remove. (path_range_query::maybe_register_phi_relation): New. (path_range_query::compute_phi_relations): Abstract out registering one PHI relation to... (path_range_query::compute_outgoing_relations): ...here. * gimple-range-path.h (class path_range_query): Remove compute_relations. Add maybe_register_phi_relation. --- gcc/gimple-range-fold.cc | 2 + gcc/gimple-range-path.cc | 107 ++++++++++++++++++++------------------- gcc/gimple-range-path.h | 3 +- 3 files changed, 58 insertions(+), 54 deletions(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index ed2fbe121cf..2fab904e6b0 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -620,7 +620,9 @@ fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src) if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_NONE) { fprintf (dump_file, " folding with relation "); + print_generic_expr (dump_file, op1, TDF_SLIM); print_relation (dump_file, rel); + print_generic_expr (dump_file, op2, TDF_SLIM); fputc ('\n', dump_file); } // Fold range, and register any dependency if available. diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 557338993ae..2f570a13e05 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -316,6 +316,9 @@ path_range_query::compute_ranges_in_block (basic_block bb) int_range_max r, cached_range; unsigned i; + if (m_resolve && !at_entry ()) + compute_phi_relations (bb, prev_bb ()); + // Force recalculation of any names in the cache that are defined in // this block. This can happen on interdependent SSA/phis in loops. EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) @@ -341,7 +344,8 @@ path_range_query::compute_ranges_in_block (basic_block bb) return; // Solve imports that are exported to the next block. - edge e = find_edge (bb, next_bb ()); + basic_block next = next_bb (); + edge e = find_edge (bb, next); EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) { tree name = ssa_name (i); @@ -369,6 +373,9 @@ path_range_query::compute_ranges_in_block (basic_block bb) } } } + + if (m_resolve) + compute_outgoing_relations (bb, next); } // Adjust all pointer imports in BB with non-null information. @@ -485,7 +492,6 @@ path_range_query::compute_ranges (const vec &path, { add_copies_to_imports (); get_path_oracle ()->reset_path (); - compute_relations (path); } if (DEBUG_SOLVER) @@ -527,7 +533,12 @@ path_range_query::compute_ranges (const vec &path, } if (DEBUG_SOLVER) - dump (dump_file); + { + fprintf (dump_file, "\npath_oracle:\n"); + get_path_oracle ()->dump (dump_file); + fprintf (dump_file, "\n"); + dump (dump_file); + } } // A folding aid used to register and query relations along a path. @@ -624,49 +635,23 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) return true; } -// Compute relations on a path. This involves two parts: relations -// along the conditionals joining a path, and relations determined by -// examining PHIs. - void -path_range_query::compute_relations (const vec &path) +path_range_query::maybe_register_phi_relation (gphi *phi, tree arg) { - if (!dom_info_available_p (CDI_DOMINATORS)) - return; + basic_block bb = gimple_bb (phi); + tree result = gimple_phi_result (phi); + gimple *def = SSA_NAME_DEF_STMT (arg); - jt_fur_source src (NULL, this, &m_ranger.gori (), path); - basic_block prev = NULL; - for (unsigned i = path.length (); i > 0; --i) - { - basic_block bb = path[i - 1]; - gimple *stmt = last_stmt (bb); + // Avoid recording the equivalence if the arg is defined in this + // block, as that would create an ordering problem. + if (def && gimple_bb (def) == bb) + return; - compute_phi_relations (bb, prev); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " from bb%d:", bb->index); - // Compute relations in outgoing edges along the path. Skip the - // final conditional which we don't know yet. - if (i > 1 - && stmt - && gimple_code (stmt) == GIMPLE_COND - && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt)))) - { - basic_block next = path[i - 2]; - int_range<2> r; - gcond *cond = as_a (stmt); - edge e0 = EDGE_SUCC (bb, 0); - edge e1 = EDGE_SUCC (bb, 1); - - if (e0->dest == next) - gcond_edge_range (r, e0); - else if (e1->dest == next) - gcond_edge_range (r, e1); - else - gcc_unreachable (); - - src.register_outgoing_edges (cond, r, e0, e1); - } - prev = bb; - } + get_path_oracle ()->killing_def (result); + m_oracle->register_relation (entry_bb (), EQ_EXPR, arg, result); } // Compute relations for each PHI in BB. For example: @@ -681,15 +666,12 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev) if (prev == NULL) return; - basic_block entry = entry_bb (); edge e_in = find_edge (prev, bb); - gcc_checking_assert (e_in); for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter)) { gphi *phi = iter.phi (); - tree result = gimple_phi_result (phi); unsigned nargs = gimple_phi_num_args (phi); for (size_t i = 0; i < nargs; ++i) @@ -698,17 +680,36 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev) tree arg = gimple_phi_arg_def (phi, i); if (gimple_range_ssa_p (arg)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " from bb%d:", bb->index); + maybe_register_phi_relation (phi, arg); + break; + } + } +} - // Throw away any previous relation. - get_path_oracle ()->killing_def (result); +// Compute outgoing relations from BB to NEXT. - m_oracle->register_relation (entry, EQ_EXPR, arg, result); - } +void +path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) +{ + gimple *stmt = last_stmt (bb); - break; - } + if (stmt + && gimple_code (stmt) == GIMPLE_COND + && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt)))) + { + int_range<2> r; + gcond *cond = as_a (stmt); + edge e0 = EDGE_SUCC (bb, 0); + edge e1 = EDGE_SUCC (bb, 1); + + if (e0->dest == next) + gcond_edge_range (r, e0); + else if (e1->dest == next) + gcond_edge_range (r, e1); + else + gcc_unreachable (); + + jt_fur_source src (NULL, this, &m_ranger.gori (), *m_path); + src.register_outgoing_edges (cond, r, e0, e1); } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 5f4e73a5949..541613956e1 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -57,8 +57,9 @@ private: void compute_ranges_in_block (basic_block bb); void adjust_for_non_null_uses (basic_block bb); void ssa_range_in_phi (irange &r, gphi *phi); - void compute_relations (const vec &); + 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);