diff options
author | Richard Guenther <rguenther@suse.de> | 2010-05-06 09:04:00 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2010-05-06 09:04:00 +0000 |
commit | e3bdfed62abe1c163b93162e53a377b21b5658dc (patch) | |
tree | 06f32bf636037d2caf5f7c51678ee35c661cafa5 | |
parent | a81b065a47a134e66937060f7ae14f1ae939b7b5 (diff) | |
download | gcc-e3bdfed62abe1c163b93162e53a377b21b5658dc.zip gcc-e3bdfed62abe1c163b93162e53a377b21b5658dc.tar.gz gcc-e3bdfed62abe1c163b93162e53a377b21b5658dc.tar.bz2 |
re PR tree-optimization/43934 (LIM should handle PHI nodes)
2010-05-06 Richard Guenther <rguenther@suse.de>
PR tree-optimization/43934
* tree-ssa-loop-im.c (movement_possibility): Handle PHI nodes.
(stmt_cost): Likewise.
(extract_true_false_args_from_phi): New helper.
(determine_max_movement): For PHI nodes verify we can hoist them
and compute their cost.
(determine_invariantness_stmt): Handle PHI nodes.
(move_computations_stmt): Likewise. Hoist PHI nodes in
if-converted form using COND_EXPRs.
(move_computations): Return TODO_cleanup_cfg if we hoisted PHI
nodes.
(tree_ssa_lim): Likewise.
* tree-flow.h (tree_ssa_lim): Adjust prototype.
* tree-ssa-loop.c (tree_ssa_loop_im): Return todo.
* gcc.dg/tree-ssa/ssa-lim-9.c: New testcase.
From-SVN: r159099
-rw-r--r-- | gcc/ChangeLog | 17 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 15 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-9.c | 20 | ||||
-rw-r--r-- | gcc/tree-flow.h | 2 | ||||
-rw-r--r-- | gcc/tree-ssa-loop-im.c | 258 | ||||
-rw-r--r-- | gcc/tree-ssa-loop.c | 3 |
6 files changed, 304 insertions, 11 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 4d0c54a..5051ece 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,22 @@ 2010-05-06 Richard Guenther <rguenther@suse.de> + PR tree-optimization/43934 + * tree-ssa-loop-im.c (movement_possibility): Handle PHI nodes. + (stmt_cost): Likewise. + (extract_true_false_args_from_phi): New helper. + (determine_max_movement): For PHI nodes verify we can hoist them + and compute their cost. + (determine_invariantness_stmt): Handle PHI nodes. + (move_computations_stmt): Likewise. Hoist PHI nodes in + if-converted form using COND_EXPRs. + (move_computations): Return TODO_cleanup_cfg if we hoisted PHI + nodes. + (tree_ssa_lim): Likewise. + * tree-flow.h (tree_ssa_lim): Adjust prototype. + * tree-ssa-loop.c (tree_ssa_loop_im): Return todo. + +2010-05-06 Richard Guenther <rguenther@suse.de> + PR tree-optimization/43987 * tree-ssa-structalias.c (could_have_pointers): For possibly address-taken variables force pointers to be recorded. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 36eea3d..2eebcf3 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,18 @@ +2010-05-06 Richard Guenther <rguenther@suse.de> + + PR tree-optimization/43934 + * gcc.dg/tree-ssa/ssa-lim-9.c: New testcase. + +2010-05-06 Richard Guenther <rguenther@suse.de> + + PR tree-optimization/43987 + * gcc.c-torture/execute/pr43987.c: New testcase. + * gcc.dg/torture/pta-escape-1.c: Adjust. + * gcc.dg/tree-ssa/pta-escape-1.c: Likewise. + * gcc.dg/tree-ssa/pta-escape-2.c: Likewise. + * gcc.dg/tree-ssa/pta-escape-3.c: Likewise. + * gcc.dg/ipa/ipa-pta-11.c: Likewise. + 2010-04-22 Jakub Jelinek <jakub@redhat.com> Dodji Seketeli <dodji@redhat.com> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-9.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-9.c new file mode 100644 index 0000000..c5a6765 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-9.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-lim1-details" } */ + +void bar (int); +void foo (int n, int m) +{ + unsigned i; + for (i = 0; i < n; ++i) + { + int x; + if (m < 0) + x = 1+n; + else + x = m-n; + bar (x); + } +} + +/* { dg-final { scan-tree-dump-times "Moving PHI node" 1 "lim1" } } */ +/* { dg-final { cleanup-tree-dump "lim1" } } */ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 465cf2e..67fb70f 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -685,7 +685,7 @@ basic_block *blocks_in_phiopt_order (void); /* In tree-ssa-loop*.c */ -void tree_ssa_lim (void); +unsigned int tree_ssa_lim (void); unsigned int tree_ssa_unswitch_loops (void); unsigned int canonicalize_induction_variables (void); unsigned int tree_unroll_loops_completely (bool, bool); diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 90b3a38..51d9e93 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -359,6 +359,12 @@ movement_possibility (gimple stmt) return MOVE_POSSIBLE; } + if (gimple_code (stmt) == GIMPLE_PHI + && gimple_phi_num_args (stmt) <= 2 + && is_gimple_reg (gimple_phi_result (stmt)) + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt))) + return MOVE_POSSIBLE; + if (gimple_get_lhs (stmt) == NULL_TREE) return MOVE_IMPOSSIBLE; @@ -513,7 +519,8 @@ stmt_cost (gimple stmt) unsigned cost = 1; /* Always try to create possibilities for unswitching. */ - if (gimple_code (stmt) == GIMPLE_COND) + if (gimple_code (stmt) == GIMPLE_COND + || gimple_code (stmt) == GIMPLE_PHI) return LIM_EXPENSIVE; /* Hoisting memory references out should almost surely be a win. */ @@ -651,6 +658,63 @@ mem_ref_in_stmt (gimple stmt) return ref; } +/* From a controlling predicate in DOM determine the arguments from + the PHI node PHI that are chosen if the predicate evaluates to + true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if + they are non-NULL. Returns true if the arguments can be determined, + else return false. */ + +static bool +extract_true_false_args_from_phi (basic_block dom, gimple phi, + tree *true_arg_p, tree *false_arg_p) +{ + basic_block bb = gimple_bb (phi); + edge true_edge, false_edge, tem; + tree arg0 = NULL_TREE, arg1 = NULL_TREE; + + /* We have to verify that one edge into the PHI node is dominated + by the true edge of the predicate block and the other edge + dominated by the false edge. This ensures that the PHI argument + we are going to take is completely determined by the path we + take from the predicate block. */ + extract_true_false_edges_from_block (dom, &true_edge, &false_edge); + tem = EDGE_PRED (bb, 0); + if (tem == true_edge + || tem->src == true_edge->dest + || dominated_by_p (CDI_DOMINATORS, + tem->src, true_edge->dest)) + arg0 = PHI_ARG_DEF (phi, tem->dest_idx); + else if (tem == false_edge + || tem->src == false_edge->dest + || dominated_by_p (CDI_DOMINATORS, + tem->src, false_edge->dest)) + arg1 = PHI_ARG_DEF (phi, tem->dest_idx); + else + return false; + tem = EDGE_PRED (bb, 1); + if (tem == true_edge + || tem->src == true_edge->dest + || dominated_by_p (CDI_DOMINATORS, + tem->src, true_edge->dest)) + arg0 = PHI_ARG_DEF (phi, tem->dest_idx); + else if (tem == false_edge + || tem->src == false_edge->dest + || dominated_by_p (CDI_DOMINATORS, + tem->src, false_edge->dest)) + arg1 = PHI_ARG_DEF (phi, tem->dest_idx); + else + return false; + if (!arg0 || !arg1) + return false; + + if (true_arg_p) + *true_arg_p = arg0; + if (false_arg_p) + *false_arg_p = arg1; + + return true; +} + /* Determine the outermost loop to that it is possible to hoist a statement STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine the outermost loop in that the value computed by STMT is invariant. @@ -677,9 +741,81 @@ determine_max_movement (gimple stmt, bool must_preserve_exec) level = superloop_at_depth (loop, 1); lim_data->max_loop = level; - FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE) - if (!add_dependency (val, lim_data, loop, true)) - return false; + if (gimple_code (stmt) == GIMPLE_PHI) + { + use_operand_p use_p; + unsigned min_cost = UINT_MAX; + unsigned total_cost = 0; + struct lim_aux_data *def_data; + + /* We will end up promoting dependencies to be unconditionally + evaluated. For this reason the PHI cost (and thus the + cost we remove from the loop by doing the invariant motion) + is that of the cheapest PHI argument dependency chain. */ + FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE) + { + val = USE_FROM_PTR (use_p); + if (TREE_CODE (val) != SSA_NAME) + continue; + if (!add_dependency (val, lim_data, loop, false)) + return false; + def_data = get_lim_data (SSA_NAME_DEF_STMT (val)); + if (def_data) + { + min_cost = MIN (min_cost, def_data->cost); + total_cost += def_data->cost; + } + } + + lim_data->cost += min_cost; + + if (gimple_phi_num_args (stmt) > 1) + { + basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb); + gimple cond; + if (gsi_end_p (gsi_last_bb (dom))) + return false; + cond = gsi_stmt (gsi_last_bb (dom)); + if (gimple_code (cond) != GIMPLE_COND) + return false; + /* Verify that this is an extended form of a diamond and + the PHI arguments are completely controlled by the + predicate in DOM. */ + if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL)) + return false; + + /* Fold in dependencies and cost of the condition. */ + FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE) + { + if (!add_dependency (val, lim_data, loop, false)) + return false; + def_data = get_lim_data (SSA_NAME_DEF_STMT (val)); + if (def_data) + total_cost += def_data->cost; + } + + /* We want to avoid unconditionally executing very expensive + operations. As costs for our dependencies cannot be + negative just claim we are not invariand for this case. + We also are not sure whether the control-flow inside the + loop will vanish. */ + if (total_cost - min_cost >= 2 * LIM_EXPENSIVE + && !(min_cost != 0 + && total_cost / min_cost <= 2)) + return false; + + /* Assume that the control-flow in the loop will vanish. + ??? We should verify this and not artificially increase + the cost if that is not the case. */ + lim_data->cost += stmt_cost (stmt); + } + + return true; + } + else + FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE) + if (!add_dependency (val, lim_data, loop, true)) + return false; if (gimple_vuse (stmt)) { @@ -920,6 +1056,43 @@ determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n", bb->index, bb->loop_father->num, loop_depth (bb->loop_father)); + /* Look at PHI nodes, but only if there is at most two. + ??? We could relax this further by post-processing the inserted + code and transforming adjacent cond-exprs with the same predicate + to control flow again. */ + bsi = gsi_start_phis (bb); + if (!gsi_end_p (bsi) + && ((gsi_next (&bsi), gsi_end_p (bsi)) + || (gsi_next (&bsi), gsi_end_p (bsi)))) + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + stmt = gsi_stmt (bsi); + + pos = movement_possibility (stmt); + if (pos == MOVE_IMPOSSIBLE) + continue; + + lim_data = init_lim_data (stmt); + lim_data->always_executed_in = outermost; + + if (!determine_max_movement (stmt, false)) + { + lim_data->max_loop = NULL; + continue; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + print_gimple_stmt (dump_file, stmt, 2, 0); + fprintf (dump_file, " invariant up to level %d, cost %d.\n\n", + loop_depth (lim_data->max_loop), + lim_data->cost); + } + + if (lim_data->cost >= LIM_EXPENSIVE) + set_profitable_level (stmt); + } + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { stmt = gsi_stmt (bsi); @@ -1021,7 +1194,7 @@ determine_invariantness (void) for walk_dominator_tree. */ static void -move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, +move_computations_stmt (struct dom_walk_data *dw_data, basic_block bb) { struct loop *level; @@ -1033,6 +1206,67 @@ move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, if (!loop_outer (bb->loop_father)) return; + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); ) + { + gimple new_stmt; + stmt = gsi_stmt (bsi); + + lim_data = get_lim_data (stmt); + if (lim_data == NULL) + { + gsi_next (&bsi); + continue; + } + + cost = lim_data->cost; + level = lim_data->tgt_loop; + clear_lim_data (stmt); + + if (!level) + { + gsi_next (&bsi); + continue; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Moving PHI node\n"); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, "(cost %u) out of loop %d.\n\n", + cost, level->num); + } + + if (gimple_phi_num_args (stmt) == 1) + { + tree arg = PHI_ARG_DEF (stmt, 0); + new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg), + gimple_phi_result (stmt), + arg, NULL_TREE); + SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt; + } + else + { + basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb); + gimple cond = gsi_stmt (gsi_last_bb (dom)); + tree arg0 = NULL_TREE, arg1 = NULL_TREE, t; + /* Get the PHI arguments corresponding to the true and false + edges of COND. */ + extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1); + gcc_assert (arg0 && arg1); + t = build2 (gimple_cond_code (cond), boolean_type_node, + gimple_cond_lhs (cond), gimple_cond_rhs (cond)); + t = build3 (COND_EXPR, TREE_TYPE (gimple_phi_result (stmt)), + t, arg0, arg1); + new_stmt = gimple_build_assign_with_ops (COND_EXPR, + gimple_phi_result (stmt), + t, NULL_TREE); + SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt; + *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg; + } + gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); + remove_phi_node (&bsi, false); + } + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); ) { stmt = gsi_stmt (bsi); @@ -1076,12 +1310,14 @@ move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, /* Hoist the statements out of the loops prescribed by data stored in LIM_DATA structures associated with each statement.*/ -static void +static unsigned int move_computations (void) { struct dom_walk_data walk_data; + unsigned int todo = 0; memset (&walk_data, 0, sizeof (struct dom_walk_data)); + walk_data.global_data = &todo; walk_data.dom_direction = CDI_DOMINATORS; walk_data.before_dom_children = move_computations_stmt; @@ -1092,6 +1328,8 @@ move_computations (void) gsi_commit_edge_inserts (); if (need_ssa_update_p (cfun)) rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); + + return todo; } /* Checks whether the statement defining variable *INDEX can be hoisted @@ -2328,9 +2566,11 @@ tree_ssa_lim_finalize (void) /* Moves invariants from loops. Only "expensive" invariants are moved out -- i.e. those that are likely to be win regardless of the register pressure. */ -void +unsigned int tree_ssa_lim (void) { + unsigned int todo; + tree_ssa_lim_initialize (); /* Gathers information about memory accesses in the loops. */ @@ -2345,7 +2585,9 @@ tree_ssa_lim (void) store_motion (); /* Move the expressions that are expensive enough. */ - move_computations (); + todo = move_computations (); tree_ssa_lim_finalize (); + + return todo; } diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index fbf8d59..d1b1e8e 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -109,8 +109,7 @@ tree_ssa_loop_im (void) if (number_of_loops () <= 1) return 0; - tree_ssa_lim (); - return 0; + return tree_ssa_lim (); } static bool |