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?
Aldy
From 627237b45cb3aadbb009f4d077475a8b0c13c987 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 (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
