diff options
| -rw-r--r-- | gcc/ChangeLog | 10 | ||||
| -rw-r--r-- | gcc/doc/invoke.texi | 7 | ||||
| -rw-r--r-- | gcc/gcse.c | 74 | ||||
| -rw-r--r-- | gcc/lcm.c | 4 | ||||
| -rw-r--r-- | gcc/params.def | 10 | ||||
| -rw-r--r-- | gcc/params.h | 4 |
6 files changed, 104 insertions, 5 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2ae86134ea2..e91f54e8cfe 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2011-01-13 Jeff Law <law@redhat.com> + + * PR rtl-optimization/39077 + * doc/invoke.texi (max-gcse-insertion-ratio): Document. + * params.h (MAX_GCSE_INSERTION_RATIO): Define. + * params.def (PARAM_MAX_GCSE_INSERTION_RATIO): Define. + * lcm.c (pre_edge_lcm): Properly initialize output sbitmaps. + * gcse.c (prune_insertions_deletions): New function. + (compute_pre_data): Use it. + 2011-01-13 Dodji Seketeli <dodji@redhat.com> PR debug/PR46973 diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index e5ba12cb041..0a1625f241a 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -1,5 +1,5 @@ @c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, -@c 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +@c 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 @c Free Software Foundation, Inc. @c This is part of the GCC manual. @c For copying conditions, see the file gcc.texi. @@ -8227,6 +8227,11 @@ order to perform the global common subexpression elimination optimization. If more memory than specified is required, the optimization will not be done. +@item max-gcse-insertion-ratio +If the ratio of expression insertions to deletions is larger than this value +for any expression, then RTL PRE will insert or remove the expression and thus +leave partially redundant computations in the instruction stream. The default value is 20. + @item max-pending-list-length The maximum number of pending dependencies scheduling will allow before flushing the current state and starting over. Large functions diff --git a/gcc/gcse.c b/gcc/gcse.c index 9ff0da82f1e..a0f51aa09b4 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -1,7 +1,7 @@ /* Global common subexpression elimination/Partial redundancy elimination and global constant/copy propagation for GNU compiler. Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, - 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. + 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. This file is part of GCC. @@ -3396,6 +3396,75 @@ prune_expressions (bool pre_p) sbitmap_free (prune_exprs); } +/* It may be necessary to insert a large number of insns on edges to + make the existing occurrences of expressions fully redundant. This + routine examines the set of insertions and deletions and if the ratio + of insertions to deletions is too high for a particular expression, then + the expression is removed from the insertion/deletion sets. + + N_ELEMS is the number of elements in the hash table. */ + +static void +prune_insertions_deletions (int n_elems) +{ + sbitmap_iterator sbi; + sbitmap prune_exprs; + + /* We always use I to iterate over blocks/edges and J to iterate over + expressions. */ + unsigned int i, j; + + /* Counts for the number of times an expression needs to be inserted and + number of times an expression can be removed as a result. */ + int *insertions = GCNEWVEC (int, n_elems); + int *deletions = GCNEWVEC (int, n_elems); + + /* Set of expressions which require too many insertions relative to + the number of deletions achieved. We will prune these out of the + insertion/deletion sets. */ + prune_exprs = sbitmap_alloc (n_elems); + sbitmap_zero (prune_exprs); + + /* Iterate over the edges counting the number of times each expression + needs to be inserted. */ + for (i = 0; i < (unsigned) n_edges; i++) + { + EXECUTE_IF_SET_IN_SBITMAP (pre_insert_map[i], 0, j, sbi) + insertions[j]++; + } + + /* Similarly for deletions, but those occur in blocks rather than on + edges. */ + for (i = 0; i < (unsigned) last_basic_block; i++) + { + EXECUTE_IF_SET_IN_SBITMAP (pre_delete_map[i], 0, j, sbi) + deletions[j]++; + } + + /* Now that we have accurate counts, iterate over the elements in the + hash table and see if any need too many insertions relative to the + number of evaluations that can be removed. If so, mark them in + PRUNE_EXPRS. */ + for (j = 0; j < (unsigned) n_elems; j++) + if (deletions[j] + && ((unsigned) insertions[j] / deletions[j]) > MAX_GCSE_INSERTION_RATIO) + SET_BIT (prune_exprs, j); + + /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */ + EXECUTE_IF_SET_IN_SBITMAP (prune_exprs, 0, j, sbi) + { + for (i = 0; i < (unsigned) n_edges; i++) + RESET_BIT (pre_insert_map[i], j); + + for (i = 0; i < (unsigned) last_basic_block; i++) + RESET_BIT (pre_delete_map[i], j); + } + + sbitmap_free (prune_exprs); + free (insertions); + free (deletions); +} + /* Top level routine to do the dataflow analysis needed by PRE. */ static void @@ -3424,6 +3493,8 @@ compute_pre_data (void) antloc = NULL; sbitmap_vector_free (ae_kill); ae_kill = NULL; + + prune_insertions_deletions (expr_hash_table.n_elems); } /* PRE utilities */ @@ -5368,3 +5439,4 @@ struct rtl_opt_pass pass_rtl_hoist = }; #include "gt-gcse.h" + diff --git a/gcc/lcm.c b/gcc/lcm.c index 31e82886df4..61c67e04ae7 100644 --- a/gcc/lcm.c +++ b/gcc/lcm.c @@ -1,6 +1,6 @@ /* Generic partial redundancy elimination with lazy code motion support. Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, - 2010 Free Software Foundation, Inc. + 2010, 2011 Free Software Foundation, Inc. This file is part of GCC. @@ -451,6 +451,8 @@ pre_edge_lcm (int n_exprs, sbitmap *transp, *insert = sbitmap_vector_alloc (num_edges, n_exprs); *del = sbitmap_vector_alloc (last_basic_block, n_exprs); + sbitmap_vector_zero (*insert, num_edges); + sbitmap_vector_zero (*del, last_basic_block); compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del); sbitmap_vector_free (laterin); diff --git a/gcc/params.def b/gcc/params.def index 2ea00137b2b..96dc858cf82 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1,5 +1,6 @@ /* params.def - Run-time parameters. - Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, + 2011 Free Software Foundation, Inc. Written by Mark Mitchell <mark@codesourcery.com>. @@ -214,6 +215,13 @@ DEFPARAM(PARAM_MAX_GCSE_MEMORY, "The maximum amount of memory to be allocated by GCSE", 50 * 1024 * 1024, 0, 0) +/* The GCSE optimization of an expression will avoided if the ratio of + insertions to deletions is greater than this value. */ +DEFPARAM(PARAM_MAX_GCSE_INSERTION_RATIO, + "max-gcse-insertion-ratio", + "The maximum ratio of insertions to deletions of expressions in GCSE", + 20, 0, 0) + /* This is the threshold ratio when to perform partial redundancy elimination after reload. We perform partial redundancy elimination when the following holds: diff --git a/gcc/params.h b/gcc/params.h index 5aeb3ef47d7..e36a5ea3406 100644 --- a/gcc/params.h +++ b/gcc/params.h @@ -1,5 +1,5 @@ /* params.h - Run-time parameters. - Copyright (C) 2001, 2003, 2004, 2005, 2007, 2008, 2009, 2010 + Copyright (C) 2001, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. Written by Mark Mitchell <mark@codesourcery.com>. @@ -142,6 +142,8 @@ extern void init_param_values (int *params); PARAM_VALUE (PARAM_MAX_PENDING_LIST_LENGTH) #define MAX_GCSE_MEMORY \ ((size_t) PARAM_VALUE (PARAM_MAX_GCSE_MEMORY)) +#define MAX_GCSE_INSERTION_RATIO \ + ((size_t) PARAM_VALUE (PARAM_MAX_GCSE_INSERTION_RATIO)) #define GCSE_AFTER_RELOAD_PARTIAL_FRACTION \ PARAM_VALUE (PARAM_GCSE_AFTER_RELOAD_PARTIAL_FRACTION) #define GCSE_AFTER_RELOAD_CRITICAL_FRACTION \ |