X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fgraphite-sese-to-poly.c;h=e7aa5568b5665ad644a0b7e5883fe29edaf0f174;hp=1eb0696705968b97a7199a87c59d0e3e045f4466;hb=1f44fe36b70bcb026e5ac6c1334b6d69c799ff60;hpb=5184a05fb65b8c71be5e2a930acdfb4bed2f0e8f diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 1eb06967059..e7aa5568b56 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -1,5 +1,5 @@ /* Conversion of SESE regions to Polyhedra. - Copyright (C) 2009 Free Software Foundation, Inc. + Copyright (C) 2009, 2010 Free Software Foundation, Inc. Contributed by Sebastian Pop . This file is part of GCC. @@ -180,7 +180,7 @@ reduction_phi_p (sese region, gimple_stmt_iterator *psi) if (simple_copy_phi_p (phi)) { - /* FIXME: PRE introduces phi nodes like these, for an example, + /* PRE introduces phi nodes like these, for an example, see id-5.f in the fortran graphite testsuite: # prephitmp.85_265 = PHI @@ -1038,6 +1038,74 @@ gbb_from_bb (basic_block bb) return (gimple_bb_p) bb->aux; } +/* Insert in the SCOP context constraints from the estimation of the + number of iterations. UB_EXPR is a linear expression describing + the number of iterations in a loop. This expression is bounded by + the estimation NIT. */ + +static void +add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit, + ppl_dimension_type dim, + ppl_Linear_Expression_t ub_expr) +{ + Value val; + ppl_Linear_Expression_t nb_iters_le; + ppl_Polyhedron_t pol; + ppl_Coefficient_t coef; + ppl_Constraint_t ub; + + ppl_new_Linear_Expression_with_dimension (&ub_expr, dim); + ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); + ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le, + ub_expr); + + /* Construct the negated number of last iteration in VAL. */ + value_init (val); + mpz_set_double_int (val, nit, false); + value_sub_int (val, val, 1); + value_oppose (val, val); + + /* NB_ITERS_LE holds the number of last iteration in + parametrical form. Subtract estimated number of last + iteration and assert that result is not positive. */ + ppl_new_Coefficient_from_mpz_t (&coef, val); + ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef); + ppl_delete_Coefficient (coef); + ppl_new_Constraint (&ub, nb_iters_le, + PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); + ppl_Polyhedron_add_constraint (pol, ub); + + /* Remove all but last GDIM dimensions from POL to obtain + only the constraints on the parameters. */ + { + graphite_dim_t gdim = scop_nb_params (scop); + ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim); + graphite_dim_t i; + + for (i = 0; i < dim - gdim; i++) + dims[i] = i; + + ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim); + XDELETEVEC (dims); + } + + /* Add the constraints on the parameters to the SCoP context. */ + { + ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps; + + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron + (&constraints_ps, pol); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign + (SCOP_CONTEXT (scop), constraints_ps); + ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps); + } + + ppl_delete_Polyhedron (pol); + ppl_delete_Linear_Expression (nb_iters_le); + ppl_delete_Constraint (ub); + value_clear (val); +} + /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives the constraints for the surrounding loops. */ @@ -1113,64 +1181,8 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one); value_clear (one); - /* N <= estimated_nb_iters - - FIXME: This is a workaround that should go away once we will - have the PIP algorithm. */ if (estimated_loop_iterations (loop, true, &nit)) - { - Value val; - ppl_Linear_Expression_t nb_iters_le; - ppl_Polyhedron_t pol; - graphite_dim_t n = scop_nb_params (scop); - ppl_Coefficient_t coef; - - ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); - ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le, - ub_expr); - - /* Construct the negated number of last iteration in VAL. */ - value_init (val); - mpz_set_double_int (val, nit, false); - value_sub_int (val, val, 1); - value_oppose (val, val); - - /* NB_ITERS_LE holds number of last iteration in parametrical form. - Subtract estimated number of last iteration and assert that result - is not positive. */ - ppl_new_Coefficient_from_mpz_t (&coef, val); - ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef); - ppl_delete_Coefficient (coef); - ppl_new_Constraint (&ub, nb_iters_le, - PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); - ppl_Polyhedron_add_constraint (pol, ub); - - /* Remove all but last N dimensions from POL to obtain constraints - on parameters. */ - { - ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - n); - graphite_dim_t i; - for (i = 0; i < dim - n; i++) - dims[i] = i; - ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - n); - XDELETEVEC (dims); - } - - /* Add constraints on parameters to SCoP context. */ - { - ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps; - ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&constraints_ps, pol); - ppl_Pointset_Powerset_C_Polyhedron_intersection_assign - (SCOP_CONTEXT (scop), constraints_ps); - ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps); - } - - ppl_delete_Polyhedron (pol); - ppl_delete_Linear_Expression (nb_iters_le); - ppl_delete_Constraint (ub); - value_clear (val); - } + add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr); /* loop_i <= expr_nb_iters */ ppl_set_coef (ub_expr, nb, -1); @@ -1499,16 +1511,18 @@ add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p) ppl_Linear_Expression_t le; tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p); tree type = TREE_TYPE (parameter); - tree lb, ub; - - /* Disabled until we fix CPU2006. */ - return; + tree lb = NULL_TREE; + tree ub = NULL_TREE; - if (!INTEGRAL_TYPE_P (type)) - return; + if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) + lb = lower_bound_in_type (type, type); + else + lb = TYPE_MIN_VALUE (type); - lb = TYPE_MIN_VALUE (type); - ub = TYPE_MAX_VALUE (type); + if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) + ub = upper_bound_in_type (type, type); + else + ub = TYPE_MAX_VALUE (type); if (lb) { @@ -2186,7 +2200,8 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi) gimple stmt = gimple_build_assign (res, zero_dim_array); tree arg = gimple_phi_arg_def (phi, 0); - if (TREE_CODE (arg) == SSA_NAME) + if (TREE_CODE (arg) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (arg)) insert_out_of_ssa_copy (zero_dim_array, arg); else insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)), @@ -2245,7 +2260,7 @@ rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) | end_2 | end_1 - whereas inserting the copy on the incomming edge is correct + whereas inserting the copy on the incoming edge is correct | a = ... | loop_1 @@ -2351,7 +2366,8 @@ rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) if (def_bb != gimple_bb (use_stmt) - && gimple_code (use_stmt) != GIMPLE_PHI) + && gimple_code (use_stmt) != GIMPLE_PHI + && !is_gimple_debug (use_stmt)) { if (!zero_dim_array) { @@ -2450,6 +2466,9 @@ split_reduction_stmt (gimple stmt) split_block (bb, stmt); + if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb))) + return bb; + gsi = gsi_last_bb (bb); gsi_prev (&gsi); e = split_block (bb, gsi_stmt (gsi)); @@ -2462,9 +2481,14 @@ split_reduction_stmt (gimple stmt) static inline bool is_reduction_operation_p (gimple stmt) { + enum tree_code code; + + gcc_assert (is_gimple_assign (stmt)); + code = gimple_assign_rhs_code (stmt); + return flag_associative_math - && commutative_tree_code (gimple_assign_rhs_code (stmt)) - && associative_tree_code (gimple_assign_rhs_code (stmt)); + && commutative_tree_code (code) + && associative_tree_code (code); } /* Returns true when PHI contains an argument ARG. */ @@ -2493,6 +2517,10 @@ follow_ssa_with_commutative_ops (tree arg, tree lhs) stmt = SSA_NAME_DEF_STMT (arg); + if (gimple_code (stmt) == GIMPLE_NOP + || gimple_code (stmt) == GIMPLE_CALL) + return NULL; + if (gimple_code (stmt) == GIMPLE_PHI) { if (phi_contains_arg (stmt, lhs)) @@ -2500,6 +2528,9 @@ follow_ssa_with_commutative_ops (tree arg, tree lhs) return NULL; } + if (!is_gimple_assign (stmt)) + return NULL; + if (gimple_num_ops (stmt) == 2) return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs); @@ -2666,13 +2697,13 @@ static void translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt, gimple loop_phi) { - basic_block bb = gimple_bb (stmt); - gimple_stmt_iterator insert_gsi = gsi_after_labels (bb); + gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi)); tree res = gimple_phi_result (loop_phi); gimple assign = gimple_build_assign (res, red); gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); + insert_gsi = gsi_after_labels (gimple_bb (stmt)); assign = gimple_build_assign (red, gimple_assign_lhs (stmt)); insert_gsi = gsi_for_stmt (stmt); gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT); @@ -2704,6 +2735,41 @@ insert_copyin (tree red, gimple loop_phi) gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts); } +/* Removes the PHI node and resets all the debug stmts that are using + the PHI_RESULT. */ + +static void +remove_phi (gimple phi) +{ + imm_use_iterator imm_iter; + tree def; + use_operand_p use_p; + gimple_stmt_iterator gsi; + VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3); + unsigned int i; + gimple stmt; + + def = PHI_RESULT (phi); + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) + { + stmt = USE_STMT (use_p); + + if (is_gimple_debug (stmt)) + { + gimple_debug_bind_reset_value (stmt); + VEC_safe_push (gimple, heap, update, stmt); + } + } + + for (i = 0; VEC_iterate (gimple, update, i, stmt); i++) + update_stmt (stmt); + + VEC_free (gimple, heap, update); + + gsi = gsi_for_phi_node (phi); + remove_phi_node (&gsi, false); +} + /* Rewrite out of SSA the reduction described by the loop phi nodes IN, and the close phi nodes OUT. IN and OUT are structured by loop levels like this: @@ -2722,7 +2788,6 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, unsigned int i; gimple loop_phi; tree red; - gimple_stmt_iterator gsi; for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++) { @@ -2749,11 +2814,8 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, insert_copyin (red, loop_phi); } - gsi = gsi_for_phi_node (loop_phi); - remove_phi_node (&gsi, false); - - gsi = gsi_for_phi_node (close_phi); - remove_phi_node (&gsi, false); + remove_phi (loop_phi); + remove_phi (close_phi); } } @@ -2825,7 +2887,7 @@ graphite_loop_normal_form (loop_p loop) bool known_niter = number_of_iterations_exit (loop, exit, &niter, false); - /* At this point we should know the number of iterations, */ + /* At this point we should know the number of iterations. */ gcc_assert (known_niter); nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, @@ -2833,7 +2895,7 @@ graphite_loop_normal_form (loop_p loop) if (stmts) gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); - loop->single_iv = canonicalize_loop_ivs (loop, &nit); + loop->single_iv = canonicalize_loop_ivs (loop, &nit, false); } /* Rewrite all the loops of SCOP in normal form: one induction @@ -2850,13 +2912,50 @@ scop_canonicalize_loops (scop_p 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) + +/* Can all ivs be represented by a signed integer? + As CLooG might generate negative values in its expressions, signed loop ivs + are required in the backend. */ +static bool +scop_ivs_can_be_represented (scop_p scop) +{ + loop_iterator li; + loop_p loop; + + 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); + + if (TYPE_UNSIGNED (type) + && precision >= TYPE_PRECISION (my_long_long)) + return false; + } + + return true; +} + +#undef my_long_long + /* Builds the polyhedral representation for a SESE region. */ -bool +void build_poly_scop (scop_p scop) { sese region = SCOP_REGION (scop); sbitmap reductions = sbitmap_alloc (last_basic_block * 2); + graphite_dim_t max_dim; sbitmap_zero (reductions); rewrite_commutative_reductions_out_of_ssa (region, reductions); @@ -2869,13 +2968,20 @@ build_poly_scop (scop_p scop) sense to optimize a scop containing only PBBs that do not belong to any loops. */ if (nb_pbbs_in_loops (scop) == 0) - return false; + return; scop_canonicalize_loops (scop); + if (!scop_ivs_can_be_represented (scop)) + return; + build_sese_loop_nests (region); build_sese_conditions (region); find_scop_parameters (scop); + max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS); + if (scop_nb_params (scop) > max_dim) + return; + build_scop_iteration_domain (scop); build_scop_context (scop); @@ -2884,7 +2990,9 @@ build_poly_scop (scop_p scop) build_scop_scattering (scop); build_scop_drs (scop); - return true; + /* This SCoP has been translated to the polyhedral + representation. */ + POLY_SCOP_P (scop) = true; } /* Always return false. Exercise the scop_to_clast function. */