From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) by sourceware.org (Postfix) with ESMTPS id 712B8385800A for ; Fri, 21 Jan 2022 10:56:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 712B8385800A Received: by mail-ed1-x52d.google.com with SMTP id j23so36331287edp.5 for ; Fri, 21 Jan 2022 02:56:33 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ScKg+jHrvb1JDQHhsY9AS/2lI/4q9SDI4KpHjtBoPPc=; b=3eroNL4tnD7bIZMZa7YKn+WSowpfyA7OSDSJxiTlQ0CVtiZe1DKAf/slDm52qYIhRW WaS2FRdm6EM8Vg02e5WpQbVjym2TjPFbSpG5S0ulbLku+IrEqdz6Cq59y8Wpiw+x1y38 5LlTBuSBzXp2cgfTGkXyUT8VXQRLnAu2l05c3gpAFA7C0A+OeUR7pAr6EP0mqqlEQ1N4 2ljdq/7InMvK5VN+RlecGM4KO5L9a2YJdgm3FEeWGzeSQWmG9YA+lozIoDDXLypYnYY6 J1hBrfywISn682m8Het3EErQJHMSc6TkKM9ThCS6YkxP4/Kphvp8nBGed4UuCQTqlxj+ a2wg== X-Gm-Message-State: AOAM531TfbSyUdtZbaWCO5BF7hHf0mYvkbpaEvy8OCi3FOCr5cWSZdew HELgTVDyU6IsQ85f6jP5NeNL6kHuQcxD+qGywfU= X-Google-Smtp-Source: ABdhPJy/GMAHxM0R5YfdbRoFlqbT8jTyXLfXFb44VY6mfiHgfJy1kd8HcXuhgKHP9zo8eapXuJpyIVcTOymBW/W7zIU= X-Received: by 2002:a17:907:3e26:: with SMTP id hp38mr2389829ejc.445.1642762592151; Fri, 21 Jan 2022 02:56:32 -0800 (PST) MIME-Version: 1.0 References: <20220121082901.223286-1-aldyh@redhat.com> In-Reply-To: From: Richard Biener Date: Fri, 21 Jan 2022 11:56:21 +0100 Message-ID: Subject: Re: [PATCH] Reset relations when crossing backedges. To: Aldy Hernandez Cc: GCC patches , Jeff Law , "MacLeod, Andrew" Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-8.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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-List-Received-Date: Fri, 21 Jan 2022 10:56:35 -0000 On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez wrote: > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener > wrote: > > > > On Fri, Jan 21, 2022 at 9:30 AM Aldy Hernandez via Gcc-patches > > wrote: > > > > > > 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? > > > > Not for regression fixes. > > OK, I've pushed it to fix the P1s. We can continue refining the > solution in a follow-up patch. > > > > > Btw, I wonder whether you have to treat irreducible regions in the same > > way more generally - which edges are marked as backedge there depends > > on which edge into the region was visited first. I also wonder how we > > Jeff, Andrew?? > > > I also wonder how we guarantee that all users of the resolve mode have backedges marked > > properly? Also note that CFG manipulation routines in general do not > > keep backedge markings up-to-date so incremental modification and > > resolving queries might not mix. > > > > It's a bit unfortunate that we can't query the CFG on whether backedges > > are marked. > > Ughh. The call to mark_dfs_back_edges is currently in the backward > threader. Perhaps we could put it in the path_range_query > constructor? That way other users of path_range_query can benefit > (loop_ch for instance, though it doesn't use it in a way that crosses > backedges so perhaps it's unaffected). Does that sound reasonable? Hmm, I'd rather keep the burden on the callers because many already should have backedges marked. What you could instead do is add sth like if (flag_checking) { auto_edge_flag saved_dfs_back; for-each-edge-in-cfg () set saved_dfs_back flag if dfs_back is set, clear dfs_back mark_dfs_back_edges (); for-each-edge-in-cfg () verify the flags are set on the same edges and clear saved_dfs_back } to the path_range_query constructor. That way we at least notice when passes do _not_ have the backedges marked properly. Richard. > Aldy > > > > > If you're only dealing with non-irreducible regions you can use a > > dominance query to identify a backedge. Oh, and irreducible regions > > are also not marked (but at least CFG manipulation tries to conservatively > > keep that info up-to-date). > > > > > gcc/ChangeLog: > > > > > > PR 103721/tree-optimization > > > > swapped, it should be PR tree-optimization/103721 > > > > > * 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: > > > -- > > > 2.34.1 > > > > > >