On Mon, Jan 24, 2022 at 9:51 AM Richard Biener
<richard.guent...@gmail.com> wrote:
>
> On Fri, Jan 21, 2022 at 1:12 PM Aldy Hernandez <al...@redhat.com> wrote:
> >
> > On Fri, Jan 21, 2022 at 11:56 AM Richard Biener
> > <richard.guent...@gmail.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 11:30 AM Aldy Hernandez <al...@redhat.com> wrote:
> > > >
> > > > On Fri, Jan 21, 2022 at 10:43 AM Richard Biener
> > > > <richard.guent...@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.
From 73b747b9fcfb35669ce1cc154b66f49b8383f32f Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@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
