From patchwork Fri Jan 21 08:29:02 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 50299 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 7FAEA385840D for ; Fri, 21 Jan 2022 08:30:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7FAEA385840D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1642753813; bh=vmO9E7VgIEOTjyRiGZqHpxF0IUVYLz/K8K1CwSvkyiI=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=hw5xdwTie0l7zYJTL7/XMhimoeTrXxhbwIe0JEl8N15CbvO3k3q1ZlX0mnkZvhlW4 5X/k4fItmPa/z+2oeQmaqGO3A9EVQz+BmVAbrFOKpV9nSMv+7riVWHTOYKXgwLhU8X 1T+KJj4I5iXCkzaDM/Oord60ZwpBzrWZlBTKyHDw= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id F38483857C48 for ; Fri, 21 Jan 2022 08:29:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F38483857C48 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-433-aIOgad2CMU-59x3M2K4cmQ-1; Fri, 21 Jan 2022 03:29:24 -0500 X-MC-Unique: aIOgad2CMU-59x3M2K4cmQ-1 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 77F73190A7A2; Fri, 21 Jan 2022 08:29:23 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.171]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 2A3667B039; Fri, 21 Jan 2022 08:29:19 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.15.2) with ESMTPS id 20L8TG7n223305 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 21 Jan 2022 09:29:16 +0100 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 20L8TFea223304; Fri, 21 Jan 2022 09:29:15 +0100 To: GCC patches Subject: [PATCH] Reset relations when crossing backedges. Date: Fri, 21 Jan 2022 09:29:02 +0100 Message-Id: <20220121082901.223286-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.12 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.2 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_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: , 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" As discussed in PR103721, the problem here is that we are crossing a backedge and causing us to use relations from a previous iteration of a loop. This handles the testcases in both PR103721 and PR104067 which are variants of the same thing. Tested on x86-64 Linux with the usual regstrap as well as verifying the thread count before and after the patch. The number of threads is reduced by a miniscule amount. I assume we need release manager approval at this point? OK for trunk? gcc/ChangeLog: PR 103721/tree-optimization * gimple-range-path.cc (path_range_query::relations_may_be_invalidated): New. (path_range_query::compute_ranges_in_block): Reset relations if they may be invalidated. (path_range_query::maybe_register_phi_relation): Exit if relations may be invalidated on incoming edge. (path_range_query::compute_phi_relations): Pass incoming PHI edge to maybe_register_phi_relation. * gimple-range-path.h (relations_may_be_invalidated): New. (maybe_register_phi_relation): Pass edge instead of tree. * tree-ssa-threadbackward.cc (back_threader::back_threader): * value-relation.cc (path_oracle::path_oracle): Call mark_dfs_back_edges. (path_oracle::register_relation): Add SSA names to m_registered bitmap. (path_oracle::reset_path): Clear m_registered bitmap. * value-relation.h (path_oracle::set_root_oracle): New. gcc/testsuite/ChangeLog: * gcc.dg/pr103721-2.c: New test. * gcc.dg/pr103721.c: New test. --- gcc/gimple-range-path.cc | 48 +++++++++++++++++++++++++++---- gcc/gimple-range-path.h | 3 +- gcc/testsuite/gcc.dg/pr103721-2.c | 28 ++++++++++++++++++ gcc/testsuite/gcc.dg/pr103721.c | 25 ++++++++++++++++ gcc/tree-ssa-threadbackward.cc | 4 +++ gcc/value-relation.cc | 4 +-- gcc/value-relation.h | 1 + 7 files changed, 104 insertions(+), 9 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr103721-2.c create mode 100644 gcc/testsuite/gcc.dg/pr103721.c diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index a1bcca0b5fb..3ee4989f4b0 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -400,6 +400,19 @@ path_range_query::compute_ranges_in_phis (basic_block bb) bitmap_ior_into (m_has_cache_entry, phi_set); } +// Return TRUE if relations may be invalidated after crossing edge E. + +bool +path_range_query::relations_may_be_invalidated (edge e) +{ + // As soon as the path crosses a back edge, we can encounter + // definitions of SSA_NAMEs that may have had a use in the path + // already, so this will then be a new definition. The relation + // code is all designed around seeing things in dominator order, and + // crossing a back edge in the path violates this assumption. + return (e->flags & EDGE_DFS_BACK); +} + // Compute ranges defined in the current block, or exported to the // next block. @@ -440,6 +453,22 @@ path_range_query::compute_ranges_in_block (basic_block bb) // Solve imports that are exported to the next block. basic_block next = next_bb (); edge e = find_edge (bb, next); + + if (m_resolve && relations_may_be_invalidated (e)) + { + if (DEBUG_SOLVER) + fprintf (dump_file, + "Resetting relations as they may be invalidated in %d->%d.\n", + e->src->index, e->dest->index); + + path_oracle *p = get_path_oracle (); + p->reset_path (); + // ?? Instead of nuking the root oracle altogether, we could + // reset the path oracle to search for relations from the top of + // the loop with the root oracle. Something for future development. + p->set_root_oracle (nullptr); + } + EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) { tree name = ssa_name (i); @@ -742,9 +771,19 @@ path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) return true; } +// If possible, register the relation on the incoming edge E into PHI. + void -path_range_query::maybe_register_phi_relation (gphi *phi, tree arg) +path_range_query::maybe_register_phi_relation (gphi *phi, edge e) { + tree arg = gimple_phi_arg_def (phi, e->dest_idx); + + if (!gimple_range_ssa_p (arg)) + return; + + if (relations_may_be_invalidated (e)) + return; + basic_block bb = gimple_bb (phi); tree result = gimple_phi_result (phi); @@ -754,7 +793,7 @@ path_range_query::maybe_register_phi_relation (gphi *phi, tree arg) return; if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " from bb%d:", bb->index); + fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index); get_path_oracle ()->killing_def (result); m_oracle->register_relation (entry_bb (), EQ_EXPR, arg, result); @@ -787,10 +826,7 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev) for (size_t i = 0; i < nargs; ++i) if (e_in == gimple_phi_arg_edge (phi, i)) { - tree arg = gimple_phi_arg_def (phi, i); - - if (gimple_range_ssa_p (arg)) - maybe_register_phi_relation (phi, arg); + maybe_register_phi_relation (phi, e_in); break; } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index f090b7c2727..1820626161f 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -63,10 +63,11 @@ private: void ssa_range_in_phi (irange &r, gphi *phi); 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 maybe_register_phi_relation (gphi *, edge e); bool add_to_imports (tree name, bitmap imports); bool import_p (tree name); bool ssa_defined_in_bb (tree name, basic_block bb); + bool relations_may_be_invalidated (edge); // Path navigation. void set_path (const vec &); diff --git a/gcc/testsuite/gcc.dg/pr103721-2.c b/gcc/testsuite/gcc.dg/pr103721-2.c new file mode 100644 index 00000000000..aefa1f0f147 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr103721-2.c @@ -0,0 +1,28 @@ +// { dg-do run } +// { dg-options "-O2" } + +extern void abort (); +struct S { int x; } a[10]; +struct S *b; + +int +main () +{ + int i, j = 0; + struct S *q = a; + + for (i = 100; --i > 0; ) + { + struct S *p; + j++; + if (j >= 10) + j = 0; + p = &a[j]; + + if (p == q) + abort (); + __atomic_thread_fence (__ATOMIC_SEQ_CST); + q = p; + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/pr103721.c b/gcc/testsuite/gcc.dg/pr103721.c new file mode 100644 index 00000000000..6ec2e44b30f --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr103721.c @@ -0,0 +1,25 @@ +// { dg-do run } +// { dg-options "-O2" } + +int ipos = 0; +int f (int world) +{ + int searchVolume = world; + int currentVolume = 0; + while (currentVolume != searchVolume && searchVolume) { + currentVolume = searchVolume; + if (ipos != 0) + searchVolume = 0; + else + searchVolume = 1; + } + return (currentVolume); +} +int main() +{ + const int i = f (1111); + __builtin_printf ("%d\n", (int)(i)); + if (i != 1) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index d685b659df0..3ca65b32216 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -144,6 +144,10 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) m_flags = flags; m_solver = new path_range_query (flags & BT_RESOLVE); m_last_stmt = NULL; + + // The path solver needs EDGE_DFS_BACK in resolving mode. + if (flags & BT_RESOLVE) + mark_dfs_back_edges (); } back_threader::~back_threader () diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 32ca693c464..fcb574553df 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1234,7 +1234,7 @@ relation_oracle::debug () const path_oracle::path_oracle (relation_oracle *oracle) { - m_root = oracle; + set_root_oracle (oracle); bitmap_obstack_initialize (&m_bitmaps); obstack_init (&m_chain_obstack); @@ -1368,7 +1368,7 @@ path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, value_relation vr (k, ssa1, ssa2); fprintf (dump_file, " Registering value_relation (path_oracle) "); vr.dump (dump_file); - fprintf (dump_file, " (bb%d)\n", bb->index); + fprintf (dump_file, " (root: bb%d)\n", bb->index); } if (k == EQ_EXPR) diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 44d0796d939..848ffd3dab0 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -227,6 +227,7 @@ public: relation_kind query_relation (basic_block, tree, tree); relation_kind query_relation (basic_block, const_bitmap, const_bitmap); void reset_path (); + void set_root_oracle (relation_oracle *oracle) { m_root = oracle; } void dump (FILE *, basic_block) const; void dump (FILE *) const; private: