Fix PR63155

The following fixes the memory use at -O0 from out-of-SSA coalescing
(conflict computation in particular) with lots of abnormals (setjmp
calls).  After reviewing I found no reason to not use
compute_optimized_partition_bases since we populate the coalesce lists
and used_in_copy pieces correctly at -O0 and using 
compute_optimized_partition_bases avoids having gigantic bases for
type-equivalent variables, specifically:

-       /* This restricts what anonymous SSA names we can coalesce
-          as it restricts the sets we compute conflicts for.
-          Using TREE_TYPE to generate sets is the easiest as
-          type equivalency also holds for SSA names with the same
-          underlying decl.
-
-          Check gimple_can_coalesce_p when changing this code.  */
-       m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
-                       ? TYPE_CANONICAL (TREE_TYPE (var))
-                       : TREE_TYPE (var));

but instead uses bases that only include things that we desire to
coalesce later.  Memory use of the conflict bitmaps is quadratic
in the sizes of the base sets so splitting up to more bases is
desirable (and doesn't change code generation).

{,-O0} Bootstrap and regtest running on x86_64-unknown-linux-gnu.

I still have one other memory/compile-time improvement patch but
I lack a testcase that shows a measurable difference.

Richard.

2018-09-17  Richard Biener  <rguenther@suse.de>

	PR middle-end/63155
	* tree-ssa-coalesce.c (tree_int_map_hasher): Remove.
	(compute_samebase_partition_bases): Likewise.
	(coalesce_ssa_name): Always use compute_optimized_partition_bases.

On Mon, 17 Sep 2018, Richard Biener wrote:

> 
> The following fixes the memory use at -O0 from out-of-SSA coalescing
> (conflict computation in particular) with lots of abnormals (setjmp
> calls).  After reviewing I found no reason to not use
> compute_optimized_partition_bases since we populate the coalesce lists
> and used_in_copy pieces correctly at -O0 and using 
> compute_optimized_partition_bases avoids having gigantic bases for
> type-equivalent variables, specifically:
> 
> -       /* This restricts what anonymous SSA names we can coalesce
> -          as it restricts the sets we compute conflicts for.
> -          Using TREE_TYPE to generate sets is the easiest as
> -          type equivalency also holds for SSA names with the same
> -          underlying decl.
> -
> -          Check gimple_can_coalesce_p when changing this code.  */
> -       m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
> -                       ? TYPE_CANONICAL (TREE_TYPE (var))
> -                       : TREE_TYPE (var));
> 
> but instead uses bases that only include things that we desire to
> coalesce later.  Memory use of the conflict bitmaps is quadratic
> in the sizes of the base sets so splitting up to more bases is
> desirable (and doesn't change code generation).
> 
> {,-O0} Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> 
> I still have one other memory/compile-time improvement patch but
> I lack a testcase that shows a measurable difference.

Re-bootstrapped and tested the following which adds a small
cleanup to gimple_can_coalesce_p, simplifying it a bit.

Committed to trunk.  If there's no fallout I plan to backport this.

Richard.

2018-09-17  Richard Biener  <rguenther@suse.de>

	PR middle-end/63155
	* tree-ssa-coalesce.c (tree_int_map_hasher): Remove.
	(compute_samebase_partition_bases): Likewise.
	(coalesce_ssa_name): Always use compute_optimized_partition_bases.
	(gimple_can_coalesce_p): Simplify.

Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c	(revision 264369)
+++ gcc/tree-ssa-coalesce.c	(working copy)
@@ -1579,22 +1579,9 @@ gimple_can_coalesce_p (tree name1, tree
 
   /* If the types are not the same, see whether they are compatible.  This
      (for example) allows coalescing when the types are fundamentally the
-     same, but just have different names.
-
-     In the non-optimized case, we must first test TYPE_CANONICAL because
-     we use it to compute the partition_to_base_index of the map.  */
-  if (flag_tree_coalesce_vars)
-    {
-      if (types_compatible_p (t1, t2))
-	goto check_modes;
-    }
-  else
-    {
-      if (TYPE_CANONICAL (t1)
-	  && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
-	  && types_compatible_p (t1, t2))
-	goto check_modes;
-    }
+     same, but just have different names.  */
+  if (types_compatible_p (t1, t2))
+    goto check_modes;
 
   return false;
 }
@@ -1720,89 +1707,6 @@ compute_optimized_partition_bases (var_m
   partition_delete (tentative);
 }
 
-/* Hashtable helpers.  */
-
-struct tree_int_map_hasher : nofree_ptr_hash <tree_int_map>
-{
-  static inline hashval_t hash (const tree_int_map *);
-  static inline bool equal (const tree_int_map *, const tree_int_map *);
-};
-
-inline hashval_t
-tree_int_map_hasher::hash (const tree_int_map *v)
-{
-  return tree_map_base_hash (v);
-}
-
-inline bool
-tree_int_map_hasher::equal (const tree_int_map *v, const tree_int_map *c)
-{
-  return tree_int_map_eq (v, c);
-}
-
-/* This routine will initialize the basevar fields of MAP with base
-   names.  Partitions will share the same base if they have the same
-   SSA_NAME_VAR, or, being anonymous variables, the same type.  This
-   must match gimple_can_coalesce_p in the non-optimized case.  */
-
-static void
-compute_samebase_partition_bases (var_map map)
-{
-  int x, num_part;
-  tree var;
-  struct tree_int_map *m, *mapstorage;
-
-  num_part = num_var_partitions (map);
-  hash_table<tree_int_map_hasher> tree_to_index (num_part);
-  /* We can have at most num_part entries in the hash tables, so it's
-     enough to allocate so many map elements once, saving some malloc
-     calls.  */
-  mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
-
-  /* If a base table already exists, clear it, otherwise create it.  */
-  free (map->partition_to_base_index);
-  map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
-
-  /* Build the base variable list, and point partitions at their bases.  */
-  for (x = 0; x < num_part; x++)
-    {
-      struct tree_int_map **slot;
-      unsigned baseindex;
-      var = partition_to_var (map, x);
-      if (SSA_NAME_VAR (var)
-	  && (!VAR_P (SSA_NAME_VAR (var))
-	      || !DECL_IGNORED_P (SSA_NAME_VAR (var))))
-	m->base.from = SSA_NAME_VAR (var);
-      else
-	/* This restricts what anonymous SSA names we can coalesce
-	   as it restricts the sets we compute conflicts for.
-	   Using TREE_TYPE to generate sets is the easiest as
-	   type equivalency also holds for SSA names with the same
-	   underlying decl.
-
-	   Check gimple_can_coalesce_p when changing this code.  */
-	m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
-			? TYPE_CANONICAL (TREE_TYPE (var))
-			: TREE_TYPE (var));
-      /* If base variable hasn't been seen, set it up.  */
-      slot = tree_to_index.find_slot (m, INSERT);
-      if (!*slot)
-	{
-	  baseindex = m - mapstorage;
-	  m->to = baseindex;
-	  *slot = m;
-	  m++;
-	}
-      else
-	baseindex = (*slot)->to;
-      map->partition_to_base_index[x] = baseindex;
-    }
-
-  map->num_basevars = m - mapstorage;
-
-  free (mapstorage);
-}
-
 /* Given an initial var_map MAP, coalesce variables and return a partition map
    with the resulting coalesce.  Note that this function is called in either
    live range computation context or out-of-ssa context, indicated by MAP.  */
@@ -1824,10 +1728,7 @@ coalesce_ssa_name (var_map map)
 
   partition_view_bitmap (map, used_in_copies);
 
-  if (flag_tree_coalesce_vars)
-    compute_optimized_partition_bases (map, used_in_copies, cl);
-  else
-    compute_samebase_partition_bases (map);
+  compute_optimized_partition_bases (map, used_in_copies, cl);
 
   if (num_var_partitions (map) < 1)
     {