X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite-sese-to-poly.c;h=3be2d8603912cb76e4e17697160f7211eba387ce;hb=05476866247e4b65496693ee6ced12d85922d011;hp=06a98a3b4121e8a3cf18aa70208ca788e2603ddd;hpb=f289f81b86af56e7c3025c6bdbcad5fe85cc17d7;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 06a98a3b412..3be2d860391 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -290,12 +290,15 @@ free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) { unsigned int i; struct data_reference *dr; - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) - if (dr->aux != NULL) + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + if (dr->aux) { base_alias_pair *bap = (base_alias_pair *)(dr->aux); - if (bap->alias_set != NULL) + + if (bap->alias_set) free (bap->alias_set); + free (bap); dr->aux = NULL; } @@ -743,26 +746,6 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k) ppl_delete_Coefficient (coef); } -/* Saves in NV at index I a new name for variable P. */ - -static void -save_var_name (char **nv, int i, tree p) -{ - const char *name = get_name (SSA_NAME_VAR (p)); - - if (name) - { - int len = strlen (name) + 16; - nv[i] = XNEWVEC (char, len); - snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p)); - } - else - { - nv[i] = XNEWVEC (char, 16); - snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p)); - } -} - /* When parameter NAME is in REGION, returns its index in SESE_PARAMS. Otherwise returns -1. */ @@ -799,9 +782,6 @@ parameter_index_in_region (tree name, sese region) gcc_assert (SESE_ADD_PARAMS (region)); i = VEC_length (tree, SESE_PARAMS (region)); - save_var_name (SESE_PARAMS_NAMES (region), i, name); - save_clast_name_index (SESE_PARAMS_INDEX (region), - SESE_PARAMS_NAMES (region)[i], i); VEC_safe_push (tree, heap, SESE_PARAMS (region), name); return i; } @@ -1063,7 +1043,8 @@ gbb_from_bb (basic_block bb) static void build_loop_iteration_domains (scop_p scop, struct loop *loop, - ppl_Polyhedron_t outer_ph, int nb) + ppl_Polyhedron_t outer_ph, int nb, + ppl_Pointset_Powerset_C_Polyhedron_t *domains) { int i; ppl_Polyhedron_t ph; @@ -1202,15 +1183,15 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, gcc_unreachable (); if (loop->inner && loop_in_sese_p (loop->inner, region)) - build_loop_iteration_domains (scop, loop->inner, ph, nb + 1); + build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains); if (nb != 0 && loop->next && loop_in_sese_p (loop->next, region)) - build_loop_iteration_domains (scop, loop->next, outer_ph, nb); + build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains); ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - ((ppl_Pointset_Powerset_C_Polyhedron_t *) &loop->aux, ph); + (&domains[loop->num], ph); ppl_delete_Polyhedron (ph); } @@ -1589,31 +1570,34 @@ build_scop_iteration_domain (scop_p scop) int i; ppl_Polyhedron_t ph; poly_bb_p pbb; + int nb_loops = number_of_loops (); + ppl_Pointset_Powerset_C_Polyhedron_t *domains + = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops); + + for (i = 0; i < nb_loops; i++) + domains[i] = NULL; ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0); for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) if (!loop_in_sese_p (loop_outer (loop), region)) - build_loop_iteration_domains (scop, loop, ph, 0); + build_loop_iteration_domains (scop, loop, ph, 0, domains); for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) - if (gbb_loop (PBB_BLACK_BOX (pbb))->aux) + if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]) ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t) - gbb_loop (PBB_BLACK_BOX (pbb))->aux); + domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]); else ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&PBB_DOMAIN (pbb), ph); - for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++) - if (loop->aux) - { - ppl_delete_Pointset_Powerset_C_Polyhedron - ((ppl_Pointset_Powerset_C_Polyhedron_t) loop->aux); - loop->aux = NULL; - } + for (i = 0; i < nb_loops; i++) + if (domains[i]) + ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]); ppl_delete_Polyhedron (ph); + free (domains); } /* Add a constrain to the ACCESSES polyhedron for the alias set of @@ -1631,7 +1615,7 @@ pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, int alias_set_num = 0; base_alias_pair *bap = (base_alias_pair *)(dr->aux); - if (bap != NULL && bap->alias_set != NULL) + if (bap && bap->alias_set) alias_set_num = *(bap->alias_set); ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims); @@ -1775,7 +1759,7 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) accesses); ppl_delete_Polyhedron (accesses); - if (dr->aux != NULL) + if (dr->aux) dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set; new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, @@ -1919,13 +1903,14 @@ build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs) { data_reference_p dr = VEC_index (data_reference_p, drs, i); base_alias_pair *bap; - if (dr->aux != NULL) + + if (dr->aux) bap = (base_alias_pair *)(dr->aux); + bap->alias_set = XNEW (int); *(bap->alias_set) = g->vertices[i].component + 1; } - /* Verify if the DFS numbering results in optimal solution. */ for (i = 0; i < num_connected_components; i++) { @@ -1977,7 +1962,6 @@ build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) struct graph *g = new_graph (num_vertex); data_reference_p dr1, dr2; int i, j; - int num_component; int *queue; for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) @@ -1992,14 +1976,16 @@ build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) for (i = 0; i < num_vertex; i++) queue[i] = i; - num_component = graphds_dfs (g, queue, num_vertex, NULL, true, NULL); + graphds_dfs (g, queue, num_vertex, NULL, true, NULL); for (i = 0; i < g->n_vertices; i++) { data_reference_p dr = VEC_index (data_reference_p, drs, i); base_alias_pair *bap; - if (dr->aux != NULL) + + if (dr->aux) bap = (base_alias_pair *)(dr->aux); + bap->base_obj_set = g->vertices[i].component + 1; } @@ -2020,6 +2006,42 @@ build_pbb_drs (poly_bb_p pbb) build_poly_dr (dr, pbb); } +/* Dump to file the alias graphs for the data references in DRS. */ + +static void +dump_alias_graphs (VEC (data_reference_p, heap) *drs) +{ + char comment[100]; + FILE *file_dimacs, *file_ecc, *file_dot; + + file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab"); + if (file_dimacs) + { + snprintf (comment, sizeof (comment), "%s %s", main_input_filename, + current_function_name ()); + write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs); + fclose (file_dimacs); + } + + file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab"); + if (file_ecc) + { + snprintf (comment, sizeof (comment), "%s %s", main_input_filename, + current_function_name ()); + write_alias_graph_to_ascii_ecc (file_ecc, comment, drs); + fclose (file_ecc); + } + + file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab"); + if (file_dot) + { + snprintf (comment, sizeof (comment), "%s %s", main_input_filename, + current_function_name ()); + write_alias_graph_to_ascii_dot (file_dot, comment, drs); + fclose (file_dot); + } +} + /* Build data references in SCOP. */ static void @@ -2048,37 +2070,8 @@ build_scop_drs (scop_p scop) /* When debugging, enable the following code. This cannot be used in production compilers. */ -#if 0 - { - char comment[100]; - FILE *file_dimacs, *file_ecc, *file_dot; - - file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab"); - file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab"); - file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab"); - if (file_dimacs) - { - snprintf (comment, sizeof (comment), "%s %s", main_input_filename, - current_function_name ()); - write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs); - fclose (file_dimacs); - } - if (file_ecc) - { - snprintf (comment, sizeof (comment), "%s %s", main_input_filename, - current_function_name ()); - write_alias_graph_to_ascii_ecc (file_ecc, comment, drs); - fclose (file_ecc); - } - if (file_dot) - { - snprintf (comment, sizeof (comment), "%s %s", main_input_filename, - current_function_name ()); - write_alias_graph_to_ascii_dot (file_dot, comment, drs); - fclose (file_dot); - } - } -#endif + if (0) + dump_alias_graphs (drs); VEC_free (data_reference_p, heap, drs); @@ -2154,12 +2147,12 @@ insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr) /* Creates a zero dimension array of the same type as VAR. */ static tree -create_zero_dim_array (tree var) +create_zero_dim_array (tree var, const char *base_name) { tree index_type = build_index_type (integer_zero_node); tree elt_type = TREE_TYPE (var); tree array_type = build_array_type (elt_type, index_type); - tree base = create_tmp_var (array_type, "Red"); + tree base = create_tmp_var (array_type, base_name); add_referenced_var (base); @@ -2188,12 +2181,16 @@ 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); + 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); tree arg = gimple_phi_arg_def (phi, 0); - insert_out_of_ssa_copy (zero_dim_array, arg); + if (TREE_CODE (arg) == SSA_NAME) + insert_out_of_ssa_copy (zero_dim_array, arg); + else + insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)), + zero_dim_array, arg); remove_phi_node (psi, false); gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); @@ -2211,7 +2208,7 @@ rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) basic_block bb = gimple_bb (phi); tree res = gimple_phi_result (phi); tree var = SSA_NAME_VAR (res); - tree zero_dim_array = create_zero_dim_array (var); + tree zero_dim_array = create_zero_dim_array (var, "General_Reduction"); gimple_stmt_iterator gsi; gimple stmt; gimple_seq stmts; @@ -2248,7 +2245,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 @@ -2358,7 +2355,8 @@ rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) { if (!zero_dim_array) { - zero_dim_array = create_zero_dim_array (SSA_NAME_VAR (def)); + zero_dim_array = create_zero_dim_array + (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence"); insert_out_of_ssa_copy (zero_dim_array, def); gsi_next (gsi); } @@ -2452,6 +2450,9 @@ split_reduction_stmt (gimple stmt) split_block (bb, stmt); + if (gsi_one_before_end_p (gsi_start_bb (bb))) + return bb; + gsi = gsi_last_bb (bb); gsi_prev (&gsi); e = split_block (bb, gsi_stmt (gsi)); @@ -2464,9 +2465,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. */ @@ -2495,6 +2501,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)) @@ -2502,6 +2512,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); @@ -2517,7 +2530,7 @@ follow_ssa_with_commutative_ops (tree arg, tree lhs) } /* Detect commutative and associative scalar reductions starting at - the STMT. */ + the STMT. Return the phi node of the reduction cycle, or NULL. */ static gimple detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg, @@ -2526,18 +2539,16 @@ detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg, { gimple phi = follow_ssa_with_commutative_ops (arg, lhs); - if (phi) - { - VEC_safe_push (gimple, heap, *in, stmt); - VEC_safe_push (gimple, heap, *out, stmt); - return phi; - } + if (!phi) + return NULL; - return NULL; + VEC_safe_push (gimple, heap, *in, stmt); + VEC_safe_push (gimple, heap, *out, stmt); + return phi; } /* Detect commutative and associative scalar reductions starting at - the STMT. */ + the STMT. Return the phi node of the reduction cycle, or NULL. */ static gimple detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in, @@ -2625,7 +2636,8 @@ initial_value_for_loop_phi (gimple phi) } /* Detect commutative and associative scalar reductions starting at - the loop closed phi node CLOSE_PHI. */ + the loop closed phi node CLOSE_PHI. Return the phi node of the + reduction cycle, or NULL. */ static gimple detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in, @@ -2634,8 +2646,13 @@ detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in, if (scalar_close_phi_node_p (stmt)) { tree arg = gimple_phi_arg_def (stmt, 0); - gimple def = SSA_NAME_DEF_STMT (arg); - gimple loop_phi = detect_commutative_reduction (def, in, out); + gimple def, loop_phi; + + if (TREE_CODE (arg) != SSA_NAME) + return NULL; + + def = SSA_NAME_DEF_STMT (arg); + loop_phi = detect_commutative_reduction (def, in, out); if (loop_phi) { @@ -2664,13 +2681,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); @@ -2734,7 +2751,8 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, SET_BIT (reductions, bb->index); gcc_assert (close_phi == loop_phi); - red = create_zero_dim_array (gimple_assign_lhs (stmt)); + red = create_zero_dim_array + (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction"); translate_scalar_reduction_to_array_for_stmt (red, stmt, VEC_index (gimple, in, 1)); continue; @@ -2808,6 +2826,45 @@ 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); +} + +/* 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); +} + /* Builds the polyhedral representation for a SESE region. */ bool @@ -2829,6 +2886,7 @@ build_poly_scop (scop_p scop) if (nb_pbbs_in_loops (scop) == 0) return false; + scop_canonicalize_loops (scop); build_sese_loop_nests (region); build_sese_conditions (region); find_scop_parameters (scop);