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]

[ tree-ssa] Speed up phi insertion and rewriting


There's three significant changes in this patchkit.

  1. "currdefs" really shouldn't be a hash table.  It's highly dense and
     its size is fixed for the life of rewriting.  A varray is much more
     efficient.

  2. When we're adding arguments to phis during rewriting, we can stop
     the inner loop as soon as we encounter a rewritten phi.

  3. When computing phi insertion points we were doing a lot of unnecessary
     bitmap operations that could be avoided by using appropriate bitmap
     functionality :-)

  4. Minor cleanup to tree-ssa-dom.


Before these patches we had the following times for building interpret.cc:


 tree PHI insertion    :   0.86 ( 8%) usr   0.10 (30%) sys   0.95 ( 8%) wall
 tree SSA rewrite      :   2.52 (23%) usr   0.00 ( 0%) sys   2.51 (22%) wall

And with the patches:


 tree PHI insertion    :   0.50 ( 5%) usr   0.04 (16%) sys   0.52 ( 5%) wall
 tree SSA rewrite      :   1.70 (17%) usr   0.02 ( 8%) sys   1.73 (17%) wall


The changes are compile-time neutral on more sane codebases.

Bootstrapped, regression tested, etc.


	* tree-ssa-dom.c (get_value_for, set_value_for): Move to the start
	of the file.  Delete pointless sanity checking.

	* tree-ssa.c (currdefs): Now a varray instead of a hash table.
	(get_value_for, set_value_for): Corresponding changes.  Move to
	the start of the file and delete pointless sanity checking.
	(rewrite_into_ssa, dump_tree_ssa_stats): Corresponding changes.
	(var_value_hash, var_value_eq): Kill.

	* tree-ssa.c (rewrite_add_phi_arguments): Once we encounter a
	rewritten PHI break the inner loop.

	* tree-ssa.c (insert_phi_nodes_for): Use EXECUTE_IF_AND_COMPL_IN_BITMAP.

	

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.61
diff -c -3 -p -r1.1.2.61 tree-ssa-dom.c
*** tree-ssa-dom.c	15 Oct 2003 18:22:58 -0000	1.1.2.61
--- tree-ssa-dom.c	16 Oct 2003 21:26:40 -0000
*************** static void dom_opt_initialize_block (st
*** 204,209 ****
--- 204,227 ----
  static void dom_opt_walk_stmts (struct dom_walk_data *, basic_block, tree);
  static void cprop_into_phis (struct dom_walk_data *, basic_block, tree);
  
+ /* Return the value associated with variable VAR in TABLE.  */
+ 
+ static inline tree
+ get_value_for (tree var)
+ {
+   return VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var));
+ }
+ 
+ 
+ /* Associate VALUE to variable VAR in TABLE.  */
+ 
+ static inline void
+ set_value_for (tree var, tree value)
+ {
+   VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var)) = value;
+ }
+ 
+ 
  /* Optimize function FNDECL based on the dominator tree.  This does
     simple const/copy propagation and redundant expression elimination using
     value numbering.
*************** update_rhs_and_lookup_avail_expr (tree s
*** 1952,1986 ****
  
    return cached_lhs;
  }
- 
- /* Return the value associated with variable VAR in TABLE.  */
- 
- static inline tree
- get_value_for (tree var)
- {
- 
- #if defined ENABLE_CHECKING
-   if (TREE_CODE (var) != SSA_NAME)
-     abort ();
- #endif
-   return VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var));
- }
- 
- 
- /* Associate VALUE to variable VAR in TABLE.  */
- 
- static inline void
- set_value_for (tree var, tree value)
- {
- 
- #if defined ENABLE_CHECKING
-   if (TREE_CODE (var) != SSA_NAME)
-     abort ();
- #endif
- 
-   VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var)) = value;
- }
- 
  
  /* Search for an existing instance of STMT in the AVAIL_EXPRS table.  If
     found, return its LHS. Otherwise insert STMT in the table and return
--- 1970,1975 ----
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.136
diff -c -3 -p -r1.1.4.136 tree-ssa.c
*** tree-ssa.c	16 Oct 2003 14:32:26 -0000	1.1.4.136
--- tree-ssa.c	16 Oct 2003 21:26:46 -0000
*************** struct GTY(()) def_blocks_d
*** 85,94 ****
    bitmap livein_blocks;
  };
  
! /* Hash table to store the current reaching definition for every variable in
     the function.  Given a variable V, its entry will be its immediately
     reaching SSA_NAME node.  */
! static htab_t currdefs;
  
  /* Structure to map variables to values.  It's used to keep track of the
     current reaching definition, constant values and variable copies while
--- 85,94 ----
    bitmap livein_blocks;
  };
  
! /* Table to store the current reaching definition for every variable in
     the function.  Given a variable V, its entry will be its immediately
     reaching SSA_NAME node.  */
! static varray_type currdefs;
  
  /* Structure to map variables to values.  It's used to keep track of the
     current reaching definition, constant values and variable copies while
*************** static void register_new_def (tree, tree
*** 159,170 ****
  static void insert_phi_nodes_for (tree, bitmap *);
  static tree remove_annotations_r (tree *, int *, void *);
  static tree get_reaching_def (tree);
! static tree get_value_for (tree, htab_t);
! static void set_value_for (tree, tree, htab_t);
  static hashval_t def_blocks_hash (const void *);
  static int def_blocks_eq (const void *, const void *);
- static hashval_t var_value_hash (const void *);
- static int var_value_eq (const void *, const void *);
  static int debug_def_blocks_r (void **, void *);
  static struct def_blocks_d *get_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
--- 159,168 ----
  static void insert_phi_nodes_for (tree, bitmap *);
  static tree remove_annotations_r (tree *, int *, void *);
  static tree get_reaching_def (tree);
! static tree get_value_for (tree, varray_type);
! static void set_value_for (tree, tree, varray_type);
  static hashval_t def_blocks_hash (const void *);
  static int def_blocks_eq (const void *, const void *);
  static int debug_def_blocks_r (void **, void *);
  static struct def_blocks_d *get_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
*************** static void print_exprs (FILE *, const c
*** 191,196 ****
--- 189,211 ----
  static void print_exprs_edge (FILE *, edge, const char *, tree, const char *, 
  			      tree);
  
+ /* Return the value associated with variable VAR in TABLE.  */
+ 
+ static inline tree
+ get_value_for (tree var, varray_type table)
+ {
+   return VARRAY_TREE (table, var_ann (var)->uid);
+ }
+ 
+ 
+ /* Associate VALUE to variable VAR in TABLE.  */
+ 
+ static inline void
+ set_value_for (tree var, tree value, varray_type table)
+ {
+   VARRAY_TREE (table, var_ann (var)->uid) = value;
+ }
+ 
  /* Main entry point to the SSA builder.  FNDECL is the gimplified function
     to convert.  VARS is an sbitmap representing variables that need to be
     renamed into SSA form.  A variable in REFERENCED_VARS will be renamed
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 309,317 ****
    def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
  			    def_blocks_hash, def_blocks_eq, NULL);
  
!   /* Allocate memory for the CURRDEFS hash table.  */
!   currdefs = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
! 			  var_value_hash, var_value_eq, NULL);
  
    /* Allocate memory for the GLOBALS bitmap which will indicate which
       variables are live across basic block boundaries.  Note that this
--- 324,330 ----
    def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
  			    def_blocks_hash, def_blocks_eq, NULL);
  
!   VARRAY_TREE_INIT (currdefs, num_referenced_vars, "currdefs");
  
    /* Allocate memory for the GLOBALS bitmap which will indicate which
       variables are live across basic block boundaries.  Note that this
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 393,399 ****
      sbitmap_free (vars_to_rename);
  
    htab_delete (def_blocks);
!   htab_delete (currdefs);
  
    timevar_pop (TV_TREE_SSA_OTHER);
  }
--- 406,412 ----
      sbitmap_free (vars_to_rename);
  
    htab_delete (def_blocks);
!   VARRAY_CLEAR (currdefs);
  
    timevar_pop (TV_TREE_SSA_OTHER);
  }
*************** rewrite_add_phi_arguments (struct dom_wa
*** 796,804 ****
  	  tree currdef;
  
  	  /* If this PHI node has already been rewritten, then there is
! 	     nothing to do.  */
  	  if (PHI_REWRITTEN (phi))
! 	    continue;
  
  	  currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
  	  add_phi_arg (&phi, currdef, e);
--- 809,818 ----
  	  tree currdef;
  
  	  /* If this PHI node has already been rewritten, then there is
! 	     nothing to do for this PHI or any following PHIs since we
! 	     always add new PHI nodes at the start of the PHI chain.  */
  	  if (PHI_REWRITTEN (phi))
! 	    break;
  
  	  currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
  	  add_phi_arg (&phi, currdef, e);
*************** dump_tree_ssa_stats (FILE *file)
*** 1831,1839 ****
    fprintf (file, "    def_blocks: ");
    htab_statistics (file, def_blocks);
  
-   fprintf (file, "    currdefs: ");
-   htab_statistics (file, currdefs);
- 
    fprintf (file, "\n");
  }
  
--- 1845,1850 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 1903,1921 ****
      {
        basic_block bb = VARRAY_TOP_BB (work_stack);
        int bb_index = bb->index;
  
        VARRAY_POP (work_stack);
        
!       EXECUTE_IF_SET_IN_BITMAP (dfs[bb_index], 0, bb_index,
  	{
!           basic_block bb = BASIC_BLOCK (bb_index);
  
! 	  if (! bitmap_bit_p (phi_insertion_points, bb_index))
! 	    {
! 	      phi_vector_lengths += bb_ann (bb)->num_preds;
! 	      VARRAY_PUSH_BB (work_stack, bb);
! 	      bitmap_set_bit (phi_insertion_points, bb_index);
! 	    }
  	});
      }
  
--- 1914,1932 ----
      {
        basic_block bb = VARRAY_TOP_BB (work_stack);
        int bb_index = bb->index;
+       int dfs_index;
  
        VARRAY_POP (work_stack);
        
!       EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index],
! 				      phi_insertion_points,
! 				      0, dfs_index,
  	{
! 	  basic_block bb = BASIC_BLOCK (dfs_index);
  
! 	  phi_vector_lengths += bb_ann (bb)->num_preds;
! 	  VARRAY_PUSH_BB (work_stack, bb);
! 	  bitmap_set_bit (phi_insertion_points, dfs_index);
  	});
      }
  
*************** def_blocks_eq (const void *p1, const voi
*** 2195,2217 ****
  }
  
  
- /* Hashing and equality functions for VAR_VALUE_D.  */
- 
- static hashval_t
- var_value_hash (const void *p)
- {
-   return htab_hash_pointer
- 	((const void *)((const struct var_value_d *)p)->var);
- }
- 
- static int
- var_value_eq (const void *p1, const void *p2)
- {
-   return ((const struct var_value_d *)p1)->var
- 	 == ((const struct var_value_d *)p2)->var;
- }
- 
- 
  /* Dump the DEF_BLOCKS hash table on stderr.  */
  
  void
--- 2206,2211 ----
*************** debug_def_blocks_r (void **slot, void *d
*** 2242,2292 ****
    return 1;
  }
  
- 
- /* Return the value associated with variable VAR in TABLE.  */
- 
- static tree
- get_value_for (tree var, htab_t table)
- {
-   struct var_value_d *vm_p, vm;
- 
- #if defined ENABLE_CHECKING
-   if (!SSA_VAR_P (var))
-     abort ();
- #endif
- 
-   vm.var = var;
-   vm_p = (struct var_value_d *) htab_find (table, (void *) &vm);
-   return (vm_p) ? vm_p->value : NULL_TREE;
- }
- 
- 
- /* Associate VALUE to variable VAR in TABLE.  */
- 
- static void
- set_value_for (tree var, tree value, htab_t table)
- {
-   struct var_value_d *vm_p, vm;
-   void **slot;
- 
- #if defined ENABLE_CHECKING
-   if (!SSA_VAR_P (var))
-     abort ();
- #endif
- 
-   vm.var = var;
-   slot = htab_find_slot (table, (void *) &vm, INSERT);
-   if (*slot == NULL)
-     {
-       vm_p = ggc_alloc (sizeof *vm_p);
-       vm_p->var = var;
-       *slot = (void *) vm_p;
-     }
-   else
-     vm_p = (struct var_value_d *) *slot;
- 
-   vm_p->value = value;
- }
  
  /* Return the set of blocks where variable VAR is defined and the blocks
     where VAR is live on entry (livein).  */
--- 2236,2241 ----



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