X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite-sese-to-poly.c;h=3be2d8603912cb76e4e17697160f7211eba387ce;hb=c1630d65d745a592779683d793933220559986d9;hp=c6d82eeaa46978bc876ae859e91a71b1a61f53c5;hpb=19b42529ceeca3b4536cf667b12d739e1e5dc9e6;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index c6d82eeaa46..3be2d860391 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -57,7 +57,6 @@ along with GCC; see the file COPYING3. If not see static bool var_used_in_not_loop_header_phi_node (tree var) { - imm_use_iterator imm_iter; gimple stmt; bool result = false; @@ -194,7 +193,11 @@ reduction_phi_p (sese region, gimple_stmt_iterator *psi) reductions. */ if (simple_iv (loop, loop, res, &iv, true)) { - gsi_next (psi); + if (integer_zerop (iv.step)) + remove_invariant_phi (region, psi); + else + gsi_next (psi); + return false; } @@ -232,6 +235,7 @@ graphite_stmt_p (sese region, basic_block bb, 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. */ @@ -281,6 +285,24 @@ new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs) return gbb; } +static void +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) + { + base_alias_pair *bap = (base_alias_pair *)(dr->aux); + + if (bap->alias_set) + free (bap->alias_set); + + free (bap); + dr->aux = NULL; + } +} /* Frees GBB. */ static void @@ -289,6 +311,7 @@ free_gimple_bb (struct gimple_bb *gbb) if (GBB_CLOOG_IV_TYPES (gbb)) htab_delete (GBB_CLOOG_IV_TYPES (gbb)); + free_data_refs_aux (GBB_DATA_REFS (gbb)); free_data_refs (GBB_DATA_REFS (gbb)); VEC_free (gimple, heap, GBB_CONDITIONS (gbb)); @@ -331,19 +354,24 @@ free_scops (VEC (scop_p, heap) *scops) information. */ static void -try_generate_gimple_bb (scop_p scop, basic_block bb) +try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions) { VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb); gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - graphite_find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs); + { + gimple stmt = gsi_stmt (gsi); + if (!is_gimple_debug (stmt)) + 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)); + new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions, + bb->index)); } /* Returns true if all predecessors of BB, that are not dominated by BB, are @@ -398,7 +426,7 @@ 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) +build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions) { sese region = SCOP_REGION (scop); VEC (basic_block, heap) *dom; @@ -407,7 +435,7 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb) || !bb_in_sese_p (bb, region)) return; - try_generate_gimple_bb (scop, bb); + try_generate_gimple_bb (scop, bb, reductions); SET_BIT (visited, bb->index); dom = get_dominated_by (CDI_DOMINATORS, bb); @@ -425,7 +453,7 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb) for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++) if (all_non_dominated_preds_marked_p (dom_bb, visited)) { - build_scop_bbs_1 (scop, visited, dom_bb); + build_scop_bbs_1 (scop, visited, dom_bb, reductions); VEC_unordered_remove (basic_block, dom, i); break; } @@ -436,15 +464,14 @@ build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb) /* Gather the basic blocks belonging to the SCOP. */ -void -build_scop_bbs (scop_p scop) +static void +build_scop_bbs (scop_p scop, sbitmap reductions) { 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)); - + build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions); sbitmap_free (visited); } @@ -719,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. */ @@ -775,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; } @@ -950,45 +954,6 @@ scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c, } } -/* Data structure for idx_record_params. */ - -struct irp_data -{ - struct loop *loop; - sese region; -}; - -/* For a data reference with an ARRAY_REF as its BASE, record the - parameters occurring in IDX. DTA is passed in as complementary - information, and is used by the automatic walker function. This - function is a callback for for_each_index. */ - -static bool -idx_record_params (tree base, tree *idx, void *dta) -{ - struct irp_data *data = (struct irp_data *) dta; - - if (TREE_CODE (base) != ARRAY_REF) - return true; - - if (TREE_CODE (*idx) == SSA_NAME) - { - tree scev; - sese region = data->region; - struct loop *loop = data->loop; - Value one; - - scev = scalar_evolution_in_region (region, loop, *idx); - - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (region, scev, NULL, one); - value_clear (one); - } - - return true; -} - /* Find parameters with respect to REGION in BB. We are looking in memory access functions, conditions and loop bounds. */ @@ -996,34 +961,33 @@ static void find_params_in_bb (sese region, gimple_bb_p gbb) { int i; + unsigned j; data_reference_p dr; gimple stmt; loop_p loop = GBB_BB (gbb)->loop_father; + Value one; - for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++) - { - struct irp_data irp; + value_init (one); + value_set_si (one, 1); - irp.loop = loop; - irp.region = region; - for_each_index (&dr->ref, idx_record_params, &irp); - } + /* Find parameters in the access functions of data references. */ + for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++) + for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++) + scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one); /* Find parameters in conditional statements. */ for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++) { - Value one; tree lhs = scalar_evolution_in_region (region, loop, gimple_cond_lhs (stmt)); tree rhs = scalar_evolution_in_region (region, loop, gimple_cond_rhs (stmt)); - value_init (one); - value_set_si (one, 1); scan_tree_for_params (region, lhs, NULL, one); scan_tree_for_params (region, rhs, NULL, one); - value_clear (one); } + + value_clear (one); } /* Record the parameters used in the SCOP. A variable is a parameter @@ -1061,6 +1025,9 @@ find_scop_parameters (scop_p scop) scop_set_nb_params (scop, sese_nb_params (region)); SESE_ADD_PARAMS (region) = false; + + ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension + (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0); } /* Returns a gimple_bb from BB. */ @@ -1076,8 +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; @@ -1137,6 +1104,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, Value one; ppl_Constraint_t ub; ppl_Linear_Expression_t ub_expr; + double_int nit; value_init (one); value_set_si (one, 1); @@ -1145,6 +1113,65 @@ 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); + } + /* loop_i <= expr_nb_iters */ ppl_set_coef (ub_expr, nb, -1); ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); @@ -1156,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); } @@ -1178,7 +1205,7 @@ create_linear_expr_from_tree (poly_bb_p pbb, tree t) ppl_Linear_Expression_t res; ppl_dimension_type dim; sese region = SCOP_REGION (PBB_SCOP (pbb)); - loop_p loop = GBB_BB (PBB_BLACK_BOX (pbb))->loop_father; + loop_p loop = pbb_loop (pbb); dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb); ppl_new_Linear_Expression_with_dimension (&res, dim); @@ -1514,6 +1541,7 @@ static void build_scop_context (scop_p scop) { ppl_Polyhedron_t context; + ppl_Pointset_Powerset_C_Polyhedron_t ps; graphite_dim_t p, n = scop_nb_params (scop); ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0); @@ -1522,8 +1550,11 @@ build_scop_context (scop_p scop) add_param_constraints (scop, context, p); ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron - (&SCOP_CONTEXT (scop), context); + (&ps, context); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign + (SCOP_CONTEXT (scop), ps); + ppl_delete_Pointset_Powerset_C_Polyhedron (ps); ppl_delete_Polyhedron (context); } @@ -1539,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 @@ -1579,13 +1613,10 @@ pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, ppl_Linear_Expression_t alias; ppl_Constraint_t cstr; int alias_set_num = 0; + base_alias_pair *bap = (base_alias_pair *)(dr->aux); - if (dr->aux != NULL) - { - alias_set_num = *((int *)(dr->aux)); - free (dr->aux); - dr->aux = NULL; - } + if (bap && bap->alias_set) + alias_set_num = *(bap->alias_set); ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims); @@ -1654,49 +1685,52 @@ pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr, { tree ref = DR_REF (dr); int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); - tree array_size; - HOST_WIDE_INT elt_size; - array_size = TYPE_SIZE (TREE_TYPE (ref)); - if (array_size == NULL_TREE - || TREE_CODE (array_size) != INTEGER_CST) - return; - - elt_size = int_cst_value (array_size); - - for (i = nb_subscripts - 1; i >= 0; i--) + for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) { ppl_Linear_Expression_t expr; ppl_Constraint_t cstr; ppl_dimension_type subscript = dom_nb_dims + 1 + i; + tree low, high; - /* 0 <= subscript */ - ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); - ppl_set_coef (expr, subscript, 1); - ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); - ppl_Polyhedron_add_constraint (accesses, cstr); - ppl_delete_Linear_Expression (expr); - ppl_delete_Constraint (cstr); - - ref = TREE_OPERAND (ref, 0); - array_size = TYPE_SIZE (TREE_TYPE (ref)); - if (array_size == NULL_TREE - || TREE_CODE (array_size) != INTEGER_CST) + if (TREE_CODE (ref) != ARRAY_REF) break; - /* subscript <= array_size */ - ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); - ppl_set_coef (expr, subscript, -1); + low = array_ref_low_bound (ref); + + /* subscript - low >= 0 */ + if (host_integerp (low, 0)) + { + ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); + ppl_set_coef (expr, subscript, 1); - if (elt_size) - ppl_set_inhomogeneous (expr, int_cst_value (array_size) / elt_size); + ppl_set_inhomogeneous (expr, -int_cst_value (low)); - ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); - ppl_Polyhedron_add_constraint (accesses, cstr); - ppl_delete_Linear_Expression (expr); - ppl_delete_Constraint (cstr); + ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); + ppl_Polyhedron_add_constraint (accesses, cstr); + ppl_delete_Linear_Expression (expr); + ppl_delete_Constraint (cstr); + } + + high = array_ref_up_bound (ref); + + /* high - subscript >= 0 */ + if (high && host_integerp (high, 0) + /* 1-element arrays at end of structures may extend over + their declared size. */ + && !(array_at_struct_end_p (ref) + && operand_equal_p (low, high, 0))) + { + ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims); + ppl_set_coef (expr, subscript, -1); - elt_size = int_cst_value (array_size); + ppl_set_inhomogeneous (expr, int_cst_value (high)); + + ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); + ppl_Polyhedron_add_constraint (accesses, cstr); + ppl_delete_Linear_Expression (expr); + ppl_delete_Constraint (cstr); + } } } @@ -1709,6 +1743,7 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps; ppl_dimension_type dom_nb_dims; ppl_dimension_type accessp_nb_dims; + int dr_base_object_set; ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dom_nb_dims); @@ -1723,24 +1758,215 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, accesses); ppl_delete_Polyhedron (accesses); - new_poly_dr (pbb, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, dr); + + 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, + dr, DR_NUM_DIMENSIONS (dr)); } -/* Group each data reference in DRS with it's alias set num. */ +/* Write to FILE the alias graph of data references in DIMACS format. */ + +static inline bool +write_alias_graph_to_ascii_dimacs (FILE *file, char *comment, + VEC (data_reference_p, heap) *drs) +{ + int num_vertex = VEC_length (data_reference_p, drs); + int edge_num = 0; + data_reference_p dr1, dr2; + int i, j; + + if (num_vertex == 0) + return true; + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_may_alias_p (dr1, dr2)) + edge_num++; + + fprintf (file, "$\n"); + + if (comment) + fprintf (file, "c %s\n", comment); + + fprintf (file, "p edge %d %d\n", num_vertex, edge_num); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_may_alias_p (dr1, dr2)) + fprintf (file, "e %d %d\n", i + 1, j + 1); + + return true; +} + +/* Write to FILE the alias graph of data references in DOT format. */ + +static inline bool +write_alias_graph_to_ascii_dot (FILE *file, char *comment, + VEC (data_reference_p, heap) *drs) +{ + int num_vertex = VEC_length (data_reference_p, drs); + data_reference_p dr1, dr2; + int i, j; + + if (num_vertex == 0) + return true; + + fprintf (file, "$\n"); + + if (comment) + fprintf (file, "c %s\n", comment); + + /* First print all the vertices. */ + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + fprintf (file, "n%d;\n", i); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_may_alias_p (dr1, dr2)) + fprintf (file, "n%d n%d\n", i, j); + + return true; +} + +/* Write to FILE the alias graph of data references in ECC format. */ + +static inline bool +write_alias_graph_to_ascii_ecc (FILE *file, char *comment, + VEC (data_reference_p, heap) *drs) +{ + int num_vertex = VEC_length (data_reference_p, drs); + data_reference_p dr1, dr2; + int i, j; + + if (num_vertex == 0) + return true; + + fprintf (file, "$\n"); + + if (comment) + fprintf (file, "c %s\n", comment); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_may_alias_p (dr1, dr2)) + fprintf (file, "%d %d\n", i, j); + + return true; +} + +/* Check if DR1 and DR2 are in the same object set. */ + +static bool +dr_same_base_object_p (const struct data_reference *dr1, + const struct data_reference *dr2) +{ + return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0); +} + +/* Uses DFS component number as representative of alias-sets. Also tests for + optimality by verifying if every connected component is a clique. Returns + true (1) if the above test is true, and false (0) otherwise. */ + +static int +build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs) +{ + int num_vertices = VEC_length (data_reference_p, drs); + struct graph *g = new_graph (num_vertices); + data_reference_p dr1, dr2; + int i, j; + int num_connected_components; + int v_indx1, v_indx2, num_vertices_in_component; + int *all_vertices; + int *vertices; + struct graph_edge *e; + int this_component_is_clique; + int all_components_are_cliques = 1; + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_may_alias_p (dr1, dr2)) + { + add_edge (g, i, j); + add_edge (g, j, i); + } + + all_vertices = XNEWVEC (int, num_vertices); + vertices = XNEWVEC (int, num_vertices); + for (i = 0; i < num_vertices; i++) + all_vertices[i] = i; + + num_connected_components = graphds_dfs (g, all_vertices, num_vertices, + 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) + 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++) + { + num_vertices_in_component = 0; + /* Get all vertices whose DFS component number is the same as i. */ + for (j = 0; j < num_vertices; j++) + if (g->vertices[j].component == i) + vertices[num_vertices_in_component++] = j; + + /* Now test if the vertices in 'vertices' form a clique, by testing + for edges among each pair. */ + this_component_is_clique = 1; + for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++) + { + for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++) + { + /* Check if the two vertices are connected by iterating + through all the edges which have one of these are source. */ + e = g->vertices[vertices[v_indx2]].pred; + while (e) + { + if (e->src == vertices[v_indx1]) + break; + e = e->pred_next; + } + if (!e) + { + this_component_is_clique = 0; + break; + } + } + if (!this_component_is_clique) + all_components_are_cliques = 0; + } + } + + free (all_vertices); + free (vertices); + free_graph (g); + return all_components_are_cliques; +} + +/* Group each data reference in DRS with it's base object set num. */ static void -build_alias_set_for_drs (VEC (data_reference_p, heap) **drs) +build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs) { - int num_vertex = VEC_length (data_reference_p, *drs); + int num_vertex = VEC_length (data_reference_p, 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++) - for (j = i+1; VEC_iterate (data_reference_p, *drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++) + for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++) + if (dr_same_base_object_p (dr1, dr2)) { add_edge (g, i, j); add_edge (g, j, i); @@ -1750,13 +1976,17 @@ build_alias_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); - dr->aux = XNEW (int); - *((int *)(dr->aux)) = g->vertices[i].component + 1; + data_reference_p dr = VEC_index (data_reference_p, drs, i); + base_alias_pair *bap; + + if (dr->aux) + bap = (base_alias_pair *)(dr->aux); + + bap->base_obj_set = g->vertices[i].component + 1; } free (queue); @@ -1776,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 @@ -1787,47 +2053,46 @@ build_scop_drs (scop_p scop) VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3); for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) + for (j = 0; VEC_iterate (data_reference_p, + GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++) + VEC_safe_push (data_reference_p, heap, drs, dr); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++) + dr->aux = XNEW (base_alias_pair); + + if (!build_alias_set_optimal_p (drs)) { - VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb)); - for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++) - VEC_safe_push (data_reference_p, heap, drs, dr); + /* TODO: Add support when building alias set is not optimal. */ + ; } - build_alias_set_for_drs (&drs); + build_base_obj_set_for_drs (drs); + + /* When debugging, enable the following code. This cannot be used + in production compilers. */ + if (0) + dump_alias_graphs (drs); + VEC_free (data_reference_p, heap, drs); for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) build_pbb_drs (pbb); } -/* Return a gsi at the position of the VAR definition. */ +/* Return a gsi at the position of the phi node STMT. */ static gimple_stmt_iterator -gsi_for_ssa_name_def (tree var) +gsi_for_phi_node (gimple stmt) { - gimple stmt; - basic_block bb; - gimple_stmt_iterator gsi; gimple_stmt_iterator psi; - - gcc_assert (TREE_CODE (var) == SSA_NAME); - - stmt = SSA_NAME_DEF_STMT (var); - bb = gimple_bb (stmt); + basic_block bb = gimple_bb (stmt); for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) if (stmt == gsi_stmt (psi)) - return gsi_after_labels (bb); - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - if (stmt == gsi_stmt (gsi)) - { - gsi_next (&gsi); - return gsi; - } + return psi; gcc_unreachable (); - return gsi; + return psi; } /* Insert the assignment "RES := VAR" just after the definition of VAR. */ @@ -1835,10 +2100,10 @@ gsi_for_ssa_name_def (tree var) static void insert_out_of_ssa_copy (tree res, tree var) { - gimple_stmt_iterator gsi = gsi_for_ssa_name_def (var); gimple stmt; gimple_seq stmts; gimple_stmt_iterator si; + gimple_stmt_iterator gsi; var = force_gimple_operand (var, &stmts, true, NULL_TREE); stmt = gimple_build_assign (res, var); @@ -1846,7 +2111,18 @@ insert_out_of_ssa_copy (tree res, tree var) stmts = gimple_seq_alloc (); si = gsi_last (stmts); gsi_insert_after (&si, stmt, GSI_NEW_STMT); - gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); + + stmt = SSA_NAME_DEF_STMT (var); + if (gimple_code (stmt) == GIMPLE_PHI) + { + gsi = gsi_after_labels (gimple_bb (stmt)); + gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); + } + else + { + gsi = gsi_for_stmt (stmt); + gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); + } } /* Insert on edge E the assignment "RES := EXPR". */ @@ -1871,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); @@ -1889,9 +2165,8 @@ create_zero_dim_array (tree var) static bool scalar_close_phi_node_p (gimple phi) { - gcc_assert (gimple_code (phi) == GIMPLE_PHI); - - if (!is_gimple_reg (gimple_phi_result (phi))) + if (gimple_code (phi) != GIMPLE_PHI + || !is_gimple_reg (gimple_phi_result (phi))) return false; return (gimple_phi_num_args (phi) == 1); @@ -1906,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); @@ -1929,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; @@ -1966,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 @@ -2007,6 +2286,85 @@ rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi) gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT); } +/* 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); +} + +/* Rewrite the scalar dependence of DEF used in USE_STMT with a memory + read from ZERO_DIM_ARRAY. */ + +static void +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); + tree name = make_ssa_name (var, name_stmt); + ssa_op_iter iter; + use_operand_p use_p; + gimple_stmt_iterator gsi; + + gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI); + + gimple_assign_set_lhs (name_stmt, name); + + gsi = gsi_for_stmt (use_stmt); + gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT); + + FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES) + if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)) + replace_exp (use_p, name); + + update_stmt (use_stmt); +} + +/* Rewrite the scalar dependences crossing the boundary of the BB + containing STMT with an array. */ + +static void +rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + imm_use_iterator imm_iter; + tree def; + basic_block def_bb; + tree zero_dim_array = NULL_TREE; + gimple use_stmt; + + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return; + + def = gimple_assign_lhs (stmt); + if (!is_gimple_reg (def) + || scev_analyzable_p (def, region)) + return; + + def_bb = gimple_bb (stmt); + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) + if (def_bb != gimple_bb (use_stmt) + && gimple_code (use_stmt) != GIMPLE_PHI) + { + if (!zero_dim_array) + { + 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); + } + + rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt); + } +} + /* Rewrite out of SSA all the reduction phi nodes of SCOP. */ static void @@ -2017,7 +2375,7 @@ rewrite_reductions_out_of_ssa (scop_p scop) sese region = SCOP_REGION (scop); FOR_EACH_BB (bb) - if (bb_in_region (bb, SESE_ENTRY_BB (region), SESE_EXIT_BB (region))) + if (bb_in_sese_p (bb, region)) for (psi = gsi_start_phis (bb); !gsi_end_p (psi);) { if (scalar_close_phi_node_p (gsi_stmt (psi))) @@ -2031,6 +2389,17 @@ rewrite_reductions_out_of_ssa (scop_p scop) verify_ssa (false); verify_loop_closed_ssa (); #endif + + FOR_EACH_BB (bb) + if (bb_in_sese_p (bb, region)) + for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) + rewrite_cross_bb_scalar_deps (region, &psi); + + update_ssa (TODO_update_ssa); +#ifdef ENABLE_CHECKING + verify_ssa (false); + verify_loop_closed_ssa (); +#endif } /* Returns the number of pbbs that are in loops contained in SCOP. */ @@ -2049,14 +2418,466 @@ nb_pbbs_in_loops (scop_p scop) return res; } +/* Return the number of data references in BB that write in + memory. */ + +static int +nb_data_writes_in_bb (basic_block bb) +{ + int res = 0; + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if (gimple_vdef (gsi_stmt (gsi))) + res++; + + return res; +} + +/* Splits STMT out of its current BB. */ + +static basic_block +split_reduction_stmt (gimple stmt) +{ + gimple_stmt_iterator gsi; + basic_block bb = gimple_bb (stmt); + edge e; + + /* 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); + + 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)); + + return e->dest; +} + +/* Return true when stmt is a reduction operation. */ + +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 (code) + && associative_tree_code (code); +} + +/* Returns true when PHI contains an argument ARG. */ + +static bool +phi_contains_arg (gimple phi, tree arg) +{ + size_t i; + + for (i = 0; i < gimple_phi_num_args (phi); i++) + if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0)) + return true; + + return false; +} + +/* Return a loop phi node that corresponds to a reduction containing LHS. */ + +static gimple +follow_ssa_with_commutative_ops (tree arg, tree lhs) +{ + gimple stmt; + + if (TREE_CODE (arg) != SSA_NAME) + return NULL; + + 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)) + return stmt; + 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); + + if (is_reduction_operation_p (stmt)) + { + gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs); + + return res ? res : + follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs); + } + + return NULL; +} + +/* Detect commutative and associative scalar reductions starting at + the STMT. Return the phi node of the reduction cycle, or NULL. */ + +static gimple +detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg, + VEC (gimple, heap) **in, + VEC (gimple, heap) **out) +{ + gimple phi = follow_ssa_with_commutative_ops (arg, lhs); + + if (!phi) + 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. Return the phi node of the reduction cycle, or NULL. */ + +static gimple +detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in, + VEC (gimple, heap) **out) +{ + tree lhs = gimple_assign_lhs (stmt); + + if (gimple_num_ops (stmt) == 2) + return detect_commutative_reduction_arg (lhs, stmt, + gimple_assign_rhs1 (stmt), + in, out); + + if (is_reduction_operation_p (stmt)) + { + gimple res = detect_commutative_reduction_arg (lhs, stmt, + gimple_assign_rhs1 (stmt), + in, out); + return res ? res + : detect_commutative_reduction_arg (lhs, stmt, + gimple_assign_rhs2 (stmt), + in, out); + } + + return NULL; +} + +/* Return a loop phi node that corresponds to a reduction containing LHS. */ + +static gimple +follow_inital_value_to_phi (tree arg, tree lhs) +{ + gimple stmt; + + if (!arg || TREE_CODE (arg) != SSA_NAME) + return NULL; + + stmt = SSA_NAME_DEF_STMT (arg); + + if (gimple_code (stmt) == GIMPLE_PHI + && phi_contains_arg (stmt, lhs)) + return stmt; + + return NULL; +} + + +/* Return the argument of the loop PHI that is the inital value coming + from outside the loop. */ + +static edge +edge_initial_value_for_loop_phi (gimple phi) +{ + size_t i; + + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + edge e = gimple_phi_arg_edge (phi, i); + + if (loop_depth (e->src->loop_father) + < loop_depth (e->dest->loop_father)) + return e; + } + + return NULL; +} + +/* Return the argument of the loop PHI that is the inital value coming + from outside the loop. */ + +static tree +initial_value_for_loop_phi (gimple phi) +{ + size_t i; + + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + edge e = gimple_phi_arg_edge (phi, i); + + if (loop_depth (e->src->loop_father) + < loop_depth (e->dest->loop_father)) + return gimple_phi_arg_def (phi, i); + } + + return NULL_TREE; +} + +/* Detect commutative and associative scalar reductions starting at + 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, + VEC (gimple, heap) **out) +{ + if (scalar_close_phi_node_p (stmt)) + { + tree arg = gimple_phi_arg_def (stmt, 0); + 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) + { + tree lhs = gimple_phi_result (stmt); + tree init = initial_value_for_loop_phi (loop_phi); + gimple 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 + return NULL; + } + + if (gimple_code (stmt) == GIMPLE_ASSIGN) + return detect_commutative_reduction_assign (stmt, in, out); + + return NULL; +} + +/* Translate the scalar reduction statement STMT to an array RED + knowing that its recursive phi node is LOOP_PHI. */ + +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); + + 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); +} + +/* Insert the assignment "result (CLOSE_PHI) = RED". */ + +static void +insert_copyout (tree red, gimple close_phi) +{ + tree res = gimple_phi_result (close_phi); + basic_block bb = gimple_bb (close_phi); + gimple_stmt_iterator insert_gsi = gsi_after_labels (bb); + gimple assign = gimple_build_assign (res, red); + + gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT); +} + +/* Insert the assignment "RED = initial_value (LOOP_PHI)". */ + +static void +insert_copyin (tree red, gimple loop_phi) +{ + gimple_seq stmts; + tree init = initial_value_for_loop_phi (loop_phi); + tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init); + + force_gimple_operand (expr, &stmts, true, NULL); + gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts); +} + +/* 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: + + IN: stmt, loop_n, ..., loop_0 + OUT: stmt, close_n, ..., close_0 + + the first element is the reduction statement, and the next elements + 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) +{ + unsigned int i; + gimple loop_phi; + tree red; + gimple_stmt_iterator gsi; + + for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++) + { + gimple close_phi = VEC_index (gimple, out, i); + + if (i == 0) + { + gimple stmt = loop_phi; + basic_block bb = split_reduction_stmt (stmt); + + SET_BIT (reductions, bb->index); + gcc_assert (close_phi == loop_phi); + + 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; + } + + if (i == VEC_length (gimple, in) - 1) + { + insert_copyout (red, close_phi); + 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); + } +} + +/* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */ + +static void +rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi, + sbitmap reductions) +{ + VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10); + VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); + + detect_commutative_reduction (close_phi, &in, &out); + if (VEC_length (gimple, in) > 0) + translate_scalar_reduction_to_array (in, out, reductions); + + VEC_free (gimple, heap, in); + VEC_free (gimple, heap, out); +} + +/* Rewrites all the commutative reductions from LOOP out of SSA. */ + +static void +rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop, + sbitmap reductions) +{ + gimple_stmt_iterator gsi; + edge exit = single_exit (loop); + + if (!exit) + return; + + for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi)) + rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi), + reductions); +} + +/* Rewrites all the commutative reductions from SCOP out of SSA. */ + +static void +rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions) +{ + loop_iterator li; + loop_p loop; + + FOR_EACH_LOOP (li, loop, 0) + if (loop_in_sese_p (loop, region)) + rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions); + + gsi_commit_edge_inserts (); + update_ssa (TODO_update_ssa); +#ifdef ENABLE_CHECKING + verify_ssa (false); + verify_loop_closed_ssa (); +#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 build_poly_scop (scop_p scop) { sese region = SCOP_REGION (scop); + sbitmap reductions = sbitmap_alloc (last_basic_block * 2); + + sbitmap_zero (reductions); + rewrite_commutative_reductions_out_of_ssa (region, reductions); rewrite_reductions_out_of_ssa (scop); - build_scop_bbs (scop); + build_scop_bbs (scop, reductions); + sbitmap_free (reductions); /* FIXME: This restriction is needed to avoid a problem in CLooG. Once CLooG is fixed, remove this guard. Anyways, it makes no @@ -2065,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); @@ -2073,6 +2895,7 @@ build_poly_scop (scop_p scop) build_scop_context (scop); add_conditions_to_constraints (scop); + scop_to_lst (scop); build_scop_scattering (scop); build_scop_drs (scop); @@ -2082,7 +2905,7 @@ build_poly_scop (scop_p scop) /* Always return false. Exercise the scop_to_clast function. */ void -check_poly_representation (scop_p scop) +check_poly_representation (scop_p scop ATTRIBUTE_UNUSED) { #ifdef ENABLE_CHECKING cloog_prog_clast pc = scop_to_clast (scop);