* [PATCH 00/12] [graphite] Remove the induction variable canonicalization
@ 2010-07-16 7:04 Sebastian Pop
2010-07-16 7:04 ` [PATCH 07/12] Scevs could be expressions without chrecs and still be scev_analyzable_p Sebastian Pop
` (11 more replies)
0 siblings, 12 replies; 15+ messages in thread
From: Sebastian Pop @ 2010-07-16 7:04 UTC (permalink / raw)
To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop
In order to improve the vectorization of loops transformed by
Graphite, the following set of patches clean up the Graphite
infrastructure to avoid the canonicalization of induction variables.
The process of IV canonicalization introduces a single IV with a type
that has to be unsigned in order to be able to represent all the IVs
with the canonical one that starts at 0 and is incremented by strides
of 1. In several cases, the unsigned type of the canonical IV makes
the analysis of scalar evolutions impossible, as the cast to unsigned
cannot be removed, transforming most of the scev results into a
"chrec_dont_know".
I committed this patch-set to the Graphite branch for further testing.
Sebastian Pop (12):
Remove insert_loop_close_phis.
Remove expand_scalar_variables_ hack.
chrec_apply should only apply to the specified variable.
Also handle GIMPLE_CALLs in rewrite_cross_bb_scalar_deps.
Remove uses of loop->single_iv.
Bump the size of scevs.
Scevs could be expressions without chrecs and still be
scev_analyzable_p.
Special case non close-phi nodes with one argument in
rewrite_close_phi_out_of_ssa.
Add testcase for PR42729 and fix handling of gimple_debug info.
Correctly handle SSA_NAME_IS_DEFAULT_DEF in
rewrite_close_phi_out_of_ssa.
Do not rewrite out of SSA scalar phi nodes that can be
scev_analyzable_p.
Unshare the scev before code generating it.
gcc/ChangeLog.graphite | 125 ++++-
gcc/cfgloop.c | 1 -
gcc/cfgloop.h | 4 -
gcc/graphite-clast-to-gimple.c | 133 ++---
gcc/graphite-clast-to-gimple.h | 1 -
gcc/graphite-sese-to-poly.c | 140 ++---
gcc/params.def | 2 +-
gcc/sese.c | 843 ++++------------------------
gcc/sese.h | 20 +-
gcc/testsuite/gcc.dg/graphite/id-23.c | 22 +
gcc/testsuite/gcc.dg/graphite/pr42729.c | 15 +
gcc/testsuite/gfortran.dg/graphite/id-20.f | 12 +-
gcc/tree-chrec.c | 62 ++-
gcc/tree-chrec.h | 1 +
14 files changed, 447 insertions(+), 934 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/graphite/id-23.c
create mode 100644 gcc/testsuite/gcc.dg/graphite/pr42729.c
^ permalink raw reply [flat|nested] 15+ messages in thread* [PATCH 07/12] Scevs could be expressions without chrecs and still be scev_analyzable_p. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop @ 2010-07-16 7:04 ` Sebastian Pop 2010-07-16 7:04 ` [PATCH 03/12] chrec_apply should only apply to the specified variable Sebastian Pop ` (10 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:04 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * sese.h (scev_analyzable_p): Scevs could be expressions without chrecs and still be scev_analyzable_p. --- gcc/ChangeLog.graphite | 5 +++++ gcc/sese.h | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index d75912c..bbd6a34 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,10 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * sese.h (scev_analyzable_p): Scevs could be expressions without + chrecs and still be scev_analyzable_p. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> diff --git a/gcc/sese.h b/gcc/sese.h index 1502cbe..f10030c 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -398,7 +398,8 @@ scev_analyzable_p (tree def, sese region) return !chrec_contains_undetermined (scev) && TREE_CODE (scev) != SSA_NAME - && evolution_function_is_affine_p (scev); + && (tree_does_not_contain_chrecs (scev) + || evolution_function_is_affine_p (scev)); } #endif -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 03/12] chrec_apply should only apply to the specified variable. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop 2010-07-16 7:04 ` [PATCH 07/12] Scevs could be expressions without chrecs and still be scev_analyzable_p Sebastian Pop @ 2010-07-16 7:04 ` Sebastian Pop 2010-07-16 7:04 ` [PATCH 09/12] Add testcase for PR42729 and fix handling of gimple_debug info Sebastian Pop ` (9 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:04 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * tree-chrec.c (chrec_apply): Should only apply to the specified variable. Also handle multivariate chains of recurrences that satisfy evolution_function_is_affine_p. Also handle CASE_CONVERT. --- gcc/ChangeLog.graphite | 6 ++++++ gcc/tree-chrec.c | 45 +++++++++++++++++++++++++++++++-------------- 2 files changed, 37 insertions(+), 14 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 7498956..e6daa32 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,11 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * tree-chrec.c (chrec_apply): Should only apply to the specified + variable. Also handle multivariate chains of recurrences that + satisfy evolution_function_is_affine_p. Also handle CASE_CONVERT. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-clast-to-gimple.c (debug_clast_name_index): Removed. (debug_clast_name_indexes_1): Removed. (debug_clast_name_indexes): Removed. diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index c92b6b9..92f8de9 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -599,23 +599,40 @@ chrec_apply (unsigned var, if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) x = build_real_from_int_cst (type, x); - if (evolution_function_is_affine_p (chrec)) + switch (TREE_CODE (chrec)) { - /* "{a, +, b} (x)" -> "a + b*x". */ - x = chrec_convert_rhs (type, x, NULL); - res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x); - res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); - } + case POLYNOMIAL_CHREC: + if (evolution_function_is_affine_p (chrec)) + { + if (CHREC_VARIABLE (chrec) != var) + return build_polynomial_chrec + (CHREC_VARIABLE (chrec), + chrec_apply (var, CHREC_LEFT (chrec), x), + chrec_apply (var, CHREC_RIGHT (chrec), x)); + + /* "{a, +, b} (x)" -> "a + b*x". */ + x = chrec_convert_rhs (type, x, NULL); + res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x); + res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); + } + else if (TREE_CODE (x) == INTEGER_CST + && tree_int_cst_sgn (x) == 1) + /* testsuite/.../ssa-chrec-38.c. */ + res = chrec_evaluate (var, chrec, x, 0); + else + res = chrec_dont_know; + break; - else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) - res = chrec; + CASE_CONVERT: + res = chrec_convert (TREE_TYPE (chrec), + chrec_apply (var, TREE_OPERAND (chrec, 0), x), + NULL); + break; - else if (TREE_CODE (x) == INTEGER_CST - && tree_int_cst_sgn (x) == 1) - /* testsuite/.../ssa-chrec-38.c. */ - res = chrec_evaluate (var, chrec, x, 0); - else - res = chrec_dont_know; + default: + res = chrec; + break; + } if (dump_file && (dump_flags & TDF_DETAILS)) { -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 09/12] Add testcase for PR42729 and fix handling of gimple_debug info. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop 2010-07-16 7:04 ` [PATCH 07/12] Scevs could be expressions without chrecs and still be scev_analyzable_p Sebastian Pop 2010-07-16 7:04 ` [PATCH 03/12] chrec_apply should only apply to the specified variable Sebastian Pop @ 2010-07-16 7:04 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 01/12] Remove insert_loop_close_phis Sebastian Pop ` (8 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:04 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * sese.c (rename_uses): Handl unconditionally gimple_debug statements. * gcc.dg/graphite/pr42729.c: New. --- gcc/ChangeLog.graphite | 6 ++++++ gcc/sese.c | 24 +++++++++++------------- gcc/testsuite/gcc.dg/graphite/pr42729.c | 15 +++++++++++++++ 3 files changed, 32 insertions(+), 13 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/pr42729.c diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 40db483..f57ef7d 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,11 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * sese.c (rename_uses): Handl unconditionally gimple_debug statements. + + * gcc.dg/graphite/pr42729.c: New. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Special case non close-phi nodes with one argument. diff --git a/gcc/sese.c b/gcc/sese.c index 913ac4d..f59f317 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -480,6 +480,16 @@ rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, use_operand_p use_p; ssa_op_iter op_iter; + if (is_gimple_debug (copy)) + { + if (gimple_debug_bind_p (copy)) + gimple_debug_bind_reset_value (copy); + else + gcc_unreachable (); + + return; + } + FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES) { tree old_name = USE_FROM_PTR (use_p); @@ -501,19 +511,7 @@ rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, || (TREE_CODE (new_expr) != SSA_NAME && is_gimple_reg (old_name))) { - tree var; - - if (is_gimple_debug (copy)) - { - if (gimple_debug_bind_p (copy)) - gimple_debug_bind_reset_value (copy); - else - gcc_unreachable (); - - break; - } - - var = create_tmp_var (type_old_name, "var"); + tree var = create_tmp_var (type_old_name, "var"); if (type_old_name != type_new_expr) new_expr = fold_convert (type_old_name, new_expr); diff --git a/gcc/testsuite/gcc.dg/graphite/pr42729.c b/gcc/testsuite/gcc.dg/graphite/pr42729.c new file mode 100644 index 0000000..3a0e901 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr42729.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fgraphite-identity -fcompare-debug" } */ + +int A[10]; +int *foo () +{ + int *p1, *p2, i; + for (i = 0; i < 10; i++) + { + p1 = &A[i]; + *p1 = 0; + } + p2 = p1; + return p2; +} -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 01/12] Remove insert_loop_close_phis. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (2 preceding siblings ...) 2010-07-16 7:04 ` [PATCH 09/12] Add testcase for PR42729 and fix handling of gimple_debug info Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 06/12] Bump the size of scevs Sebastian Pop ` (7 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-clast-to-gimple.c (translate_clast_for_loop): Do not call insert_loop_close_phis. * sese.c (name_defined_in_loop_p): Removed. (expr_defined_in_loop_p): Removed. (alive_after_loop): Removed. (close_phi_not_yet_inserted_p): Removed. (struct alep): Removed. (add_loop_exit_phis): Removed. (insert_loop_close_phis): Removed. --- gcc/ChangeLog.graphite | 19 ++++- gcc/graphite-clast-to-gimple.c | 4 - gcc/sese.c | 167 ---------------------------------------- 3 files changed, 15 insertions(+), 175 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 6d915a7..3774b46 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,9 +1,20 @@ +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + + * graphite-clast-to-gimple.c (translate_clast_for_loop): Do not call + insert_loop_close_phis. + * sese.c (name_defined_in_loop_p): Removed. + (expr_defined_in_loop_p): Removed. + (alive_after_loop): Removed. + (close_phi_not_yet_inserted_p): Removed. + (struct alep): Removed. + (add_loop_exit_phis): Removed. + (insert_loop_close_phis): Removed. + 2010-07-15 Andreas Simbuerger <simbuerg@fim.uni-passau.de> - * graphite-cloog-util.c - (cloog_matrix_to_ppl_constraint): Fix flipped condition. - * graphite-poly.c - (psct_scattering_dim_for_loop_depth): Same. + * graphite-cloog-util.c (cloog_matrix_to_ppl_constraint): Fix flipped + condition. + * graphite-poly.c (psct_scattering_dim_for_loop_depth): Same. 2010-07-07 Sebastian Pop <sebastian.pop@amd.com> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c index d12f177..042857f 100644 --- a/gcc/graphite-clast-to-gimple.c +++ b/gcc/graphite-clast-to-gimple.c @@ -1046,10 +1046,6 @@ translate_clast_for_loop (sese region, loop_p context_loop, redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); - /* Remove from rename_map all the tuples containing variables - defined in loop's body. */ - insert_loop_close_phis (rename_map, loop); - if (flag_loop_parallelize_all && !dependency_in_loop_p (loop, bb_pbb_mapping, get_scattering_level (level))) diff --git a/gcc/sese.c b/gcc/sese.c index 6883073..e0c06da 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -888,173 +888,6 @@ get_false_edge_from_guard_bb (basic_block bb) return NULL; } -/* Returns true when NAME is defined in LOOP. */ - -static bool -name_defined_in_loop_p (tree name, loop_p loop) -{ - return !SSA_NAME_IS_DEFAULT_DEF (name) - && gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop; -} - -/* Returns true when EXPR contains SSA_NAMEs defined in LOOP. */ - -static bool -expr_defined_in_loop_p (tree expr, loop_p loop) -{ - switch (TREE_CODE_LENGTH (TREE_CODE (expr))) - { - case 3: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop); - - case 2: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop) - || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop); - - case 1: - return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop); - - case 0: - return TREE_CODE (expr) == SSA_NAME - && name_defined_in_loop_p (expr, loop); - - default: - return false; - } -} - -/* Returns the gimple statement that uses NAME outside the loop it is - defined in, returns NULL if there is no such loop close phi node. - An invariant of the loop closed SSA form is that the only use of a - variable, outside the loop it is defined in, is in the loop close - phi node that just follows the loop. */ - -static gimple -alive_after_loop (tree name) -{ - use_operand_p use_p; - imm_use_iterator imm_iter; - loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father; - - FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name) - { - gimple stmt = USE_STMT (use_p); - - if (gimple_code (stmt) == GIMPLE_PHI - && gimple_bb (stmt)->loop_father != loop) - return stmt; - } - - return NULL; -} - -/* Return true if a close phi has not yet been inserted for the use of - variable NAME on the single exit of LOOP. */ - -static bool -close_phi_not_yet_inserted_p (loop_p loop, tree name) -{ - gimple_stmt_iterator psi; - basic_block bb = single_exit (loop)->dest; - - for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) - if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name) - return false; - - return true; -} - -/* A structure for passing parameters to add_loop_exit_phis. */ - -typedef struct alep { - loop_p loop; - VEC (rename_map_elt, heap) *new_renames; -} *alep_p; - -/* Helper function for htab_traverse in insert_loop_close_phis. */ - -static int -add_loop_exit_phis (void **slot, void *data) -{ - struct rename_map_elt_s *entry; - alep_p a; - loop_p loop; - tree expr, new_name, old_name; - bool def_in_loop_p, used_outside_p, need_close_phi_p; - gimple old_close_phi; - - if (!slot || !*slot || !data) - return 1; - - entry = (struct rename_map_elt_s *) *slot; - a = (alep_p) data; - loop = a->loop; - new_name = expr = entry->expr; - old_name = entry->old_name; - - def_in_loop_p = expr_defined_in_loop_p (expr, loop); - if (!def_in_loop_p) - return 1; - - /* Remove the old rename from the map when the expression is defined - in the loop that we're closing. */ - free (*slot); - *slot = NULL; - - if (TREE_CODE (expr) != SSA_NAME) - return 1; - - old_close_phi = alive_after_loop (old_name); - used_outside_p = (old_close_phi != NULL); - need_close_phi_p = (used_outside_p - && close_phi_not_yet_inserted_p (loop, new_name)); - - /* Insert a loop close phi node. */ - if (need_close_phi_p) - { - basic_block bb = single_exit (loop)->dest; - gimple phi = create_phi_node (new_name, bb); - tree new_res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION); - VEC_safe_push (rename_map_elt, heap, a->new_renames, - new_rename_map_elt (gimple_phi_result (old_close_phi), - new_res)); - } - - return 1; -} - -/* Traverses MAP and removes from it all the tuples (OLD, NEW) where - NEW is defined in LOOP. Inserts on the exit of LOOP the close phi - node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in - the original code. Inserts in MAP the tuple (OLD_RES, RES). */ - -void -insert_loop_close_phis (htab_t map, loop_p loop) -{ - int i; - struct alep a; - rename_map_elt elt; - - a.loop = loop; - a.new_renames = VEC_alloc (rename_map_elt, heap, 3); - update_ssa (TODO_update_ssa); - htab_traverse (map, add_loop_exit_phis, &a); - update_ssa (TODO_update_ssa); - - for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++) - { - set_rename (map, elt->old_name, elt->expr); - free (elt); - } - - VEC_free (rename_map_elt, heap, a.new_renames); -} - /* Helper structure for htab_traverse in insert_guard_phis. */ struct igp { -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 06/12] Bump the size of scevs. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (3 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 01/12] Remove insert_loop_close_phis Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 8:03 ` Richard Guenther 2010-07-16 7:05 ` [PATCH 10/12] Correctly handle SSA_NAME_IS_DEFAULT_DEF in rewrite_close_phi_out_of_ssa Sebastian Pop ` (6 subsequent siblings) 11 siblings, 1 reply; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. --- gcc/ChangeLog.graphite | 4 ++++ gcc/params.def | 2 +- 2 files changed, 5 insertions(+), 1 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 8408cf2..d75912c 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,9 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * cfgloop.c (alloc_loop): Remove initialization of loop->single_iv. * cfgloop.h (struct loop): Remove single_iv field. * graphite-sese-to-poly.c (graphite_loop_normal_form): Removed. diff --git a/gcc/params.def b/gcc/params.def index 35650ff..5a91e74 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -438,7 +438,7 @@ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND, DEFPARAM(PARAM_SCEV_MAX_EXPR_SIZE, "scev-max-expr-size", "Bound on size of expressions used in the scalar evolutions analyzer", - 20, 0, 0) + 100, 0, 0) DEFPARAM(PARAM_OMEGA_MAX_VARS, "omega-max-vars", -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 06/12] Bump the size of scevs. 2010-07-16 7:05 ` [PATCH 06/12] Bump the size of scevs Sebastian Pop @ 2010-07-16 8:03 ` Richard Guenther 2010-07-16 14:41 ` Sebastian Pop 0 siblings, 1 reply; 15+ messages in thread From: Richard Guenther @ 2010-07-16 8:03 UTC (permalink / raw) To: Sebastian Pop; +Cc: gcc-patches, gcc-graphite On Fri, Jul 16, 2010 at 9:03 AM, Sebastian Pop <sebpop@gmail.com> wrote: > 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> > > * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. What's the effect on compile-time here? Richard. > --- > gcc/ChangeLog.graphite | 4 ++++ > gcc/params.def | 2 +- > 2 files changed, 5 insertions(+), 1 deletions(-) > > diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite > index 8408cf2..d75912c 100644 > --- a/gcc/ChangeLog.graphite > +++ b/gcc/ChangeLog.graphite > @@ -1,5 +1,9 @@ > 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> > > + * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. > + > +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> > + > * cfgloop.c (alloc_loop): Remove initialization of loop->single_iv. > * cfgloop.h (struct loop): Remove single_iv field. > * graphite-sese-to-poly.c (graphite_loop_normal_form): Removed. > diff --git a/gcc/params.def b/gcc/params.def > index 35650ff..5a91e74 100644 > --- a/gcc/params.def > +++ b/gcc/params.def > @@ -438,7 +438,7 @@ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND, > DEFPARAM(PARAM_SCEV_MAX_EXPR_SIZE, > "scev-max-expr-size", > "Bound on size of expressions used in the scalar evolutions analyzer", > - 20, 0, 0) > + 100, 0, 0) > > DEFPARAM(PARAM_OMEGA_MAX_VARS, > "omega-max-vars", > -- > 1.7.0.4 > > ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH 06/12] Bump the size of scevs. 2010-07-16 8:03 ` Richard Guenther @ 2010-07-16 14:41 ` Sebastian Pop 0 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 14:41 UTC (permalink / raw) To: Richard Guenther; +Cc: gcc-patches, gcc-graphite On Fri, Jul 16, 2010 at 03:03, Richard Guenther <richard.guenther@gmail.com> wrote: > On Fri, Jul 16, 2010 at 9:03 AM, Sebastian Pop <sebpop@gmail.com> wrote: >> 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> >> >> * params.def (PARAM_SCEV_MAX_EXPR_SIZE): Bump the value to 100. > > What's the effect on compile-time here? PARAM_SCEV_MAX_EXPR_SIZE was introduced to solve http://gcc.gnu.org/PR20742 I see that we never committed the testcase for that PR. With a slightly modified testcase: /* { dg-do compile } */ /* { dg-options "-O2" } */ #define TEN(x) x x x x x x x x x x #define THOUSAND(x) TEN (TEN (TEN (x))) int foo (int x, int y) { register int a = y + 57; register int b = y + 31; while (x-- > 0) { TEN (THOUSAND (a += b; b -= a;)) } return a + b; } I am seeing this with the Graphite branch (passes taking more than a second): tree SSA verifier : 1.92 (16%) usr 0.00 ( 0%) sys 1.96 (16%) wall 0 kB ( 0%) ggc tree STMT verifier : 4.17 (35%) usr 0.04 (25%) sys 4.26 (35%) wall 0 kB ( 0%) ggc combiner : 1.15 (10%) usr 0.00 ( 0%) sys 1.17 ( 9%) wall 5664 kB (10%) ggc TOTAL : 11.96 0.16 12.32 58997 kB These passes are not using the scev analysis. Without the patch I am seeing the exact same thing: tree SSA verifier : 1.86 (15%) usr 0.01 ( 4%) sys 1.93 (15%) wall 0 kB ( 0%) ggc tree STMT verifier : 4.12 (34%) usr 0.09 (36%) sys 4.23 (33%) wall 0 kB ( 0%) ggc combiner : 1.17 (10%) usr 0.00 ( 0%) sys 1.19 ( 9%) wall 5664 kB ( 9%) ggc TOTAL : 12.25 0.25 12.64 61271 kB I will probably add a testcase with a THOUSAND operations to the tree-ssa testsuite. Sebastian ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 10/12] Correctly handle SSA_NAME_IS_DEFAULT_DEF in rewrite_close_phi_out_of_ssa. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (4 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 06/12] Bump the size of scevs Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 04/12] Also handle GIMPLE_CALLs in rewrite_cross_bb_scalar_deps Sebastian Pop ` (5 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Correctly handle SSA_NAME_IS_DEFAULT_DEF. --- gcc/ChangeLog.graphite | 5 +++++ gcc/graphite-sese-to-poly.c | 4 ++-- 2 files changed, 7 insertions(+), 2 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index f57ef7d..8230d31 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,10 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Correctly + handle SSA_NAME_IS_DEFAULT_DEF. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * sese.c (rename_uses): Handl unconditionally gimple_debug statements. * gcc.dg/graphite/pr42729.c: New. diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 3d02197..3d903d3 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2215,6 +2215,7 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) /* The phi node can be a non close phi node, when its argument is invariant, or when it is defined in the same loop as the phi node. */ if (is_gimple_min_invariant (arg) + || SSA_NAME_IS_DEFAULT_DEF (arg) || gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father) stmt = gimple_build_assign (res, arg); else @@ -2223,8 +2224,7 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) stmt = gimple_build_assign (res, zero_dim_array); - if (TREE_CODE (arg) == SSA_NAME - && !SSA_NAME_IS_DEFAULT_DEF (arg)) + if (TREE_CODE (arg) == SSA_NAME) insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg)); else insert_out_of_ssa_copy_on_edge (single_pred_edge (bb), -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 04/12] Also handle GIMPLE_CALLs in rewrite_cross_bb_scalar_deps. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (5 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 10/12] Correctly handle SSA_NAME_IS_DEFAULT_DEF in rewrite_close_phi_out_of_ssa Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 02/12] Remove expand_scalar_variables_ hack Sebastian Pop ` (4 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-sese-to-poly.c (rewrite_cross_bb_scalar_deps): Also handle GIMPLE_CALL. --- gcc/ChangeLog.graphite | 5 +++++ gcc/graphite-sese-to-poly.c | 16 +++++++++++++--- 2 files changed, 18 insertions(+), 3 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index e6daa32..a83cc99 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,10 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_cross_bb_scalar_deps): Also + handle GIMPLE_CALL. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * tree-chrec.c (chrec_apply): Should only apply to the specified variable. Also handle multivariate chains of recurrences that satisfy evolution_function_is_affine_p. Also handle CASE_CONVERT. diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 6e09532..22f9536 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2404,10 +2404,20 @@ rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) tree zero_dim_array = NULL_TREE; gimple use_stmt; - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return; + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + def = gimple_assign_lhs (stmt); + break; + + case GIMPLE_CALL: + def = gimple_call_lhs (stmt); + break; + + default: + return; + } - def = gimple_assign_lhs (stmt); if (!is_gimple_reg (def) || scev_analyzable_p (def, region)) return; -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 02/12] Remove expand_scalar_variables_ hack. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (6 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 04/12] Also handle GIMPLE_CALLs in rewrite_cross_bb_scalar_deps Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 05/12] Remove uses of loop->single_iv Sebastian Pop ` (3 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-clast-to-gimple.c (debug_clast_name_index): Removed. (debug_clast_name_indexes_1): Removed. (debug_clast_name_indexes): Removed. (pbb_to_depth_to_oldiv): Removed. (build_iv_mapping): Replace the use of rename_map with iv_map. (translate_clast_user): Remove uses of rename_map. Allocate and free iv_map. (translate_clast_for_loop): Remove uses of rename_map. (translate_clast_for): Same. (translate_clast_guard): Same. (translate_clast): Same. (gloog): Same. * graphite-clast-to-gimple.h (debug_clast_name_indexes): Removed. * graphite-sese-to-poly.c (scev_analyzable_p): Moved... * sese.c (set_rename): Now static. (rename_variables_in_stmt): Removed. (rename_uses): New. (is_parameter): Removed. (is_iv): Removed. (expand_scalar_variables_call): Removed. (expand_scalar_variables_ssa_name): Removed. (expand_scalar_variables_expr): Removed. (expand_scalar_variables_stmt): Removed. (expand_scalar_variables): Removed. (rename_variables): Removed. (remove_condition): Removed. (get_true_edge_from_guard_bb): Removed. (get_false_edge_from_guard_bb): Removed. (struct igp): Removed. (default_before_guard): Removed. (convert_for_phi_arg): Removed. (add_guard_exit_phis): Removed. (insert_guard_phis): Removed. (graphite_copy_stmts_from_block): Now also uses iv_map and a region. Do not copy conditions. Do not copy induction variables. Call rename_uses. (copy_bb_and_scalar_dependences): Allocate a local rename_map for the translated statement. Use the iv_map for the induction variable renaming. * sese.h (copy_bb_and_scalar_dependences): Update declaration. (set_rename): Removed declaration. (scev_analyzable_p): ...here. * tree-chrec.c (chrec_apply_map): New. * tree-chrec.h (chrec_apply_map): Declared. --- gcc/ChangeLog.graphite | 47 +++ gcc/graphite-clast-to-gimple.c | 129 +++----- gcc/graphite-clast-to-gimple.h | 1 - gcc/graphite-sese-to-poly.c | 14 - gcc/sese.c | 675 ++++++++-------------------------------- gcc/sese.h | 19 +- gcc/tree-chrec.c | 17 + gcc/tree-chrec.h | 1 + 8 files changed, 246 insertions(+), 657 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 3774b46..7498956 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,52 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-clast-to-gimple.c (debug_clast_name_index): Removed. + (debug_clast_name_indexes_1): Removed. + (debug_clast_name_indexes): Removed. + (pbb_to_depth_to_oldiv): Removed. + (build_iv_mapping): Replace the use of rename_map with iv_map. + (translate_clast_user): Remove uses of rename_map. Allocate and + free iv_map. + (translate_clast_for_loop): Remove uses of rename_map. + (translate_clast_for): Same. + (translate_clast_guard): Same. + (translate_clast): Same. + (gloog): Same. + * graphite-clast-to-gimple.h (debug_clast_name_indexes): Removed. + * graphite-sese-to-poly.c (scev_analyzable_p): Moved... + * sese.c (set_rename): Now static. + (rename_variables_in_stmt): Removed. + (rename_uses): New. + (is_parameter): Removed. + (is_iv): Removed. + (expand_scalar_variables_call): Removed. + (expand_scalar_variables_ssa_name): Removed. + (expand_scalar_variables_expr): Removed. + (expand_scalar_variables_stmt): Removed. + (expand_scalar_variables): Removed. + (rename_variables): Removed. + (remove_condition): Removed. + (get_true_edge_from_guard_bb): Removed. + (get_false_edge_from_guard_bb): Removed. + (struct igp): Removed. + (default_before_guard): Removed. + (convert_for_phi_arg): Removed. + (add_guard_exit_phis): Removed. + (insert_guard_phis): Removed. + (graphite_copy_stmts_from_block): Now also uses iv_map and a + region. Do not copy conditions. Do not copy induction variables. + Call rename_uses. + (copy_bb_and_scalar_dependences): Allocate a local rename_map for + the translated statement. Use the iv_map for the induction + variable renaming. + * sese.h (copy_bb_and_scalar_dependences): Update declaration. + (set_rename): Removed declaration. + (scev_analyzable_p): ...here. + * tree-chrec.c (chrec_apply_map): New. + * tree-chrec.h (chrec_apply_map): Declared. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-clast-to-gimple.c (translate_clast_for_loop): Do not call insert_loop_close_phis. * sese.c (name_defined_in_loop_p): Removed. diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c index 042857f..4d30daf 100644 --- a/gcc/graphite-clast-to-gimple.c +++ b/gcc/graphite-clast-to-gimple.c @@ -130,32 +130,6 @@ save_clast_name_index (htab_t index_table, const char *name, int index) } } -/* Print to stderr the element ELT. */ - -static inline void -debug_clast_name_index (clast_name_index_p elt) -{ - fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name); -} - -/* Helper function for debug_rename_map. */ - -static inline int -debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED) -{ - struct clast_name_index *entry = (struct clast_name_index *) *slot; - debug_clast_name_index (entry); - return 1; -} - -/* Print to stderr all the elements of MAP. */ - -DEBUG_FUNCTION void -debug_clast_name_indexes (htab_t map) -{ - htab_traverse (map, debug_clast_name_indexes_1, NULL); -} - /* Computes a hash function for database element ELT. */ static inline hashval_t @@ -175,20 +149,6 @@ eq_clast_name_indexes (const void *e1, const void *e2) return (elt1->name == elt2->name); } - -/* For a given loop DEPTH in the loop nest of the original black box - PBB, return the old induction variable associated to that loop. */ - -static inline tree -pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth) -{ - gimple_bb_p gbb = PBB_BLACK_BOX (pbb); - sese region = SCOP_REGION (PBB_SCOP (pbb)); - loop_p loop = gbb_loop_at_index (gbb, region, depth); - - return loop->single_iv; -} - /* For a given scattering dimension, return the new induction variable associated to it. */ @@ -820,34 +780,36 @@ graphite_create_new_loop (sese region, edge entry_edge, return loop; } -/* Inserts in RENAME_MAP a tuple (OLD_NAME, NEW_NAME) for the induction - variables of the loops around GBB in SESE. */ +/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the + induction variables of the loops around GBB in SESE. */ static void -build_iv_mapping (htab_t rename_map, sese region, +build_iv_mapping (VEC (tree, heap) *iv_map, sese region, VEC (tree, heap) *newivs, htab_t newivs_index, struct clast_user_stmt *user_stmt, htab_t params_index) { struct clast_stmt *t; - int index = 0; + int depth = 0; CloogStatement *cs = user_stmt->statement; poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); - for (t = user_stmt->substitutions; t; t = t->next, index++) + for (t = user_stmt->substitutions; t; t = t->next, depth++) { struct clast_expr *expr = (struct clast_expr *) ((struct clast_assignment *)t)->RHS; tree type = gcc_type_for_clast_expr (expr, region, newivs, newivs_index, params_index); - tree old_name = pbb_to_depth_to_oldiv (pbb, index); - tree e = clast_to_gcc_expression (type, expr, region, newivs, - newivs_index, params_index); - set_rename (rename_map, old_name, e); + tree new_name = clast_to_gcc_expression (type, expr, region, newivs, + newivs_index, params_index); + loop_p old_loop = gbb_loop_at_index (gbb, region, depth); + + VEC_replace (tree, iv_map, old_loop->num, new_name); } } -/* Construct bb_pbb_def with BB and PBB. */ +/* Construct bb_pbb_def with BB and PBB. */ static bb_pbb_def * new_bb_pbb_def (basic_block bb, poly_bb_p pbb) @@ -930,38 +892,39 @@ dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level) return false; } -static edge -translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t, - VEC (tree, heap) **, htab_t, htab_t, int, htab_t); - /* Translates a clast user statement STMT to gimple. - REGION is the sese region we used to generate the scop. - NEXT_E is the edge where new generated code should be attached. - CONTEXT_LOOP is the loop in which the generated code will be placed - - RENAME_MAP contains a set of tuples of new names associated to - the original variables names. - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. - PARAMS_INDEX connects the cloog parameters with the gimple parameters in the sese region. */ static edge translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e, - htab_t rename_map, VEC (tree, heap) **newivs, + VEC (tree, heap) **newivs, htab_t newivs_index, htab_t bb_pbb_mapping, htab_t params_index) { - gimple_bb_p gbb; + int i, nb_loops; basic_block new_bb; poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement); - gbb = PBB_BLACK_BOX (pbb); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + VEC (tree, heap) *iv_map; if (GBB_BB (gbb) == ENTRY_BLOCK_PTR) return next_e; - build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt, - params_index); + nb_loops = number_of_loops (); + iv_map = VEC_alloc (tree, heap, nb_loops); + for (i = 0; i < nb_loops; i++) + VEC_quick_push (tree, iv_map, NULL_TREE); + + build_iv_mapping (iv_map, region, *newivs, newivs_index, stmt, params_index); next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region, - next_e, rename_map); + next_e, iv_map); + VEC_free (tree, heap, iv_map); + new_bb = next_e->src; mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping); update_ssa (TODO_update_ssa); @@ -1011,20 +974,21 @@ graphite_create_new_loop_guard (sese region, edge entry_edge, return exit_edge; } +static edge +translate_clast (sese, loop_p, struct clast_stmt *, edge, + VEC (tree, heap) **, htab_t, htab_t, int, htab_t); /* Create the loop for a clast for statement. - REGION is the sese region we used to generate the scop. - NEXT_E is the edge where new generated code should be attached. - - RENAME_MAP contains a set of tuples of new names associated to - the original variables names. - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. - PARAMS_INDEX connects the cloog parameters with the gimple parameters in the sese region. */ static edge translate_clast_for_loop (sese region, loop_p context_loop, struct clast_for *stmt, edge next_e, - htab_t rename_map, VEC (tree, heap) **newivs, + VEC (tree, heap) **newivs, htab_t newivs_index, htab_t bb_pbb_mapping, int level, htab_t params_index) { @@ -1040,7 +1004,7 @@ translate_clast_for_loop (sese region, loop_p context_loop, last_e = single_succ_edge (split_edge (last_e)); /* Translate the body of the loop. */ - next_e = translate_clast (region, loop, stmt->body, to_body, rename_map, + next_e = translate_clast (region, loop, stmt->body, to_body, newivs, newivs_index, bb_pbb_mapping, level + 1, params_index); redirect_edge_succ_nodup (next_e, after); @@ -1060,14 +1024,12 @@ translate_clast_for_loop (sese region, loop_p context_loop, - REGION is the sese region we used to generate the scop. - NEXT_E is the edge where new generated code should be attached. - - RENAME_MAP contains a set of tuples of new names associated to - the original variables names. - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. - PARAMS_INDEX connects the cloog parameters with the gimple parameters in the sese region. */ static edge translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt, - edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, + edge next_e, VEC (tree, heap) **newivs, htab_t newivs_index, htab_t bb_pbb_mapping, int level, htab_t params_index) { @@ -1075,8 +1037,7 @@ translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt, newivs_index, params_index); edge true_e = get_true_edge_from_guard_bb (next_e->dest); - translate_clast_for_loop (region, context_loop, stmt, true_e, - rename_map, newivs, + translate_clast_for_loop (region, context_loop, stmt, true_e, newivs, newivs_index, bb_pbb_mapping, level, params_index); return last_e; @@ -1087,15 +1048,13 @@ translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt, - REGION is the sese region we used to generate the scop. - NEXT_E is the edge where new generated code should be attached. - CONTEXT_LOOP is the loop in which the generated code will be placed - - RENAME_MAP contains a set of tuples of new names associated to - the original variables names. - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. - PARAMS_INDEX connects the cloog parameters with the gimple parameters in the sese region. */ static edge translate_clast_guard (sese region, loop_p context_loop, struct clast_guard *stmt, edge next_e, - htab_t rename_map, VEC (tree, heap) **newivs, + VEC (tree, heap) **newivs, htab_t newivs_index, htab_t bb_pbb_mapping, int level, htab_t params_index) { @@ -1104,7 +1063,7 @@ translate_clast_guard (sese region, loop_p context_loop, edge true_e = get_true_edge_from_guard_bb (next_e->dest); translate_clast (region, context_loop, stmt->then, true_e, - rename_map, newivs, newivs_index, bb_pbb_mapping, + newivs, newivs_index, bb_pbb_mapping, level, params_index); return last_e; } @@ -1114,12 +1073,10 @@ translate_clast_guard (sese region, loop_p context_loop, - NEXT_E is the edge where new generated code should be attached. - CONTEXT_LOOP is the loop in which the generated code will be placed - - RENAME_MAP contains a set of tuples of new names associated to - the original variables names. - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ static edge translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt, - edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, + edge next_e, VEC (tree, heap) **newivs, htab_t newivs_index, htab_t bb_pbb_mapping, int level, htab_t params_index) { @@ -1131,25 +1088,25 @@ translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt, else if (CLAST_STMT_IS_A (stmt, stmt_user)) next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt, - next_e, rename_map, newivs, newivs_index, + next_e, newivs, newivs_index, bb_pbb_mapping, params_index); else if (CLAST_STMT_IS_A (stmt, stmt_for)) next_e = translate_clast_for (region, context_loop, (struct clast_for *) stmt, next_e, - rename_map, newivs, newivs_index, + newivs, newivs_index, bb_pbb_mapping, level, params_index); else if (CLAST_STMT_IS_A (stmt, stmt_guard)) next_e = translate_clast_guard (region, context_loop, (struct clast_guard *) stmt, next_e, - rename_map, newivs, newivs_index, + newivs, newivs_index, bb_pbb_mapping, level, params_index); else if (CLAST_STMT_IS_A (stmt, stmt_block)) next_e = translate_clast (region, context_loop, ((struct clast_block *) stmt)->body, - next_e, rename_map, newivs, newivs_index, + next_e, newivs, newivs_index, bb_pbb_mapping, level, params_index); else gcc_unreachable(); @@ -1158,7 +1115,7 @@ translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt, graphite_verify (); return translate_clast (region, context_loop, stmt->next, next_e, - rename_map, newivs, newivs_index, + newivs, newivs_index, bb_pbb_mapping, level, params_index); } @@ -1485,7 +1442,7 @@ gloog (scop_p scop, htab_t bb_pbb_mapping) loop_p context_loop; sese region = SCOP_REGION (scop); ifsese if_region = NULL; - htab_t rename_map, newivs_index, params_index; + htab_t newivs_index, params_index; cloog_prog_clast pc; timevar_push (TV_GRAPHITE_CODE_GEN); @@ -1512,7 +1469,6 @@ gloog (scop_p scop, htab_t bb_pbb_mapping) graphite_verify (); context_loop = SESE_ENTRY (region)->src->loop_father; - rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free); newivs_index = htab_create (10, clast_name_index_elt_info, eq_clast_name_indexes, free); params_index = htab_create (10, clast_name_index_elt_info, @@ -1522,7 +1478,7 @@ gloog (scop_p scop, htab_t bb_pbb_mapping) translate_clast (region, context_loop, pc.stmt, if_region->true_region->entry, - rename_map, &newivs, newivs_index, + &newivs, newivs_index, bb_pbb_mapping, 1, params_index); graphite_verify (); scev_reset_htab (); @@ -1536,7 +1492,6 @@ gloog (scop_p scop, htab_t bb_pbb_mapping) free (if_region->region); free (if_region); - htab_delete (rename_map); htab_delete (newivs_index); htab_delete (params_index); VEC_free (tree, heap, newivs); diff --git a/gcc/graphite-clast-to-gimple.h b/gcc/graphite-clast-to-gimple.h index c90cfc0..fbb4efa 100644 --- a/gcc/graphite-clast-to-gimple.h +++ b/gcc/graphite-clast-to-gimple.h @@ -40,7 +40,6 @@ extern bool gloog (scop_p, htab_t); extern cloog_prog_clast scop_to_clast (scop_p); extern void debug_clast_stmt (struct clast_stmt *); extern void print_clast_stmt (FILE *, struct clast_stmt *); -extern void debug_clast_name_indexes (htab_t); /* Hash function for data base element BB_PBB. */ diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index c186dd1..6e09532 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2332,20 +2332,6 @@ rewrite_reductions_out_of_ssa (scop_p scop) #endif } -/* Return true when DEF can be analyzed in REGION by the scalar - evolution analyzer. */ - -static bool -scev_analyzable_p (tree def, sese region) -{ - gimple stmt = SSA_NAME_DEF_STMT (def); - loop_p loop = loop_containing_stmt (stmt); - tree scev = scalar_evolution_in_region (region, loop, def); - - return !chrec_contains_undetermined (scev) - && TREE_CODE (scev) != SSA_NAME; -} - /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory read from ZERO_DIM_ARRAY. */ diff --git a/gcc/sese.c b/gcc/sese.c index e0c06da..913ac4d 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -394,6 +394,38 @@ sese_insert_phis_for_liveouts (sese region, basic_block bb, update_ssa (TODO_update_ssa); } +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ + +edge +get_true_edge_from_guard_bb (basic_block bb) +{ + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_TRUE_VALUE) + return e; + + gcc_unreachable (); + return NULL; +} + +/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ + +edge +get_false_edge_from_guard_bb (basic_block bb) +{ + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (!(e->flags & EDGE_TRUE_VALUE)) + return e; + + gcc_unreachable (); + return NULL; +} + /* Returns the expression associated to OLD_NAME in RENAME_MAP. */ static tree @@ -409,12 +441,12 @@ get_rename (htab_t rename_map, tree old_name) if (slot && *slot) return ((rename_map_elt) *slot)->expr; - return old_name; + return NULL_TREE; } /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ -void +static void set_rename (htab_t rename_map, tree old_name, tree expr) { struct rename_map_elt_s tmp; @@ -435,579 +467,101 @@ set_rename (htab_t rename_map, tree old_name, tree expr) *slot = new_rename_map_elt (old_name, expr); } -/* Rename the SSA_NAMEs used in STMT and that appear in RENAME_MAP. */ +/* Renames the scalar uses of the statement COPY, using the + substitution map RENAME_MAP, inserting the gimplification code at + GSI_TGT, for the translation REGION, with the original copied + statement in LOOP, and using the induction variable renaming map + IV_MAP. */ static void -rename_variables_in_stmt (gimple stmt, htab_t rename_map, gimple_stmt_iterator *insert_gsi) +rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, + sese region, loop_p loop, VEC (tree, heap) *iv_map) { - ssa_op_iter iter; use_operand_p use_p; + ssa_op_iter op_iter; - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES) { - tree use = USE_FROM_PTR (use_p); - tree expr, type_use, type_expr; + tree old_name = USE_FROM_PTR (use_p); + tree new_expr, scev; gimple_seq stmts; - if (TREE_CODE (use) != SSA_NAME) - continue; - - expr = get_rename (rename_map, use); - if (use == expr) + if (TREE_CODE (old_name) != SSA_NAME + || !is_gimple_reg (old_name) + || SSA_NAME_IS_DEFAULT_DEF (old_name)) continue; - type_use = TREE_TYPE (use); - type_expr = TREE_TYPE (expr); - - if (type_use != type_expr - || (TREE_CODE (expr) != SSA_NAME - && is_gimple_reg (use))) + new_expr = get_rename (rename_map, old_name); + if (new_expr) { - tree var; + tree type_old_name = TREE_TYPE (old_name); + tree type_new_expr = TREE_TYPE (new_expr); - if (is_gimple_debug (stmt)) + if (type_old_name != type_new_expr + || (TREE_CODE (new_expr) != SSA_NAME + && is_gimple_reg (old_name))) { - if (gimple_debug_bind_p (stmt)) - gimple_debug_bind_reset_value (stmt); - else - gcc_unreachable (); - - break; - } - - var = create_tmp_var (type_use, "var"); - - if (type_use != type_expr) - expr = fold_convert (type_use, expr); - - expr = build2 (MODIFY_EXPR, type_use, var, expr); - expr = force_gimple_operand (expr, &stmts, true, NULL); - gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT); - } - - replace_exp (use_p, expr); - } - - update_stmt (stmt); -} - -/* Returns true if NAME is a parameter of SESE. */ - -static bool -is_parameter (sese region, tree name) -{ - int i; - tree p; - - for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++) - if (p == name) - return true; - - return false; -} - -/* Returns true if NAME is an induction variable. */ - -static bool -is_iv (tree name) -{ - return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI; -} - -static void expand_scalar_variables_stmt (gimple, basic_block, sese, - htab_t, gimple_stmt_iterator *); -static tree -expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block, - sese, htab_t, gimple_stmt_iterator *); - -static tree -expand_scalar_variables_call (gimple stmt, basic_block bb, sese region, - htab_t rename_map, gimple_stmt_iterator *gsi) -{ - int i, nargs = gimple_call_num_args (stmt); - VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs); - tree fn_type = TREE_TYPE (gimple_call_fn (stmt)); - tree fn = gimple_call_fndecl (stmt); - tree call_expr, var, lhs; - gimple call; - - for (i = 0; i < nargs; i++) - { - tree arg = gimple_call_arg (stmt, i); - tree t = TREE_TYPE (arg); - - var = create_tmp_var (t, "var"); - arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL, - bb, region, rename_map, gsi); - arg = build2 (MODIFY_EXPR, t, var, arg); - arg = force_gimple_operand_gsi (gsi, arg, true, NULL, - true, GSI_SAME_STMT); - VEC_quick_push (tree, args, arg); - } - - lhs = gimple_call_lhs (stmt); - var = create_tmp_var (TREE_TYPE (lhs), "var"); - call_expr = build_call_vec (fn_type, fn, args); - call = gimple_build_call_from_tree (call_expr); - var = make_ssa_name (var, call); - gimple_call_set_lhs (call, var); - gsi_insert_before (gsi, call, GSI_SAME_STMT); - - return var; -} - -/* Copies at GSI all the scalar computations on which the ssa_name OP0 - depends on in the SESE: these are all the scalar variables used in - the definition of OP0, that are defined outside BB and still in the - SESE, i.e. not a parameter of the SESE. The expression that is - returned contains only induction variables from the generated code: - RENAME_MAP contains the induction variables renaming mapping, and is used - to translate the names of induction variables. */ - -static tree -expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb, - sese region, htab_t rename_map, - gimple_stmt_iterator *gsi) -{ - gimple def_stmt; - tree new_op; - - if (is_parameter (region, op0) - || is_iv (op0)) - return fold_convert (type, get_rename (rename_map, op0)); - - def_stmt = SSA_NAME_DEF_STMT (op0); - - /* Check whether we already have a rename for OP0. */ - new_op = get_rename (rename_map, op0); - - if (new_op != op0 - && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb) - return fold_convert (type, new_op); - - if (gimple_bb (def_stmt) == bb) - { - /* If the defining statement is in the basic block already - we do not need to create a new expression for it, we - only need to ensure its operands are expanded. */ - expand_scalar_variables_stmt (def_stmt, bb, region, rename_map, gsi); - return fold_convert (type, new_op); - } - else - { - if (!gimple_bb (def_stmt) - || !bb_in_sese_p (gimple_bb (def_stmt), region)) - return fold_convert (type, new_op); - - switch (gimple_code (def_stmt)) - { - case GIMPLE_ASSIGN: - { - tree var0 = gimple_assign_rhs1 (def_stmt); - enum tree_code subcode = gimple_assign_rhs_code (def_stmt); - tree var1 = gimple_assign_rhs2 (def_stmt); - tree type = gimple_expr_type (def_stmt); - - return expand_scalar_variables_expr (type, var0, subcode, var1, bb, - region, rename_map, gsi); - } - - case GIMPLE_CALL: - return expand_scalar_variables_call (def_stmt, bb, region, rename_map, gsi); - - default: - gcc_unreachable (); - return new_op; - } - } -} - -/* Copies at GSI all the scalar computations on which the expression - OP0 CODE OP1 depends on in the SESE: these are all the scalar - variables used in OP0 and OP1, defined outside BB and still defined - in the SESE, i.e. not a parameter of the SESE. The expression that - is returned contains only induction variables from the generated - code: RENAME_MAP contains the induction variables renaming mapping, and is - used to translate the names of induction variables. */ - -static tree -expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, - tree op1, basic_block bb, sese region, - htab_t rename_map, gimple_stmt_iterator *gsi) -{ - if (TREE_CODE_CLASS (code) == tcc_constant - || TREE_CODE_CLASS (code) == tcc_declaration) - return op0; - - /* For data references we have to duplicate also its memory - indexing. */ - if (TREE_CODE_CLASS (code) == tcc_reference) - { - switch (code) - { - case REALPART_EXPR: - case IMAGPART_EXPR: - { - tree op = TREE_OPERAND (op0, 0); - tree res = expand_scalar_variables_expr - (type, op, TREE_CODE (op), NULL, bb, region, rename_map, gsi); - return build1 (code, type, res); - } - - case INDIRECT_REF: - { - tree old_name = TREE_OPERAND (op0, 0); - tree expr = expand_scalar_variables_ssa_name - (type, old_name, bb, region, rename_map, gsi); - - if (TREE_CODE (expr) != SSA_NAME - && is_gimple_reg (old_name)) - { - tree type = TREE_TYPE (old_name); - tree var = create_tmp_var (type, "var"); - - expr = build2 (MODIFY_EXPR, type, var, expr); - expr = force_gimple_operand_gsi (gsi, expr, true, NULL, - true, GSI_SAME_STMT); - } - - return fold_build1 (code, type, expr); - } - - case ARRAY_REF: - { - tree op00 = TREE_OPERAND (op0, 0); - tree op01 = TREE_OPERAND (op0, 1); - tree op02 = TREE_OPERAND (op0, 2); - tree op03 = TREE_OPERAND (op0, 3); - tree base = expand_scalar_variables_expr - (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region, - rename_map, gsi); - tree subscript = expand_scalar_variables_expr - (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region, - rename_map, gsi); - - return build4 (ARRAY_REF, type, base, subscript, op02, op03); - } - - case COMPONENT_REF: - return op0; - - default: - /* The above cases should catch everything. */ - gcc_unreachable (); - } - } - - if (TREE_CODE_CLASS (code) == tcc_unary) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, region, rename_map, gsi); - - return fold_build1 (code, type, op0_expr); - } - - if (TREE_CODE_CLASS (code) == tcc_binary - || TREE_CODE_CLASS (code) == tcc_comparison) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, region, rename_map, gsi); - tree op1_type = TREE_TYPE (op1); - enum tree_code op1_code = TREE_CODE (op1); - tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code, - NULL, bb, region, rename_map, gsi); - - return fold_build2 (code, type, op0_expr, op1_expr); - } - - if (code == SSA_NAME) - return expand_scalar_variables_ssa_name (type, op0, bb, region, rename_map, gsi); - - if (code == ADDR_EXPR) - { - tree op00 = TREE_OPERAND (op0, 0); - - if (handled_component_p (op00) - && TREE_CODE (op00) == ARRAY_REF) - { - tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00, - TREE_CODE (op00), - NULL, bb, region, rename_map, gsi); - return fold_build1 (code, TREE_TYPE (op0), e); - } - - return op0; - } - - gcc_unreachable (); - return NULL; -} - -/* Copies at the beginning of BB all the scalar computations on which - STMT depends on in the SESE: these are all the scalar variables used - in STMT, defined outside BB and still defined in the SESE, i.e. not a - parameter of the SESE. The expression that is returned contains - only induction variables from the generated code: RENAME_MAP contains the - induction variables renaming mapping, and is used to translate the - names of induction variables. */ - -static void -expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region, - htab_t rename_map, gimple_stmt_iterator *gsi) -{ - ssa_op_iter iter; - use_operand_p use_p; - - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) - { - tree use = USE_FROM_PTR (use_p); - tree type = TREE_TYPE (use); - enum tree_code code = TREE_CODE (use); - tree use_expr; - - if (!is_gimple_reg (use)) - continue; - - /* Don't expand USE if we already have a rename for it. */ - use_expr = get_rename (rename_map, use); - if (use_expr != use) - continue; + tree var; - use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb, - region, rename_map, gsi); - use_expr = fold_convert (type, use_expr); + if (is_gimple_debug (copy)) + { + if (gimple_debug_bind_p (copy)) + gimple_debug_bind_reset_value (copy); + else + gcc_unreachable (); - if (use_expr == use) - continue; + break; + } - if (is_gimple_debug (stmt)) - { - if (gimple_debug_bind_p (stmt)) - gimple_debug_bind_reset_value (stmt); - else - gcc_unreachable (); + var = create_tmp_var (type_old_name, "var"); - break; - } + if (type_old_name != type_new_expr) + new_expr = fold_convert (type_old_name, new_expr); - if (TREE_CODE (use_expr) != SSA_NAME) - { - tree var = create_tmp_var (type, "var"); + new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr); + new_expr = force_gimple_operand (new_expr, &stmts, true, NULL); + gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + } - use_expr = build2 (MODIFY_EXPR, type, var, use_expr); - use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL, - true, GSI_SAME_STMT); + replace_exp (use_p, new_expr); + continue; } - replace_exp (use_p, use_expr); - } - - update_stmt (stmt); -} - -/* Copies at the beginning of BB all the scalar computations on which - BB depends on in the SESE: these are all the scalar variables used - in BB, defined outside BB and still defined in the SESE, i.e. not a - parameter of the SESE. The expression that is returned contains - only induction variables from the generated code: RENAME_MAP contains the - induction variables renaming mapping, and is used to translate the - names of induction variables. */ - -static void -expand_scalar_variables (basic_block bb, sese region, htab_t rename_map) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) - { - gimple stmt = gsi_stmt (gsi); - expand_scalar_variables_stmt (stmt, bb, region, rename_map, &gsi); - gsi_next (&gsi); - } -} - -/* Rename all the SSA_NAMEs from block BB according to the RENAME_MAP. */ - -static void -rename_variables (basic_block bb, htab_t rename_map) -{ - gimple_stmt_iterator gsi; - gimple_stmt_iterator insert_gsi = gsi_start_bb (bb); - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - rename_variables_in_stmt (gsi_stmt (gsi), rename_map, &insert_gsi); -} - -/* Remove condition from BB. */ - -static void -remove_condition (basic_block bb) -{ - gimple last = last_stmt (bb); - - if (last && gimple_code (last) == GIMPLE_COND) - { - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_remove (&gsi, true); - } -} - -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ - -edge -get_true_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_TRUE_VALUE) - return e; - - gcc_unreachable (); - return NULL; -} - -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ - -edge -get_false_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (!(e->flags & EDGE_TRUE_VALUE)) - return e; - - gcc_unreachable (); - return NULL; -} - -/* Helper structure for htab_traverse in insert_guard_phis. */ + scev = scalar_evolution_in_region (region, loop, old_name); -struct igp { - basic_block bb; - edge true_edge, false_edge; - htab_t before_guard; -}; + /* At this point we should know the exact scev for each + scalar SSA_NAME used in the scop: all the other scalar + SSA_NAMEs should have been translated out of SSA using + arrays with one element. */ + gcc_assert (!chrec_contains_undetermined (scev)); -/* Return the default name that is before the guard. */ + new_expr = chrec_apply_map (scev, iv_map); -static tree -default_before_guard (htab_t before_guard, tree old_name) -{ - tree res = get_rename (before_guard, old_name); + /* The apply should produce an expression tree containing + the uses of the new induction variables. We should be + able to use new_expr instead of the old_name in the newly + generated loop nest. */ + gcc_assert (!chrec_contains_undetermined (new_expr) + && !tree_contains_chrecs (new_expr, NULL)); - if (res == old_name) - { - if (is_gimple_reg (res)) - return fold_convert (TREE_TYPE (res), integer_zero_node); - return gimple_default_def (cfun, SSA_NAME_VAR (res)); + /* Replace the old_name with the new_expr. */ + new_expr = force_gimple_operand (new_expr, &stmts, true, NULL); + gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); + replace_exp (use_p, new_expr); + set_rename (rename_map, old_name, new_expr); } - - return res; } -/* Prepares EXPR to be a good phi argument when the phi result is - RES. Insert needed statements on edge E. */ - -static tree -convert_for_phi_arg (tree expr, tree res, edge e) -{ - tree type = TREE_TYPE (res); - - if (TREE_TYPE (expr) != type) - expr = fold_convert (type, expr); - - if (TREE_CODE (expr) != SSA_NAME - && !is_gimple_min_invariant (expr)) - { - tree var = create_tmp_var (type, "var"); - gimple_seq stmts; - - expr = build2 (MODIFY_EXPR, type, var, expr); - expr = force_gimple_operand (expr, &stmts, true, NULL); - gsi_insert_seq_on_edge_immediate (e, stmts); - } - - return expr; -} - -/* Helper function for htab_traverse in insert_guard_phis. */ - -static int -add_guard_exit_phis (void **slot, void *s) -{ - struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; - struct igp *i = (struct igp *) s; - basic_block bb = i->bb; - edge true_edge = i->true_edge; - edge false_edge = i->false_edge; - tree res = entry->old_name; - tree name1 = entry->expr; - tree name2 = default_before_guard (i->before_guard, res); - gimple phi; - - /* Nothing to be merged if the name before the guard is the same as - the one after. */ - if (name1 == name2) - return 1; - - name1 = convert_for_phi_arg (name1, res, true_edge); - name2 = convert_for_phi_arg (name2, res, false_edge); - - phi = create_phi_node (res, bb); - res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION); - add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION); - - entry->expr = res; - *slot = entry; - return 1; -} - -/* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1). - If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD, - with NAME1 different than NAME2, then insert in BB the phi node: - - | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))" - - if there is no tuple for OLD in BEFORE_GUARD, insert - - | RES = phi (NAME1 (on TRUE_EDGE), - | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))". - - Finally register in RENAME_MAP the tuple (OLD, RES). */ - -void -insert_guard_phis (basic_block bb, edge true_edge, edge false_edge, - htab_t before_guard, htab_t rename_map) -{ - struct igp i; - i.bb = bb; - i.true_edge = true_edge; - i.false_edge = false_edge; - i.before_guard = before_guard; - - update_ssa (TODO_update_ssa); - htab_traverse (rename_map, add_guard_exit_phis, &i); - update_ssa (TODO_update_ssa); -} - -/* Create a duplicate of the basic block BB. NOTE: This does not - preserve SSA form. */ +/* Duplicates the statements of basic block BB into basic block NEW_BB + and compute the new induction variables according to the IV_MAP. */ static void -graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t rename_map) +graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, + htab_t rename_map, + VEC (tree, heap) *iv_map, sese region) { gimple_stmt_iterator gsi, gsi_tgt; + loop_p loop = bb->loop_father; gsi_tgt = gsi_start_bb (new_bb); for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -1016,8 +570,19 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t renam ssa_op_iter op_iter; gimple stmt = gsi_stmt (gsi); gimple copy; + tree lhs; + + /* Do not copy labels or conditions. */ + if (gimple_code (stmt) == GIMPLE_LABEL + || gimple_code (stmt) == GIMPLE_COND) + continue; - if (gimple_code (stmt) == GIMPLE_LABEL) + /* Do not copy induction variables. */ + if (is_gimple_assign (stmt) + && (lhs = gimple_assign_lhs (stmt)) + && TREE_CODE (lhs) == SSA_NAME + && is_gimple_reg (lhs) + && scev_analyzable_p (lhs, region)) continue; /* Create a new copy of STMT and duplicate STMT's virtual @@ -1032,11 +597,15 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t renam /* Create new names for all the definitions created by COPY and add replacement mappings for each new name. */ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) - { - tree old_name = DEF_FROM_PTR (def_p); - tree new_name = create_new_def_for (old_name, copy, def_p); + { + tree old_name = DEF_FROM_PTR (def_p); + tree new_name = create_new_def_for (old_name, copy, def_p); set_rename (rename_map, old_name, new_name); - } + } + + rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map); + + update_stmt (copy); } } @@ -1046,16 +615,16 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t renam edge copy_bb_and_scalar_dependences (basic_block bb, sese region, - edge next_e, htab_t rename_map) + edge next_e, VEC (tree, heap) *iv_map) { basic_block new_bb = split_edge (next_e); + htab_t rename_map = htab_create (10, rename_map_elt_info, + eq_rename_map_elts, free); next_e = single_succ_edge (new_bb); - graphite_copy_stmts_from_block (bb, new_bb, rename_map); - remove_condition (new_bb); + graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region); remove_phi_nodes (new_bb); - expand_scalar_variables (new_bb, region, rename_map); - rename_variables (new_bb, rename_map); + htab_delete (rename_map); return next_e; } diff --git a/gcc/sese.h b/gcc/sese.h index d0d829f..1502cbe 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -56,7 +56,8 @@ extern sese new_sese (edge, edge); extern void free_sese (sese); extern void sese_insert_phis_for_liveouts (sese, basic_block, edge, edge); extern void build_sese_loop_nests (sese); -extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, htab_t); +extern edge copy_bb_and_scalar_dependences (basic_block, sese, edge, + VEC (tree, heap) *); extern struct loop *outermost_loop_in_sese (sese, basic_block); extern void insert_loop_close_phis (htab_t, loop_p); extern void insert_guard_phis (basic_block, edge, edge, htab_t, htab_t); @@ -261,7 +262,6 @@ DEF_VEC_ALLOC_P (rename_map_elt, heap); extern void debug_rename_map (htab_t); extern hashval_t rename_map_elt_info (const void *); extern int eq_rename_map_elts (const void *, const void *); -extern void set_rename (htab_t, tree, tree); /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ @@ -386,4 +386,19 @@ nb_common_loops (sese region, gimple_bb_p gbb1, gimple_bb_p gbb2) return sese_loop_depth (region, common); } +/* Return true when DEF can be analyzed in REGION by the scalar + evolution analyzer. */ + +static inline bool +scev_analyzable_p (tree def, sese region) +{ + gimple stmt = SSA_NAME_DEF_STMT (def); + loop_p loop = loop_containing_stmt (stmt); + tree scev = scalar_evolution_in_region (region, loop, def); + + return !chrec_contains_undetermined (scev) + && TREE_CODE (scev) != SSA_NAME + && evolution_function_is_affine_p (scev); +} + #endif diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 2d15285..c92b6b9 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -632,6 +632,23 @@ chrec_apply (unsigned var, return res; } +/* For a given CHREC and an induction variable map IV_MAP that maps + (loop->num, expr) for every loop number of the current_loops an + expression, calls chrec_apply when the expression is not NULL. */ + +tree +chrec_apply_map (tree chrec, VEC (tree, heap) *iv_map) +{ + int i; + tree expr; + + for (i = 0; VEC_iterate (tree, iv_map, i, expr); i++) + if (expr) + chrec = chrec_apply (i, chrec, expr); + + return chrec; +} + /* Replaces the initial condition in CHREC with INIT_COND. */ tree diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index fcff93a..eb60ac9 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -64,6 +64,7 @@ extern tree chrec_convert_aggressive (tree, tree); /* Operations. */ extern tree chrec_apply (unsigned, tree, tree); +extern tree chrec_apply_map (tree, VEC (tree, heap) *); extern tree chrec_replace_initial_condition (tree, tree); extern tree initial_condition (tree); extern tree initial_condition_in_loop_num (tree, unsigned); -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 05/12] Remove uses of loop->single_iv. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (7 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 02/12] Remove expand_scalar_variables_ hack Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 08/12] Special case non close-phi nodes with one argument in rewrite_close_phi_out_of_ssa Sebastian Pop ` (2 subsequent siblings) 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * cfgloop.c (alloc_loop): Remove initialization of loop->single_iv. * cfgloop.h (struct loop): Remove single_iv field. * graphite-sese-to-poly.c (graphite_loop_normal_form): Removed. (scop_canonicalize_loops): Removed. (scop_ivs_can_be_represented): Do not use loop->single_iv. Iterate over all the loop phi nodes in loop->header. (build_poly_scop): Remove use of scop_canonicalize_loops. --- gcc/ChangeLog.graphite | 10 +++++++ gcc/cfgloop.c | 1 - gcc/cfgloop.h | 4 --- gcc/graphite-sese-to-poly.c | 62 +++++++----------------------------------- 4 files changed, 21 insertions(+), 56 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index a83cc99..8408cf2 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,15 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * cfgloop.c (alloc_loop): Remove initialization of loop->single_iv. + * cfgloop.h (struct loop): Remove single_iv field. + * graphite-sese-to-poly.c (graphite_loop_normal_form): Removed. + (scop_canonicalize_loops): Removed. + (scop_ivs_can_be_represented): Do not use loop->single_iv. Iterate + over all the loop phi nodes in loop->header. + (build_poly_scop): Remove use of scop_canonicalize_loops. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_cross_bb_scalar_deps): Also handle GIMPLE_CALL. diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 858e75b..0a8ceba 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -339,7 +339,6 @@ alloc_loop (void) loop->exits = GGC_CNEW (struct loop_exit); loop->exits->next = loop->exits->prev = loop->exits; loop->can_be_parallel = false; - loop->single_iv = NULL_TREE; return loop; } diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 3821ee6..4d16a23 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -165,10 +165,6 @@ struct GTY ((chain_next ("%h.next"))) loop { /* Head of the cyclic list of the exits of the loop. */ struct loop_exit *exits; - - /* The single induction variable of the loop when the loop is in - normal form. */ - tree single_iv; }; /* Flags for state of loop structure. */ diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 22f9536..9c54f0b 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2905,45 +2905,6 @@ rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions) #endif } -/* A LOOP is in normal form for Graphite when it contains only one - scalar phi node that defines the main induction variable of the - loop, only one increment of the IV, and only one exit condition. */ - -static void -graphite_loop_normal_form (loop_p loop) -{ - struct tree_niter_desc niter; - tree nit; - gimple_seq stmts; - edge exit = single_dom_exit (loop); - - bool known_niter = number_of_iterations_exit (loop, exit, &niter, false); - - /* At this point we should know the number of iterations. */ - gcc_assert (known_niter); - - nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, - NULL_TREE); - if (stmts) - gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); - - loop->single_iv = canonicalize_loop_ivs (loop, &nit, false); -} - -/* Rewrite all the loops of SCOP in normal form: one induction - variable per loop. */ - -static void -scop_canonicalize_loops (scop_p scop) -{ - loop_iterator li; - loop_p loop; - - FOR_EACH_LOOP (li, loop, 0) - if (loop_in_sese_p (loop, SCOP_REGION (scop))) - graphite_loop_normal_form (loop); -} - /* Java does not initialize long_long_integer_type_node. */ #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) @@ -2956,24 +2917,24 @@ scop_ivs_can_be_represented (scop_p scop) { loop_iterator li; loop_p loop; + gimple_stmt_iterator psi; FOR_EACH_LOOP (li, loop, 0) { - tree type; - int precision; - if (!loop_in_sese_p (loop, SCOP_REGION (scop))) continue; - if (!loop->single_iv) - continue; - - type = TREE_TYPE (loop->single_iv); - precision = TYPE_PRECISION (type); + for (psi = gsi_start_phis (loop->header); + !gsi_end_p (psi); gsi_next (&psi)) + { + gimple phi = gsi_stmt (psi); + tree res = PHI_RESULT (phi); + tree type = TREE_TYPE (res); - if (TYPE_UNSIGNED (type) - && precision >= TYPE_PRECISION (my_long_long)) - return false; + if (TYPE_UNSIGNED (type) + && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long)) + return false; + } } return true; @@ -2997,7 +2958,6 @@ build_poly_scop (scop_p scop) if (nb_pbbs_in_loops (scop) == 0) return; - scop_canonicalize_loops (scop); if (!scop_ivs_can_be_represented (scop)) return; -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 08/12] Special case non close-phi nodes with one argument in rewrite_close_phi_out_of_ssa. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (8 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 05/12] Remove uses of loop->single_iv Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 12/12] Unshare the scev before code generating it Sebastian Pop 2010-07-16 7:05 ` [PATCH 11/12] Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p Sebastian Pop 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Special case non close-phi nodes with one argument. --- gcc/ChangeLog.graphite | 5 +++++ gcc/graphite-sese-to-poly.c | 28 ++++++++++++++++++++-------- 2 files changed, 25 insertions(+), 8 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index bbd6a34..40db483 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,10 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Special + case non close-phi nodes with one argument. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * sese.h (scev_analyzable_p): Scevs could be expressions without chrecs and still be scev_analyzable_p. diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 9c54f0b..3d02197 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2202,22 +2202,34 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) gimple phi = gsi_stmt (*psi); tree res = gimple_phi_result (phi); tree var = SSA_NAME_VAR (res); - tree zero_dim_array = create_zero_dim_array (var, "Close_Phi"); - gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); - gimple stmt = gimple_build_assign (res, zero_dim_array); + basic_block bb = gimple_bb (phi); + gimple_stmt_iterator gsi = gsi_after_labels (bb); tree arg = gimple_phi_arg_def (phi, 0); + gimple stmt; /* Note that loop close phi nodes should have a single argument because we translated the representation into a canonical form before Graphite: see canonicalize_loop_closed_ssa_form. */ gcc_assert (gimple_phi_num_args (phi) == 1); - if (TREE_CODE (arg) == SSA_NAME - && !SSA_NAME_IS_DEFAULT_DEF (arg)) - insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg)); + /* The phi node can be a non close phi node, when its argument is + invariant, or when it is defined in the same loop as the phi node. */ + if (is_gimple_min_invariant (arg) + || gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father) + stmt = gimple_build_assign (res, arg); else - insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)), - zero_dim_array, arg); + { + tree zero_dim_array = create_zero_dim_array (var, "Close_Phi"); + + stmt = gimple_build_assign (res, zero_dim_array); + + if (TREE_CODE (arg) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (arg)) + insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg)); + else + insert_out_of_ssa_copy_on_edge (single_pred_edge (bb), + zero_dim_array, arg); + } remove_phi_node (psi, false); gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 12/12] Unshare the scev before code generating it. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (9 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 08/12] Special case non close-phi nodes with one argument in rewrite_close_phi_out_of_ssa Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 11/12] Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p Sebastian Pop 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * sese.c (rename_uses): Call unshare_expr before force_gimple_operand. * gcc.dg/graphite/id-23.c: New. --- gcc/ChangeLog.graphite | 6 ++++++ gcc/sese.c | 3 ++- gcc/testsuite/gcc.dg/graphite/id-23.c | 22 ++++++++++++++++++++++ 3 files changed, 30 insertions(+), 1 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/id-23.c diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 6600df7..1cf50f3 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,11 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * sese.c (rename_uses): Call unshare_expr before force_gimple_operand. + + * gcc.dg/graphite/id-23.c: New. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (reduction_phi_p): Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p. diff --git a/gcc/sese.c b/gcc/sese.c index f59f317..3f7266b 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -543,7 +543,8 @@ rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, && !tree_contains_chrecs (new_expr, NULL)); /* Replace the old_name with the new_expr. */ - new_expr = force_gimple_operand (new_expr, &stmts, true, NULL); + new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, + true, NULL); gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); replace_exp (use_p, new_expr); set_rename (rename_map, old_name, new_expr); diff --git a/gcc/testsuite/gcc.dg/graphite/id-23.c b/gcc/testsuite/gcc.dg/graphite/id-23.c new file mode 100644 index 0000000..0f8a1f3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/id-23.c @@ -0,0 +1,22 @@ +double *ZV_entries (void); +void SubMtx_fillRowZV (int irow) +{ + double *rowvec = ZV_entries (); + double *entries; + int ii, ipivot, jrow, kk, m; + int *pivotsizes; + + SubMtx_blockDiagonalInfo (&pivotsizes); + + for (jrow = ipivot = kk = 0; jrow <= irow; ipivot++) + { + m = pivotsizes[ipivot]; + if (jrow <= irow && irow < jrow + m) + for (ii = jrow; ii < irow; ii++) + { + rowvec[2*ii] = entries[2*kk]; + rowvec[2*ii+1] = entries[2*kk+1]; + } + jrow += m; + } +} -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH 11/12] Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p. 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop ` (10 preceding siblings ...) 2010-07-16 7:05 ` [PATCH 12/12] Unshare the scev before code generating it Sebastian Pop @ 2010-07-16 7:05 ` Sebastian Pop 11 siblings, 0 replies; 15+ messages in thread From: Sebastian Pop @ 2010-07-16 7:05 UTC (permalink / raw) To: gcc-patches; +Cc: gcc-graphite, Sebastian Pop 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> * graphite-sese-to-poly.c (reduction_phi_p): Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p. * gfortran.dg/graphite/id-20.f: Adjust testcase. --- gcc/ChangeLog.graphite | 7 +++++++ gcc/graphite-sese-to-poly.c | 20 ++++---------------- gcc/testsuite/gfortran.dg/graphite/id-20.f | 12 +++++++++--- 3 files changed, 20 insertions(+), 19 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 8230d31..6600df7 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,12 @@ 2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (reduction_phi_p): Do not rewrite out of + SSA scalar phi nodes that can be scev_analyzable_p. + + * gfortran.dg/graphite/id-20.f: Adjust testcase. + +2010-07-15 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (rewrite_close_phi_out_of_ssa): Correctly handle SSA_NAME_IS_DEFAULT_DEF. diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 3d903d3..c08a4f2 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -165,8 +165,6 @@ static bool reduction_phi_p (sese region, gimple_stmt_iterator *psi) { loop_p loop; - tree scev; - affine_iv iv; gimple phi = gsi_stmt (*psi); tree res = gimple_phi_result (phi); @@ -189,11 +187,11 @@ reduction_phi_p (sese region, gimple_stmt_iterator *psi) return false; } - /* Main induction variables with constant strides in LOOP are not - reductions. */ - if (simple_iv (loop, loop, res, &iv, true)) + if (scev_analyzable_p (res, region)) { - if (integer_zerop (iv.step)) + tree scev = scalar_evolution_in_region (region, loop, res); + + if (evolution_function_is_invariant_p (scev, loop->num)) remove_invariant_phi (region, psi); else gsi_next (psi); @@ -201,16 +199,6 @@ reduction_phi_p (sese region, gimple_stmt_iterator *psi) return false; } - scev = scalar_evolution_in_region (region, loop, res); - if (chrec_contains_undetermined (scev)) - return true; - - if (evolution_function_is_invariant_p (scev, loop->num)) - { - remove_invariant_phi (region, psi); - return false; - } - /* All the other cases are considered reductions. */ return true; } diff --git a/gcc/testsuite/gfortran.dg/graphite/id-20.f b/gcc/testsuite/gfortran.dg/graphite/id-20.f index 110ae3f..795cb1b 100644 --- a/gcc/testsuite/gfortran.dg/graphite/id-20.f +++ b/gcc/testsuite/gfortran.dg/graphite/id-20.f @@ -1,4 +1,10 @@ - DO 32 MB=1,NVIRA - * PVIRA(MA,MB)*(EA(MA+NOA)+EA(MB+NOA))*PT5 - 32 CONTINUE +! { dg-options "-O3 -ffast-math" } + + DIMENSION FPQR(25,25,25) + INTEGER P,Q,R + DO 130 R=1,N4MAX,2 + IF(P.GT.1) THEN + FPQR(P,Q,R)= RM2*FPQR(P,Q,R-2)*REC(P+Q+R-2) + END IF + 130 RM2= RM2+TWO END -- 1.7.0.4 ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2010-07-16 14:41 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2010-07-16 7:04 [PATCH 00/12] [graphite] Remove the induction variable canonicalization Sebastian Pop 2010-07-16 7:04 ` [PATCH 07/12] Scevs could be expressions without chrecs and still be scev_analyzable_p Sebastian Pop 2010-07-16 7:04 ` [PATCH 03/12] chrec_apply should only apply to the specified variable Sebastian Pop 2010-07-16 7:04 ` [PATCH 09/12] Add testcase for PR42729 and fix handling of gimple_debug info Sebastian Pop 2010-07-16 7:05 ` [PATCH 01/12] Remove insert_loop_close_phis Sebastian Pop 2010-07-16 7:05 ` [PATCH 06/12] Bump the size of scevs Sebastian Pop 2010-07-16 8:03 ` Richard Guenther 2010-07-16 14:41 ` Sebastian Pop 2010-07-16 7:05 ` [PATCH 10/12] Correctly handle SSA_NAME_IS_DEFAULT_DEF in rewrite_close_phi_out_of_ssa Sebastian Pop 2010-07-16 7:05 ` [PATCH 04/12] Also handle GIMPLE_CALLs in rewrite_cross_bb_scalar_deps Sebastian Pop 2010-07-16 7:05 ` [PATCH 02/12] Remove expand_scalar_variables_ hack Sebastian Pop 2010-07-16 7:05 ` [PATCH 05/12] Remove uses of loop->single_iv Sebastian Pop 2010-07-16 7:05 ` [PATCH 08/12] Special case non close-phi nodes with one argument in rewrite_close_phi_out_of_ssa Sebastian Pop 2010-07-16 7:05 ` [PATCH 12/12] Unshare the scev before code generating it Sebastian Pop 2010-07-16 7:05 ` [PATCH 11/12] Do not rewrite out of SSA scalar phi nodes that can be scev_analyzable_p Sebastian Pop
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).