This fixes the currently O(region-size) unwinding of avail info
to be O(unwind-size) by tracking a linked-list stack of pushed
avails. This reduces the compile-time spent in complete unrolling
for WRF and removes do_unwind from the radar of perf for the
testcase.
Bootstrapped and tested on x86_64-unknown-linux-gnu, will push soon.
2021-02-09 Richard Biener <rguent...@suse.de>
PR tree-optimization/98863
* tree-ssa-sccvn.h (vn_avail::next_undo): Add.
* tree-ssa-sccvn.c (last_pushed_avail): New global.
(rpo_elim::eliminate_push_avail): Chain pushed avails.
(unwind_state::avail_top): Add.
(do_unwind): Rewrite unwinding of avail entries.
(do_rpo_vn): Initialize last_pushed_avail and
avail_top of the undo state.
---
gcc/tree-ssa-sccvn.c | 31 ++++++++++++++++---------------
gcc/tree-ssa-sccvn.h | 2 ++
2 files changed, 18 insertions(+), 15 deletions(-)
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index d45aee8e502..65b3967b9e1 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -298,6 +298,7 @@ static obstack vn_tables_insert_obstack;
static vn_reference_t last_inserted_ref;
static vn_phi_t last_inserted_phi;
static vn_nary_op_t last_inserted_nary;
+static vn_ssa_aux_t last_pushed_avail;
/* Valid hashtables storing information we have proven to be
correct. */
@@ -6898,6 +6899,8 @@ rpo_elim::eliminate_push_avail (basic_block bb, tree
leader)
av->location = bb->index;
av->leader = SSA_NAME_VERSION (leader);
av->next = value->avail;
+ av->next_undo = last_pushed_avail;
+ last_pushed_avail = value;
value->avail = av;
}
@@ -7338,12 +7341,13 @@ struct unwind_state
vn_reference_t ref_top;
vn_phi_t phi_top;
vn_nary_op_t nary_top;
+ vn_avail *avail_top;
};
/* Unwind the RPO VN state for iteration. */
static void
-do_unwind (unwind_state *to, int rpo_idx, rpo_elim &avail, int *bb_to_rpo)
+do_unwind (unwind_state *to, rpo_elim &avail)
{
gcc_assert (to->iterate);
for (; last_inserted_nary != to->nary_top;
@@ -7378,20 +7382,14 @@ do_unwind (unwind_state *to, int rpo_idx, rpo_elim
&avail, int *bb_to_rpo)
obstack_free (&vn_tables_obstack, to->ob_top);
/* Prune [rpo_idx, ] from avail. */
- /* ??? This is O(number-of-values-in-region) which is
- O(region-size) rather than O(iteration-piece). */
- for (hash_table<vn_ssa_aux_hasher>::iterator i = vn_ssa_aux_hash->begin ();
- i != vn_ssa_aux_hash->end (); ++i)
+ for (; last_pushed_avail && last_pushed_avail->avail != to->avail_top;)
{
- while ((*i)->avail)
- {
- if (bb_to_rpo[(*i)->avail->location] < rpo_idx)
- break;
- vn_avail *av = (*i)->avail;
- (*i)->avail = (*i)->avail->next;
- av->next = avail.m_avail_freelist;
- avail.m_avail_freelist = av;
- }
+ vn_ssa_aux_t val = last_pushed_avail;
+ vn_avail *av = val->avail;
+ val->avail = av->next;
+ last_pushed_avail = av->next_undo;
+ av->next = avail.m_avail_freelist;
+ avail.m_avail_freelist = av;
}
}
@@ -7505,6 +7503,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
last_inserted_ref = NULL;
last_inserted_phi = NULL;
last_inserted_nary = NULL;
+ last_pushed_avail = NULL;
vn_valueize = rpo_vn_valueize;
@@ -7598,6 +7597,8 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
rpo_state[idx].ref_top = last_inserted_ref;
rpo_state[idx].phi_top = last_inserted_phi;
rpo_state[idx].nary_top = last_inserted_nary;
+ rpo_state[idx].avail_top
+ = last_pushed_avail ? last_pushed_avail->avail : NULL;
}
if (!(bb->flags & BB_EXECUTABLE))
@@ -7675,7 +7676,7 @@ do_rpo_vn (function *fn, edge entry, bitmap exit_bbs,
}
if (iterate_to != -1)
{
- do_unwind (&rpo_state[iterate_to], iterate_to, avail, bb_to_rpo);
+ do_unwind (&rpo_state[iterate_to], avail);
idx = iterate_to;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Iterating to %d BB%d\n",
diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
index 94968de5d6c..e4f1ff1eb20 100644
--- a/gcc/tree-ssa-sccvn.h
+++ b/gcc/tree-ssa-sccvn.h
@@ -212,6 +212,8 @@ struct vn_avail
int location;
/* The LEADER for the value we are chained on. */
int leader;
+ /* The previous value we pushed a avail record to. */
+ struct vn_ssa_aux *next_undo;
};
typedef struct vn_ssa_aux
--
2.26.2
