diff options
author | Richard Biener <rguenther@suse.de> | 2021-02-09 11:59:06 +0100 |
---|---|---|
committer | Richard Biener <rguenther@suse.de> | 2021-02-09 13:06:55 +0100 |
commit | 396cc31317ebad416e234dfa5f85d42585d32437 (patch) | |
tree | 90973acdc77a92ed5a5630f73b6b0075c6b4e310 | |
parent | e14ea108faa6eba6a60a45ff0ca3099ce6ae45c2 (diff) | |
download | gcc-396cc31317ebad416e234dfa5f85d42585d32437.zip gcc-396cc31317ebad416e234dfa5f85d42585d32437.tar.gz gcc-396cc31317ebad416e234dfa5f85d42585d32437.tar.bz2 |
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 <rguenther@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.
-rw-r--r-- | gcc/tree-ssa-sccvn.c | 31 | ||||
-rw-r--r-- | 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 d45aee8..65b3967 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 94968de..e4f1ff1 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 |