[PATCH] Adjust alias-oracle cut-off in DCE

[PATCH] Adjust alias-oracle cut-off in DCE

[Richard Guenther]

This adjusts the cutoff to be more balanced and handle rths
vector permutation testcase a bit more gracefully.  It's very
special in that it loads from a global non-address-taken static
variable a lot of times but never stores to it.

Alias-oracle queries are not exactly cheap because of our
memory reference representation.

The adjustment brings down the number of queries by a factor of 10
for the testcase and the time we spent there to 2% compared to
20% before the change (with checking and profiling enabled).

Bootstrap and regtest running on x86_64-unknown-linux-gnu, I'll
apply it after that succeeded.

Richard.

2009-11-26  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-dce.c (nr_walks): New variable.
	(mark_aliased_reaching_defs_necessary): Adjust oracle cut-off.
	(perform_tree_ssa_dce): Init nr_walks.

Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c	(revision 154672)
--- gcc/tree-ssa-dce.c	(working copy)
*************** ref_may_be_aliased (tree ref)
*** 489,494 ****
--- 489,495 ----
  static bitmap visited = NULL;
  static unsigned int longest_chain = 0;
  static unsigned int total_chain = 0;
+ static unsigned int nr_walks = 0;
  static bool chain_ovfl = false;
  
  /* Worker for the walker that marks reaching definitions of REF,
*************** mark_aliased_reaching_defs_necessary (gi
*** 557,562 ****
--- 558,564 ----
    if (chain > longest_chain)
      longest_chain = chain;
    total_chain += chain;
+   nr_walks++;
  }
  
  /* Worker for the walker that marks reaching definitions of REF, which
*************** propagate_necessity (struct edge_list *e
*** 803,813 ****
  	    gcc_unreachable ();
  
  	  /* If we over-used our alias oracle budget drop to simple
! 	     mode.  The cost metric allows quadratic behavior up to
! 	     a constant maximal chain and after that falls back to
  	     super-linear complexity.  */
! 	  if (longest_chain > 256
! 	      && total_chain > 256 * longest_chain)
  	    {
  	      chain_ovfl = true;
  	      if (visited)
--- 805,820 ----
  	    gcc_unreachable ();
  
  	  /* If we over-used our alias oracle budget drop to simple
! 	     mode.  The cost metric allows quadratic behavior
! 	     (number of uses times number of may-defs queries) up to
! 	     a constant maximal number of queries and after that falls back to
  	     super-linear complexity.  */
! 	  if (/* Constant but quadratic for small functions.  */
! 	      total_chain > 128 * 128
! 	      /* Linear in the number of may-defs.  */
! 	      && total_chain > 32 * longest_chain
! 	      /* Linear in the number of uses.  */
! 	      && total_chain > nr_walks * 32)
  	    {
  	      chain_ovfl = true;
  	      if (visited)
*************** perform_tree_ssa_dce (bool aggressive)
*** 1376,1381 ****
--- 1383,1389 ----
  
    longest_chain = 0;
    total_chain = 0;
+   nr_walks = 0;
    chain_ovfl = false;
    visited = BITMAP_ALLOC (NULL);
    propagate_necessity (el);