During RPO iteration and value elimination, dominated_by_p_w_unex is
queried frequently to test dominance in the executable part of the CFG.
The current implementation performs a dynamic heuristic walk across CFG
predecessors and successors which is slow and constrained by arbitrary
heuristic limits (checking at most 8 edges). The existing conditional
handling of backedges also looks incomplete - as we do not iterate
when dominated_by_p_w_unex would change after making a backedge newly
executable the limited gating is not safe.
This patch instead dynamically tracks immediate dominators of the executable
part of the CFG during the RPO walk using an array vn_exec_idom indexed by
RPO number, updated via a single-pass Cooper-Harvey-Kennedy
nearest-common-ancestor intersection, strictly limited to forward edges
with backward edges handled conservatively using the whole-CFG immediate
dominators.
This speeds up dominated_by_p_w_unex which now runs in O(depth of the
dominator tree) (like dominated_by_p without fast queries), and it
removes the artificial limitation, making it more precise but losing
the (incorrect) non-executable backedge handling. The per-predecessor
work is now shifted to process_bb which updates the immediate dominator
info which is O(number-of-predecessors x depth-of-the-dominator-tree).
For the degenerate testcase from PR87615 this is now 6% slower,
the testcase from PR106809 is unchanged. I avoided this regression
by limiting the walk over idoms in dominated_by_p_w_unex, so we fall
back to non-dominance. The overall optimization effect on cc1files
is minor but strictly positive.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
I don't like the hack we have at the moment, but clearly this
one has higher complexity. I also believe the current sometimes
handling of not executable backedges is broken. So I'm a bit torn,
there was my older idea to "fix" the current scheme by caching the
single executable edge into/out of a block as those get marked
executable to remove the scanning. That would leave us with
a single-block distance "dominator peek". The backedge issue
can of course be fixed in the same way in the current code.
So - any opinions in either way?
Thanks,
Richard.
* tree-ssa-sccvn.cc (vn_exec_idom): New static variable.
(exec_idom_intersect): New static function.
(update_exec_idom): Likewise.
(dominated_by_p_w_unex): Rewrite using vn_exec_idom ancestor
walk. Drop allow_back parameter.
(vn_nary_op_get_predicated_value): Adjust caller.
(rpo_elim::eliminate_avail): Likewise.
(process_bb): Call update_exec_idom.
(do_rpo_vn_1): Allocate and initialize vn_exec_idom to static
immediate dominators; clean it up on exit.
* gcc.dg/tree-ssa/ssa-fre-115.c: New testcase.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-115.c | 33 +++
gcc/tree-ssa-sccvn.cc | 221 ++++++++++----------
2 files changed, 138 insertions(+), 116 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-115.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-115.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-115.c
new file mode 100644
index 00000000000..489b7c0601b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-115.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+extern void bar(void);
+extern void foo1(void);
+
+void foo (int cond1, int x, int a, int b)
+{
+ if (a == b)
+ {
+ if (a != b)
+ goto dead;
+
+ if (!cond1) return;
+
+ switch (x) {
+ case 1: case 10: case 20: case 30: case 40:
+ case 50: case 60: case 70: case 80: case 90:
+ goto dead;
+ case 11:
+ foo1();
+ goto dead;
+ default:
+ return;
+ }
+
+ dead:
+ if (!cond1)
+ bar();
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "bar" "fre1" } } */
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index c496ff93d11..946a40506b1 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -379,6 +379,7 @@ static vn_tables_t valid_info;
static class eliminate_dom_walker *rpo_avail;
basic_block vn_context_bb;
int *vn_bb_to_rpo;
+static int *vn_exec_idom;
/* Valueization hook for simplify_replace_tree. Valueize NAME if it is
@@ -4956,7 +4957,7 @@ vn_nary_op_insert_pieces_predicated (unsigned int length,
enum tree_code code,
}
static bool
-dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool);
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2);
static tree
vn_nary_op_get_predicated_value (vn_nary_op_t vno, basic_block bb,
@@ -4969,10 +4970,7 @@ vn_nary_op_get_predicated_value (vn_nary_op_t vno,
basic_block bb,
{
basic_block cand
= BASIC_BLOCK_FOR_FN (cfun, val->valid_dominated_by_p[i]);
- /* Do not handle backedge executability optimistically since
- when figuring out whether to iterate we do not consider
- changed predication.
- When asking for predicated values on an edge avoid looking
+ /* When asking for predicated values on an edge avoid looking
at edge executability for edges forward in our iteration
as well. */
if (e && (e->flags & EDGE_DFS_BACK))
@@ -4980,7 +4978,7 @@ vn_nary_op_get_predicated_value (vn_nary_op_t vno,
basic_block bb,
if (dominated_by_p (CDI_DOMINATORS, bb, cand))
return val->result;
}
- else if (dominated_by_p_w_unex (bb, cand, false))
+ else if (dominated_by_p_w_unex (bb, cand))
return val->result;
}
return NULL_TREE;
@@ -5311,128 +5309,102 @@ vn_phi_insert (gimple *phi, tree result, bool
backedges_varying_p)
}
-/* Return true if BB1 is dominated by BB2 taking into account edges
- that are not executable. When ALLOW_BACK is false consider not
- executable backedges as executable. */
+/* Find the nearest common dominator of R1 and R2 in the IDOMS tree
+ using Reverse Postorder (RPO) numbers. Both walks terminate latest
+ at the root (RPO number 0, whose IDOMS entry is -1) because callers
+ maintain the invariant IDOMS[x] < x for every x they store into
+ IDOMS. */
-static bool
-dominated_by_p_w_unex (basic_block bb1, basic_block bb2, bool allow_back)
+static int
+exec_idom_intersect (int *idoms, int r1, int r2)
{
- edge_iterator ei;
- edge e;
+ while (r1 != r2)
+ {
+ if (r1 > r2)
+ r1 = idoms[r1];
+ else
+ r2 = idoms[r2];
+ }
+ return r1;
+}
- if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
- return true;
+/* Update the immediate dominator of BB based on its executable predecessors.
- /* 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. */
+ This performs one step of a Cooper-Harvey-Kennedy style dominator
+ computation, but unlike the textbook algorithm we do not have the
+ luxury of iterating over a fixed graph to a fixpoint: the executable
+ subgraph is discovered incrementally as the RPO walk proceeds (edges
+ only ever turn executable, never back), and BB can be visited before
+ every one of its predecessors has reached its final executable state.
- /* Iterate to the single executable bb1 predecessor. */
- if (EDGE_COUNT (bb1->preds) > 1)
- {
- edge prede = NULL;
- FOR_EACH_EDGE (e, ei, bb1->preds)
- if ((e->flags & EDGE_EXECUTABLE)
- || (!allow_back && (e->flags & EDGE_DFS_BACK)))
- {
- if (prede)
- {
- prede = NULL;
- break;
- }
- prede = e;
- }
- if (prede)
- {
- bb1 = prede->src;
+ We can only trust an edges executable state if it is not a backedge
+ in the RPO order. Any other predecessor edge is folded in as BB's
+ immediate dominator in the static (whole-graph, CDI_DOMINATORS)
+ dominator tree. */
- /* Re-do the dominance check with changed bb1. */
- if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
- return true;
- }
- }
+static void
+update_exec_idom (basic_block bb)
+{
+ int rpo = vn_bb_to_rpo[bb->index];
+ /* Skip the entry block (RPO number zero) as its predecessors are
+ not covered by the region. */
+ if (rpo == 0)
+ return;
- /* Iterate to the single executable bb2 successor. */
- if (EDGE_COUNT (bb2->succs) > 1)
+ edge_iterator ei;
+ edge e;
+ int idom = -1;
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
- edge succe = NULL;
- FOR_EACH_EDGE (e, ei, bb2->succs)
- if ((e->flags & EDGE_EXECUTABLE)
- || (!allow_back && (e->flags & EDGE_DFS_BACK)))
- {
- if (succe)
- {
- succe = NULL;
- break;
- }
- succe = e;
- }
- if (succe
- /* Limit the number of edges we check, we should bring in
- context from the iteration and compute the single
- executable incoming edge when visiting a block. */
- && EDGE_COUNT (succe->dest->preds) < 8)
- {
- /* 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. */
- if (EDGE_COUNT (succe->dest->preds) > 1)
- {
- FOR_EACH_EDGE (e, ei, succe->dest->preds)
- if (e != succe
- && ((e->flags & EDGE_EXECUTABLE)
- || (!allow_back && (e->flags & EDGE_DFS_BACK))))
- {
- succe = NULL;
- break;
- }
- }
- if (succe)
- {
- bb2 = succe->dest;
+ int pred_rpo = vn_bb_to_rpo[e->src->index];
+ /* For backedges fall back to the static immediate dominator. */
+ if (pred_rpo >= rpo)
+ /* We initialize to the static immediate dominator and this is
+ never overwritten to another value since we either visit each
+ block exactly once or iterate in the same order. */
+ return;
- /* Re-do the dominance check with changed bb2. */
- if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
- return true;
- }
- }
- }
- /* Iterate to the single successor of bb2 with only a single executable
- incoming edge. */
- else if (EDGE_COUNT (bb2->succs) == 1
- && EDGE_COUNT (single_succ (bb2)->preds) > 1
- /* Limit the number of edges we check, we should bring in
- context from the iteration and compute the single
- executable incoming edge when visiting a block. */
- && EDGE_COUNT (single_succ (bb2)->preds) < 8)
- {
- edge prede = NULL;
- FOR_EACH_EDGE (e, ei, single_succ (bb2)->preds)
- if ((e->flags & EDGE_EXECUTABLE)
- || (!allow_back && (e->flags & EDGE_DFS_BACK)))
- {
- if (prede)
- {
- prede = NULL;
- break;
- }
- prede = e;
- }
- /* We might actually get to a query with BB2 not visited yet when
- we're querying for a predicated value. */
- if (prede && prede->src == bb2)
+ if (e->flags & EDGE_EXECUTABLE)
{
- bb2 = prede->dest;
-
- /* Re-do the dominance check with changed bb2. */
- if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
- return true;
+ if (idom == -1)
+ idom = pred_rpo;
+ else
+ idom = exec_idom_intersect (vn_exec_idom, idom, pred_rpo);
}
}
- /* We could now iterate updating bb1 / bb2. */
- return false;
+ gcc_checking_assert (idom != -1);
+ vn_exec_idom[rpo] = idom;
+}
+
+/* Return true if BB1 is dominated by BB2 taking into account edges
+ that are known executable, including those that are not executable
+ only because they are backedges not yet proven to be taken (see
+ the commentary on update_exec_idom for why folding those in
+ unconditionally is always sound, and why it used to be handled by
+ a second, separate optimistic/pessimistic pair of trees here).
+
+ Note: It is assumed that both BB1 and BB2 are inside the region
+ currently being value-numbered. */
+
+static bool
+dominated_by_p_w_unex (basic_block bb1, basic_block bb2)
+{
+ if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+ return true;
+
+ if (!vn_exec_idom)
+ return false;
+
+ int rpo2 = vn_bb_to_rpo[bb2->index];
+ int rpo1 = vn_bb_to_rpo[bb1->index];
+
+ int curr = rpo1;
+ int limit = 32;
+ while (curr > rpo2 && limit-- > 0)
+ curr = vn_exec_idom[curr];
+
+ return curr == rpo2;
}
/* Set the value number of FROM to TO, return true if it has changed
@@ -8221,7 +8193,7 @@ rpo_elim::eliminate_avail (basic_block bb, tree op)
may also be able to "pre-compute" (bits of) the next immediate
(non-)dominator during the RPO walk when marking edges as
executable. */
- if (dominated_by_p_w_unex (bb, abb, true))
+ if (dominated_by_p_w_unex (bb, abb))
{
tree leader = ssa_name (av->leader);
/* Prevent eliminations that break loop-closed SSA. */
@@ -8483,6 +8455,8 @@ process_bb (rpo_elim &avail, basic_block bb,
vn_context_bb = bb;
+ update_exec_idom (bb);
+
/* If we are in loop-closed SSA preserve this state. This is
relevant when called on regions from outside of FRE/PRE. */
bool lc_phi_nodes = false;
@@ -8931,6 +8905,18 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
bb_to_rpo[rpo[i]] = i;
vn_bb_to_rpo = bb_to_rpo;
+ /* When not iterating we can end up with executable edges from unvisited
+ but backward reachable blocks, so we cannot rely on the idom being
+ up-to-date. Initialize it with a conservative default. */
+ vn_exec_idom = XNEWVEC (int, n);
+ vn_exec_idom[0] = -1;
+ for (int i = 1; i < n; ++i)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
+ vn_exec_idom[i]
+ = bb_to_rpo[get_immediate_dominator (CDI_DOMINATORS, bb)->index];
+ }
+
unwind_state *rpo_state = XNEWVEC (unwind_state, n);
rpo_elim avail (entry->dest);
@@ -9289,6 +9275,9 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
rpo_avail = NULL;
vn_bb_to_rpo = NULL;
+ XDELETEVEC (vn_exec_idom);
+ vn_exec_idom = NULL;
+
XDELETEVEC (bb_to_rpo);
XDELETEVEC (rpo);
XDELETEVEC (rpo_state);
--
2.51.0
