diff options
| -rw-r--r-- | gcc/ChangeLog | 53 | ||||
| -rw-r--r-- | gcc/ChangeLog.graphite | 55 | ||||
| -rw-r--r-- | gcc/graphite-poly.c | 10 | ||||
| -rw-r--r-- | gcc/graphite-poly.h | 18 | ||||
| -rw-r--r-- | gcc/graphite-sese-to-poly.c | 347 | ||||
| -rw-r--r-- | gcc/graphite-sese-to-poly.h | 4 | ||||
| -rw-r--r-- | gcc/graphite.c | 29 | ||||
| -rw-r--r-- | gcc/sese.h | 10 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 5 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/pr45297.c | 9 |
10 files changed, 337 insertions, 203 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cd8f8368c67..7540273c999 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,58 @@ 2010-12-01 Sebastian Pop <sebastian.pop@amd.com> + PR middle-end/45297 + * graphite-poly.c (new_poly_bb): Returns a poly_bb_p. Do not take + the reduction bool in parameter. Clear PBB_IS_REDUCTION. Set GBB_PBB. + * graphite-poly.h (new_poly_bb): Update declaration. + (gbb_from_bb): Moved here... + (pbb_from_bb): New. + * graphite-sese-to-poly.c (var_used_in_not_loop_header_phi_node): + Removed. + (graphite_stmt_p): Removed. + (try_generate_gimple_bb): Returns a gimple_bb_p. Do not pass in + sbitmap reductions. Always build a gimple_bb_p. Do not call + new_poly_bb. + (build_scop_bbs_1): Do not pass in sbitmap reductions. + (build_scop_bbs): Same. + (gbb_from_bb): ... from here. + (add_conditions_to_constraints): Moved up. + (analyze_drs): New. + (build_scop_drs): Call analyze_drs. Remove all the PBBs that do + not contain data references. + (new_pbb_from_pbb): New. + (insert_out_of_ssa_copy_on_edge): Call new_pbb_from_pbb after a + block is split. + (rewrite_close_phi_out_of_ssa): Update call to + insert_out_of_ssa_copy_on_edge. + (rewrite_reductions_out_of_ssa): Now static. + (rewrite_cross_bb_scalar_deps_out_of_ssa): Same. + (split_pbb): New. + (split_reduction_stmt): Call split_pbb. + (translate_scalar_reduction_to_array): Pass in the scop, do not + pass in the sbitmap reductions. + (rewrite_commutative_reductions_out_of_ssa_close_phi): Same. + (rewrite_commutative_reductions_out_of_ssa_loop): Same. + (rewrite_commutative_reductions_out_of_ssa): Same. + (build_poly_scop): Call build_scop_bbs, + rewrite_commutative_reductions_out_of_ssa, + rewrite_reductions_out_of_ssa, and + rewrite_cross_bb_scalar_deps_out_of_ssa. Move build_scop_drs + before scop_to_lst. + * graphite-sese-to-poly.h (rewrite_commutative_reductions_out_of_ssa): + Removed declaration. + (rewrite_reductions_out_of_ssa): Same. + (rewrite_cross_bb_scalar_deps_out_of_ssa): Same. + (build_scop_bbs): Same. + * graphite.c (graphite_transform_loops): Do not initialize reductions. + Do not call build_scop_bbs, + rewrite_commutative_reductions_out_of_ssa, + rewrite_reductions_out_of_ssa, and + rewrite_cross_bb_scalar_deps_out_of_ssa. + * sese.h (struct gimple_bb): Add field pbb. + (GBB_PBB): New. + +2010-12-01 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (handle_scalar_deps_crossing_scop_limits): New. (rewrite_cross_bb_scalar_deps): Pass in the scop. Call diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 08a48477d05..4461ade8893 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,5 +1,60 @@ 2010-11-22 Sebastian Pop <sebastian.pop@amd.com> + PR middle-end/45297 + * graphite-poly.c (new_poly_bb): Returns a poly_bb_p. Do not take + the reduction bool in parameter. Clear PBB_IS_REDUCTION. Set GBB_PBB. + * graphite-poly.h (new_poly_bb): Update declaration. + (gbb_from_bb): Moved here... + (pbb_from_bb): New. + * graphite-sese-to-poly.c (var_used_in_not_loop_header_phi_node): + Removed. + (graphite_stmt_p): Removed. + (try_generate_gimple_bb): Returns a gimple_bb_p. Do not pass in + sbitmap reductions. Always build a gimple_bb_p. Do not call + new_poly_bb. + (build_scop_bbs_1): Do not pass in sbitmap reductions. + (build_scop_bbs): Same. + (gbb_from_bb): ... from here. + (add_conditions_to_constraints): Moved up. + (analyze_drs): New. + (build_scop_drs): Call analyze_drs. Remove all the PBBs that do + not contain data references. + (new_pbb_from_pbb): New. + (insert_out_of_ssa_copy_on_edge): Call new_pbb_from_pbb after a + block is split. + (rewrite_close_phi_out_of_ssa): Update call to + insert_out_of_ssa_copy_on_edge. + (rewrite_reductions_out_of_ssa): Now static. + (rewrite_cross_bb_scalar_deps_out_of_ssa): Same. + (split_pbb): New. + (split_reduction_stmt): Call split_pbb. + (translate_scalar_reduction_to_array): Pass in the scop, do not + pass in the sbitmap reductions. + (rewrite_commutative_reductions_out_of_ssa_close_phi): Same. + (rewrite_commutative_reductions_out_of_ssa_loop): Same. + (rewrite_commutative_reductions_out_of_ssa): Same. + (build_poly_scop): Call build_scop_bbs, + rewrite_commutative_reductions_out_of_ssa, + rewrite_reductions_out_of_ssa, and + rewrite_cross_bb_scalar_deps_out_of_ssa. Move build_scop_drs + before scop_to_lst. + * graphite-sese-to-poly.h (rewrite_commutative_reductions_out_of_ssa): + Removed declaration. + (rewrite_reductions_out_of_ssa): Same. + (rewrite_cross_bb_scalar_deps_out_of_ssa): Same. + (build_scop_bbs): Same. + * graphite.c (graphite_transform_loops): Do not initialize reductions. + Do not call build_scop_bbs, + rewrite_commutative_reductions_out_of_ssa, + rewrite_reductions_out_of_ssa, and + rewrite_cross_bb_scalar_deps_out_of_ssa. + * sese.h (struct gimple_bb): Add field pbb. + (GBB_PBB): New. + + * gcc.dg/graphite/pr45297.c: New. + +2010-11-22 Sebastian Pop <sebastian.pop@amd.com> + * graphite-sese-to-poly.c (handle_scalar_deps_crossing_scop_limits): New. (rewrite_cross_bb_scalar_deps): Pass in the scop. Call diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 4f5a437dd1e..9416cd754f8 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -874,8 +874,8 @@ free_poly_dr (poly_dr_p pdr) /* Create a new polyhedral black box. */ -void -new_poly_bb (scop_p scop, void *black_box, bool reduction) +poly_bb_p +new_poly_bb (scop_p scop, void *black_box) { poly_bb_p pbb = XNEW (struct poly_bb); @@ -886,9 +886,11 @@ new_poly_bb (scop_p scop, void *black_box, bool reduction) PBB_SAVED (pbb) = NULL; PBB_ORIGINAL (pbb) = NULL; PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3); - PBB_IS_REDUCTION (pbb) = reduction; + PBB_IS_REDUCTION (pbb) = false; PBB_PDR_DUPLICATES_REMOVED (pbb) = false; - VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb); + GBB_PBB ((gimple_bb_p) black_box) = pbb; + + return pbb; } /* Free polyhedral black box. */ diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index 4a2f25cd227..8be905ef921 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -389,7 +389,7 @@ struct poly_bb #define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed) #define PBB_IS_REDUCTION(PBB) (PBB->is_reduction) -extern void new_poly_bb (scop_p, void *, bool); +extern poly_bb_p new_poly_bb (scop_p, void *); extern void free_poly_bb (poly_bb_p); extern void debug_loop_vec (poly_bb_p); extern void schedule_to_scattering (poly_bb_p, int); @@ -434,6 +434,22 @@ number_of_write_pdrs (poly_bb_p pbb) return res; } +/* Returns a gimple_bb from BB. */ + +static inline gimple_bb_p +gbb_from_bb (basic_block bb) +{ + return (gimple_bb_p) bb->aux; +} + +/* The poly_bb of the BB. */ + +static inline poly_bb_p +pbb_from_bb (basic_block bb) +{ + return GBB_PBB (gbb_from_bb (bb)); +} + /* The basic block of the PBB. */ static inline basic_block diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 1697e630385..badd25f41f9 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -49,27 +49,6 @@ along with GCC; see the file COPYING3. If not see #include "graphite-scop-detection.h" #include "graphite-sese-to-poly.h" -/* Check if VAR is used in a phi node, that is no loop header. */ - -static bool -var_used_in_not_loop_header_phi_node (tree var) -{ - imm_use_iterator imm_iter; - gimple stmt; - bool result = false; - - FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var) - { - basic_block bb = gimple_bb (stmt); - - if (gimple_code (stmt) == GIMPLE_PHI - && bb->loop_father->header != bb) - result = true; - } - - return result; -} - /* Returns the index of the PHI argument defined in the outermost loop. */ @@ -196,58 +175,6 @@ reduction_phi_p (sese region, gimple_stmt_iterator *psi) return true; } -/* Returns true when BB will be represented in graphite. Return false - for the basic blocks that contain code eliminated in the code - generation pass: i.e. induction variables and exit conditions. */ - -static bool -graphite_stmt_p (sese region, basic_block bb, - VEC (data_reference_p, heap) *drs) -{ - gimple_stmt_iterator gsi; - loop_p loop = bb->loop_father; - - if (VEC_length (data_reference_p, drs) > 0) - return true; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple stmt = gsi_stmt (gsi); - - switch (gimple_code (stmt)) - { - case GIMPLE_DEBUG: - /* Control flow expressions can be ignored, as they are - represented in the iteration domains and will be - regenerated by graphite. */ - case GIMPLE_COND: - case GIMPLE_GOTO: - case GIMPLE_SWITCH: - break; - - case GIMPLE_ASSIGN: - { - tree var = gimple_assign_lhs (stmt); - - /* We need these bbs to be able to construct the phi nodes. */ - if (var_used_in_not_loop_header_phi_node (var)) - return true; - - var = scalar_evolution_in_region (region, loop, var); - if (chrec_contains_undetermined (var)) - return true; - - break; - } - - default: - return true; - } - } - - return false; -} - /* Store the GRAPHITE representation of BB. */ static gimple_bb_p @@ -330,8 +257,8 @@ free_scops (VEC (scop_p, heap) *scops) /* Generates a polyhedral black box only if the bb contains interesting information. */ -static void -try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions) +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); @@ -344,11 +271,7 @@ try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions) graphite_find_data_references_in_stmt (nest, stmt, &drs); } - if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs)) - free_data_refs (drs); - else - new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions, - bb->index)); + return new_gimple_bb (bb, drs); } /* Returns true if all predecessors of BB, that are not dominated by BB, are @@ -400,16 +323,18 @@ graphite_sort_dominated_info (VEC (basic_block, heap) *dom) /* Recursive helper function for build_scops_bbs. */ static void -build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions) +build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb) { sese region = SCOP_REGION (scop); VEC (basic_block, heap) *dom; + poly_bb_p pbb; if (TEST_BIT (visited, bb->index) || !bb_in_sese_p (bb, region)) return; - try_generate_gimple_bb (scop, bb, reductions); + pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb)); + VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb); SET_BIT (visited, bb->index); dom = get_dominated_by (CDI_DOMINATORS, bb); @@ -427,7 +352,7 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductio FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb) if (all_non_dominated_preds_marked_p (dom_bb, visited)) { - build_scop_bbs_1 (scop, visited, dom_bb, reductions); + build_scop_bbs_1 (scop, visited, dom_bb); VEC_unordered_remove (basic_block, dom, i); break; } @@ -438,14 +363,14 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductio /* Gather the basic blocks belonging to the SCOP. */ -void -build_scop_bbs (scop_p scop, sbitmap reductions) +static void +build_scop_bbs (scop_p scop) { sbitmap visited = sbitmap_alloc (last_basic_block); sese region = SCOP_REGION (scop); sbitmap_zero (visited); - build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions); + build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region)); sbitmap_free (visited); } @@ -1004,14 +929,6 @@ find_scop_parameters (scop_p scop) (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0); } -/* Returns a gimple_bb from BB. */ - -static inline gimple_bb_p -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 @@ -1348,6 +1265,19 @@ add_conditions_to_domain (poly_bb_p pbb) } } +/* Traverses all the GBBs of the SCOP and add their constraints to the + iteration domains. */ + +static void +add_conditions_to_constraints (scop_p scop) +{ + int i; + poly_bb_p pbb; + + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) + add_conditions_to_domain (pbb); +} + /* Structure used to pass data to dom_walk. */ struct bsc @@ -1470,19 +1400,6 @@ build_sese_conditions (sese region) VEC_free (gimple, heap, cases); } -/* Traverses all the GBBs of the SCOP and add their constraints to the - iteration domains. */ - -static void -add_conditions_to_constraints (scop_p scop) -{ - int i; - poly_bb_p pbb; - - FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) - add_conditions_to_domain (pbb); -} - /* Add constraints on the possible values of parameter P from the type of P. */ @@ -1950,7 +1867,7 @@ build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs) return all_components_are_cliques; } -/* Group each data reference in DRS with it's base object set num. */ +/* Group each data reference in DRS with its base object set num. */ static void build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) @@ -2039,6 +1956,36 @@ dump_alias_graphs (VEC (data_reference_p, heap) *drs) } } +/* Recompute all the data references of BB and add them to the + GBB_DATA_REFS vector. */ + +static void +analyze_drs (scop_p scop, basic_block bb) +{ + loop_p nest; + poly_bb_p pbb; + gimple_stmt_iterator gsi; + gimple_bb_p gbb; + + if (!bb_in_sese_p (bb, SCOP_REGION (scop))) + return; + + nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); + pbb = pbb_from_bb (bb); + gbb = PBB_BLACK_BOX (pbb); + + VEC_free (data_reference_p, heap, GBB_DATA_REFS (gbb)); + GBB_DATA_REFS (gbb) = VEC_alloc (data_reference_p, heap, 3); + + 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, + &GBB_DATA_REFS (gbb)); + } +} + /* Build data references in SCOP. */ static void @@ -2049,6 +1996,18 @@ build_scop_drs (scop_p scop) data_reference_p dr; VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); + /* Remove all the PBBs that do not have data references: these basic + blocks are not handled in the polyhedral representation. */ + for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) + { + analyze_drs (scop, GBB_BB (PBB_BLACK_BOX (pbb))); + if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb)))) + { + VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i); + i--; + } + } + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb) for (j = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++) @@ -2092,18 +2051,17 @@ gsi_for_phi_node (gimple stmt) return psi; } -/* Insert the assignment "RES := VAR" just after AFTER_STMT. */ +/* Insert the assignment "RES := EXPR" just after AFTER_STMT. */ static void -insert_out_of_ssa_copy (tree res, tree var, gimple after_stmt) +insert_out_of_ssa_copy (tree res, tree expr, gimple after_stmt) { - gimple stmt; gimple_seq stmts; gimple_stmt_iterator si; gimple_stmt_iterator gsi; + tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); + gimple stmt = gimple_build_assign (res, var); - var = force_gimple_operand (var, &stmts, true, NULL_TREE); - stmt = gimple_build_assign (res, var); if (!stmts) stmts = gimple_seq_alloc (); si = gsi_last (stmts); @@ -2121,15 +2079,40 @@ insert_out_of_ssa_copy (tree res, tree var, gimple after_stmt) } } +/* Creates a poly_bb_p for basic_block BB from the existing PBB. */ + +static void +new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb) +{ + VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + gimple_bb_p gbb1 = new_gimple_bb (bb, drs); + poly_bb_p pbb1 = new_poly_bb (scop, gbb1); + int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop)); + + /* The INDEX of PBB in SCOP_BBS. */ + for (index = 0; index < n; index++) + if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb) + break; + + 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); +} + /* Insert on edge E the assignment "RES := EXPR". */ static void -insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr) +insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr) { gimple_stmt_iterator gsi; gimple_seq stmts; tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE); gimple stmt = gimple_build_assign (res, var); + basic_block bb; if (!stmts) stmts = gimple_seq_alloc (); @@ -2138,6 +2121,13 @@ insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr) gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); gsi_insert_seq_on_edge (e, stmts); gsi_commit_edge_inserts (); + bb = gimple_bb (stmt); + + if (!bb_in_sese_p (bb, SCOP_REGION (scop))) + return; + + if (!gbb_from_bb (bb)) + new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb); } /* Creates a zero dimension array of the same type as VAR. */ @@ -2213,8 +2203,9 @@ propagate_expr_outside_region (tree def, tree expr, sese region) dimension array for it. */ static void -rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region) +rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi) { + sese region = SCOP_REGION (scop); gimple phi = gsi_stmt (*psi); tree res = gimple_phi_result (phi); tree var = SSA_NAME_VAR (res); @@ -2278,9 +2269,10 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region) stmt = gimple_build_assign (res, zero_dim_array); if (TREE_CODE (arg) == SSA_NAME) - insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (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), + insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb), zero_dim_array, arg); } @@ -2293,7 +2285,7 @@ rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region) dimension array for it. */ static void -rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) +rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi) { size_t i; gimple phi = gsi_stmt (*psi); @@ -2314,9 +2306,10 @@ rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) pattern matching of the vectorizer. */ if (TREE_CODE (arg) == SSA_NAME && e->src == bb->loop_father->latch) - insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg)); + insert_out_of_ssa_copy (zero_dim_array, arg, + SSA_NAME_DEF_STMT (arg)); else - insert_out_of_ssa_copy_on_edge (e, zero_dim_array, arg); + insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg); } var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE); @@ -2362,7 +2355,7 @@ rewrite_degenerate_phi (gimple_stmt_iterator *psi) /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ -void +static void rewrite_reductions_out_of_ssa (scop_p scop) { basic_block bb; @@ -2386,10 +2379,10 @@ rewrite_reductions_out_of_ssa (scop_p scop) rewrite_degenerate_phi (&psi); else if (scalar_close_phi_node_p (phi)) - rewrite_close_phi_out_of_ssa (&psi, region); + rewrite_close_phi_out_of_ssa (scop, &psi); else if (reduction_phi_p (region, &psi)) - rewrite_phi_out_of_ssa (&psi); + rewrite_phi_out_of_ssa (scop, &psi); } update_ssa (TODO_update_ssa); @@ -2402,7 +2395,8 @@ rewrite_reductions_out_of_ssa (scop_p scop) read from ZERO_DIM_ARRAY. */ static void -rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt) +rewrite_cross_bb_scalar_dependence (tree zero_dim_array, + tree def, gimple use_stmt) { tree var = SSA_NAME_VAR (def); gimple name_stmt = gimple_build_assign (var, zero_dim_array); @@ -2525,9 +2519,9 @@ rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi) gimple_stmt_iterator psi = gsi_for_stmt (use_stmt); if (scalar_close_phi_node_p (gsi_stmt (psi))) - rewrite_close_phi_out_of_ssa (&psi, region); + rewrite_close_phi_out_of_ssa (scop, &psi); else - rewrite_phi_out_of_ssa (&psi); + rewrite_phi_out_of_ssa (scop, &psi); } FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) @@ -2545,7 +2539,8 @@ rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi) gsi_next (gsi); } - rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt); + rewrite_cross_bb_scalar_dependence (zero_dim_array, + def, use_stmt); } return res; @@ -2553,7 +2548,7 @@ rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi) /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ -void +static void rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop) { basic_block bb; @@ -2612,30 +2607,44 @@ nb_data_writes_in_bb (basic_block bb) return res; } -/* Splits STMT out of its current BB. */ +/* Splits at STMT the basic block BB represented as PBB in the + polyhedral form. */ + +static edge +split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt) +{ + edge e1 = split_block (bb, stmt); + new_pbb_from_pbb (scop, pbb, e1->dest); + return e1; +} + +/* Splits STMT out of its current BB. This is done for reduction + statements for which we want to ignore data dependences. */ static basic_block -split_reduction_stmt (gimple stmt) +split_reduction_stmt (scop_p scop, gimple stmt) { - gimple_stmt_iterator gsi; basic_block bb = gimple_bb (stmt); - edge e; + poly_bb_p pbb = pbb_from_bb (bb); + edge e1; /* Do not split basic blocks with no writes to memory: the reduction will be the only write to memory. */ if (nb_data_writes_in_bb (bb) == 0) return bb; - split_block (bb, stmt); + e1 = split_pbb (scop, pbb, 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)); + /* Split once more only when the reduction stmt is not the only one + left in the original BB. */ + if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb))) + { + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_prev (&gsi); + e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi)); + } - return e->dest; + return e1->dest; } /* Return true when stmt is a reduction operation. */ @@ -2864,13 +2873,12 @@ static void translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt, gimple loop_phi) { - 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); + gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi)); 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); @@ -2922,9 +2930,9 @@ remove_phi (gimple phi) are the loop and close phi nodes of each of the outer loops. */ static void -translate_scalar_reduction_to_array (VEC (gimple, heap) *in, - VEC (gimple, heap) *out, - sbitmap reductions) +translate_scalar_reduction_to_array (scop_p scop, + VEC (gimple, heap) *in, + VEC (gimple, heap) *out) { unsigned int i; gimple loop_phi; @@ -2937,9 +2945,9 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, if (i == 0) { gimple stmt = loop_phi; - basic_block bb = split_reduction_stmt (stmt); - - SET_BIT (reductions, bb->index); + basic_block bb = split_reduction_stmt (scop, stmt); + poly_bb_p pbb = pbb_from_bb (bb); + PBB_IS_REDUCTION (pbb) = true; gcc_assert (close_phi == loop_phi); red = create_zero_dim_array @@ -2954,7 +2962,7 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, insert_out_of_ssa_copy (gimple_phi_result (close_phi), red, close_phi); insert_out_of_ssa_copy_on_edge - (edge_initial_value_for_loop_phi (loop_phi), + (scop, edge_initial_value_for_loop_phi (loop_phi), red, initial_value_for_loop_phi (loop_phi)); } @@ -2967,8 +2975,8 @@ translate_scalar_reduction_to_array (VEC (gimple, heap) *in, true when something has been changed. */ static bool -rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, - sbitmap reductions) +rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop, + gimple close_phi) { bool res; VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10); @@ -2977,7 +2985,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, detect_commutative_reduction (close_phi, &in, &out); res = VEC_length (gimple, in) > 0; if (res) - translate_scalar_reduction_to_array (in, out, reductions); + translate_scalar_reduction_to_array (scop, in, out); VEC_free (gimple, heap, in); VEC_free (gimple, heap, out); @@ -2988,9 +2996,8 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, Returns true when something has been changed. */ static bool -rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop, - sbitmap reductions, - sese region) +rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop, + loop_p loop) { gimple_stmt_iterator gsi; edge exit = single_exit (loop); @@ -3003,30 +3010,26 @@ rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop, for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi)) if ((res = gimple_phi_result (gsi_stmt (gsi))) && is_gimple_reg (res) - && !scev_analyzable_p (res, region)) + && !scev_analyzable_p (res, SCOP_REGION (scop))) changed |= rewrite_commutative_reductions_out_of_ssa_close_phi - (gsi_stmt (gsi), reductions); + (scop, gsi_stmt (gsi)); return changed; } /* Rewrites all the commutative reductions from SCOP out of SSA. */ -void -rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions) +static void +rewrite_commutative_reductions_out_of_ssa (scop_p scop) { loop_iterator li; loop_p loop; bool changed = false; - - if (!flag_associative_math) - return; + sese region = SCOP_REGION (scop); FOR_EACH_LOOP (li, loop, 0) if (loop_in_sese_p (loop, region)) - changed |= rewrite_commutative_reductions_out_of_ssa_loop (loop, - reductions, - region); + changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop); if (changed) { @@ -3084,6 +3087,7 @@ build_poly_scop (scop_p scop) sese region = SCOP_REGION (scop); graphite_dim_t max_dim; + build_scop_bbs (scop); /* FIXME: This restriction is needed to avoid a problem in CLooG. Once CLooG is fixed, remove this guard. Anyways, it makes no @@ -3105,11 +3109,20 @@ build_poly_scop (scop_p scop) build_scop_iteration_domain (scop); build_scop_context (scop); - add_conditions_to_constraints (scop); + + /* Rewrite out of SSA only after having translated the + 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); + + build_scop_drs (scop); scop_to_lst (scop); build_scop_scattering (scop); - build_scop_drs (scop); /* This SCoP has been translated to the polyhedral representation. */ diff --git a/gcc/graphite-sese-to-poly.h b/gcc/graphite-sese-to-poly.h index b0053d023e5..d341c0fa4b7 100644 --- a/gcc/graphite-sese-to-poly.h +++ b/gcc/graphite-sese-to-poly.h @@ -29,9 +29,5 @@ struct base_alias_pair }; void build_poly_scop (scop_p); -void rewrite_commutative_reductions_out_of_ssa (sese, sbitmap); -void rewrite_reductions_out_of_ssa (scop_p); -void rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p); -void build_scop_bbs (scop_p, sbitmap); #endif diff --git a/gcc/graphite.c b/gcc/graphite.c index 74b671d1279..4ce484afdad 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -262,7 +262,6 @@ graphite_transform_loops (void) bool need_cfg_cleanup_p = false; VEC (scop_p, heap) *scops = NULL; htab_t bb_pbb_mapping; - sbitmap reductions; if (!graphite_initialize ()) return; @@ -276,33 +275,17 @@ graphite_transform_loops (void) } bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); - reductions = sbitmap_alloc (last_basic_block * 2); - sbitmap_zero (reductions); - - FOR_EACH_VEC_ELT (scop_p, scops, i, scop) - if (dbg_cnt (graphite_scop)) - rewrite_commutative_reductions_out_of_ssa (SCOP_REGION (scop), - reductions); FOR_EACH_VEC_ELT (scop_p, scops, i, scop) if (dbg_cnt (graphite_scop)) { - rewrite_reductions_out_of_ssa (scop); - rewrite_cross_bb_scalar_deps_out_of_ssa (scop); - build_scop_bbs (scop, reductions); - } - - sbitmap_free (reductions); + build_poly_scop (scop); - FOR_EACH_VEC_ELT (scop_p, scops, i, scop) - if (dbg_cnt (graphite_scop)) - build_poly_scop (scop); - - FOR_EACH_VEC_ELT (scop_p, scops, i, scop) - if (POLY_SCOP_P (scop) - && apply_poly_transforms (scop) - && gloog (scop, bb_pbb_mapping)) - need_cfg_cleanup_p = true; + if (POLY_SCOP_P (scop) + && apply_poly_transforms (scop) + && gloog (scop, bb_pbb_mapping)) + need_cfg_cleanup_p = true; + } htab_delete (bb_pbb_mapping); free_scops (scops); diff --git a/gcc/sese.h b/gcc/sese.h index 61f3a17b9b7..10bf874a174 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -312,6 +312,7 @@ recompute_all_dominators (void) typedef struct gimple_bb { basic_block bb; + struct poly_bb *pbb; /* Lists containing the restrictions of the conditional statements dominating this bb. This bb can only be executed, if all conditions @@ -338,10 +339,11 @@ typedef struct gimple_bb VEC (data_reference_p, heap) *data_refs; } *gimple_bb_p; -#define GBB_BB(GBB) GBB->bb -#define GBB_DATA_REFS(GBB) GBB->data_refs -#define GBB_CONDITIONS(GBB) GBB->conditions -#define GBB_CONDITION_CASES(GBB) GBB->condition_cases +#define GBB_BB(GBB) (GBB)->bb +#define GBB_PBB(GBB) (GBB)->pbb +#define GBB_DATA_REFS(GBB) (GBB)->data_refs +#define GBB_CONDITIONS(GBB) (GBB)->conditions +#define GBB_CONDITION_CASES(GBB) (GBB)->condition_cases /* Return the innermost loop that contains the basic block GBB. */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 55f33a1068e..08e7788dd20 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2010-11-29 Sebastian Pop <sebastian.pop@amd.com> + + PR middle-end/45297 + * gcc.dg/graphite/pr45297.c: New. + 2010-12-01 Richard Guenther <rguenther@suse.de> PR tree-optimization/46730 diff --git a/gcc/testsuite/gcc.dg/graphite/pr45297.c b/gcc/testsuite/gcc.dg/graphite/pr45297.c new file mode 100644 index 00000000000..faa653a5779 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr45297.c @@ -0,0 +1,9 @@ +/* { dg-options "-Os -fgraphite-identity" } */ + +void +foo (int *p) +{ + int *q = p + 1024; + while (q != p) + *--q = *--q; +} |