From 396cc31317ebad416e234dfa5f85d42585d32437 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 9 Feb 2021 11:59:06 +0100 Subject: [PATCH] Fix O(region-size) unwind in VN 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. 2021-02-09 Richard Biener 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::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.30.2