From 90c1d75a9bb8e25aa963da02f9c91f5f40143be1 Mon Sep 17 00:00:00 2001 From: Diego Novillo Date: Wed, 23 Feb 2005 05:08:32 +0000 Subject: re PR tree-optimization/20100 (LIM is pulling out a pure function even though there is something which can modify global memory) PR tree-optimization/20100 PR tree-optimization/20115 * tree-optimize.c (init_tree_optimization_passes): Remove pass_maybe_create_global_var. * tree-pass.h (pass_maybe_create_global_var): Remove. * tree-ssa-alias.c (aliases_computed_p): Declare. (struct alias_info): Add field NUM_PURE_CONST_CALLS_FOUND. (count_calls_and_maybe_create_global_var): Remove. (pass_maybe_create_global_var): Remove. (init_alias_info): Do not declare aliases_computed_p. (maybe_create_global_var): If the function contains no call-clobbered variables and a mix of pure/const and regular function calls, create .GLOBAL_VAR. Mark all call-clobbered variables for renaming. (merge_pointed_to_info): Update comment. (add_pointed_to_var): Likewise. (is_escape_site): Likewise. Accept struct alias_info * instead of size_t *. Update all users. Update AI->NUM_CALLS_FOUND and AI->NUM_PURE_CONST_CALLS_FOUND as necessary. * tree-ssa-operands.c (get_call_expr_operands): If ALIASES_COMPUTED_P is false, do not add call-clobbering operands. * tree-ssa.c (init_tree_ssa): Set ALIASES_COMPUTED_P to false. (delete_tree_ssa): Likewise. testsuite/ChangeLog PR tree-optimization/20100 PR tree-optimization/20115 * gcc.dg/pr20115.c: New test. * gcc.dg/pr20115-1.c: New test. * gcc.dg/pr20100.c: New test. * gcc.dg/tree-ssa/20040517-1.c: Expect virtual operands for call-clobbered variables after alias1. From-SVN: r95437 --- gcc/ChangeLog | 29 ++++++ gcc/testsuite/ChangeLog | 10 ++ gcc/testsuite/gcc.dg/pr20100.c | 32 +++++++ gcc/testsuite/gcc.dg/pr20115-1.c | 14 +++ gcc/testsuite/gcc.dg/pr20115.c | 28 ++++++ gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c | 5 +- gcc/tree-optimize.c | 1 - gcc/tree-pass.h | 1 - gcc/tree-ssa-alias.c | 147 +++++++++++++---------------- gcc/tree-ssa-operands.c | 12 ++- gcc/tree-ssa.c | 2 + 11 files changed, 193 insertions(+), 88 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr20100.c create mode 100644 gcc/testsuite/gcc.dg/pr20115-1.c create mode 100644 gcc/testsuite/gcc.dg/pr20115.c (limited to 'gcc') diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 903d625..ee37f3e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,32 @@ +2005-02-22 Diego Novillo + + PR tree-optimization/20100 + PR tree-optimization/20115 + * tree-optimize.c (init_tree_optimization_passes): Remove + pass_maybe_create_global_var. + * tree-pass.h (pass_maybe_create_global_var): Remove. + * tree-ssa-alias.c (aliases_computed_p): Declare. + (struct alias_info): Add field NUM_PURE_CONST_CALLS_FOUND. + (count_calls_and_maybe_create_global_var): Remove. + (pass_maybe_create_global_var): Remove. + (init_alias_info): Do not declare aliases_computed_p. + (maybe_create_global_var): If the function contains no + call-clobbered variables and a mix of pure/const and regular + function calls, create .GLOBAL_VAR. + Mark all call-clobbered variables for renaming. + (merge_pointed_to_info): Update comment. + (add_pointed_to_var): Likewise. + (is_escape_site): Likewise. + Accept struct alias_info * instead of size_t *. + Update all users. + Update AI->NUM_CALLS_FOUND and AI->NUM_PURE_CONST_CALLS_FOUND + as necessary. + * tree-ssa-operands.c (get_call_expr_operands): If + ALIASES_COMPUTED_P is false, do not add call-clobbering + operands. + * tree-ssa.c (init_tree_ssa): Set ALIASES_COMPUTED_P to false. + (delete_tree_ssa): Likewise. + 2005-02-22 James E Wilson * toplev.c (backend_init): Don't call init_adjust_machine_modes here. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ddaa9cc..530d9a3 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,13 @@ +2005-02-22 Diego Novillo + + PR tree-optimization/20100 + PR tree-optimization/20115 + * gcc.dg/pr20115.c: New test. + * gcc.dg/pr20115-1.c: New test. + * gcc.dg/pr20100.c: New test. + * gcc.dg/tree-ssa/20040517-1.c: Expect virtual operands for + call-clobbered variables after alias1. + 2005-02-22 Bud Davis * gfortran.dg/list_read_4.f90: new test. diff --git a/gcc/testsuite/gcc.dg/pr20100.c b/gcc/testsuite/gcc.dg/pr20100.c new file mode 100644 index 0000000..988fbda --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr20100.c @@ -0,0 +1,32 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +int func_pure (void) __attribute__ ((pure)); +void func_other (int); +int global_int; +void abort (); +void func_other(int a) +{ + if (a != global_int) + abort (); + global_int++; +} + +int func_pure(void) +{ + return global_int; +} + +int +func_loop (int arg) +{ + // global_int ++; + while (arg--) + func_other (func_pure ()); +} + +int main(void) +{ + func_loop(10); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/pr20115-1.c b/gcc/testsuite/gcc.dg/pr20115-1.c new file mode 100644 index 0000000..d1c4066 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr20115-1.c @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dom1" } */ + +extern int foo (void) __attribute__((pure)); + +int bar() +{ + int a = foo (); + a += foo (); + return a; +} + +/* Check that we only have one call to foo. */ +/* { dg-final { scan-tree-dump-times "foo" 1 "dom1" } } */ diff --git a/gcc/testsuite/gcc.dg/pr20115.c b/gcc/testsuite/gcc.dg/pr20115.c new file mode 100644 index 0000000..cea4b48 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr20115.c @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +int func_pure (void); +void func_other (int); +int global_int; +int func_pure (void) { return global_int; } +void func_other (int a) +{ + global_int = a + 1; +} +int f(void) +{ + int a; + a = func_pure(); + func_other (a); + a = func_pure (); // We were removing this function call + return a; +} +void abort (void); + +int main(void) +{ + global_int = 10; + if (f() != 11) + abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c b/gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c index 5f99be2..4b09b53 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O1 -fdump-tree-ssa-vops" } */ +/* { dg-options "-O1 -fdump-tree-alias1-vops" } */ extern void abort (void); int a; @@ -17,5 +17,4 @@ void bar (void) malloc functions may clobber global memory. Only the function result does not alias any other pointer. Hence, we must have a VDEF for a before and after the call to foo(). */ -/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "ssa"} } */ - +/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "alias1"} } */ diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c index d2c8ede..f4ad966 100644 --- a/gcc/tree-optimize.c +++ b/gcc/tree-optimize.c @@ -347,7 +347,6 @@ init_tree_optimization_passes (void) p = &pass_all_optimizations.sub; NEXT_PASS (pass_referenced_vars); - NEXT_PASS (pass_maybe_create_global_var); NEXT_PASS (pass_build_ssa); NEXT_PASS (pass_may_alias); NEXT_PASS (pass_rename_ssa_copies); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 6bedfcb..bf81809 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -166,6 +166,5 @@ extern struct tree_opt_pass pass_expand; extern struct tree_opt_pass pass_rest_of_compilation; extern struct tree_opt_pass pass_fre; extern struct tree_opt_pass pass_linear_transform; -extern struct tree_opt_pass pass_maybe_create_global_var; #endif /* GCC_TREE_PASS_H */ diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index bfa1685..f6cdf99 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -43,6 +43,8 @@ Boston, MA 02111-1307, USA. */ #include "convert.h" #include "params.h" +/* 'true' after aliases have been computed (see compute_may_aliases). */ +bool aliases_computed_p; /* Structure to map a variable to its alias set and keep track of the virtual operands that will be needed to represent it. */ @@ -94,6 +96,9 @@ struct alias_info /* Number of function calls found in the program. */ size_t num_calls_found; + /* Number of const/pure function calls found in the program. */ + size_t num_pure_const_calls_found; + /* Array of counters to keep track of how many times each pointer has been dereferenced in the program. This is used by the alias grouping heuristic in compute_flow_insensitive_aliasing. */ @@ -145,7 +150,7 @@ static void compute_points_to_and_addr_escape (struct alias_info *); static void compute_flow_sensitive_aliasing (struct alias_info *); static void setup_pointers_and_addressables (struct alias_info *); static bool collect_points_to_info_r (tree, tree, void *); -static bool is_escape_site (tree, size_t *); +static bool is_escape_site (tree, struct alias_info *); static void add_pointed_to_var (struct alias_info *, tree, tree); static void create_global_var (void); static void collect_points_to_info_for (struct alias_info *, tree); @@ -465,70 +470,12 @@ count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, } -/* Count the number of calls in the function and conditionally - create GLOBAL_VAR. This is performed before translation - into SSA (and thus before alias analysis) to avoid compile time - and memory utilization explosions in functions with many - of calls and call clobbered variables. */ - -static void -count_calls_and_maybe_create_global_var (void) -{ - struct alias_info ai; - basic_block bb; - bool temp; - - memset (&ai, 0, sizeof (struct alias_info)); - - /* First count the number of calls in the IL. */ - FOR_EACH_BB (bb) - { - block_stmt_iterator si; - - for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) - { - tree stmt = bsi_stmt (si); - - if (get_call_expr_in (stmt) != NULL_TREE) - ai.num_calls_found++; - } - } - - /* If there are no call clobbered variables, then maybe_create_global_var - will always create a GLOBAL_VAR. At this point we do not want that - behavior. So we turn on one bit in CALL_CLOBBERED_VARs, call - maybe_create_global_var, then reset the bit to its original state. */ - temp = bitmap_bit_p (call_clobbered_vars, 0); - bitmap_set_bit (call_clobbered_vars, 0); - maybe_create_global_var (&ai); - if (!temp) - bitmap_clear_bit (call_clobbered_vars, 0); -} - -struct tree_opt_pass pass_maybe_create_global_var = -{ - "maybe_create_global_var", /* name */ - NULL, /* gate */ - count_calls_and_maybe_create_global_var, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_MAY_ALIAS, /* tv_id */ - PROP_cfg, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ - 0 /* letter */ -}; - /* Initialize the data structures used for alias analysis. */ static struct alias_info * init_alias_info (void) { struct alias_info *ai; - static bool aliases_computed_p = false; ai = xcalloc (1, sizeof (struct alias_info)); ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); @@ -695,7 +642,7 @@ compute_points_to_and_addr_escape (struct alias_info *ai) { bitmap addr_taken; tree stmt = bsi_stmt (si); - bool stmt_escapes_p = is_escape_site (stmt, &ai->num_calls_found); + bool stmt_escapes_p = is_escape_site (stmt, ai); bitmap_iterator bi; /* Mark all the variables whose address are taken by the @@ -1586,22 +1533,56 @@ maybe_create_global_var (struct alias_info *ai) n_clobbered++; } - if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD) + /* If the number of virtual operands that would be needed to + model all the call-clobbered variables is larger than + GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR. + + Also create .GLOBAL_VAR if there are no call-clobbered + variables and the program contains a mixture of pure/const + and regular function calls. This is to avoid the problem + described in PR 20115: + + int X; + int func_pure (void) { return X; } + int func_non_pure (int a) { X += a; } + int foo () + { + int a = func_pure (); + func_non_pure (a); + a = func_pure (); + return a; + } + + Since foo() has no call-clobbered variables, there is + no relationship between the calls to func_pure and + func_non_pure. Since func_pure has no side-effects, value + numbering optimizations elide the second call to func_pure. + So, if we have some pure/const and some regular calls in the + program we create .GLOBAL_VAR to avoid missing these + relations. */ + if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD + || (n_clobbered == 0 + && ai->num_calls_found > 0 + && ai->num_pure_const_calls_found > 0 + && ai->num_calls_found > ai->num_pure_const_calls_found)) create_global_var (); } - /* If the function has calls to clobbering functions and .GLOBAL_VAR has - been created, make it an alias for all call-clobbered variables. */ - if (global_var) - EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) - { - tree var = referenced_var (i); - if (var != global_var) - { - add_may_alias (var, global_var); - bitmap_set_bit (vars_to_rename, var_ann (var)->uid); - } - } + /* Mark all call-clobbered symbols for renaming. Since the initial + rewrite into SSA ignored all call sites, we may need to rename + .GLOBAL_VAR and the call-clobbered variables. */ + EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) + { + tree var = referenced_var (i); + + /* If the function has calls to clobbering functions and + .GLOBAL_VAR has been created, make it an alias for all + call-clobbered variables. */ + if (global_var && var != global_var) + add_may_alias (var, global_var); + + bitmap_set_bit (vars_to_rename, var_ann (var)->uid); + } } @@ -1762,8 +1743,8 @@ set_pt_malloc (tree ptr) /* Given two different pointers DEST and ORIG. Merge the points-to - information in ORIG into DEST. AI is as in - collect_points_to_info. */ + information in ORIG into DEST. AI contains all the alias + information collected up to this point. */ static void merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) @@ -1908,7 +1889,7 @@ add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr) /* If VALUE is of the form &DECL, add DECL to the set of variables pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by - PTR. AI is as in collect_points_to_info. */ + PTR. AI points to the collected alias information. */ static void add_pointed_to_var (struct alias_info *ai, tree ptr, tree value) @@ -2040,16 +2021,18 @@ collect_points_to_info_r (tree var, tree stmt, void *data) 3- STMT is an assignment to a non-local variable, or 4- STMT is a return statement. - If NUM_CALLS_P is not NULL, the counter is incremented if STMT contains - a function call. */ + AI points to the alias information collected so far. */ static bool -is_escape_site (tree stmt, size_t *num_calls_p) +is_escape_site (tree stmt, struct alias_info *ai) { - if (get_call_expr_in (stmt) != NULL_TREE) + tree call = get_call_expr_in (stmt); + if (call != NULL_TREE) { - if (num_calls_p) - (*num_calls_p)++; + ai->num_calls_found++; + + if (!TREE_SIDE_EFFECTS (call)) + ai->num_pure_const_calls_found++; return true; } diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index 0f27912..3b5de9b 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -1460,7 +1460,17 @@ get_call_expr_operands (tree stmt, tree expr) tree op; int call_flags = call_expr_flags (expr); - if (!bitmap_empty_p (call_clobbered_vars)) + /* If aliases have been computed already, add V_MAY_DEF or V_USE + operands for all the symbols that have been found to be + call-clobbered. + + Note that if aliases have not been computed, the global effects + of calls will not be included in the SSA web. This is fine + because no optimizer should run before aliases have been + computed. By not bothering with virtual operands for CALL_EXPRs + we avoid adding superfluous virtual operands, which can be a + significant compile time sink (See PR 15855). */ + if (aliases_computed_p && !bitmap_empty_p (call_clobbered_vars)) { /* A 'pure' or a 'const' functions never call clobber anything. A 'noreturn' function might, but since we don't return anyway diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index 56a181a..b39c260 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -723,6 +723,7 @@ init_tree_ssa (void) init_ssanames (); init_phinodes (); global_var = NULL_TREE; + aliases_computed_p = false; } @@ -767,6 +768,7 @@ delete_tree_ssa (void) BITMAP_FREE (addressable_vars); addressable_vars = NULL; modified_noreturn_calls = NULL; + aliases_computed_p = false; } -- cgit v1.1