[PATCH] Low-hanging speedups [5/n]

[Richard Guenther <rguenther at suse dot de>]

This optimizes the topmost used expression kind in PRE - SSA names.
We don't need to go through expensive hashing to get the canonical
pre-expr for a SSA name.  Instead we can maintain a simple
direct-mapping of SSA name version to expression-id.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2010-01-06  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-pre.c (name_to_id): New global.
	(alloc_expression_id): Simplify SSA name handling.
	(lookup_expression_id): Likewise.
	(init_pre): Zero name_to_id.
	(fini_pre): Free it.

Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c	(revision 155673)
--- gcc/tree-ssa-pre.c	(working copy)
*************** DEF_VEC_P (pre_expr);
*** 236,241 ****
--- 236,242 ----
  DEF_VEC_ALLOC_P (pre_expr, heap);
  static VEC(pre_expr, heap) *expressions;
  static htab_t expression_to_id;
+ static VEC(unsigned, heap) *name_to_id;
  
  /* Allocate an expression id for EXPR.  */
  
*************** alloc_expression_id (pre_expr expr)
*** 247,255 ****
    gcc_assert (next_expression_id + 1 > next_expression_id);
    expr->id = next_expression_id++;
    VEC_safe_push (pre_expr, heap, expressions, expr);
!   slot = htab_find_slot (expression_to_id, expr, INSERT);
!   gcc_assert (!*slot);
!   *slot = expr;
    return next_expression_id - 1;
  }
  
--- 248,270 ----
    gcc_assert (next_expression_id + 1 > next_expression_id);
    expr->id = next_expression_id++;
    VEC_safe_push (pre_expr, heap, expressions, expr);
!   if (expr->kind == NAME)
!     {
!       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
!       /* VEC_safe_grow_cleared allocates no headroom.  Avoid frequent
! 	 re-allocations by using VEC_reserve upfront.  There is no
! 	 VEC_quick_grow_cleared unfortunately.  */
!       VEC_reserve (unsigned, heap, name_to_id, num_ssa_names);
!       VEC_safe_grow_cleared (unsigned, heap, name_to_id, num_ssa_names);
!       gcc_assert (VEC_index (unsigned, name_to_id, version) == 0);
!       VEC_replace (unsigned, name_to_id, version, expr->id);
!     }
!   else
!     {
!       slot = htab_find_slot (expression_to_id, expr, INSERT);
!       gcc_assert (!*slot);
!       *slot = expr;
!     }
    return next_expression_id - 1;
  }
  
*************** lookup_expression_id (const pre_expr exp
*** 266,275 ****
  {
    void **slot;
  
!   slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
!   if (!slot)
!     return 0;
!   return ((pre_expr)*slot)->id;
  }
  
  /* Return the existing expression id for EXPR, or create one if one
--- 281,300 ----
  {
    void **slot;
  
!   if (expr->kind == NAME)
!     {
!       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
!       if (VEC_length (unsigned, name_to_id) <= version)
! 	return 0;
!       return VEC_index (unsigned, name_to_id, version);
!     }
!   else
!     {
!       slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
!       if (!slot)
! 	return 0;
!       return ((pre_expr)*slot)->id;
!     }
  }
  
  /* Return the existing expression id for EXPR, or create one if one
*************** init_pre (bool do_fre)
*** 4483,4488 ****
--- 4526,4532 ----
    value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
    VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
  			 get_max_value_id() + 1);
+   name_to_id = NULL;
  
    in_fre = do_fre;
  
*************** fini_pre (bool do_fre)
*** 4544,4549 ****
--- 4588,4594 ----
    free_alloc_pool (pre_expr_pool);
    htab_delete (phi_translate_table);
    htab_delete (expression_to_id);
+   VEC_free (unsigned, heap, name_to_id);
  
    FOR_ALL_BB (bb)
      {