[PATCH][3/n] into-SSA TLC

[PATCH][3/n] into-SSA TLC

[Richard Guenther]

This tries to more clearly separate per-SSA name held information
from per-DECL held information during update-ssa.  We already have
a global array of SSA name informations so it is pointless to
have a hashtable mapping SSA names to yet another piece of information
(a bitmap).  This patch simply puts the bitmap into that SSA name
auxiliar vector.  Lifetime is managed by using a separate obstack
and the aux vector age.

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

Richard.

2012-07-27  Richard Guenther  <rguenther@suse.de>

	* tree-cfg.c (gimple_can_merge_blocks_p): Do more fine-grained
	check whether SSA form is not up-to-date.
	* tree-flow.h (name_mappings_registered_p): Remove.
	* tree-into-ssa.c (struct repl_map_d): Remove.
	(repl_tbl): Likewise.
	(struct ssa_name_info): Add repl_set member.
	(update_ssa_obstack): New static global.
	(get_ssa_name_ann): Initialize repl_set.
	(clear_ssa_name_info): Assert age did not wrap.
	(repl_map_hash, repl_map_eq, repl_map_free): Remove.
	(names_replaced_by): Adjust.
	(add_to_repl_tbl): Likewise.
	(dump_tree_ssa_stats): Likewise.
	(init_update_ssa): Initialize update_ssa_obstack.
	(delete_update_ssa): Free update_ssa_obstack.
	(name_mappings_registered_p): Remove.
	(update_ssa): Adjust.

Index: trunk/gcc/tree-cfg.c
===================================================================
*** trunk.orig/gcc/tree-cfg.c	2012-07-26 10:46:43.000000000 +0200
--- trunk/gcc/tree-cfg.c	2012-07-27 13:40:30.603790938 +0200
*************** gimple_can_merge_blocks_p (basic_block a
*** 1449,1455 ****
  {
    gimple stmt;
    gimple_stmt_iterator gsi;
-   gimple_seq phis;
  
    if (!single_succ_p (a))
      return false;
--- 1449,1454 ----
*************** gimple_can_merge_blocks_p (basic_block a
*** 1499,1508 ****
    /* It must be possible to eliminate all phi nodes in B.  If ssa form
       is not up-to-date and a name-mapping is registered, we cannot eliminate
       any phis.  Symbols marked for renaming are never a problem though.  */
!   phis = phi_nodes (b);
!   if (!gimple_seq_empty_p (phis)
!       && name_mappings_registered_p ())
!     return false;
  
    /* When not optimizing, don't merge if we'd lose goto_locus.  */
    if (!optimize
--- 1498,1510 ----
    /* It must be possible to eliminate all phi nodes in B.  If ssa form
       is not up-to-date and a name-mapping is registered, we cannot eliminate
       any phis.  Symbols marked for renaming are never a problem though.  */
!   for (gsi = gsi_start_phis (b); !gsi_end_p (gsi); gsi_next (&gsi))
!     {
!       gimple phi = gsi_stmt (gsi);
!       /* Technically only new names matter.  */
!       if (name_registered_for_update_p (PHI_RESULT (phi)))
! 	return false;
!     }
  
    /* When not optimizing, don't merge if we'd lose goto_locus.  */
    if (!optimize
Index: trunk/gcc/tree-flow.h
===================================================================
*** trunk.orig/gcc/tree-flow.h	2012-07-27 12:46:26.000000000 +0200
--- trunk/gcc/tree-flow.h	2012-07-27 13:40:41.441790559 +0200
*************** void delete_update_ssa (void);
*** 570,576 ****
  void register_new_name_mapping (tree, tree);
  tree create_new_def_for (tree, gimple, def_operand_p);
  bool need_ssa_update_p (struct function *);
- bool name_mappings_registered_p (void);
  bool name_registered_for_update_p (tree);
  void release_ssa_name_after_update_ssa (tree);
  void compute_global_livein (bitmap, bitmap);
--- 570,575 ----
Index: trunk/gcc/tree-into-ssa.c
===================================================================
*** trunk.orig/gcc/tree-into-ssa.c	2012-07-27 12:52:09.000000000 +0200
--- trunk/gcc/tree-into-ssa.c	2012-07-27 14:00:30.533749404 +0200
*************** static bitmap blocks_with_phis_to_rewrit
*** 128,145 ****
     strategy.  */
  #define NAME_SETS_GROWTH_FACTOR	(MAX (3, num_ssa_names / 3))
  
- /* Tuple used to represent replacement mappings.  */
- struct repl_map_d
- {
-   tree name;
-   bitmap set;
- };
- 
- 
- /* NEW -> OLD_SET replacement table.  If we are replacing several
-    existing SSA names O_1, O_2, ..., O_j with a new name N_i,
-    then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }.  */
- static htab_t repl_tbl;
  
  /* The function the SSA updating data structures have been initialized for.
     NULL if they need to be initialized by register_new_name_mapping.  */
--- 128,133 ----
*************** struct mark_def_sites_global_data
*** 157,174 ****
  /* Information stored for SSA names.  */
  struct ssa_name_info
  {
!   /* The current reaching definition replacing this SSA name.  */
!   tree current_def;
  
    /* This field indicates whether or not the variable may need PHI nodes.
       See the enum's definition for more detailed information about the
       states.  */
    ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
  
!   /* Age of this record (so that info_for_ssa_name table can be cleared
!      quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
!      are assumed to be null.  */
!   unsigned age;
  };
  
  /* The information associated with names.  */
--- 145,165 ----
  /* Information stored for SSA names.  */
  struct ssa_name_info
  {
!   /* Age of this record (so that info_for_ssa_name table can be cleared
!      quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
!      are assumed to be null.  */
!   unsigned age;
  
    /* This field indicates whether or not the variable may need PHI nodes.
       See the enum's definition for more detailed information about the
       states.  */
    ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
  
!   /* The current reaching definition replacing this SSA name.  */
!   tree current_def;
! 
!   /* Replacement mappings, allocated from update_ssa_obstack.  */
!   bitmap repl_set;
  };
  
  /* The information associated with names.  */
*************** DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
*** 179,184 ****
--- 170,177 ----
  static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
  static unsigned current_info_for_ssa_name_age;
  
+ static bitmap_obstack update_ssa_obstack;
+ 
  /* The set of blocks affected by update_ssa.  */
  static bitmap blocks_to_update;
  
*************** get_ssa_name_ann (tree name)
*** 288,293 ****
--- 281,287 ----
      {
        info->need_phi_state = NEED_PHI_STATE_UNKNOWN;
        info->current_def = NULL_TREE;
+       info->repl_set = NULL;
        info->age = current_info_for_ssa_name_age;
      }
  
*************** static void
*** 301,306 ****
--- 295,304 ----
  clear_ssa_name_info (void)
  {
    current_info_for_ssa_name_age++;
+ 
+   /* If current_info_for_ssa_name_age wraps we use stale information.
+      Asser that this does not happen.  */
+   gcc_assert (current_info_for_ssa_name_age != 0);
  }
  
  
*************** is_new_name (tree name)
*** 573,617 ****
  }
  
  
- /* Hashing and equality functions for REPL_TBL.  */
- 
- static hashval_t
- repl_map_hash (const void *p)
- {
-   return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
- }
- 
- static int
- repl_map_eq (const void *p1, const void *p2)
- {
-   return ((const struct repl_map_d *)p1)->name
- 	 == ((const struct repl_map_d *)p2)->name;
- }
- 
- static void
- repl_map_free (void *p)
- {
-   BITMAP_FREE (((struct repl_map_d *)p)->set);
-   free (p);
- }
- 
- 
  /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */
  
  static inline bitmap
  names_replaced_by (tree new_tree)
  {
!   struct repl_map_d m;
!   void **slot;
! 
!   m.name = new_tree;
!   slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
! 
!   /* If N was not registered in the replacement table, return NULL.  */
!   if (slot == NULL || *slot == NULL)
!     return NULL;
! 
!   return ((struct repl_map_d *) *slot)->set;
  }
  
  
--- 571,582 ----
  }
  
  
  /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */
  
  static inline bitmap
  names_replaced_by (tree new_tree)
  {
!   return get_ssa_name_ann (new_tree)->repl_set;
  }
  
  
*************** names_replaced_by (tree new_tree)
*** 620,641 ****
  static inline void
  add_to_repl_tbl (tree new_tree, tree old)
  {
!   struct repl_map_d m, *mp;
!   void **slot;
! 
!   m.name = new_tree;
!   slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
!   if (*slot == NULL)
!     {
!       mp = XNEW (struct repl_map_d);
!       mp->name = new_tree;
!       mp->set = BITMAP_ALLOC (NULL);
!       *slot = (void *) mp;
!     }
!   else
!     mp = (struct repl_map_d *) *slot;
! 
!   bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
  }
  
  
--- 585,594 ----
  static inline void
  add_to_repl_tbl (tree new_tree, tree old)
  {
!   bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
!   if (!*set)
!     *set = BITMAP_ALLOC (&update_ssa_obstack);
!   bitmap_set_bit (*set, SSA_NAME_VERSION (old));
  }
  
  
*************** htab_statistics (FILE *file, htab_t htab
*** 1719,1725 ****
  void
  dump_tree_ssa_stats (FILE *file)
  {
!   if (def_blocks || repl_tbl)
      fprintf (file, "\nHash table statistics:\n");
  
    if (def_blocks)
--- 1672,1678 ----
  void
  dump_tree_ssa_stats (FILE *file)
  {
!   if (def_blocks)
      fprintf (file, "\nHash table statistics:\n");
  
    if (def_blocks)
*************** dump_tree_ssa_stats (FILE *file)
*** 1728,1740 ****
        htab_statistics (file, def_blocks);
      }
  
!   if (repl_tbl)
!     {
!       fprintf (file, "    repl_tbl:     ");
!       htab_statistics (file, repl_tbl);
!     }
! 
!   if (def_blocks || repl_tbl)
      fprintf (file, "\n");
  }
  
--- 1681,1687 ----
        htab_statistics (file, def_blocks);
      }
  
!   if (def_blocks)
      fprintf (file, "\n");
  }
  
*************** init_update_ssa (struct function *fn)
*** 2838,2844 ****
    new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
    sbitmap_zero (new_ssa_names);
  
!   repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
    names_to_release = NULL;
    update_ssa_initialized_fn = fn;
  }
--- 2785,2792 ----
    new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
    sbitmap_zero (new_ssa_names);
  
!   bitmap_obstack_initialize (&update_ssa_obstack);
! 
    names_to_release = NULL;
    update_ssa_initialized_fn = fn;
  }
*************** delete_update_ssa (void)
*** 2858,2866 ****
    sbitmap_free (new_ssa_names);
    new_ssa_names = NULL;
  
-   htab_delete (repl_tbl);
-   repl_tbl = NULL;
- 
    bitmap_clear (SYMS_TO_RENAME (update_ssa_initialized_fn));
  
    if (names_to_release)
--- 2806,2811 ----
*************** delete_update_ssa (void)
*** 2885,2890 ****
--- 2830,2838 ----
  
    BITMAP_FREE (blocks_with_phis_to_rewrite);
    BITMAP_FREE (blocks_to_update);
+ 
+   bitmap_obstack_release (&update_ssa_obstack);
+ 
    update_ssa_initialized_fn = NULL;
  }
  
*************** need_ssa_update_p (struct function *fn)
*** 2957,2975 ****
  	      && !bitmap_empty_p (SYMS_TO_RENAME (fn))));
  }
  
- /* Return true if SSA name mappings have been registered for SSA updating.  */
- 
- bool
- name_mappings_registered_p (void)
- {
-   if (!update_ssa_initialized_fn)
-     return false;
- 
-   gcc_assert (update_ssa_initialized_fn == cfun);
- 
-   return repl_tbl && htab_elements (repl_tbl) > 0;
- }
- 
  /* Return true if name N has been registered in the replacement table.  */
  
  bool
--- 2905,2910 ----
*************** update_ssa (unsigned update_flags)
*** 3212,3218 ****
      {
        sbitmap_zero (old_ssa_names);
        sbitmap_zero (new_ssa_names);
-       htab_empty (repl_tbl);
      }
  
    insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
--- 3147,3152 ----

Re: [PATCH][3/n] into-SSA TLC

[H.J. Lu]

On Fri, Jul 27, 2012 at 5:16 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> This tries to more clearly separate per-SSA name held information
> from per-DECL held information during update-ssa.  We already have
> a global array of SSA name informations so it is pointless to
> have a hashtable mapping SSA names to yet another piece of information
> (a bitmap).  This patch simply puts the bitmap into that SSA name
> auxiliar vector.  Lifetime is managed by using a separate obstack
> and the aux vector age.
>
> Bootstrap and regtest pending on x86_64-unknown-linux-gnu.
>
> Richard.
>
> 2012-07-27  Richard Guenther  <rguenther@suse.de>
>
>         * tree-cfg.c (gimple_can_merge_blocks_p): Do more fine-grained
>         check whether SSA form is not up-to-date.
>         * tree-flow.h (name_mappings_registered_p): Remove.
>         * tree-into-ssa.c (struct repl_map_d): Remove.
>         (repl_tbl): Likewise.
>         (struct ssa_name_info): Add repl_set member.
>         (update_ssa_obstack): New static global.
>         (get_ssa_name_ann): Initialize repl_set.
>         (clear_ssa_name_info): Assert age did not wrap.
>         (repl_map_hash, repl_map_eq, repl_map_free): Remove.
>         (names_replaced_by): Adjust.
>         (add_to_repl_tbl): Likewise.
>         (dump_tree_ssa_stats): Likewise.
>         (init_update_ssa): Initialize update_ssa_obstack.
>         (delete_update_ssa): Free update_ssa_obstack.
>         (name_mappings_registered_p): Remove.
>         (update_ssa): Adjust.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54327


-- 
H.J.