Re: [PATCH] Reset relations when crossing backedges.

[Aldy Hernandez <aldyh@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 2994 bytes --]

On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 9:30 AM Aldy Hernandez via Gcc-patches
> > > <gcc-patches@gcc.gnu.org> 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.

Sounds good.  Thanks.

I've put the verifier by mark_dfs_back_edges(), since it really has
nothing to do with the path solver.  Perhaps it's useful for someone
else.

The patch triggered with the loop-ch use, so I've added a
corresponding mark_dfs_back_edges there.

OK pending tests?

Aldy

[-- Attachment #2: 0001-Assert-that-backedges-are-available-in-path-solver.patch --]
[-- Type: text/x-patch, Size: 4293 bytes --]

From 627237b45cb3aadbb009f4d077475a8b0c13c987 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Fri, 21 Jan 2022 13:04:20 +0100
Subject: [PATCH] Assert that backedges are available in path solver.

gcc/ChangeLog:

	* cfganal.cc (dfs_back_edges_available_p): New.
	* cfganal.h (dfs_back_edges_available_p): New.
	* gimple-range-path.cc (path_range_query::path_range_query):
	Verify freshness of back edges.
	* tree-ssa-loop-ch.cc (ch_base::copy_headers): Call
	mark_dfs_back_edges.
	* tree-ssa-threadbackward.cc (back_threader::back_threader): Move
	path_range_query construction after backedges have been
	updated.
---
 gcc/cfganal.cc                 | 37 ++++++++++++++++++++++++++++++++++
 gcc/cfganal.h                  |  1 +
 gcc/gimple-range-path.cc       |  2 ++
 gcc/tree-ssa-loop-ch.cc        |  2 ++
 gcc/tree-ssa-threadbackward.cc |  2 +-
 5 files changed, 43 insertions(+), 1 deletion(-)

diff --git a/gcc/cfganal.cc b/gcc/cfganal.cc
index e570d27768b..361d80da100 100644
--- a/gcc/cfganal.cc
+++ b/gcc/cfganal.cc
@@ -135,6 +135,43 @@ mark_dfs_back_edges (void)
   return found;
 }
 
+/* Return TRUE if EDGE_DFS_BACK is up to date for CFUN.  */
+
+bool
+dfs_back_edges_available_p ()
+{
+  auto_edge_flag saved_dfs_back (cfun);
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+  bool ret = true;
+
+  // Save all the back edges...
+  FOR_EACH_BB_FN (bb, cfun)
+    FOR_EACH_EDGE (e, ei, bb->succs)
+      {
+	if (e->flags & EDGE_DFS_BACK)
+	  {
+	    e->flags |= saved_dfs_back;
+	    e->flags &= ~EDGE_DFS_BACK;
+	  }
+      }
+
+  // ...and verify that recalculating them agrees with the saved ones.
+  mark_dfs_back_edges ();
+  FOR_EACH_BB_FN (bb, cfun)
+    FOR_EACH_EDGE (e, ei, bb->succs)
+      {
+	if (((e->flags & EDGE_DFS_BACK) != 0)
+	    != ((e->flags & saved_dfs_back) != 0))
+	  ret = false;
+
+	e->flags &= ~saved_dfs_back;
+      }
+
+  return ret;
+}
+
 /* Find unreachable blocks.  An unreachable block will have 0 in
    the reachable bit in block->flags.  A nonzero value indicates the
    block is reachable.  */
diff --git a/gcc/cfganal.h b/gcc/cfganal.h
index 386cfbf211f..21e1e09c6ce 100644
--- a/gcc/cfganal.h
+++ b/gcc/cfganal.h
@@ -50,6 +50,7 @@ private:
 };
 
 extern bool mark_dfs_back_edges (void);
+extern bool dfs_back_edges_available_p (void);
 extern void find_unreachable_blocks (void);
 extern void verify_no_unreachable_blocks (void);
 struct edge_list * create_edge_list (void);
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 3ee4989f4b0..89761c1be8c 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -48,6 +48,8 @@ path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
     m_ranger = ranger;
 
   m_oracle = new path_oracle (m_ranger->oracle ());
+
+  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());
 }
 
 path_range_query::~path_range_query ()
diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
index 8e64863cda2..2f5a390404c 100644
--- a/gcc/tree-ssa-loop-ch.cc
+++ b/gcc/tree-ssa-loop-ch.cc
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "value-range.h"
 #include "gimple-range.h"
 #include "gimple-range-path.h"
+#include "cfganal.h"
 
 /* Duplicates headers of loops if they are small enough, so that the statements
    in the loop body are always executed when the loop is entered.  This
@@ -384,6 +385,7 @@ ch_base::copy_headers (function *fun)
   auto_vec<loop_p> candidates;
   auto_vec<std::pair<edge, loop_p> > copied;
 
+  mark_dfs_back_edges ();
   path_range_query *query = new path_range_query;
   for (auto loop : loops_list (cfun, 0))
     {
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 3ca65b32216..3519aca84cd 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -142,12 +142,12 @@ back_threader::back_threader (function *fun, unsigned flags, bool first)
 
   m_fun = fun;
   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 ();
+  m_solver = new path_range_query (flags & BT_RESOLVE);
 }
 
 back_threader::~back_threader ()
-- 
2.34.1