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.

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