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] More dominator optimizer compile-time improvements


This change slightly improves the compile-time performance of the
dominator optimizer when checking is enabled.  

The major component of this patch is avoiding redundant calls into the
available expression hash routine (avail_expr_hash).  We avoid the redundant
calls by saving the expression's hash value in its associated hash table
entry itself.

We also avoid many thousands of calls to is_gimple_stmt in Gerald's testcase
by using [V]DEF_OPS instead of STMT_[V]DEF_OPS.

Finally, this patch cleans up clearing the various tables before the next
iteration of the optimizer.  I don't think this will have any performance
impact, it's strictly to make the code easier to read.

Bootstrapped and regression tested i686-pc-linux-gnu.

	* tree-ssa-dom.c (struct expr_hash_elt): Add new field for hash value.
	(initialize_hash_element): New LHS argument.  Callers changed.
	Initialize the hash value field.
	(remove_local_expressions_from_table): Use htab_remove_elt_with_hash.
	(update_rhs_and_lookup_avail_expr): Similary.
	(lookup_avail_expr): Use htab_find_slot_with_hash.  Simplify slightly
	and pass LHS to initialize_hash_element.
	(record_cond): Also use htab_find_slot_with_hash.  Initialize the
	hash table entry with initialize_hash_element.
	(avail_expr_eq): Use the saved hash value rather than calling into
	the hash functions again.

	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Slightly rearrange
	code to clear tables before each iteration to be clearer.

	* tree-ssa-dom.c (redirect_edges_and_update_ssa_graph): Use
	DEF_OPS and VDEF_OPS instead of STMT_DEF_OPS and STMT_VDEF_OPS.

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.153
diff -c -p -r1.1.2.153 tree-ssa-dom.c
*** tree-ssa-dom.c	12 Apr 2004 20:04:12 -0000	1.1.2.153
--- tree-ssa-dom.c	13 Apr 2004 14:51:47 -0000
*************** struct expr_hash_elt
*** 74,79 ****
--- 74,82 ----
  
    /* The annotation if this element corresponds to a statement.  */
    stmt_ann_t ann;
+ 
+   /* The hash value for RHS/ann.  */
+   hashval_t hash;
  };
  
  /* Table of constant values and copies indexed by SSA name.  When the
*************** redirect_edges_and_update_ssa_graph (var
*** 378,397 ****
  	  def_optype defs;
  	  vdef_optype vdefs;
  	  tree stmt = bsi_stmt (bsi);
  
  	  if (TREE_CODE (stmt) == COND_EXPR)
  	    break;
  
  	  get_stmt_operands (stmt);
  
! 	  defs = STMT_DEF_OPS (stmt);
  	  for (j = 0; j < NUM_DEFS (defs); j++)
  	    {
  	      tree op = SSA_NAME_VAR (DEF_OP (defs, j));
  	      bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
  	    }
  
! 	  vdefs = STMT_VDEF_OPS (stmt);
  	  for (j = 0; j < NUM_VDEFS (vdefs); j++)
  	    {
  	      tree op = VDEF_RESULT (vdefs, j);
--- 381,401 ----
  	  def_optype defs;
  	  vdef_optype vdefs;
  	  tree stmt = bsi_stmt (bsi);
+ 	  stmt_ann_t ann = stmt_ann (stmt);
  
  	  if (TREE_CODE (stmt) == COND_EXPR)
  	    break;
  
  	  get_stmt_operands (stmt);
  
! 	  defs = DEF_OPS (ann);
  	  for (j = 0; j < NUM_DEFS (defs); j++)
  	    {
  	      tree op = SSA_NAME_VAR (DEF_OP (defs, j));
  	      bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
  	    }
  
! 	  vdefs = VDEF_OPS (ann);
  	  for (j = 0; j < NUM_VDEFS (vdefs); j++)
  	    {
  	      tree op = VDEF_RESULT (vdefs, j);
*************** tree_ssa_dominator_optimize (void)
*** 604,613 ****
        walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
  
        /* Wipe the hash tables.  */
-       htab_empty (avail_exprs);
- 
-       VARRAY_CLEAR (const_and_copies);
-       bitmap_clear (nonzero_vars);
  
        if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
  	redirect_edges_and_update_ssa_graph (redirection_edges);
--- 608,613 ----
*************** tree_ssa_dominator_optimize (void)
*** 632,645 ****
  	{
  	  rewrite_into_ssa ();
  	  bitmap_clear (vars_to_rename);
  	  VARRAY_GROW (const_and_copies, highest_ssa_version);
  	  VARRAY_GROW (vrp_data, highest_ssa_version);
- 	  VARRAY_GROW (currdefs, num_referenced_vars);
- 	  VARRAY_CLEAR (const_and_copies);
- 	  VARRAY_CLEAR (vrp_data);
- 	  bitmap_clear (nonzero_vars);
- 	  VARRAY_CLEAR (currdefs);
  	}
      }
    while (cfg_altered);
  
--- 632,654 ----
  	{
  	  rewrite_into_ssa ();
  	  bitmap_clear (vars_to_rename);
+ 
+ 	  /* The out-of SSA translation may have created new variables which
+ 	     affects the size of CURRDEFS.  */
+ 	  VARRAY_GROW (currdefs, num_referenced_vars);
+ 
+ 	  /* The into SSA translation may have created new SSA_NAMES whic
+ 	     affect the size of CONST_AND_COPIES and VRP_DATA.  */
  	  VARRAY_GROW (const_and_copies, highest_ssa_version);
  	  VARRAY_GROW (vrp_data, highest_ssa_version);
  	}
+ 
+       /* Reinitialize the various tables.  */
+       bitmap_clear (nonzero_vars);
+       htab_empty (avail_exprs);
+       VARRAY_CLEAR (const_and_copies);
+       VARRAY_CLEAR (vrp_data);
+       VARRAY_CLEAR (currdefs);
      }
    while (cfg_altered);
  
*************** tree_ssa_dominator_optimize (void)
*** 650,661 ****
    if (dump_file && (dump_flags & TDF_STATS))
      dump_dominator_optimization_stats (dump_file);
  
    htab_delete (avail_exprs);
  
!   VARRAY_CLEAR (redirection_edges);
!   VARRAY_CLEAR (currdefs);
! 
!   BITMAP_XFREE (nonzero_vars);
  
    /* And finalize the dominator walker.  */
    fini_walk_dominator_tree (&walk_data);
--- 659,670 ----
    if (dump_file && (dump_flags & TDF_STATS))
      dump_dominator_optimization_stats (dump_file);
  
+   /* We emptyed the hash table earlier, now delete it completely.  */
    htab_delete (avail_exprs);
  
!   /* It is not nocessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
!      CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
!      of the do-while loop above.  */
  
    /* And finalize the dominator walker.  */
    fini_walk_dominator_tree (&walk_data);
*************** dom_opt_initialize_block (struct dom_wal
*** 1024,1030 ****
     initialize the hash table element pointed by by ELEMENT.  */
  
  static void
! initialize_hash_element (tree expr, struct expr_hash_elt *element)
  {
    /* Hash table elements may be based on conditional expressions or 
statements.
  
--- 1033,1039 ----
     initialize the hash table element pointed by by ELEMENT.  */
  
  static void
! initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
  {
    /* Hash table elements may be based on conditional expressions or 
statements.
  
*************** initialize_hash_element (tree expr, stru
*** 1058,1064 ****
        element->rhs = TREE_OPERAND (expr, 1);
      }
  
!   element->lhs = NULL;
  }
  
  /* Remove all the expressions in LOCALS from TABLE, stopping when there are
--- 1067,1074 ----
        element->rhs = TREE_OPERAND (expr, 1);
      }
  
!   element->lhs = lhs;
!   element->hash = avail_expr_hash (element);
  }
  
  /* Remove all the expressions in LOCALS from TABLE, stopping when there are
*************** remove_local_expressions_from_table (var
*** 1079,1086 ****
        tree expr = VARRAY_TOP_TREE (locals);
        VARRAY_POP (locals);
  
!       initialize_hash_element (expr, &element);
!       htab_remove_elt (table, &element);
      }
  }
  
--- 1089,1096 ----
        tree expr = VARRAY_TOP_TREE (locals);
        VARRAY_POP (locals);
  
!       initialize_hash_element (expr, NULL, &element);
!       htab_remove_elt_with_hash (table, &element, element.hash);
      }
  }
  
*************** record_cond (tree cond, tree value, varr
*** 1570,1580 ****
    struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
    void **slot;
  
!   element->rhs = cond;
!   element->lhs = value;
!   element->ann = NULL;
  
!   slot = htab_find_slot (avail_exprs, (void *)element, true);
    if (*slot == NULL)
      {
        *slot = (void *) element;
--- 1580,1589 ----
    struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
    void **slot;
  
!   initialize_hash_element (cond, value, element);
  
!   slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
! 				   element->hash, true);
    if (*slot == NULL)
      {
        *slot = (void *) element;
*************** update_rhs_and_lookup_avail_expr (tree s
*** 2663,2670 ****
      {
        struct expr_hash_elt element;
  
!       initialize_hash_element (stmt, &element);
!       htab_remove_elt (avail_exprs, &element);
      }
  
    /* Now update the RHS of the assignment.  */
--- 2672,2679 ----
      {
        struct expr_hash_elt element;
  
!       initialize_hash_element (stmt, NULL, &element);
!       htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
      }
  
    /* Now update the RHS of the assignment.  */
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2724,2731 ****
    tree temp;
    struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
  
  
!   initialize_hash_element (stmt, element);
  
    /* Don't bother remembering constant assignments and copy operations.
       Constants and copy operations are handled by the constant/copy 
propagator
--- 2733,2741 ----
    tree temp;
    struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
  
+   lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
  
!   initialize_hash_element (stmt, lhs, element);
  
    /* Don't bother remembering constant assignments and copy operations.
       Constants and copy operations are handled by the constant/copy 
propagator
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2737,2746 ****
        return NULL_TREE;
      }
  
-   /* If STMT is a MODIFY_EXPR, then we want to record its LHS as well.  */
-   if (TREE_CODE (stmt) == MODIFY_EXPR)
-     element->lhs = TREE_OPERAND (stmt, 0);
- 
    /* If this is an equality test against zero, see if we have recorded a
       nonzero value for the variable in question.  */
    if ((TREE_CODE (element->rhs) == EQ_EXPR
--- 2747,2752 ----
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2762,2768 ****
      }
  
    /* Finally try to find the expression in the main expression hash table.  
*/
!   slot = htab_find_slot (avail_exprs, element, (insert ? INSERT : 
NO_INSERT));
    if (slot == NULL)
      {
        free (element);
--- 2768,2775 ----
      }
  
    /* Finally try to find the expression in the main expression hash table.  
*/
!   slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
! 				   (insert ? INSERT : NO_INSERT));
    if (slot == NULL)
      {
        free (element);
*************** avail_expr_eq (const void *p1, const voi
*** 3108,3114 ****
  	  return false;
  
  #ifdef ENABLE_CHECKING
!       if (avail_expr_hash (p1) != avail_expr_hash (p2))
  	abort ();
  #endif
        return true;
--- 3115,3122 ----
  	  return false;
  
  #ifdef ENABLE_CHECKING
!       if (((struct expr_hash_elt *)p1)->hash
! 	  != ((struct expr_hash_elt *)p2)->hash)
  	abort ();
  #endif
        return true;




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