X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite-sese-to-poly.c;h=d9bcf2783072328368fd864c9924ead11824f097;hb=ba2f8f6bb45dad549b9ba03546ff5d1f2ff4bad7;hp=35a231655f12982f85389d7dee94d51c94be75be;hpb=041f1b343a876b88bd4c0c381c1c8de560f91450;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 35a231655f1..d9bcf278307 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -190,8 +190,7 @@ free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) { base_alias_pair *bap = (base_alias_pair *)(dr->aux); - if (bap->alias_set) - free (bap->alias_set); + free (bap->alias_set); free (bap); dr->aux = NULL; @@ -241,6 +240,32 @@ free_scops (VEC (scop_p, heap) *scops) VEC_free (scop_p, heap, scops); } +/* Same as outermost_loop_in_sese, returns the outermost loop + containing BB in REGION, but makes sure that the returned loop + belongs to the REGION, and so this returns the first loop in the + REGION when the loop containing BB does not belong to REGION. */ + +static loop_p +outermost_loop_in_sese_1 (sese region, basic_block bb) +{ + loop_p nest = outermost_loop_in_sese (region, bb); + + if (loop_in_sese_p (nest, region)) + return nest; + + /* When the basic block BB does not belong to a loop in the region, + return the first loop in the region. */ + nest = nest->inner; + while (nest) + if (loop_in_sese_p (nest, region)) + break; + else + nest = nest->next; + + gcc_assert (nest); + return nest; +} + /* Generates a polyhedral black box only if the bb contains interesting information. */ @@ -248,14 +273,23 @@ static gimple_bb_p try_generate_gimple_bb (scop_p scop, basic_block bb) { VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); - loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); + sese region = SCOP_REGION (scop); + loop_p nest = outermost_loop_in_sese_1 (region, bb); gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple stmt = gsi_stmt (gsi); - if (!is_gimple_debug (stmt)) - graphite_find_data_references_in_stmt (nest, stmt, &drs); + loop_p loop; + + if (is_gimple_debug (stmt)) + continue; + + loop = loop_containing_stmt (stmt); + if (!loop_in_sese_p (loop, region)) + loop = nest; + + graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); } return new_gimple_bb (bb, drs); @@ -1058,7 +1092,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one); mpz_clear (one); - if (estimated_loop_iterations (loop, true, &nit)) + if (max_stmt_executions (loop, true, &nit)) add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr); /* loop_i <= expr_nb_iters */ @@ -1686,7 +1720,7 @@ write_alias_graph_to_ascii_dimacs (FILE *file, char *comment, FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if (dr_may_alias_p (dr1, dr2, true)) edge_num++; fprintf (file, "$\n"); @@ -1698,7 +1732,7 @@ write_alias_graph_to_ascii_dimacs (FILE *file, char *comment, FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if (dr_may_alias_p (dr1, dr2, true)) fprintf (file, "e %d %d\n", i + 1, j + 1); return true; @@ -1728,7 +1762,7 @@ write_alias_graph_to_ascii_dot (FILE *file, char *comment, FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if (dr_may_alias_p (dr1, dr2, true)) fprintf (file, "n%d n%d\n", i, j); return true; @@ -1754,7 +1788,7 @@ write_alias_graph_to_ascii_ecc (FILE *file, char *comment, FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if (dr_may_alias_p (dr1, dr2, true)) fprintf (file, "%d %d\n", i, j); return true; @@ -1790,7 +1824,7 @@ build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs) FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1) for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if (dr_may_alias_p (dr1, dr2, true)) { add_edge (g, i, j); add_edge (g, j, i); @@ -2019,17 +2053,28 @@ analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts) gimple_bb_p gbb; gimple stmt; int i; + sese region = SCOP_REGION (scop); - if (!bb_in_sese_p (bb, SCOP_REGION (scop))) + if (!bb_in_sese_p (bb, region)) return; - nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); + nest = outermost_loop_in_sese_1 (region, bb); gbb = gbb_from_bb (bb); FOR_EACH_VEC_ELT (gimple, stmts, i, stmt) - if (!is_gimple_debug (stmt)) - graphite_find_data_references_in_stmt (nest, stmt, + { + loop_p loop; + + if (is_gimple_debug (stmt)) + continue; + + loop = loop_containing_stmt (stmt); + if (!loop_in_sese_p (loop, region)) + loop = nest; + + graphite_find_data_references_in_stmt (nest, loop, stmt, &GBB_DATA_REFS (gbb)); + } } /* Insert STMT at the end of the STMTS sequence and then insert the @@ -2106,9 +2151,11 @@ new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb) if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb) break; + if (PBB_DOMAIN (pbb)) + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb)); + GBB_PBB (gbb1) = pbb1; - ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron - (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb)); GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb)); GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb)); VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1); @@ -2850,6 +2897,30 @@ initial_value_for_loop_phi (gimple phi) return NULL_TREE; } +/* Returns true when DEF is used outside the reduction cycle of + LOOP_PHI. */ + +static bool +used_outside_reduction (tree def, gimple loop_phi) +{ + use_operand_p use_p; + imm_use_iterator imm_iter; + loop_p loop = loop_containing_stmt (loop_phi); + + /* In LOOP, DEF should be used only in LOOP_PHI. */ + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) + { + gimple stmt = USE_STMT (use_p); + + if (stmt != loop_phi + && !is_gimple_debug (stmt) + && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) + return true; + } + + return false; +} + /* Detect commutative and associative scalar reductions belonging to the SCOP starting at the loop closed phi node STMT. Return the phi node of the reduction cycle, or NULL. */ @@ -2860,8 +2931,8 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, { if (scalar_close_phi_node_p (stmt)) { - tree arg = gimple_phi_arg_def (stmt, 0); - gimple def, loop_phi; + gimple def, loop_phi, phi, close_phi = stmt; + tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0); if (TREE_CODE (arg) != SSA_NAME) return NULL; @@ -2869,26 +2940,24 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, /* 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 (stmt) == 1); + gcc_assert (gimple_phi_num_args (close_phi) == 1); def = SSA_NAME_DEF_STMT (arg); - if (!stmt_in_sese_p (def, SCOP_REGION (scop))) + if (!stmt_in_sese_p (def, SCOP_REGION (scop)) + || !(loop_phi = detect_commutative_reduction (scop, def, in, out))) return NULL; - loop_phi = detect_commutative_reduction (scop, def, in, out); - - if (loop_phi) - { - tree lhs = gimple_phi_result (stmt); - tree init = initial_value_for_loop_phi (loop_phi); - gimple phi = follow_inital_value_to_phi (init, lhs); + lhs = gimple_phi_result (close_phi); + init = initial_value_for_loop_phi (loop_phi); + phi = follow_inital_value_to_phi (init, lhs); - VEC_safe_push (gimple, heap, *in, loop_phi); - VEC_safe_push (gimple, heap, *out, stmt); - return phi; - } - else + if (phi && (used_outside_reduction (lhs, phi) + || !has_single_use (gimple_phi_result (phi)))) return NULL; + + VEC_safe_push (gimple, heap, *in, loop_phi); + VEC_safe_push (gimple, heap, *out, close_phi); + return phi; } if (gimple_code (stmt) == GIMPLE_ASSIGN) @@ -2951,6 +3020,35 @@ remove_phi (gimple phi) remove_phi_node (&gsi, false); } +/* Helper function for for_each_index. For each INDEX of the data + reference REF, returns true when its indices are valid in the loop + nest LOOP passed in as DATA. */ + +static bool +dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED, tree *index, void *data) +{ + loop_p loop; + basic_block header, def_bb; + gimple stmt; + + if (TREE_CODE (*index) != SSA_NAME) + return true; + + loop = *((loop_p *) data); + header = loop->header; + stmt = SSA_NAME_DEF_STMT (*index); + + if (!stmt) + return true; + + def_bb = gimple_bb (stmt); + + if (!def_bb) + return true; + + return dominated_by_p (CDI_DOMINATORS, header, def_bb); +} + /* When the result of a CLOSE_PHI is written to a memory location, return a pointer to that memory reference, otherwise return NULL_TREE. */ @@ -2959,21 +3057,40 @@ static tree close_phi_written_to_memory (gimple close_phi) { imm_use_iterator imm_iter; - tree res, def = gimple_phi_result (close_phi); use_operand_p use_p; gimple stmt; + tree res, def = gimple_phi_result (close_phi); FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) if ((stmt = USE_STMT (use_p)) && gimple_code (stmt) == GIMPLE_ASSIGN - && (res = gimple_assign_lhs (stmt)) - && (TREE_CODE (res) == ARRAY_REF - || TREE_CODE (res) == MEM_REF - || TREE_CODE (res) == VAR_DECL - || TREE_CODE (res) == PARM_DECL - || TREE_CODE (res) == RESULT_DECL)) - return res; + && (res = gimple_assign_lhs (stmt))) + { + switch (TREE_CODE (res)) + { + case VAR_DECL: + case PARM_DECL: + case RESULT_DECL: + return res; + + case ARRAY_REF: + case MEM_REF: + { + tree arg = gimple_phi_arg_def (close_phi, 0); + loop_p nest = loop_containing_stmt (SSA_NAME_DEF_STMT (arg)); + + /* FIXME: this restriction is for id-{24,25}.f and + could be handled by duplicating the computation of + array indices before the loop of the close_phi. */ + if (for_each_index (&res, dr_indices_valid_in_loop, &nest)) + return res; + } + /* Fallthru. */ + default: + continue; + } + } return NULL_TREE; } @@ -3043,7 +3160,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop, VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); detect_commutative_reduction (scop, close_phi, &in, &out); - res = VEC_length (gimple, in) > 0; + res = VEC_length (gimple, in) > 1; if (res) translate_scalar_reduction_to_array (scop, in, out); @@ -3102,9 +3219,6 @@ rewrite_commutative_reductions_out_of_ssa (scop_p scop) } } -/* 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. */ @@ -3129,7 +3243,7 @@ scop_ivs_can_be_represented (scop_p scop) tree type = TREE_TYPE (res); if (TYPE_UNSIGNED (type) - && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long)) + && TYPE_PRECISION (type) >= TYPE_PRECISION (long_long_integer_type_node)) return false; } } @@ -3137,8 +3251,6 @@ scop_ivs_can_be_represented (scop_p scop) return true; } -#undef my_long_long - /* Builds the polyhedral representation for a SESE region. */ void @@ -3159,6 +3271,9 @@ build_poly_scop (scop_p scop) if (!scop_ivs_can_be_represented (scop)) return; + if (flag_associative_math) + rewrite_commutative_reductions_out_of_ssa (scop); + build_sese_loop_nests (region); build_sese_conditions (region); find_scop_parameters (scop); @@ -3175,8 +3290,6 @@ build_poly_scop (scop_p scop) representation to the polyhedral representation to avoid scev analysis failures. That means that these functions will insert new data references that they create in the right place. */ - if (flag_associative_math) - rewrite_commutative_reductions_out_of_ssa (scop); rewrite_reductions_out_of_ssa (scop); rewrite_cross_bb_scalar_deps_out_of_ssa (scop);