SCCVN data-structure TLC

Message ID alpine.LSU.2.20.1807191405370.16707@zhemvz.fhfr.qr
State New
Headers show
Series
  • SCCVN data-structure TLC
Related show

Commit Message

Richard Biener July 19, 2018, 12:09 p.m.
The following does away with copying hashtable elements when moving them
from the optimistic hashtable to the valid one.  It does that by
keeping only a single global obstack for all phi, ref and nary
elements and freeing things between iterations by unwinding that obstack.
In this process phis and refs no longer use an alloc-pool and I changed
phis to have arguments as a trailing array.

All nice and dandy but vn_nary_build_or_lookup_1 throws a wrench in
because of its need to insert to the valid tables.  So I need to
allocate those nary elements on a separate obstack.  Bah.

The patch is big enough so further cleanups (make ref operands a trailing
array, go away with having two sets of hashtables) will be followups.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2018-07-19  Richard Biener  <rguenther@suse.de>

	* tree-ssa-sccvn.h (struct vn_phi_s): Make phiargs member
	a trailing array.
	* tree-ssa-sccvn.c: Remove alloc-pool.h use.
	(vn_phi_hasher): Derive from nofree_ptr_hash and remove remove method.
	(vn_reference_hasher): Likewise.
	(struct vn_tables_s): Remove obstack and alloc-pool members.
	(vn_tables_obstack, vn_tables_insert_obstack): New global obstacks.
	(vn_nary_build_or_lookup_1): Manually build in vn_tables_insert_obstack.
	(vn_reference_insert): Allocate from obstack instead of from alloc-pool.
	(vn_reference_insert_pieces): Likewise.
	(alloc_vn_nary_op_noinit): Adjust.
	(vn_nary_op_insert_stmt): Allocate phiargs in-place.
	(vn_phi_eq): Adjust.
	(shared_lookup_phiargs): Remove.
	(vn_phi_lookup): Allocate temporary vn_phi_s on the stack.
	(vn_phi_insert): Allocate from obstack instead of from alloc-pool.
	(visit_reference_op_call): Likewise.
	(copy_nary, copy_phi, copy_reference): Remove.
	(process_scc): Rewind the obstack when iterating.  Do not
	copy the elements to valid_info but just move them from one
	hashtable to the other.
	(allocate_vn_table): Adjust.
	(free_vn_table): Likewise.
	(init_scc_vn): Likewise.
	(free_scc_vn): Likewise.

Patch

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 262871)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -25,7 +25,6 @@  along with GCC; see the file COPYING3.
 #include "rtl.h"
 #include "tree.h"
 #include "gimple.h"
-#include "alloc-pool.h"
 #include "ssa.h"
 #include "expmed.h"
 #include "insn-config.h"
@@ -169,11 +168,10 @@  typedef vn_nary_op_table_type::iterator
 static int
 vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2);
 
-struct vn_phi_hasher : pointer_hash <vn_phi_s>
+struct vn_phi_hasher : nofree_ptr_hash <vn_phi_s>
 { 
   static inline hashval_t hash (const vn_phi_s *);
   static inline bool equal (const vn_phi_s *, const vn_phi_s *);
-  static inline void remove (vn_phi_s *);
 };
 
 /* Return the computed hashcode for phi operation P1.  */
@@ -192,14 +190,6 @@  vn_phi_hasher::equal (const vn_phi_s *vp
   return vn_phi_eq (vp1, vp2);
 }
 
-/* Free a phi operation structure VP.  */
-
-inline void
-vn_phi_hasher::remove (vn_phi_s *phi)
-{
-  phi->phiargs.release ();
-}
-
 typedef hash_table<vn_phi_hasher> vn_phi_table_type;
 typedef vn_phi_table_type::iterator vn_phi_iterator_type;
 
@@ -235,11 +225,10 @@  free_reference (vn_reference_s *vr)
 
 /* vn_reference hashtable helpers.  */
 
-struct vn_reference_hasher : pointer_hash <vn_reference_s>
+struct vn_reference_hasher : nofree_ptr_hash <vn_reference_s>
 {
   static inline hashval_t hash (const vn_reference_s *);
   static inline bool equal (const vn_reference_s *, const vn_reference_s *);
-  static inline void remove (vn_reference_s *);
 };
 
 /* Return the hashcode for a given reference operation P1.  */
@@ -256,26 +245,17 @@  vn_reference_hasher::equal (const vn_ref
   return vn_reference_eq (v, c);
 }
 
-inline void
-vn_reference_hasher::remove (vn_reference_s *v)
-{
-  free_reference (v);
-}
-
 typedef hash_table<vn_reference_hasher> vn_reference_table_type;
 typedef vn_reference_table_type::iterator vn_reference_iterator_type;
 
 
-/* The set of hashtables and alloc_pool's for their items.  */
+/* The set of VN hashtables.  */
 
 typedef struct vn_tables_s
 {
   vn_nary_op_table_type *nary;
   vn_phi_table_type *phis;
   vn_reference_table_type *references;
-  struct obstack nary_obstack;
-  object_allocator<vn_phi_s> *phis_pool;
-  object_allocator<vn_reference_s> *references_pool;
 } *vn_tables_t;
 
 
@@ -310,25 +290,26 @@  static hash_table<vn_constant_hasher> *c
 static bitmap constant_value_ids;
 
 
+/* Obstack we allocate the vn-tables elements from.  */
+static obstack vn_tables_obstack;
+/* Special obstack we never unwind.  */
+static obstack vn_tables_insert_obstack;
+
 /* Valid hashtables storing information we have proven to be
    correct.  */
-
 static vn_tables_t valid_info;
 
 /* Optimistic hashtables storing information we are making assumptions about
    during iterations.  */
-
 static vn_tables_t optimistic_info;
 
 /* Pointer to the set of hashtables that is currently being used.
    Should always point to either the optimistic_info, or the
    valid_info.  */
-
 static vn_tables_t current_info;
 
 
 /* Reverse post order index for each basic block.  */
-
 static int *rpo_numbers;
 
 #define SSA_VAL(x) (VN_INFO ((x))->valnum)
@@ -1647,7 +1628,12 @@  vn_reference_lookup_or_insert_for_pieces
 				     operands.copy (), value, value_id);
 }
 
-static vn_nary_op_t vn_nary_op_insert_stmt (gimple *stmt, tree result);
+static vn_nary_op_t vn_nary_op_insert_stmt (gimple *, tree);
+static unsigned int vn_nary_length_from_stmt (gimple *);
+static vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, obstack *);
+static vn_nary_op_t vn_nary_op_insert_into (vn_nary_op_t,
+					    vn_nary_op_table_type *, bool);
+static void init_vn_nary_op_from_stmt (vn_nary_op_t, gimple *);
 
 /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables.  */
 
@@ -1751,9 +1737,14 @@  vn_nary_build_or_lookup_1 (gimple_match_
 	 lookups there will fall back to the valid table.  */
       else if (current_info == optimistic_info)
 	{
-	  current_info = valid_info;
-	  vn_nary_op_insert_stmt (new_stmt, result);
-	  current_info = optimistic_info;
+	  unsigned int length = vn_nary_length_from_stmt (new_stmt);
+	  vn_nary_op_t vno1
+	    = alloc_vn_nary_op_noinit (length, &vn_tables_insert_obstack);
+	  vno1->value_id = VN_INFO (result)->value_id;
+	  vno1->length = length;
+	  vno1->result = result;
+	  init_vn_nary_op_from_stmt (vno1, new_stmt);
+	  vn_nary_op_insert_into (vno1, valid_info->nary, true);
 	}
       else
 	vn_nary_op_insert_stmt (new_stmt, result);
@@ -2620,7 +2611,7 @@  vn_reference_insert (tree op, tree resul
   vn_reference_t vr1;
   bool tem;
 
-  vr1 = current_info->references_pool->allocate ();
+  vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s);
   if (TREE_CODE (result) == SSA_NAME)
     vr1->value_id = VN_INFO (result)->value_id;
   else
@@ -2665,7 +2656,7 @@  vn_reference_insert_pieces (tree vuse, a
   vn_reference_s **slot;
   vn_reference_t vr1;
 
-  vr1 = current_info->references_pool->allocate ();
+  vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s);
   vr1->value_id = value_id;
   vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE;
   vr1->operands = valueize_refs (operands);
@@ -2931,8 +2922,7 @@  alloc_vn_nary_op_noinit (unsigned int le
 static vn_nary_op_t
 alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id)
 {
-  vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length,
-					       &current_info->nary_obstack);
+  vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length, &vn_tables_obstack);
 
   vno1->value_id = value_id;
   vno1->length = length;
@@ -3016,8 +3006,8 @@  vn_nary_op_insert_stmt (gimple *stmt, tr
 static inline hashval_t
 vn_phi_compute_hash (vn_phi_t vp1)
 {
-  inchash::hash hstate (vp1->phiargs.length () > 2
-			? vp1->block->index : vp1->phiargs.length ());
+  inchash::hash hstate (EDGE_COUNT (vp1->block->preds) > 2
+			? vp1->block->index : EDGE_COUNT (vp1->block->preds));
   tree phi1op;
   tree type;
   edge e;
@@ -3089,10 +3079,10 @@  vn_phi_eq (const_vn_phi_t const vp1, con
 
   if (vp1->block != vp2->block)
     {
-      if (vp1->phiargs.length () != vp2->phiargs.length ())
+      if (EDGE_COUNT (vp1->block->preds) != EDGE_COUNT (vp2->block->preds))
 	return false;
 
-      switch (vp1->phiargs.length ())
+      switch (EDGE_COUNT (vp1->block->preds))
 	{
 	case 1:
 	  /* Single-arg PHIs are just copies.  */
@@ -3167,10 +3157,9 @@  vn_phi_eq (const_vn_phi_t const vp1, con
 
   /* Any phi in the same block will have it's arguments in the
      same edge order, because of how we store phi nodes.  */
-  int i;
-  tree phi1op;
-  FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
+  for (unsigned i = 0; i < EDGE_COUNT (vp1->block->preds); ++i)
     {
+      tree phi1op = vp1->phiargs[i];
       tree phi2op = vp2->phiargs[i];
       if (phi1op == VN_TOP || phi2op == VN_TOP)
 	continue;
@@ -3181,8 +3170,6 @@  vn_phi_eq (const_vn_phi_t const vp1, con
   return true;
 }
 
-static vec<tree> shared_lookup_phiargs;
-
 /* Lookup PHI in the current hash table, and return the resulting
    value number if it exists in the hash table.  Return NULL_TREE if
    it does not exist in the hash table. */
@@ -3191,38 +3178,38 @@  static tree
 vn_phi_lookup (gimple *phi)
 {
   vn_phi_s **slot;
-  struct vn_phi_s vp1;
+  struct vn_phi_s *vp1;
   edge e;
   edge_iterator ei;
 
-  shared_lookup_phiargs.truncate (0);
-  shared_lookup_phiargs.safe_grow (gimple_phi_num_args (phi));
+  vp1 = XALLOCAVAR (struct vn_phi_s,
+		    sizeof (struct vn_phi_s)
+		    + (gimple_phi_num_args (phi) - 1) * sizeof (tree));
 
   /* Canonicalize the SSA_NAME's to their value number.  */
   FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
     {
       tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
-      shared_lookup_phiargs[e->dest_idx] = def;
+      vp1->phiargs[e->dest_idx] = def;
     }
-  vp1.type = TREE_TYPE (gimple_phi_result (phi));
-  vp1.phiargs = shared_lookup_phiargs;
-  vp1.block = gimple_bb (phi);
+  vp1->type = TREE_TYPE (gimple_phi_result (phi));
+  vp1->block = gimple_bb (phi);
   /* Extract values of the controlling condition.  */
-  vp1.cclhs = NULL_TREE;
-  vp1.ccrhs = NULL_TREE;
-  basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1.block);
+  vp1->cclhs = NULL_TREE;
+  vp1->ccrhs = NULL_TREE;
+  basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
   if (EDGE_COUNT (idom1->succs) == 2)
     if (gcond *last1 = safe_dyn_cast <gcond *> (last_stmt (idom1)))
       {
-	vp1.cclhs = vn_valueize (gimple_cond_lhs (last1));
-	vp1.ccrhs = vn_valueize (gimple_cond_rhs (last1));
+	vp1->cclhs = vn_valueize (gimple_cond_lhs (last1));
+	vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1));
       }
-  vp1.hashcode = vn_phi_compute_hash (&vp1);
-  slot = current_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
+  vp1->hashcode = vn_phi_compute_hash (vp1);
+  slot = current_info->phis->find_slot_with_hash (vp1, vp1->hashcode,
 						  NO_INSERT);
   if (!slot && current_info == optimistic_info)
-    slot = valid_info->phis->find_slot_with_hash (&vp1, vp1.hashcode,
+    slot = valid_info->phis->find_slot_with_hash (vp1, vp1->hashcode,
 						  NO_INSERT);
   if (!slot)
     return NULL_TREE;
@@ -3236,23 +3223,22 @@  static vn_phi_t
 vn_phi_insert (gimple *phi, tree result)
 {
   vn_phi_s **slot;
-  vn_phi_t vp1 = current_info->phis_pool->allocate ();
-  vec<tree> args = vNULL;
+  vn_phi_t vp1 = (vn_phi_t) obstack_alloc (&vn_tables_obstack,
+					   sizeof (vn_phi_s)
+					   + ((gimple_phi_num_args (phi) - 1)
+					      * sizeof (tree)));
   edge e;
   edge_iterator ei;
 
-  args.safe_grow (gimple_phi_num_args (phi));
-
   /* Canonicalize the SSA_NAME's to their value number.  */
   FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
     {
       tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
-      args[e->dest_idx] = def;
+      vp1->phiargs[e->dest_idx] = def;
     }
   vp1->value_id = VN_INFO (result)->value_id;
   vp1->type = TREE_TYPE (gimple_phi_result (phi));
-  vp1->phiargs = args;
   vp1->block = gimple_bb (phi);
   /* Extract values of the controlling condition.  */
   vp1->cclhs = NULL_TREE;
@@ -3781,7 +3767,7 @@  visit_reference_op_call (tree lhs, gcall
 	}
       if (lhs)
 	changed |= set_ssa_val_to (lhs, lhs);
-      vr2 = current_info->references_pool->allocate ();
+      vr2 = XOBNEW (&vn_tables_obstack, vn_reference_s);
       vr2->vuse = vr1.vuse;
       /* As we are not walking the virtual operand chain we know the
 	 shared_lookup_references are still original so we can re-use
@@ -4317,48 +4303,6 @@  sort_scc (vec<tree> scc)
   scc.qsort (compare_ops);
 }
 
-/* Insert the no longer used nary ONARY to the hash INFO.  */
-
-static void
-copy_nary (vn_nary_op_t onary, vn_tables_t info)
-{
-  size_t size = sizeof_vn_nary_op (onary->length);
-  vn_nary_op_t nary = alloc_vn_nary_op_noinit (onary->length,
-					       &info->nary_obstack);
-  memcpy (nary, onary, size);
-  vn_nary_op_insert_into (nary, info->nary, false);
-}
-
-/* Insert the no longer used phi OPHI to the hash INFO.  */
-
-static void
-copy_phi (vn_phi_t ophi, vn_tables_t info)
-{
-  vn_phi_t phi = info->phis_pool->allocate ();
-  vn_phi_s **slot;
-  memcpy (phi, ophi, sizeof (*phi));
-  ophi->phiargs.create (0);
-  slot = info->phis->find_slot_with_hash (phi, phi->hashcode, INSERT);
-  gcc_assert (!*slot);
-  *slot = phi;
-}
-
-/* Insert the no longer used reference OREF to the hash INFO.  */
-
-static void
-copy_reference (vn_reference_t oref, vn_tables_t info)
-{
-  vn_reference_t ref;
-  vn_reference_s **slot;
-  ref = info->references_pool->allocate ();
-  memcpy (ref, oref, sizeof (*ref));
-  oref->operands.create (0);
-  slot = info->references->find_slot_with_hash (ref, ref->hashcode, INSERT);
-  if (*slot)
-    free_reference (*slot);
-  *slot = ref;
-}
-
 /* Process a strongly connected component in the SSA graph.  */
 
 static void
@@ -4410,33 +4354,60 @@  process_scc (vec<tree> scc)
       /* As we are value-numbering optimistically we have to
 	 clear the expression tables and the simplified expressions
 	 in each iteration until we converge.  */
-      optimistic_info->nary->empty ();
-      optimistic_info->phis->empty ();
-      optimistic_info->references->empty ();
-      obstack_free (&optimistic_info->nary_obstack, NULL);
-      gcc_obstack_init (&optimistic_info->nary_obstack);
-      optimistic_info->phis_pool->release ();
-      optimistic_info->references_pool->release ();
+      gcc_assert (optimistic_info->nary->elements () == 0
+		  && optimistic_info->phis->elements () == 0
+		  && optimistic_info->references->elements () == 0);
+      void *ob_top = obstack_alloc (&vn_tables_obstack, 0);
       FOR_EACH_VEC_ELT (scc, i, var)
 	gcc_assert (!VN_INFO (var)->needs_insertion
 		    && VN_INFO (var)->expr == NULL);
       FOR_EACH_VEC_ELT (scc, i, var)
 	changed |= visit_use (var);
+      if (changed)
+	{
+	  optimistic_info->nary->empty ();
+	  optimistic_info->phis->empty ();
+	  FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->references,
+				       ref, vn_reference_t, hir)
+	    {
+	      ref->operands.release ();
+	      optimistic_info->references->clear_slot (&*hir);
+	    }
+	  optimistic_info->references->empty ();
+	  obstack_free (&vn_tables_obstack, ob_top);
+	}
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Processing SCC needed %d iterations\n", iterations);
   statistics_histogram_event (cfun, "SCC iterations", iterations);
 
-  /* Finally, copy the contents of the no longer used optimistic
-     table to the valid table.  */
+  /* Finally, move the contents of the no longer used optimistic
+     table to the valid table and clear the optimistic table.  */
   FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->nary, nary, vn_nary_op_t, hin)
-    copy_nary (nary, valid_info);
+    {
+      optimistic_info->nary->clear_slot (&*hin);
+      vn_nary_op_insert_into (nary, valid_info->nary, false);
+    }
   FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->phis, phi, vn_phi_t, hip)
-    copy_phi (phi, valid_info);
+    {
+      optimistic_info->phis->clear_slot (&*hip);
+      vn_phi_s **slot
+	= valid_info->phis->find_slot_with_hash (phi, phi->hashcode, INSERT);
+      gcc_assert (!*slot);
+      *slot = phi;
+    }
   FOR_EACH_HASH_TABLE_ELEMENT (*optimistic_info->references,
 			       ref, vn_reference_t, hir)
-    copy_reference (ref, valid_info);
+    {
+      optimistic_info->references->clear_slot (&*hir);
+      vn_reference_s **slot
+	= valid_info->references->find_slot_with_hash (ref, ref->hashcode,
+						       INSERT);
+      if (*slot)
+	free_reference (*slot);
+      *slot = ref;
+    }
 
   current_info = valid_info;
 }
@@ -4596,11 +4567,6 @@  allocate_vn_table (vn_tables_t table)
   table->phis = new vn_phi_table_type (23);
   table->nary = new vn_nary_op_table_type (23);
   table->references = new vn_reference_table_type (23);
-
-  gcc_obstack_init (&table->nary_obstack);
-  table->phis_pool = new object_allocator<vn_phi_s> ("VN phis");
-  table->references_pool = new object_allocator<vn_reference_s>
-    ("VN references");
 }
 
 /* Free a value number table.  */
@@ -4608,15 +4574,17 @@  allocate_vn_table (vn_tables_t table)
 static void
 free_vn_table (vn_tables_t table)
 {
+  /* Walk over elements and release vectors.  */
+  vn_reference_iterator_type hir;
+  vn_reference_t vr;
+  FOR_EACH_HASH_TABLE_ELEMENT (*table->references, vr, vn_reference_t, hir)
+    vr->operands.release ();
   delete table->phis;
   table->phis = NULL;
   delete table->nary;
   table->nary = NULL;
   delete table->references;
   table->references = NULL;
-  obstack_free (&table->nary_obstack, NULL);
-  delete table->phis_pool;
-  delete table->references_pool;
 }
 
 static void
@@ -4642,7 +4610,6 @@  init_scc_vn (void)
   vn_ssa_aux_table.safe_grow_cleared (num_ssa_names + 1);
   gcc_obstack_init (&vn_ssa_aux_obstack);
 
-  shared_lookup_phiargs.create (0);
   shared_lookup_references.create (0);
   rpo_numbers = XNEWVEC (int, last_basic_block_for_fn (cfun));
   rpo_numbers_temp =
@@ -4663,6 +4630,8 @@  init_scc_vn (void)
   renumber_gimple_stmt_uids ();
 
   /* Create the valid and optimistic value numbering tables.  */
+  gcc_obstack_init (&vn_tables_obstack);
+  gcc_obstack_init (&vn_tables_insert_obstack);
   valid_info = XCNEW (struct vn_tables_s);
   allocate_vn_table (valid_info);
   optimistic_info = XCNEW (struct vn_tables_s);
@@ -4765,7 +4734,6 @@  free_scc_vn (void)
   delete constant_to_value_id;
   constant_to_value_id = NULL;
   BITMAP_FREE (constant_value_ids);
-  shared_lookup_phiargs.release ();
   shared_lookup_references.release ();
   XDELETEVEC (rpo_numbers);
 
@@ -4783,6 +4751,8 @@  free_scc_vn (void)
   XDELETE (valid_info);
   free_vn_table (optimistic_info);
   XDELETE (optimistic_info);
+  obstack_free (&vn_tables_obstack, NULL);
+  obstack_free (&vn_tables_insert_obstack, NULL);
 
   BITMAP_FREE (const_parms);
 }
Index: gcc/tree-ssa-sccvn.h
===================================================================
--- gcc/tree-ssa-sccvn.h	(revision 262871)
+++ gcc/tree-ssa-sccvn.h	(working copy)
@@ -65,13 +65,14 @@  typedef struct vn_phi_s
   /* Unique identifier that all expressions with the same value have. */
   unsigned int value_id;
   hashval_t hashcode;
-  vec<tree> phiargs;
   basic_block block;
   /* Controlling condition lhs/rhs.  */
   tree cclhs;
   tree ccrhs;
   tree type;
   tree result;
+  /* The number of args is determined by EDGE_COUT (block->preds).  */
+  tree phiargs[1];
 } *vn_phi_t;
 typedef const struct vn_phi_s *const_vn_phi_t;