This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[dataflow] Avoid hashing pointers in DSE


Kenny found a testcase that was failing because of DSE.  The test compared
RTL dump files, and different runs of DSE could produce different rtl dumps
(although they produced the same code).  The problem was that DSE was hashing
pointers to cselib_val structures.  When trying to fix that problem,
I discovered that we were also referring to cselib_vals even after
remove_useless_values had freed them.

I thought about two main types of fix.  Plan A was to add a true value
number to cselib_val; one that will be unique within the function.  The
idea seemed quite appealing from a conceptual point of view, but I decided
it would be unacceptable to make the structure bigger on ILP32 hosts.
(I don't think it would make a difference on most LP64 hosts, because
the current structure starts with an integer field followed by a
pointer field.)

So instead I went for plan B:

  (1) Make remove_useless_values call a hook before freeing VALUEs with
      null LOCS fields.

  (2) Make DSE use two tables to track stores in a basic block, one for
      invariant stores and one for value numbers.

  (3) As an optimisation enabled by (2), change DCE's representation
      of base addresses so that it is the union of an rtx and a
      cselib_val.  We always know which applies from context.

  (4) Using the hook in (1), make DSE process base addresses whose
      cselib_vals are about to be freed.  This extra walk of the hash
      table shouldn't be expensive in context; remove_useless_values
      itself is quadratic, and it also contains a similar walk of
      _all_ active cselib_vals.

I've bootstrapped and tested the patch on x86_64-linux-gnu.  There were
no regressions.  I've also diffed the -O2 output of gcc.c-torture and
gcc.dg before and after the patch and saw no changes.  Approved by
Kenny and applied to dataflow-branch.

Richard


gcc/
	* cselib.h (cselib_discard_hook): Declare.
	* cselib.c (cselib_discard_hook): New variable.
	(remove_useless_values): Call it before freeing useless values.
	* dce.c (base_address): New union.
	(store_base_info): Change the type of the base field from "rtx"
	to "union base_address".
	(local_invariant_stores, local_value_stores): New variables.
	(store_base_eq): Split into...
	(invariant_store_base_eq, value_store_base_eq): ...these new functions.
	(store_base_hash): Split into...
	(invariant_store_base_hash, value_store_base_hash): ...these
	new functions.
	(store_base_del): Fix formatting.
	(init_store_group): Split into...
	(init_invariant_store_group, init_value_store_group): ...these
	new functions.
	(init_dse): Use init_invariant_store_group instead of init_store_group.
	(get_canonical_address): Delete.
	(add_store_offset): Change the type of BASE from "rtx" to "union
	base_address *".
	(record_store): Remove the GROUP parameter.  Don't call
	get_canonical_address.  Store the base in a "union base_address" and
	add stores to either local_invariant_stores or local_value_stores.
	(record_stores): Remove the GROUP parameter and adjust the calls
	to record_store.
	(store_base_local): Add a parameter that indicates whether stores
	are invariant or cselib_vals.
	(invariant_store_base_local): New function.
	(value_store_base_local): Likewise.
	(value_store_base_useless): Likewise.
	(remove_useless_values): Likewise.
	(store_base_prune_needed): Adjust for store_base_info changes.
	(prescan_insns_for_dse): Remove the local group variable and use
	local_invariant_stores and local_value_stores instead.  Adjust the
	call to record_stores.  Use remove_useless_values as the
	cselib_discard_hook while processing a basic block.

Index: gcc/cselib.h
===================================================================
--- gcc/cselib.h	(revision 116179)
+++ gcc/cselib.h	(working copy)
@@ -62,6 +62,8 @@ struct elt_list GTY(())
   cselib_val *elt;
 };
 
+extern void (*cselib_discard_hook) (void);
+
 extern cselib_val *cselib_lookup (rtx, enum machine_mode, int);
 extern void cselib_init (bool record_memory);
 extern void cselib_clear_table (void);
Index: gcc/cselib.c
===================================================================
--- gcc/cselib.c	(revision 116179)
+++ gcc/cselib.c	(working copy)
@@ -131,6 +131,10 @@ static GTY(()) rtx callmem;
    each time memory is invalidated.  */
 static cselib_val *first_containing_mem = &dummy_val;
 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
+
+/* If nonnull, cselib will call this function before freeing useless
+   VALUEs.  A VALUE is deemed useless if its "locs" field is null.  */
+void (*cselib_discard_hook) (void);
 
 
 /* Allocate a struct elt_list and fill in its two elements with the
@@ -367,6 +371,9 @@ remove_useless_values (void)
       }
   *p = &dummy_val;
 
+  if (cselib_discard_hook)
+    cselib_discard_hook ();
+
   htab_traverse (cselib_hash_table, discard_useless_values, 0);
 
   gcc_assert (!n_useless_values);
Index: gcc/dce.c
===================================================================
--- gcc/dce.c	(revision 116179)
+++ gcc/dce.c	(working copy)
@@ -818,10 +818,17 @@ typedef struct store_offset_info store_o
 DEF_VEC_O(store_offset_info);
 DEF_VEC_ALLOC_O(store_offset_info,heap);
 
+/* Information about a base address.  Addresses are either function
+   invariants or cselib values, depending on context.  */
+union base_address {
+  rtx invariant;
+  cselib_val *value;
+};
+
 /* A structure for grouping together stores that share the same base address.
    STORES is a list of stores with base address BASE.  */
 struct store_base_info {
-  rtx base;
+  union base_address base;
   VEC(store_offset_info,heap) *stores;
 };
 typedef struct store_base_info store_base_info;
@@ -843,6 +850,10 @@ typedef struct store_group_info store_gr
 /* The identifiers of stores for which we haven't found a potential use.  */
 static VEC(int,heap) *unmarked_stores;
 
+/* Used while processing a basic block.  LOCAL_INVARIANT_STORES contains
+   stores with invariant addresses; LOCAL_VALUE_STORES contains stores
+   whose base addresses are cselib_vals.  */
+static store_group_info local_invariant_stores, local_value_stores;
 
 /* max_in_luid[B][S] is the luid of the last instruction in basic block B
    that is reached by the incoming value of store S.  It is -1 if store S
@@ -851,31 +862,47 @@ static VEC(int,heap) *unmarked_stores;
 static int **max_in_luid;
 
 /* Hashtable callbacks for maintaining the "bases" field of
-   store_group_info.  */
+   store_group_info, given that the addresses are function invariants.  */
 
 static int
-store_base_eq (const void *p1, const void *p2)
+invariant_store_base_eq (const void *p1, const void *p2)
 {
   const store_base_info *sb1 = (const store_base_info *) p1;
   const store_base_info *sb2 = (const store_base_info *) p2;
-  return (GET_CODE (sb1->base) == VALUE
-	  ? sb1->base == sb2->base
-	  : rtx_equal_p (sb1->base, sb2->base));
+  return rtx_equal_p (sb1->base.invariant, sb2->base.invariant);
 }
 
 static hashval_t
-store_base_hash (const void *p)
-  {
+invariant_store_base_hash (const void *p)
+{
   const store_base_info *sb = (const store_base_info *) p;
   int do_not_record;
-  return (GET_CODE (sb->base) == VALUE
-	  ? htab_hash_pointer (sb->base)
-	  : hash_rtx (sb->base, Pmode, &do_not_record, NULL, false));
+  return hash_rtx (sb->base.invariant, Pmode, &do_not_record, NULL, false);
 }
 
+/* Hashtable callbacks for maintaining the "bases" field of
+   store_group_info, given that the addresses are cselib_vals.  */
+
+static int
+value_store_base_eq (const void *p1, const void *p2)
+{
+  const store_base_info *sb1 = (const store_base_info *) p1;
+  const store_base_info *sb2 = (const store_base_info *) p2;
+  return sb1->base.value == sb2->base.value;
+}
+
+static hashval_t
+value_store_base_hash (const void *p)
+{
+  const store_base_info *sb = (const store_base_info *) p;
+  return sb->base.value->value;
+}
+
+/* Hash table callback for the "bases" field of store_group_info.  */
+
 static void
 store_base_del (void *p)
-  {
+{
   store_base_info *sb = (store_base_info *) p;
   VEC_free (store_offset_info, heap, sb->stores);
   XDELETE (sb);
@@ -922,14 +949,24 @@ rs_transfer_function (struct dataflow * 
   return bitmap_ior_and_compl (out, gen, in, kill);
 }
  
-/* Initialize store group *GROUP.  */
+/* Initialize store group *GROUP so that it can hold invariant addresses.  */
+ 
+static void
+init_invariant_store_group (store_group_info *group)
+{
+  group->stores = NULL;
+  group->bases = htab_create (11, invariant_store_base_hash,
+			      invariant_store_base_eq, store_base_del);
+}
+
+/* Initialize store group *GROUP so that it can hold cselib_val addresses.  */
  
- static void
-   init_store_group (store_group_info *group)
+static void
+init_value_store_group (store_group_info *group)
 {
   group->stores = NULL;
-  group->bases = htab_create (11, store_base_hash,
-			      store_base_eq, store_base_del);
+  group->bases = htab_create (11, value_store_base_hash,
+			      value_store_base_eq, store_base_del);
 }
 
 /* Forget about all stores in *GROUP.  */
@@ -1043,7 +1080,7 @@ end_unmarked_stores (void)
 static void
 init_dse (void)
 {
-  init_store_group (&stores);
+  init_invariant_store_group (&stores);
 }
 
 /* Free the structures used by DSE.  */
@@ -1111,33 +1148,11 @@ split_address (rtx x, rtx *base_out, HOS
   *base_out = x;
 }
 
-/* Try to convert the address of memory reference MEM into a canonical
-   base + offset expression.  Return true on success, storing the two
-   components in *BASE_OUT and *OFFSET_OUT respectively.  *BASE_OUT
-   will be either a nonvarying address or a VALUE rtx.  */
-
-static bool
-get_canonical_address (rtx mem, rtx *base_out, HOST_WIDE_INT *offset_out)
-{
-  cselib_val *val;
-
-  split_address (canon_rtx (XEXP (mem, 0)), base_out, offset_out);
-  if (!rtx_varies_p (*base_out, false))
-    return true;
-
-  val = cselib_lookup (*base_out, Pmode, true);
-  if (val == NULL)
-    return false;
-
-  *base_out = val->u.val_rtx;
-  return true;
-}
-
 /* Add a store_offset_info structure to GROUP, given that the next
    store to be added to it will span bytes [BASE + BEGIN, BASE + END).  */
 
 static void
-add_store_offset (store_group_info *group, rtx base,
+add_store_offset (store_group_info *group, union base_address *base,
 		  HOST_WIDE_INT begin, HOST_WIDE_INT end)
 {
   store_base_info *sb, tmp_sb;
@@ -1146,13 +1161,13 @@ add_store_offset (store_group_info *grou
 
   /* Find the store_base_info structure for BASE, creating a new one
      if necessary.  */
-  tmp_sb.base = base;
+  tmp_sb.base = *base;
   slot = htab_find_slot (group->bases, &tmp_sb, INSERT);
   sb = (store_base_info *) *slot;
   if (sb == NULL)
     {
       *slot = sb = XNEW (store_base_info);
-      sb->base = base;
+      sb->base = *base;
       sb->stores = NULL;
     }
 
@@ -1164,13 +1179,16 @@ add_store_offset (store_group_info *grou
 }
 
 /* BODY is an instruction pattern that belongs to INSN.  Return true
-   if it is a candidate store, adding it to GROUP if so.  */
+   if it is a candidate store, adding it to the appropriate local
+   store group if so.  */
 
 static bool
-record_store (store_group_info *group, rtx body, rtx insn)
+record_store (rtx body, rtx insn)
 {
+  store_group_info *group;
   store_info *store;
-  rtx base, mem;
+  rtx mem;
+  union base_address base;
   HOST_WIDE_INT offset;
 
   /* Check whether INSN sets a single value.  */
@@ -1185,11 +1203,18 @@ record_store (store_group_info *group, r
     return false;
 
   /* Split the address into canonical BASE + OFFSET terms.  */
-  if (!get_canonical_address (mem, &base, &offset))
-    return false;
+  group = &local_invariant_stores;
+  split_address (canon_rtx (XEXP (mem, 0)), &base.invariant, &offset);
+  if (rtx_varies_p (base.invariant, false))
+    {
+      group = &local_value_stores;
+      base.value = cselib_lookup (base.invariant, Pmode, true);
+      if (base.value == NULL)
+	return false;
+    }
 
-  /* Add a store_offset_info structure for the sture.  */
-  add_store_offset (group, base, offset,
+  /* Add a store_offset_info structure for the store.  */
+  add_store_offset (group, &base, offset,
 		    offset + GET_MODE_SIZE (GET_MODE (mem)));
 
   /* Record the store itself.  */
@@ -1202,11 +1227,12 @@ record_store (store_group_info *group, r
   return true;
 }
 
-/* Add all candidate stores in INSN to GROUP.  Mark INSN if some part
-   of it is not a candidate store and assigns to a non-register target.  */
+/* Apply record_store to all candidate stores in INSN.  Mark INSN
+   if some part of it is not a candidate store and assigns to a
+   non-register target.  */
 
 static void
-record_stores (store_group_info *group, rtx insn)
+record_stores (rtx insn)
 {
   rtx body;
   int i;
@@ -1215,11 +1241,11 @@ record_stores (store_group_info *group, 
   if (GET_CODE (body) == PARALLEL)
     for (i = 0; i < XVECLEN (body, 0); i++)
       {
-	if (!record_store (group, XVECEXP (body, 0, i), insn))
+	if (!record_store (XVECEXP (body, 0, i), insn))
 	  mark_nonreg_stores (XVECEXP (body, 0, i), insn, false);
       }
   else
-    if (!record_store (group, body, insn))
+    if (!record_store (body, insn))
       mark_nonreg_stores (body, insn, false);
 }
 
@@ -1240,14 +1266,17 @@ store_offset_compare (const void *p1, co
     return offset2->store - offset1->store;
 }
 
-/* A htab_traverse callback in which *SLOT is a store_base_info structure
-   that belongs to store group DATA.  Work out the max_gen_luid of the
-   stores, all of which are known to be in the same block.  Decide whether
-   we can safely compute the reaching information for each store.
-   Add it to STORES if we can, otherwise mark it as needed.  */
+/* *SLOT is a store_base_info structure that belongs to store group DATA.
+   INVARIANT_P is true if all base addresses are function invariants; it is
+   false if all addresses are cselib_vals.
+
+   Work out the max_gen_luid of the stores, all of which are known to be
+   in the same block.  Decide whether we can safely compute the reaching
+   information for each store.  Add it to STORES if we can, otherwise
+   mark it as needed.  Return true.  */
 
-static int
-store_base_local (void **slot, void *data)
+static inline int
+store_base_local (void **slot, void *data, bool invariant_p)
 {
   store_base_info *sb = (store_base_info *) *slot;
   store_group_info *group = (store_group_info *) data;
@@ -1279,12 +1308,12 @@ store_base_local (void **slot, void *dat
 	    storei->max_gen_luid = storej->luid;
 	}
 
-      if (GET_CODE (sb->base) != VALUE)
+      if (invariant_p)
 	{
 	  /* An invariant address.  We can track STOREJ globally if reaches
 	     the end of the block.  We will also want to know whether STOREJ
 	     kills stores in other basic blocks.  */
-	  add_store_offset (&stores, sb->base, so[j].begin, so[j].end);
+	  add_store_offset (&stores, &sb->base, so[j].begin, so[j].end);
 	  VEC_safe_push (store_info, heap, stores.stores, storej);
 	}
       else
@@ -1300,6 +1329,49 @@ store_base_local (void **slot, void *dat
   return true;
 }
 
+/* Like store_base_local, but for invariant base addresses only.  */
+
+static int
+invariant_store_base_local (void **slot, void *data)
+{
+  return store_base_local (slot, data, true);
+}
+
+/* Like store_base_local, but for cselib_val base addresses only.  */
+
+static int
+value_store_base_local (void **slot, void *data)
+{
+  return store_base_local (slot, data, false);
+}
+
+/* Like value_store_base_local, but only handle values that have
+   no elt_list_locs left.  Remove all such entries from the hash table.  */
+
+static int
+value_store_base_useless (void **slot, void *data)
+{
+  store_base_info *sb = (store_base_info *) *slot;
+  store_group_info *group = (store_group_info *) data;
+
+  if (sb->base.value->locs == NULL)
+    {
+      value_store_base_local (slot, data);
+      htab_clear_slot (group->bases, slot);
+    }
+  return true;
+}
+
+/* Process and remove all entries in local_value_stores that cselib
+   considers useless.  The associated cselib_vals are about to be freed.  */
+
+static void
+remove_useless_values (void)
+{
+  htab_traverse (local_value_stores.bases,
+		 value_store_base_useless, &local_value_stores);
+}
+
 /* A htab_traverse callback in which *SLOT is a store_base_info structure
    attached to STORES.  Work out the values of gen_vec, kill_vec
    and max_in_luid.  */
@@ -1415,7 +1487,7 @@ store_base_prune_needed (void **slot, vo
   store_offset_info *so;
   unsigned int i;
 
-  if (sb->base == frame_pointer_rtx && !frame_stores_escape_p ())
+  if (sb->base.invariant == frame_pointer_rtx && !frame_stores_escape_p ())
     for (i = 0; VEC_iterate (store_offset_info, sb->stores, i, so); i++)
       bitmap_clear_bit (needed, so->store);
 
@@ -1556,19 +1628,19 @@ mark_dependent_stores (rtx insn)
 static void
 prescan_insns_for_dse (void)
 {
-  store_group_info group;
   basic_block bb;
   rtx insn;
 
   if (dump_file)
     fprintf (dump_file, "Finding stores and needed instructions:\n");
 
-  /* If we haven't added a store to this group yet, initialize it now.  */
   cselib_init (false);
-  init_store_group (&group);
+  init_invariant_store_group (&local_invariant_stores);
+  init_value_store_group (&local_value_stores);
   FOR_EACH_BB (bb)
     {
       cselib_clear_table ();
+      cselib_discard_hook = remove_useless_values;
       FOR_BB_INSNS (bb, insn)
 	{
 	  if (INSN_P (insn))
@@ -1576,14 +1648,20 @@ prescan_insns_for_dse (void)
 	      if (!deletable_insn_p (insn))
 		mark_insn (insn, false);
 	      else
-		record_stores (&group, insn);
+		record_stores (insn);
 	    }
 	  cselib_process_insn (insn);
 	}
-      htab_traverse (group.bases, store_base_local, &group);
-      empty_store_group (&group);
+      cselib_discard_hook = NULL;
+      htab_traverse (local_invariant_stores.bases,
+		     invariant_store_base_local, &local_invariant_stores);
+      htab_traverse (local_value_stores.bases,
+		     value_store_base_local, &local_value_stores);
+      empty_store_group (&local_invariant_stores);
+      empty_store_group (&local_value_stores);
     }
-  end_store_group (&group);
+  end_store_group (&local_invariant_stores);
+  end_store_group (&local_value_stores);
   cselib_finish ();
 }
 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]