Re: [PATCH] Reset relations when crossing backedges.

[Aldy Hernandez <aldyh@redhat.com>]

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

On Mon, Jan 24, 2022 at 9:51 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > 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?
>
> Please rename dfs_back_edges_available_p to sth not suggesting
> it's a simple predicate check, like maybe verify_marked_backedges.
>
> +
> +  gcc_checking_assert (!m_resolve || dfs_back_edges_available_p ());
>
> I'd prefer the following which allows even release checking builds
> to verify this with -fchecking.
>
>   if (!m_resolve)
>     if (flag_checking)
>       verify_marked_backedges ();
>
> and then ideally verify_marked_backedges () should raise an
> internal_error () for the edge not marked properly, best by
> also specifying it.  Just like other CFG verifiers do.
>
> The loop ch and backwards threader changes are OK.  You
> can post the verification independently again.

How about this?

Tested on x86-64 Linux.

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

From 73b747b9fcfb35669ce1cc154b66f49b8383f32f 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 (verify_marked_backedges): New.
	* cfganal.h (verify_marked_backedges): 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                 | 39 ++++++++++++++++++++++++++++++++++
 gcc/cfganal.h                  |  1 +
 gcc/gimple-range-path.cc       |  3 +++
 gcc/tree-ssa-loop-ch.cc        |  2 ++
 gcc/tree-ssa-threadbackward.cc |  2 +-
 5 files changed, 46 insertions(+), 1 deletion(-)

diff --git a/gcc/cfganal.cc b/gcc/cfganal.cc
index e570d27768b..73d75513d85 100644
--- a/gcc/cfganal.cc
+++ b/gcc/cfganal.cc
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "timevar.h"
 #include "cfganal.h"
 #include "cfgloop.h"
+#include "diagnostic.h"
 
 namespace {
 /* Store the data structures necessary for depth-first search.  */
@@ -135,6 +136,44 @@ mark_dfs_back_edges (void)
   return found;
 }
 
+/* Return TRUE if EDGE_DFS_BACK is up to date for CFUN.  */
+
+void
+verify_marked_backedges ()
+{
+  auto_edge_flag saved_dfs_back (cfun);
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+
+  // 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))
+	  {
+	    error ("%<verify_marked_backedges%>: %<%d->%d%> incorrectly marked",
+		   e->src->index, e->dest->index);
+	    gcc_unreachable ();
+	  }
+
+	e->flags &= ~saved_dfs_back;
+      }
+}
+
 /* 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..e7f2a563466 100644
--- a/gcc/cfganal.h
+++ b/gcc/cfganal.h
@@ -50,6 +50,7 @@ private:
 };
 
 extern bool mark_dfs_back_edges (void);
+extern void verify_marked_backedges (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..eb6c36bba12 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -48,6 +48,9 @@ path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
     m_ranger = ranger;
 
   m_oracle = new path_oracle (m_ranger->oracle ());
+
+  if (m_resolve && flag_checking)
+    verify_marked_backedges ();
 }
 
 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