[1/3] remove var_ann: tlc for out-of-ssa

[Michael Matz <matz at suse dot de>]

Hi,

this tidies ssa liveness calculation a bit (related to out-of-ssa).  In 
particular it doesn't make use of var annotations to compress the index 
space from partitions to base variable indices anymore, but instead a 
hashmap built on the fly when we need it.  The basevars itself actually 
aren't needed at all (currently only for checking), only a mapping for 
which ssa names belong to the same base variable.

Regstrapped with the other two patches on x86_64-linux.  Okay for trunk?


Ciao,
Michael.
	* tree-flow.h (struct var_ann_d): Remove base_var_processed and
	base_index members.
	* tree-ssa-live.h (struct _var_map): Remove basevars member.
	(VAR_ANN_BASE_INDEX): Remove.
	* tree-ssa-live.c (var_map_base_init): Use a hash table instead
	of var annotation to compress index space.  Don't deal with above
	removed members.
	(var_map_base_fini): Don't free basevars.
	(init_var_map): Don't clear basevars.

Index: tree-flow.h
===================================================================
*** tree-flow.h.orig	2012-08-01 15:59:27.000000000 +0200
--- tree-flow.h	2012-08-01 15:59:35.000000000 +0200
*************** enum need_phi_state {
*** 178,192 ****
  
  
  struct GTY(()) var_ann_d {
-   /* Used when building base variable structures in a var_map.  */
-   unsigned base_var_processed : 1;
- 
    /* Nonzero if this variable was used after SSA optimizations were
       applied.  We set this when translating out of SSA form.  */
    unsigned used : 1;
- 
-   /* Used by var_map for the base index of ssa base variables.  */
-   unsigned base_index;
  };
  
  
--- 178,186 ----
Index: tree-ssa-live.h
===================================================================
*** tree-ssa-live.h.orig	2012-08-01 15:58:34.000000000 +0200
--- tree-ssa-live.h	2012-08-01 15:59:35.000000000 +0200
*************** along with GCC; see the file COPYING3.
*** 31,43 ****
  /* Used to create the variable mapping when we go out of SSA form.
  
     Mapping from an ssa_name to a partition number is maintained, as well as
!    partition number to back to ssa_name. A partition can also be represented
!    by a non-ssa_name variable.  This allows ssa_names and their partition to
!    be coalesced with live on entry compiler variables, as well as eventually
!    having real compiler variables assigned to each partition as part of the
!    final stage of going of of ssa.
! 
!    Non-ssa_names maintain their partition index in the variable annotation.
  
     This data structure also supports "views", which work on a subset of all
     partitions.  This allows the coalescer to decide what partitions are
--- 31,37 ----
  /* Used to create the variable mapping when we go out of SSA form.
  
     Mapping from an ssa_name to a partition number is maintained, as well as
!    partition number back to ssa_name.
  
     This data structure also supports "views", which work on a subset of all
     partitions.  This allows the coalescer to decide what partitions are
*************** typedef struct _var_map
*** 72,87 ****
  
    /* Map of partitions numbers to base variable table indexes.  */
    int *partition_to_base_index;
- 
-   /* Table of base variable's.  */
-   VEC (tree, heap) *basevars;
  } *var_map;
  
  
- /* Index to the basevar table of a non ssa-name variable.  */
- #define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
- 
- 
  /* Value used to represent no partition number.  */
  #define NO_PARTITION		-1
  
--- 66,74 ----
Index: tree-ssa-live.c
===================================================================
*** tree-ssa-live.c.orig	2012-08-01 15:58:34.000000000 +0200
--- tree-ssa-live.c	2012-08-01 15:59:35.000000000 +0200
*************** static void  verify_live_on_entry (tree_
*** 59,117 ****
  static void
  var_map_base_init (var_map map)
  {
!   int x, num_part, num;
    tree var;
!   var_ann_t ann;
  
-   num = 0;
    num_part = num_var_partitions (map);
  
    /* If a base table already exists, clear it, otherwise create it.  */
!   if (map->partition_to_base_index != NULL)
!     {
!       free (map->partition_to_base_index);
!       VEC_truncate (tree, map->basevars, 0);
!     }
!   else
!     map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));
! 
    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++)
      {
        var = partition_to_var (map, x);
!       if (TREE_CODE (var) == SSA_NAME)
! 	 var = SSA_NAME_VAR (var);
!       ann = var_ann (var);
        /* If base variable hasn't been seen, set it up.  */
!       if (!ann->base_var_processed)
!         {
! 	  ann->base_var_processed = 1;
! 	  VAR_ANN_BASE_INDEX (ann) = num++;
! 	  VEC_safe_push (tree, heap, map->basevars, var);
  	}
!       map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);
      }
  
!   map->num_basevars = num;
  
!   /* Now clear the processed bit.  */
!   for (x = 0; x < num; x++)
!     {
!        var = VEC_index (tree, map->basevars, x);
!        var_ann (var)->base_var_processed = 0;
!     }
! 
! #ifdef ENABLE_CHECKING
!   for (x = 0; x < num_part; x++)
!     {
!       tree var2;
!       var = SSA_NAME_VAR (partition_to_var (map, x));
!       var2 = VEC_index (tree, map->basevars, basevar_index (map, x));
!       gcc_assert (var == var2);
!     }
! #endif
  }
  
  
--- 59,107 ----
  static void
  var_map_base_init (var_map map)
  {
!   int x, num_part;
    tree var;
!   htab_t decl_to_index;
!   struct tree_int_map *m, *mapstorage;
  
    num_part = num_var_partitions (map);
+   decl_to_index = htab_create (num_part, tree_decl_map_hash,
+ 			       tree_int_map_eq, NULL);
+   /* 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);
!       var = SSA_NAME_VAR (var);
        /* If base variable hasn't been seen, set it up.  */
!       m->base.from = var;
!       slot = (struct tree_int_map **) htab_find_slot (decl_to_index, 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);
!   htab_delete (decl_to_index);
  }
  
  
*************** var_map_base_fini (var_map map)
*** 123,129 ****
    /* Free the basevar info if it is present.  */
    if (map->partition_to_base_index != NULL)
      {
-       VEC_free (tree, heap, map->basevars);
        free (map->partition_to_base_index);
        map->partition_to_base_index = NULL;
        map->num_basevars = 0;
--- 113,118 ----
*************** init_var_map (int size)
*** 145,151 ****
    map->partition_size = size;
    map->num_basevars = 0;
    map->partition_to_base_index = NULL;
-   map->basevars = NULL;
    return map;
  }
  
--- 134,139 ----