https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69378
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |law at gcc dot gnu.org
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
The dominator walk (recording temporary relations / equivalences) is
pessmimized
by not considering not executable edges as well (by unnecessarily popping off
those). Consider a diamond with one half not executable - the conditional
relations / equivalences still hold in the merger.
The following patch fixes this regression though dominated_by_p_w_unex
is somewhat awkward. We could do better by iterating but the key
issue is to identify quickly if there is any (exeecutable) path from bb2 to
bb1,
otherwise we'll iterate to entry or exit (dependent on which direction
we iterate) - that'll be too costly.
For example we could iterate by following bb2s single executable
successors, verifying they do have a single executable predecessor,
until we hit bb1 (or exit ...). [if not single executable successor
continue with the successor that has the executable path from bb2 to bb1...]
Maybe the patch is already too sophisticated and I should simply do
a max. n (1?) depth walk like that.
That said, "fixing" the dominator walk for DOM / SCCVN would certainly
be interesting as well - I'm not sure we can compute dominators
"on-the-fly" though, that is, keep the efficient stack of cond
equivalences, for all but very simple CFG shapes.
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 232603)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -2969,6 +2969,31 @@ print_scc (FILE *out, vec<tree> scc)
fprintf (out, "\n");
}
+/* Return true if BB1 is dominated by BB2 taking into account edges
+ that are not executable in the region starting from the
+ common immediate dominator. */
+
+static bool
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
+{
+ if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+ return true;
+
+ /* Go up to the immediate dominator of bb2 and see if that is post-dominated
+ by bb2 taking into account un-executable edges. */
+ basic_block idom2 = get_immediate_dominator (CDI_DOMINATORS, bb2);
+ if (EDGE_COUNT (idom2->succs) != 2)
+ return false;
+ if ((! (EDGE_SUCC (idom2, 0)->flags & EDGE_EXECUTABLE)
+ && dominated_by_p (CDI_DOMINATORS, bb2, EDGE_SUCC (idom2, 1)->dest))
+ || (! (EDGE_SUCC (idom2, 1)->flags & EDGE_EXECUTABLE)
+ && dominated_by_p (CDI_DOMINATORS, bb2, EDGE_SUCC (idom2, 0)->dest)))
+ /* Re-do the dominance check with the immediate dominator. */
+ return dominated_by_p (CDI_DOMINATORS, bb1, idom2);
+
+ return false;
+}
+
/* Set the value number of FROM to TO, return true if it has changed
as a result. */
@@ -3046,13 +3071,13 @@ set_ssa_val_to (tree from, tree to)
&& SSA_NAME_RANGE_INFO (to))
{
if (SSA_NAME_IS_DEFAULT_DEF (to)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
gimple_bb (SSA_NAME_DEF_STMT (from)),
gimple_bb (SSA_NAME_DEF_STMT (to))))
/* Keep the info from the dominator. */
;
else if (SSA_NAME_IS_DEFAULT_DEF (from)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
gimple_bb (SSA_NAME_DEF_STMT (to)),
gimple_bb (SSA_NAME_DEF_STMT
(from))))
{
@@ -3076,13 +3101,13 @@ set_ssa_val_to (tree from, tree to)
&& SSA_NAME_PTR_INFO (to))
{
if (SSA_NAME_IS_DEFAULT_DEF (to)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
gimple_bb (SSA_NAME_DEF_STMT (from)),
gimple_bb (SSA_NAME_DEF_STMT (to))))
/* Keep the info from the dominator. */
;
else if (SSA_NAME_IS_DEFAULT_DEF (from)
- || dominated_by_p (CDI_DOMINATORS,
+ || dominated_by_p_w_unex (
gimple_bb (SSA_NAME_DEF_STMT (to)),
gimple_bb (SSA_NAME_DEF_STMT
(from))))
{
Alternative "algorithm":
/* Return true if BB1 is dominated by BB2 taking into account edges
that are not executable. */
static bool
dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
{
if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
return true;
/* Before iterating we'd like to know if there exists a
(executable) path from bb2 to bb1 at all, if not we can
directly return false. For now simply iterate once. */
/* Iterate to the single executable bb2 successor. */
edge e, succe = NULL;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb2->succs)
if (e->flags & EDGE_EXECUTABLE)
{
/* ??? If more than one edge is executable we can (have to?)
skip to the post-dominator. */
if (succe)
return false;
succe = e;
}
if (! succe)
return false;
/* Verify the reached block is only reached through succe.
If there is only one edge we can spare us the dominator
check and iterate directly. */
bb2 = succe->dest;
if (EDGE_COUNT (bb2->preds) > 1)
{
FOR_EACH_EDGE (e, ei, bb2->preds)
if (e != succe
&& (e->flags & EDGE_EXECUTABLE))
return false;
/* Re-do the dominance check with bb2. */
if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
return true;
}
/* ??? Can iterate from here. */
return false;
}
