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

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Aug 1, 2012 at 4:05 PM, Michael Matz <matz@suse.de> wrote:
> 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?

Ok.

Thanks,
Richard.

>
> 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 ----