diff options
author | Richard Biener <rguenther@suse.de> | 2014-06-17 07:42:47 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2014-06-17 07:42:47 +0000 |
commit | ec18e2ebbf6a04097c7204032aba3f2646bede4a (patch) | |
tree | d6369b46de1be4b74f6def12abc41a2f75c74125 /gcc | |
parent | a4ab23b698ec5b8810a23df011453967d1d09180 (diff) | |
download | gcc-ec18e2ebbf6a04097c7204032aba3f2646bede4a.zip gcc-ec18e2ebbf6a04097c7204032aba3f2646bede4a.tar.gz gcc-ec18e2ebbf6a04097c7204032aba3f2646bede4a.tar.bz2 |
tree-ssa-propagate.c: Include domwalk.h.
2014-06-17 Richard Biener <rguenther@suse.de>
* tree-ssa-propagate.c: Include domwalk.h.
(substitute_and_fold): Outline main worker into a domwalker ...
(substitute_and_fold_dom_walker::before_dom_children): ... here.
Schedule stmts we can fully propagate for removal. Remove
poor-mans DCE.
(substitute_and_fold): Apply a dominator walk to perform
substitution. Process stmts scheduled for removal here.
* gcc.dg/tree-ssa/20041122-1.c: Adjust.
* gcc.dg/tree-ssa/forwprop-21.c: Likewise.
* gcc.dg/tree-ssa/vrp35.c: Revert previous adjustments.
* gcc.dg/tree-ssa/vrp36.c: Likewise.
* gcc.dg/vect/nodump-forwprop-22.c: Adjust.
From-SVN: r211725
Diffstat (limited to 'gcc')
-rw-r--r-- | gcc/ChangeLog | 10 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 8 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c | 6 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/forwprop-21.c | 8 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp35.c | 2 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp36.c | 2 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/vect/nodump-forwprop-22.c | 10 | ||||
-rw-r--r-- | gcc/tree-ssa-propagate.c | 375 |
8 files changed, 217 insertions, 204 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 16c505f..e12a8ab 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,15 @@ 2014-06-17 Richard Biener <rguenther@suse.de> + * tree-ssa-propagate.c: Include domwalk.h. + (substitute_and_fold): Outline main worker into a domwalker ... + (substitute_and_fold_dom_walker::before_dom_children): ... here. + Schedule stmts we can fully propagate for removal. Remove + poor-mans DCE. + (substitute_and_fold): Apply a dominator walk to perform + substitution. Process stmts scheduled for removal here. + +2014-06-17 Richard Biener <rguenther@suse.de> + * tree-ssa-loop-im.c (determine_max_movement): Adjust cost of PHI node moving. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 7f408ad..c9e1511 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,13 @@ 2014-06-17 Richard Biener <rguenther@suse.de> + * gcc.dg/tree-ssa/20041122-1.c: Adjust. + * gcc.dg/tree-ssa/forwprop-21.c: Likewise. + * gcc.dg/tree-ssa/vrp35.c: Revert previous adjustments. + * gcc.dg/tree-ssa/vrp36.c: Likewise. + * gcc.dg/vect/nodump-forwprop-22.c: Adjust. + +2014-06-17 Richard Biener <rguenther@suse.de> + * gcc.dg/tree-ssa/ssa-lim-12.c: New testcase. 2014-06-16 Richard Biener <rguenther@suse.de> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c b/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c index 5e6828b..80068b8 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O1 -fstrict-aliasing -fdump-tree-fre1" } */ +/* { dg-options "-O1 -fstrict-aliasing -fdump-tree-cddce1" } */ __extension__ typedef __SIZE_TYPE__ size_t; extern void *xmalloc (size_t) __attribute__ ((__malloc__)); @@ -34,5 +34,5 @@ find_unreachable_blocks (void) able to determine that modifying e->dest->flags does not modify e or e->dest if we can assert strict-aliasing rules. The net result is that we only need one load of e->dest. */ -/* { dg-final { scan-tree-dump-times "->dest" 1 "fre1" } } */ -/* { dg-final { cleanup-tree-dump "fre1" } } */ +/* { dg-final { scan-tree-dump-times "->dest" 1 "cddce1" } } */ +/* { dg-final { cleanup-tree-dump "cddce1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-21.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-21.c index d92b9b3..e613332 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-21.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-21.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O -fdump-tree-copyprop1" } */ +/* { dg-options "-O -fdump-tree-cddce1 -fno-tree-fre" } */ typedef int v4si __attribute__ ((vector_size (4 * sizeof(int)))); int @@ -10,7 +10,7 @@ test (v4si *x, v4si *y) return z[2]; } -/* Optimization in forwprop1, cleanup in copyprop1. */ +/* Optimization in forwprop1, cleanup in cddce1. */ -/* { dg-final { scan-tree-dump-not "VEC_PERM_EXPR" "copyprop1" } } */ -/* { dg-final { cleanup-tree-dump "copyprop1" } } */ +/* { dg-final { scan-tree-dump-not "VEC_PERM_EXPR" "cddce1" } } */ +/* { dg-final { cleanup-tree-dump "cddce1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c index 6402f4d..06b567d 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c @@ -11,5 +11,5 @@ int test1(int i, int k) return 1; } -/* { dg-final { scan-tree-dump-not "j_.* == 10" "vrp1" } } */ +/* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */ /* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c index de300d7..9d61960 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c @@ -8,5 +8,5 @@ int foo(int i) return 1; } -/* { dg-final { scan-tree-dump-not "i_.* == 1" "vrp1" } } */ +/* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */ /* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/nodump-forwprop-22.c b/gcc/testsuite/gcc.dg/vect/nodump-forwprop-22.c index 526e70b..6d33f00 100644 --- a/gcc/testsuite/gcc.dg/vect/nodump-forwprop-22.c +++ b/gcc/testsuite/gcc.dg/vect/nodump-forwprop-22.c @@ -1,7 +1,7 @@ /* { dg-do compile } */ /* { dg-require-effective-target vect_double } */ /* { dg-require-effective-target vect_perm } */ -/* { dg-additional-options "-fdump-tree-copyprop1" } */ +/* { dg-additional-options "-fdump-tree-cddce1 -fno-tree-fre" } */ typedef double vec __attribute__((vector_size (2 * sizeof (double)))); void f (vec *px, vec *y, vec *z) @@ -13,8 +13,8 @@ void f (vec *px, vec *y, vec *z) *z = t2; } -/* Optimization in forwprop1, cleanup in copyprop1. */ +/* Optimization in forwprop1, cleanup in cddce1. */ -/* { dg-final { scan-tree-dump-times "VEC_PERM_EXPR" 1 "copyprop1" } } */ -/* { dg-final { scan-tree-dump-not "BIT_FIELD_REF" "copyprop1" } } */ -/* { dg-final { cleanup-tree-dump "copyprop1" } } */ +/* { dg-final { scan-tree-dump-times "VEC_PERM_EXPR" 1 "cddce1" } } */ +/* { dg-final { scan-tree-dump-not "BIT_FIELD_REF" "cddce1" } } */ +/* { dg-final { cleanup-tree-dump "cddce1" } } */ diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c index 255bff9..cdc9f6a 100644 --- a/gcc/tree-ssa-propagate.c +++ b/gcc/tree-ssa-propagate.c @@ -49,6 +49,7 @@ #include "tree-ssa-propagate.h" #include "langhooks.h" #include "value-prof.h" +#include "domwalk.h" /* This file implements a generic value propagation engine based on the same propagation used by the SSA-CCP algorithm [1]. @@ -1017,225 +1018,218 @@ replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value) } -/* Perform final substitution and folding of propagated values. - - PROP_VALUE[I] contains the single value that should be substituted - at every use of SSA name N_I. If PROP_VALUE is NULL, no values are - substituted. - - If FOLD_FN is non-NULL the function will be invoked on all statements - before propagating values for pass specific simplification. - - DO_DCE is true if trivially dead stmts can be removed. - - If DO_DCE is true, the statements within a BB are walked from - last to first element. Otherwise we scan from first to last element. - - Return TRUE when something changed. */ - -bool -substitute_and_fold (ssa_prop_get_value_fn get_value_fn, - ssa_prop_fold_stmt_fn fold_fn, - bool do_dce) +class substitute_and_fold_dom_walker : public dom_walker { - basic_block bb; - bool something_changed = false; - unsigned i; +public: + substitute_and_fold_dom_walker (cdi_direction direction, + ssa_prop_get_value_fn get_value_fn_, + ssa_prop_fold_stmt_fn fold_fn_, + bool do_dce_) + : dom_walker (direction), get_value_fn (get_value_fn_), + fold_fn (fold_fn_), do_dce (do_dce_), something_changed (false) + { + stmts_to_remove.create (0); + } + ~substitute_and_fold_dom_walker () { stmts_to_remove.release (); } - if (!get_value_fn && !fold_fn) - return false; + virtual void before_dom_children (basic_block); + virtual void after_dom_children (basic_block) {} - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nSubstituting values and folding statements\n\n"); + ssa_prop_get_value_fn get_value_fn; + ssa_prop_fold_stmt_fn fold_fn; + bool do_dce; + bool something_changed; + vec<gimple> stmts_to_remove; +}; - memset (&prop_stats, 0, sizeof (prop_stats)); +void +substitute_and_fold_dom_walker::before_dom_children (basic_block bb) +{ + gimple_stmt_iterator i; - /* Substitute lattice values at definition sites. */ - if (get_value_fn) - for (i = 1; i < num_ssa_names; ++i) - { - tree name = ssa_name (i); - tree val; - gimple def_stmt; - gimple_stmt_iterator gsi; - - if (!name - || virtual_operand_p (name)) - continue; - - def_stmt = SSA_NAME_DEF_STMT (name); - if (gimple_nop_p (def_stmt) - /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP. */ - || (gimple_assign_single_p (def_stmt) - && gimple_assign_rhs_code (def_stmt) == ASSERT_EXPR) - || !(val = (*get_value_fn) (name)) - || !may_propagate_copy (name, val)) - continue; - - gsi = gsi_for_stmt (def_stmt); - if (is_gimple_assign (def_stmt)) - { - gimple_assign_set_rhs_with_ops (&gsi, TREE_CODE (val), - val, NULL_TREE); - gcc_assert (gsi_stmt (gsi) == def_stmt); - if (maybe_clean_eh_stmt (def_stmt)) - gimple_purge_dead_eh_edges (gimple_bb (def_stmt)); - update_stmt (def_stmt); - } - else if (is_gimple_call (def_stmt)) - { - int flags = gimple_call_flags (def_stmt); - - /* Don't optimize away calls that have side-effects. */ - if ((flags & (ECF_CONST|ECF_PURE)) == 0 - || (flags & ECF_LOOPING_CONST_OR_PURE)) + /* Propagate known values into PHI nodes. */ + for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) + { + gimple phi = gsi_stmt (i); + tree res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; + if (do_dce + && res && TREE_CODE (res) == SSA_NAME) + { + tree sprime = get_value_fn (res); + if (sprime + && sprime != res + && may_propagate_copy (res, sprime)) + { + stmts_to_remove.safe_push (phi); continue; - if (update_call_from_tree (&gsi, val) - && maybe_clean_or_replace_eh_stmt (def_stmt, gsi_stmt (gsi))) - gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi))); - } - else if (gimple_code (def_stmt) == GIMPLE_PHI) - { - gimple new_stmt = gimple_build_assign (name, val); - gimple_stmt_iterator gsi2; - gsi2 = gsi_after_labels (gimple_bb (def_stmt)); - gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT); - remove_phi_node (&gsi, false); - } - - something_changed = true; - } - - /* Propagate into all uses and fold. */ - FOR_EACH_BB_FN (bb, cfun) + } + } + replace_phi_args_in (phi, get_value_fn); + } + + /* Propagate known values into stmts. In some case it exposes + more trivially deletable stmts to walk backward. */ + for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) { - gimple_stmt_iterator i; + bool did_replace; + gimple stmt = gsi_stmt (i); + gimple old_stmt; + enum gimple_code code = gimple_code (stmt); + + /* Ignore ASSERT_EXPRs. They are used by VRP to generate + range information for names and they are discarded + afterwards. */ - /* Propagate known values into PHI nodes. */ - if (get_value_fn) - for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) - replace_phi_args_in (gsi_stmt (i), get_value_fn); + if (code == GIMPLE_ASSIGN + && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) + continue; - /* Propagate known values into stmts. Do a backward walk if - do_dce is true. In some case it exposes - more trivially deletable stmts to walk backward. */ - for (i = (do_dce ? gsi_last_bb (bb) : gsi_start_bb (bb)); !gsi_end_p (i);) + /* No point propagating into a stmt we have a value for we + can propagate into all uses. Mark it for removal instead. */ + tree lhs = gimple_get_lhs (stmt); + if (do_dce + && lhs && TREE_CODE (lhs) == SSA_NAME) { - bool did_replace; - gimple stmt = gsi_stmt (i); - gimple old_stmt; - enum gimple_code code = gimple_code (stmt); - gimple_stmt_iterator oldi; - - oldi = i; - if (do_dce) - gsi_prev (&i); - else - gsi_next (&i); - - /* Ignore ASSERT_EXPRs. They are used by VRP to generate - range information for names and they are discarded - afterwards. */ - - if (code == GIMPLE_ASSIGN - && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) - continue; - - /* No point propagating into a stmt whose result is not used, - but instead we might be able to remove a trivially dead stmt. - Don't do this when called from VRP, since the SSA_NAME which - is going to be released could be still referenced in VRP - ranges. */ - if (do_dce - && gimple_get_lhs (stmt) - && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME - && has_zero_uses (gimple_get_lhs (stmt)) + tree sprime = get_value_fn (lhs); + if (sprime + && sprime != lhs + && may_propagate_copy (lhs, sprime) && !stmt_could_throw_p (stmt) && !gimple_has_side_effects (stmt)) { - gimple_stmt_iterator i2; - - if (dump_file && dump_flags & TDF_DETAILS) - { - fprintf (dump_file, "Removing dead stmt "); - print_gimple_stmt (dump_file, stmt, 0, 0); - fprintf (dump_file, "\n"); - } - prop_stats.num_dce++; - i2 = gsi_for_stmt (stmt); - gsi_remove (&i2, true); - release_defs (stmt); + stmts_to_remove.safe_push (stmt); continue; } + } + + /* Replace the statement with its folded version and mark it + folded. */ + did_replace = false; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Folding statement: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + old_stmt = stmt; + + /* Some statements may be simplified using propagator + specific information. Do this before propagating + into the stmt to not disturb pass specific information. */ + if (fold_fn + && (*fold_fn)(&i)) + { + did_replace = true; + prop_stats.num_stmts_folded++; + stmt = gsi_stmt (i); + update_stmt (stmt); + } + + /* Replace real uses in the statement. */ + did_replace |= replace_uses_in (stmt, get_value_fn); + + /* If we made a replacement, fold the statement. */ + if (did_replace) + fold_stmt (&i); - /* Replace the statement with its folded version and mark it - folded. */ - did_replace = false; - if (dump_file && (dump_flags & TDF_DETAILS)) + /* Now cleanup. */ + if (did_replace) + { + stmt = gsi_stmt (i); + + /* If we cleaned up EH information from the statement, + remove EH edges. */ + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) + gimple_purge_dead_eh_edges (bb); + + if (is_gimple_assign (stmt) + && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) + == GIMPLE_SINGLE_RHS)) { - fprintf (dump_file, "Folding statement: "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + tree rhs = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); } - old_stmt = stmt; + /* Determine what needs to be done to update the SSA form. */ + update_stmt (stmt); + if (!is_gimple_debug (stmt)) + something_changed = true; + } - /* Some statements may be simplified using propagator - specific information. Do this before propagating - into the stmt to not disturb pass specific information. */ - if (fold_fn - && (*fold_fn)(&oldi)) + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (did_replace) { - did_replace = true; - prop_stats.num_stmts_folded++; - stmt = gsi_stmt (oldi); - update_stmt (stmt); + fprintf (dump_file, "Folded into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + fprintf (dump_file, "\n"); } + else + fprintf (dump_file, "Not folded\n"); + } + } +} - /* Replace real uses in the statement. */ - if (get_value_fn) - did_replace |= replace_uses_in (stmt, get_value_fn); - /* If we made a replacement, fold the statement. */ - if (did_replace) - fold_stmt (&oldi); - /* Now cleanup. */ - if (did_replace) - { - stmt = gsi_stmt (oldi); +/* Perform final substitution and folding of propagated values. - /* If we cleaned up EH information from the statement, - remove EH edges. */ - if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) - gimple_purge_dead_eh_edges (bb); + PROP_VALUE[I] contains the single value that should be substituted + at every use of SSA name N_I. If PROP_VALUE is NULL, no values are + substituted. - if (is_gimple_assign (stmt) - && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) - == GIMPLE_SINGLE_RHS)) - { - tree rhs = gimple_assign_rhs1 (stmt); + If FOLD_FN is non-NULL the function will be invoked on all statements + before propagating values for pass specific simplification. - if (TREE_CODE (rhs) == ADDR_EXPR) - recompute_tree_invariant_for_addr_expr (rhs); - } + DO_DCE is true if trivially dead stmts can be removed. - /* Determine what needs to be done to update the SSA form. */ - update_stmt (stmt); - if (!is_gimple_debug (stmt)) - something_changed = true; - } + If DO_DCE is true, the statements within a BB are walked from + last to first element. Otherwise we scan from first to last element. - if (dump_file && (dump_flags & TDF_DETAILS)) - { - if (did_replace) - { - fprintf (dump_file, "Folded into: "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - fprintf (dump_file, "\n"); - } - else - fprintf (dump_file, "Not folded\n"); - } + Return TRUE when something changed. */ + +bool +substitute_and_fold (ssa_prop_get_value_fn get_value_fn, + ssa_prop_fold_stmt_fn fold_fn, + bool do_dce) +{ + gcc_assert (get_value_fn); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nSubstituting values and folding statements\n\n"); + + memset (&prop_stats, 0, sizeof (prop_stats)); + + calculate_dominance_info (CDI_DOMINATORS); + substitute_and_fold_dom_walker walker(CDI_DOMINATORS, + get_value_fn, fold_fn, do_dce); + walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + + /* We cannot remove stmts during the BB walk, especially not release + SSA names there as that destroys the lattice of our callers. + Remove stmts in reverse order to make debug stmt creation possible. */ + while (!walker.stmts_to_remove.is_empty ()) + { + gimple stmt = walker.stmts_to_remove.pop (); + if (dump_file && dump_flags & TDF_DETAILS) + { + fprintf (dump_file, "Removing dead stmt "); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, "\n"); + } + prop_stats.num_dce++; + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + if (gimple_code (stmt) == GIMPLE_PHI) + remove_phi_node (&gsi, true); + else + { + unlink_stmt_vdef (stmt); + gsi_remove (&gsi, true); + release_defs (stmt); } } @@ -1247,7 +1241,8 @@ substitute_and_fold (ssa_prop_get_value_fn get_value_fn, prop_stats.num_stmts_folded); statistics_counter_event (cfun, "Statements deleted", prop_stats.num_dce); - return something_changed; + + return walker.something_changed; } |