diff options
| -rw-r--r-- | gcc/ChangeLog | 64 | ||||
| -rw-r--r-- | gcc/graphite.c | 527 | ||||
| -rw-r--r-- | gcc/graphite.h | 27 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 20 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-2.c | 32 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-5.c | 26 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-6.c | 25 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/pr37485.c | 1 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/pr37684.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/pr38446.c | 14 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/scop-15.c | 1 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/scop-16.c | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/scop-17.c | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gfortran.dg/graphite/pr38459.f90 | 14 |
14 files changed, 684 insertions, 81 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a697b51fe50..64a7b927315 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,67 @@ +2008-12-11 Harsha Jagasia <harsha.jagasia@amd.com> + + PR tree-optimization/38446 + * graphite.c (register_bb_in_sese): New. + (bb_in_sese_p): Check if bb belongs to sese region by explicitly + looking at the bbs in the region. + * graphite.h (sese): Add region_basic_blocks pointer set to + structure and initialize at the time of defining new scop. + +2008-12-11 Tobias Grosser <grosser@fim.uni-passau.de> + + * graphite.c (new_graphite_bb): Initialize GBB_STATIC_SCHEDULE. + (find_params_in_bb): Do not free data refs. + (free_graphite_bb): Add FIXME on disabled free_data_refs. + +2008-12-11 Sebastian Pop <sebastian.pop@amd.com> + + * graphite.c (struct ivtype_map_elt): New. + (debug_ivtype_elt, debug_ivtype_map_1, debug_ivtype_map, + new_ivtype_map_elt, ivtype_map_elt_info, eq_ivtype_map_elts, + gcc_type_for_cloog_iv): New. + (loop_iv_stack_patch_for_consts): Use the type of the induction + variable from the original loop, except for the automatically + generated loops, i.e., in the case of a strip-mined loop, in + which case there is no original loop: in that case just use + integer_type_node. + (new_graphite_bb): Initialize GBB_CLOOG_IV_TYPES. + (free_graphite_bb): Free GBB_CLOOG_IV_TYPES. + (clast_name_to_gcc): Accept params to be NULL. + (clast_to_gcc_expression): Take an extra parameter for the type. + Convert to that type all the expressions built by this function. + (gcc_type_for_clast_expr, gcc_type_for_clast_eq): New. + (graphite_translate_clast_equation): Compute the type of the + clast_equation before translating its LHS and RHS. + (clast_get_body_of_loop, gcc_type_for_iv_of_clast_loop): New. + (graphite_create_new_loop): Compute the type of the induction + variable before translating the lower and upper bounds and before + creating the induction variable. + (rename_variables_from_edge, rename_phis_end_scop): New. + (copy_bb_and_scalar_dependences): Call rename_phis_end_scop. + (sese_add_exit_phis_edge): Do not use integer_zero_node. + (find_cloog_iv_in_expr, compute_cloog_iv_types_1, + compute_cloog_iv_types): New. + (gloog): Call compute_cloog_iv_types before starting the + translation of the clast. + + * graphite.h (struct graphite_bb): New field cloog_iv_types. + (GBB_CLOOG_IV_TYPES): New. + (debug_ivtype_map): Declared. + (oldiv_for_loop): New. + +2008-12-10 Tobias Grosser <grosser@fim.uni-passau.de> + + PR middle-end/38459 + * graphite.c (new_scop): Initialize SCOP_ADD_PARAMS. + (param_index): Assert if parameter is not know after parameter + detection. + (find_params_in_bb): Detect params directly in GBB_CONDITIONS. + (find_scop_parameters): Mark, that we have finished parameter + detection. + (graphite_transform_loops): Move condition detection before parameter + detection. + * graphite.h (struct scop): Add SCOP_ADD_PARAMS. + 2008-12-11 John David Anglin <dave.anglin@nrc-cnrc.gc.ca> PR testsuite/35677 diff --git a/gcc/graphite.c b/gcc/graphite.c index 7c2b8da90b9..877dffe2816 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -64,9 +64,9 @@ static VEC (scop_p, heap) *current_scops; /* Converts a GMP constant V to a tree and returns it. */ static tree -gmp_cst_to_tree (Value v) +gmp_cst_to_tree (tree type, Value v) { - return build_int_cst (integer_type_node, value_get_si (v)); + return build_int_cst (type, value_get_si (v)); } /* Debug the list of old induction variables for this SCOP. */ @@ -244,6 +244,98 @@ free_loop_iv_stack (loop_iv_stack stack) VEC_free (iv_stack_entry_p, heap, *stack); } + + +/* Structure containing the mapping between the CLooG's induction + variable and the type of the old induction variable. */ +typedef struct ivtype_map_elt +{ + tree type; + const char *cloog_iv; +} *ivtype_map_elt; + +/* Print to stderr the element ELT. */ + +static void +debug_ivtype_elt (ivtype_map_elt elt) +{ + fprintf (stderr, "(%s, ", elt->cloog_iv); + print_generic_expr (stderr, elt->type, 0); + fprintf (stderr, ")\n"); +} + +/* Helper function for debug_ivtype_map. */ + +static int +debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) +{ + struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot; + debug_ivtype_elt (entry); + return 1; +} + +/* Print to stderr all the elements of MAP. */ + +void +debug_ivtype_map (htab_t map) +{ + htab_traverse (map, debug_ivtype_map_1, NULL); +} + +/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ + +static inline ivtype_map_elt +new_ivtype_map_elt (const char *cloog_iv, tree type) +{ + ivtype_map_elt res; + + res = XNEW (struct ivtype_map_elt); + res->cloog_iv = cloog_iv; + res->type = type; + + return res; +} + +/* Computes a hash function for database element ELT. */ + +static hashval_t +ivtype_map_elt_info (const void *elt) +{ + return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv); +} + +/* Compares database elements E1 and E2. */ + +static int +eq_ivtype_map_elts (const void *e1, const void *e2) +{ + const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1; + const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2; + + return (elt1->cloog_iv == elt2->cloog_iv); +} + + + +/* Given a CLOOG_IV, returns the type that it should have in GCC land. + If the information is not available, i.e. in the case one of the + transforms created the loop, just return integer_type_node. */ + +static tree +gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb) +{ + struct ivtype_map_elt tmp; + PTR *slot; + + tmp.cloog_iv = cloog_iv; + slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT); + + if (slot && *slot) + return ((ivtype_map_elt) *slot)->type; + + return integer_type_node; +} + /* Inserts constants derived from the USER_STMT argument list into the STACK. This is needed to map old ivs to constants when loops have been eliminated. */ @@ -254,16 +346,23 @@ loop_iv_stack_patch_for_consts (loop_iv_stack stack, { struct clast_stmt *t; int index = 0; + CloogStatement *cs = user_stmt->statement; + graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); + for (t = user_stmt->substitutions; t; t = t->next) { - struct clast_term *term = (struct clast_term*) + struct clast_expr *expr = (struct clast_expr *) ((struct clast_assignment *)t)->RHS; + struct clast_term *term = (struct clast_term *) expr; /* FIXME: What should be done with expr_bin, expr_red? */ - if (((struct clast_assignment *)t)->RHS->type == expr_term + if (expr->type == expr_term && !term->var) { - tree value = gmp_cst_to_tree (term->val); + loop_p loop = gbb_loop_at_index (gbb, index); + tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop); + tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node; + tree value = gmp_cst_to_tree (type, term->val); loop_iv_stack_insert_constant (stack, index, value); } index = index + 1; @@ -1056,6 +1155,8 @@ new_graphite_bb (scop_p scop, basic_block bb) GBB_CONDITIONS (gbb) = NULL; GBB_CONDITION_CASES (gbb) = NULL; GBB_LOOPS (gbb) = NULL; + GBB_STATIC_SCHEDULE (gbb) = NULL; + GBB_CLOOG_IV_TYPES (gbb) = NULL; VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb); } @@ -1067,6 +1168,14 @@ free_graphite_bb (struct graphite_bb *gbb) if (GBB_DOMAIN (gbb)) cloog_matrix_free (GBB_DOMAIN (gbb)); + if (GBB_CLOOG_IV_TYPES (gbb)) + htab_delete (GBB_CLOOG_IV_TYPES (gbb)); + + /* FIXME: free_data_refs is disabled for the moment, but should be + enabled. + + free_data_refs (GBB_DATA_REFS (gbb)); */ + VEC_free (gimple, heap, GBB_CONDITIONS (gbb)); VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb)); VEC_free (loop_p, heap, GBB_LOOPS (gbb)); @@ -1074,6 +1183,26 @@ free_graphite_bb (struct graphite_bb *gbb) XDELETE (gbb); } +/* Register basic blocks belonging to a region in a pointer set. */ + +static void +register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region) +{ + edge_iterator ei; + edge e; + basic_block bb = entry_bb; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) && + e->dest->index != exit_bb->index) + { + pointer_set_insert (SESE_REGION_BBS (region), e->dest); + register_bb_in_sese (e->dest, exit_bb, region); + } + } +} + /* Creates a new scop starting with ENTRY. */ static scop_p @@ -1086,6 +1215,9 @@ new_scop (edge entry, edge exit) SCOP_REGION (scop) = XNEW (struct sese); SESE_ENTRY (SCOP_REGION (scop)) = entry; SESE_EXIT (SCOP_REGION (scop)) = exit; + SESE_REGION_BBS (SCOP_REGION (scop)) = pointer_set_create (); + register_bb_in_sese (SCOP_ENTRY (scop), SCOP_EXIT (scop), + SCOP_REGION (scop)); SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3); SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3); SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL); @@ -1513,7 +1645,6 @@ scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops, static struct scopdet_info build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop) { - bool in_scop = false; sd_region open_scop; struct scopdet_info sinfo; @@ -2465,7 +2596,6 @@ find_params_in_bb (scop_p scop, graphite_bb_p gb) irp.loop = father; irp.scop = scop; for_each_index (&dr->ref, idx_record_params, &irp); - free_data_ref (dr); } /* Find parameters in conditional statements. */ @@ -3277,9 +3407,10 @@ clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params, name_tree t; tree iv; - for (i = 0; VEC_iterate (name_tree, params, i, t); i++) - if (!strcmp (name, t->name)) - return t->t; + if (params) + for (i = 0; VEC_iterate (name_tree, params, i, t); i++) + if (!strcmp (name, t->name)) + return t->t; iv = loop_iv_stack_get_iv_from_name (ivstack, name); if (iv) @@ -3288,24 +3419,24 @@ clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params, gcc_unreachable (); } -/* A union needed to convert from CLAST expressions to GMP values. */ +/* Returns the maximal precision type for expressions E1 and E2. */ -typedef union { - struct clast_expr *c; - Value v; -} value_clast; +static inline tree +max_precision_type (tree e1, tree e2) +{ + tree type1 = TREE_TYPE (e1); + tree type2 = TREE_TYPE (e2); + return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2; +} -/* Converts a Cloog AST expression E back to a GCC expression tree. */ +/* Converts a Cloog AST expression E back to a GCC expression tree + of type TYPE. */ static tree -clast_to_gcc_expression (struct clast_expr *e, +clast_to_gcc_expression (tree type, struct clast_expr *e, VEC (name_tree, heap) *params, loop_iv_stack ivstack) { - tree type = integer_type_node; - - gcc_assert (e); - switch (e->type) { case expr_term: @@ -3315,53 +3446,62 @@ clast_to_gcc_expression (struct clast_expr *e, if (t->var) { if (value_one_p (t->val)) - return clast_name_to_gcc (t->var, params, ivstack); + { + tree name = clast_name_to_gcc (t->var, params, ivstack); + return fold_convert (type, name); + } else if (value_mone_p (t->val)) - return fold_build1 (NEGATE_EXPR, type, - clast_name_to_gcc (t->var, params, ivstack)); + { + tree name = clast_name_to_gcc (t->var, params, ivstack); + name = fold_convert (type, name); + return fold_build1 (NEGATE_EXPR, type, name); + } else - return fold_build2 (MULT_EXPR, type, - gmp_cst_to_tree (t->val), - clast_name_to_gcc (t->var, params, ivstack)); + { + tree name = clast_name_to_gcc (t->var, params, ivstack); + tree cst = gmp_cst_to_tree (type, t->val); + name = fold_convert (type, name); + return fold_build2 (MULT_EXPR, type, cst, name); + } } else - return gmp_cst_to_tree (t->val); + return gmp_cst_to_tree (type, t->val); } case expr_red: { struct clast_reduction *r = (struct clast_reduction *) e; - tree left, right; switch (r->type) { case clast_red_sum: if (r->n == 1) - return clast_to_gcc_expression (r->elts[0], params, ivstack); + return clast_to_gcc_expression (type, r->elts[0], params, ivstack); else { + tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); + tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); + gcc_assert (r->n >= 1 && r->elts[0]->type == expr_term && r->elts[1]->type == expr_term); - left = clast_to_gcc_expression (r->elts[0], params, ivstack); - right = clast_to_gcc_expression (r->elts[1], params, ivstack); - return fold_build2 (PLUS_EXPR, type, left, right); + return fold_build2 (PLUS_EXPR, type, tl, tr); } break; case clast_red_min: if (r->n == 1) - return clast_to_gcc_expression (r->elts[0], params, ivstack); + return clast_to_gcc_expression (type, r->elts[0], params, ivstack); else if (r->n == 2) { - left = clast_to_gcc_expression (r->elts[0], params, ivstack); - right = clast_to_gcc_expression (r->elts[1], params, ivstack); - return fold_build2 (MIN_EXPR, type, left, right); + tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); + tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); + return fold_build2 (MIN_EXPR, type, tl, tr); } else @@ -3371,13 +3511,13 @@ clast_to_gcc_expression (struct clast_expr *e, case clast_red_max: if (r->n == 1) - return clast_to_gcc_expression (r->elts[0], params, ivstack); + return clast_to_gcc_expression (type, r->elts[0], params, ivstack); else if (r->n == 2) { - left = clast_to_gcc_expression (r->elts[0], params, ivstack); - right = clast_to_gcc_expression (r->elts[1], params, ivstack); - return fold_build2 (MAX_EXPR, type, left, right); + tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); + tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); + return fold_build2 (MAX_EXPR, type, tl, tr); } else @@ -3395,12 +3535,8 @@ clast_to_gcc_expression (struct clast_expr *e, { struct clast_binary *b = (struct clast_binary *) e; struct clast_expr *lhs = (struct clast_expr *) b->LHS; - tree tl = clast_to_gcc_expression (lhs, params, ivstack); - value_clast r; - tree tr; - - r.c = (struct clast_expr *) b->RHS; - tr = gmp_cst_to_tree (r.v); + tree tl = clast_to_gcc_expression (type, lhs, params, ivstack); + tree tr = gmp_cst_to_tree (type, b->RHS); switch (b->type) { @@ -3428,6 +3564,72 @@ clast_to_gcc_expression (struct clast_expr *e, return NULL_TREE; } +/* Returns the type for the expression E. */ + +static tree +gcc_type_for_clast_expr (struct clast_expr *e, + VEC (name_tree, heap) *params, + loop_iv_stack ivstack) +{ + switch (e->type) + { + case expr_term: + { + struct clast_term *t = (struct clast_term *) e; + + if (t->var) + return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack)); + else + return NULL_TREE; + } + + case expr_red: + { + struct clast_reduction *r = (struct clast_reduction *) e; + + if (r->n == 1) + return gcc_type_for_clast_expr (r->elts[0], params, ivstack); + else + { + int i; + for (i = 0; i < r->n; i++) + { + tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack); + if (type) + return type; + } + return NULL_TREE; + } + } + + case expr_bin: + { + struct clast_binary *b = (struct clast_binary *) e; + struct clast_expr *lhs = (struct clast_expr *) b->LHS; + return gcc_type_for_clast_expr (lhs, params, ivstack); + } + + default: + gcc_unreachable (); + } + + return NULL_TREE; +} + +/* Returns the type for the equation CLEQ. */ + +static tree +gcc_type_for_clast_eq (struct clast_equation *cleq, + VEC (name_tree, heap) *params, + loop_iv_stack ivstack) +{ + tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack); + if (type) + return type; + + return gcc_type_for_clast_expr (cleq->RHS, params, ivstack); +} + /* Translates a clast equation CLEQ to a tree. */ static tree @@ -3436,8 +3638,9 @@ graphite_translate_clast_equation (scop_p scop, loop_iv_stack ivstack) { enum tree_code comp; - tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack); - tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack); + tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack); + tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack); + tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack); if (cleq->sign == 0) comp = EQ_EXPR; @@ -3448,7 +3651,7 @@ graphite_translate_clast_equation (scop_p scop, else comp = LE_EXPR; - return fold_build2 (comp, integer_type_node, lhs, rhs); + return fold_build2 (comp, type, lhs, rhs); } /* Creates the test for the condition in STMT. */ @@ -3465,7 +3668,7 @@ graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt, tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack); if (cond) - cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq); + cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq); else cond = eq; } @@ -3485,6 +3688,41 @@ graphite_create_new_guard (scop_p scop, edge entry_edge, return exit_edge; } +/* Walks a CLAST and returns the first statement in the body of a + loop. */ + +static struct clast_user_stmt * +clast_get_body_of_loop (struct clast_stmt *stmt) +{ + if (!stmt + || CLAST_STMT_IS_A (stmt, stmt_user)) + return (struct clast_user_stmt *) stmt; + + if (CLAST_STMT_IS_A (stmt, stmt_for)) + return clast_get_body_of_loop (((struct clast_for *) stmt)->body); + + if (CLAST_STMT_IS_A (stmt, stmt_guard)) + return clast_get_body_of_loop (((struct clast_guard *) stmt)->then); + + if (CLAST_STMT_IS_A (stmt, stmt_block)) + return clast_get_body_of_loop (((struct clast_block *) stmt)->body); + + gcc_unreachable (); +} + +/* Returns the induction variable for the loop that gets translated to + STMT. */ + +static tree +gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for) +{ + struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for); + const char *cloog_iv = stmt_for->iterator; + CloogStatement *cs = stmt->statement; + graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); + + return gcc_type_for_cloog_iv (cloog_iv, gbb); +} /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction variable for the new LOOP. New LOOP is attached to CFG starting at @@ -3496,26 +3734,19 @@ graphite_create_new_loop (scop_p scop, edge entry_edge, struct clast_for *stmt, loop_iv_stack ivstack, loop_p outer) { - struct loop *loop; - tree ivvar; - tree stride, lowb, upb; + tree type = gcc_type_for_iv_of_clast_loop (stmt); + VEC (name_tree, heap) *params = SCOP_PARAMS (scop); + tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack); + tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack); + tree stride = gmp_cst_to_tree (type, stmt->stride); + tree ivvar = create_tmp_var (type, "graphiteIV"); tree iv_before; + loop_p loop = create_empty_loop_on_edge + (entry_edge, lb, stride, ub, ivvar, &iv_before, + outer ? outer : entry_edge->src->loop_father); - gcc_assert (stmt->LB - && stmt->UB); - - stride = gmp_cst_to_tree (stmt->stride); - lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack); - ivvar = create_tmp_var (integer_type_node, "graphiteIV"); add_referenced_var (ivvar); - - upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack); - loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar, - &iv_before, outer ? outer - : entry_edge->src->loop_father); - loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator); - return loop; } @@ -3786,9 +4017,7 @@ expand_scalar_variables (basic_block bb, scop_p scop, } } -/* Rename all the SSA_NAMEs from block BB that appear in IVSTACK in - terms of new induction variables. OLD is the original loop that - contained BB. */ +/* Rename all the SSA_NAMEs from block BB according to the MAP. */ static void rename_variables (basic_block bb, htab_t map) @@ -3799,6 +4028,38 @@ rename_variables (basic_block bb, htab_t map) rename_variables_in_stmt (gsi_stmt (gsi), map); } +/* Rename following the information from MAP the PHI node argument + corresponding to the edge E. In order to allow several renames of + that argument, we match the original SSA_NAME on the argument + coming from the edge different than E. */ + +static void +rename_variables_from_edge (edge e, gimple phi, htab_t map) +{ + int n = e->dest_idx == 0 ? 1 : 0; + tree old_name = gimple_phi_arg_def (phi, n); + tree new_name = get_new_name_from_old_name (map, old_name); + + gcc_assert (gimple_phi_num_args (phi) == 2 + && gimple_phi_arg_edge (phi, e->dest_idx) == e); + + SET_PHI_ARG_DEF (phi, n, new_name); +} + +/* Rename all the phi arguments for the edges comming from the scop + according to the MAP. */ + +static void +rename_phis_end_scop (scop_p scop, htab_t map) +{ + basic_block after_scop = SCOP_EXIT (scop); + edge e = SESE_EXIT (SCOP_REGION (scop)); + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_phis (after_scop); !gsi_end_p (gsi); gsi_next (&gsi)) + rename_variables_from_edge (e, gsi_stmt (gsi), map); +} + /* Remove condition from BB. */ static void @@ -3950,6 +4211,7 @@ copy_bb_and_scalar_dependences (basic_block bb, scop_p scop, rename_variables (new_bb, map); remove_phi_nodes (new_bb); expand_scalar_variables (new_bb, scop, context_loop, map); + rename_phis_end_scop (scop, map); return next_e; } @@ -4447,8 +4709,7 @@ move_sese_in_condition (sese region) static bool bb_in_sese_p (basic_block bb, sese region) { - return (dominated_by_p (CDI_DOMINATORS, bb, SESE_ENTRY (region)->src) - && dominated_by_p (CDI_POST_DOMINATORS, bb, SESE_EXIT (region)->dest)); + return pointer_set_contains (SESE_REGION_BBS (region), bb); } /* For USE in BB, if it is used outside of the REGION it is defined in, @@ -4505,7 +4766,7 @@ sese_find_uses_to_rename_bb (sese region, basic_block bb, sese_find_uses_to_rename_use (region, bb, var, use_blocks, need_phis); } -/* Add exit phis for the USE on EXIT. */ +/* Add exit phis for USE on EXIT. */ static void sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) @@ -4515,7 +4776,7 @@ sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) create_new_def_for (gimple_phi_result (phi), phi, gimple_phi_result_ptr (phi)); add_phi_arg (phi, use, false_e); - add_phi_arg (phi, integer_zero_node, true_e); + add_phi_arg (phi, use, true_e); } /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are @@ -4573,6 +4834,123 @@ rewrite_into_sese_closed_ssa (sese region, basic_block where, BITMAP_FREE (names_to_rename); } +/* Returns the first cloog name used in EXPR. */ + +static const char * +find_cloog_iv_in_expr (struct clast_expr *expr) +{ + struct clast_term *term = (struct clast_term *) expr; + + if (expr->type == expr_term + && !term->var) + return NULL; + + if (expr->type == expr_term) + return term->var; + + if (expr->type == expr_red) + { + int i; + struct clast_reduction *red = (struct clast_reduction *) expr; + + for (i = 0; i < red->n; i++) + { + const char *res = find_cloog_iv_in_expr ((red)->elts[i]); + + if (res) + return res; + } + } + + return NULL; +} + +/* Build for a clast_user_stmt USER_STMT a map between the CLAST + induction variables and the corresponding GCC old induction + variables. This information is stored on each GRAPHITE_BB. */ + +static void +compute_cloog_iv_types_1 (graphite_bb_p gbb, + struct clast_user_stmt *user_stmt) +{ + struct clast_stmt *t; + int index = 0; + + for (t = user_stmt->substitutions; t; t = t->next, index++) + { + PTR *slot; + struct ivtype_map_elt tmp; + struct clast_expr *expr = (struct clast_expr *) + ((struct clast_assignment *)t)->RHS; + + /* Create an entry (clast_var, type). */ + tmp.cloog_iv = find_cloog_iv_in_expr (expr); + if (!tmp.cloog_iv) + continue; + + slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); + + if (!*slot) + { + loop_p loop = gbb_loop_at_index (gbb, index); + tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop); + tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node; + *slot = new_ivtype_map_elt (tmp.cloog_iv, type); + } + } +} + +/* Walk the CLAST tree starting from STMT and build for each + clast_user_stmt a map between the CLAST induction variables and the + corresponding GCC old induction variables. This information is + stored on each GRAPHITE_BB. */ + +static void +compute_cloog_iv_types (struct clast_stmt *stmt) +{ + if (!stmt) + return; + + if (CLAST_STMT_IS_A (stmt, stmt_root)) + goto next; + + if (CLAST_STMT_IS_A (stmt, stmt_user)) + { + CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; + graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); + GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info, + eq_ivtype_map_elts, free); + compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt); + goto next; + } + + if (CLAST_STMT_IS_A (stmt, stmt_for)) + { + struct clast_stmt *s = ((struct clast_for *) stmt)->body; + compute_cloog_iv_types (s); + goto next; + } + + if (CLAST_STMT_IS_A (stmt, stmt_guard)) + { + struct clast_stmt *s = ((struct clast_guard *) stmt)->then; + compute_cloog_iv_types (s); + goto next; + } + + if (CLAST_STMT_IS_A (stmt, stmt_block)) + { + struct clast_stmt *s = ((struct clast_block *) stmt)->body; + compute_cloog_iv_types (s); + goto next; + } + + gcc_unreachable (); + + next: + compute_cloog_iv_types (stmt->next); +} + /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for the given SCOP. */ @@ -4598,6 +4976,7 @@ gloog (scop_p scop, struct clast_stmt *stmt) if_region->true_region->exit); graphite_verify (); context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father; + compute_cloog_iv_types (stmt); new_scop_exit_edge = translate_clast (scop, context_loop, stmt, if_region->true_region->entry, &ivstack); diff --git a/gcc/graphite.h b/gcc/graphite.h index faae00950d6..92a68167f22 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -193,6 +193,7 @@ typedef struct graphite_bb lambda_vector compressed_alpha_matrix; CloogMatrix *dynamic_schedule; VEC (data_reference_p, heap) *data_refs; + htab_t cloog_iv_types; } *gbb_p; #define GBB_BB(GBB) GBB->bb @@ -205,6 +206,7 @@ typedef struct graphite_bb #define GBB_CONDITIONS(GBB) GBB->conditions #define GBB_CONDITION_CASES(GBB) GBB->condition_cases #define GBB_LOOPS(GBB) GBB->loops +#define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types /* Return the loop that contains the basic block GBB. */ @@ -274,10 +276,12 @@ DEF_VEC_ALLOC_P (name_tree, heap); typedef struct sese { edge entry, exit; + struct pointer_set_t *region_basic_blocks; } *sese; #define SESE_ENTRY(S) (S->entry) #define SESE_EXIT(S) (S->exit) +#define SESE_REGION_BBS(S) (S->region_basic_blocks) /* A SCOP is a Static Control Part of the program, simple enough to be represented in polyhedral form. */ @@ -327,6 +331,7 @@ struct scop but just a boundary. SCOP_ENTRY is considered part of the scop. */ #define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest) #define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest) +#define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S))) #define SCOP_STATIC_SCHEDULE(S) S->static_schedule #define SCOP_LOOPS(S) S->loops #define SCOP_LOOP_NEST(S) S->loop_nest @@ -345,7 +350,8 @@ extern void dot_scop (scop_p); extern void dot_all_scops (void); extern void debug_clast_stmt (struct clast_stmt *); extern void debug_rename_map (htab_t); -extern void debug_loop_vec (graphite_bb_p gb); +extern void debug_ivtype_map (htab_t); +extern void debug_loop_vec (graphite_bb_p); extern void debug_oldivs (scop_p); /* Describes the type of an iv stack entry. */ @@ -377,6 +383,25 @@ DEF_VEC_ALLOC_P(iv_stack_entry_p,heap); typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack; extern void debug_loop_iv_stack (loop_iv_stack); +/* Return the old induction variable of the LOOP that is in normal + form in SCOP. */ + +static inline tree +oldiv_for_loop (scop_p scop, loop_p loop) +{ + int i; + name_tree iv; + + if (!loop) + return NULL_TREE; + + for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++) + if (iv->loop == loop) + return iv->t; + + return NULL_TREE; +} + /* Return the number of gimple loops contained in SCOP. */ static inline int diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 207da42eda5..cdf137fd33d 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,23 @@ +2008-12-11 Harsha Jagasia <harsha.jagasia@amd.com> + + PR tree-optimization/38446 + * gcc.dg/graphite/pr38446.c: New. + +2008-12-11 Sebastian Pop <sebastian.pop@amd.com> + + * gcc.dg/graphite/scop-16.c: Test only scop specific info. + * gcc.dg/graphite/scop-17.c: Same. + * gcc.dg/graphite/block-5.c: New. + * gcc.dg/graphite/block-6.c: New. + * gcc.dg/graphite/pr37485.c: Clean dump file after. + * gcc.dg/graphite/pr37684.c: Same. + * gcc.dg/graphite/block-2.c: Same. + +2008-12-10 Tobias Grosser <grosser@fim.uni-passau.de> + + PR middle-end/38459 + * gfortran.dg/graphite/pr38459.f90: New. + 2008-12-11 Sebastian Pop <sebastian.pop@amd.com> PR middle-end/37852 diff --git a/gcc/testsuite/gcc.dg/graphite/block-2.c b/gcc/testsuite/gcc.dg/graphite/block-2.c new file mode 100644 index 00000000000..cf0969bac1d --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/block-2.c @@ -0,0 +1,32 @@ +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ + +typedef unsigned char UChar; +typedef int Int32; +typedef unsigned int UInt32; + +void fallbackSort ( UInt32* fmap, + UInt32* eclass, + Int32 nblock, + Int32 verb ) +{ + Int32 ftab[257]; + Int32 ftabCopy[256]; + Int32 H, i, j, k, l, r, cc, cc1; + Int32 nNotDone; + Int32 nBhtab; + UChar* eclass8 = (UChar*)eclass; + + if (verb >= 4) + VPrintf0 ( " bucket sorting ...\n" ); + for (i = 0; i < 257; i++) ftab[i] = 0; + for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; + for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; + for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; + + for (i = 0; i < nblock; i++) { + j = eclass8[i] + ftab [i]; + } + AssertH ( j < 256, 1005 ); +} +/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */ +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-5.c b/gcc/testsuite/gcc.dg/graphite/block-5.c new file mode 100644 index 00000000000..e0bd4688d39 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/block-5.c @@ -0,0 +1,26 @@ +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ + +#define N 10000 +void foo (int); +int test () +{ + int a[N][N]; + int b[N][N]; + unsigned i, j; + + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + a[i][j] = i*j; + + for (j = 1; j < N; j++) + for (i = 0; i < N; i++) + a[i][j] = a[i][j-1] + b[i][j]; + + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + foo (a[i][j]); +} + +/* Interchange is legal for loops 0 and 1 of the first two SCoPs */ +/* { dg-final { scan-tree-dump-times "Interchange valid for loops 0 and 1:" 2 "graphite"} } */ +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-6.c b/gcc/testsuite/gcc.dg/graphite/block-6.c new file mode 100644 index 00000000000..77429f1cb83 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/block-6.c @@ -0,0 +1,25 @@ +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ + +#define N 10000 +void foo (int); +int test () +{ + int a[N][N]; + unsigned i, j; + + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + a[i][j] = i*j; + + for (i = 1; i < N; i++) + for (j = 1; j < (N-1) ; j++) + a[i][j] = a[i-1][j+1] * a[i-1][j+1]/2; + + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + foo (a[i][j]); +} + +/* Interchange is not legal for loops 0 and 1 of SCoP 2. */ +/* { dg-final { scan-tree-dump-times "Interchange not valid for loops 0 and 1:" 1 "graphite"} } */ +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr37485.c b/gcc/testsuite/gcc.dg/graphite/pr37485.c index 67661910ba2..cf0969bac1d 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr37485.c +++ b/gcc/testsuite/gcc.dg/graphite/pr37485.c @@ -29,3 +29,4 @@ void fallbackSort ( UInt32* fmap, AssertH ( j < 256, 1005 ); } /* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */ +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr37684.c b/gcc/testsuite/gcc.dg/graphite/pr37684.c index 35c32911c30..a9e6f5a4a59 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr37684.c +++ b/gcc/testsuite/gcc.dg/graphite/pr37684.c @@ -63,3 +63,5 @@ int BZ2_bzCompressInit } prepare_new_block ( s ); } + +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr38446.c b/gcc/testsuite/gcc.dg/graphite/pr38446.c new file mode 100644 index 00000000000..b7b346cd98b --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr38446.c @@ -0,0 +1,14 @@ +/* { dg-options "-O2 -fgraphite-identity" } */ + +void copy_data() +{ + int ****source; + int ****dest; + + int i, j, k, l; + for (i = 0; i < 10; i++) + for (k = 0; k < 2; k++) + for (l = 0; l < 65; l++) + source[i][j][k][l] = dest[i][j][k][l]; +} + diff --git a/gcc/testsuite/gcc.dg/graphite/scop-15.c b/gcc/testsuite/gcc.dg/graphite/scop-15.c index 7e242537315..9324631e2fd 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-15.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-15.c @@ -48,5 +48,6 @@ int longest_match(IPos cur_match) && --chain_length != 0); return best_len; } + /* { dg-final { scan-tree-dump-times "number of SCoPs: 0" 1 "graphite"} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/scop-16.c b/gcc/testsuite/gcc.dg/graphite/scop-16.c index 42f7b6aade3..d0b32f63973 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-16.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-16.c @@ -1,4 +1,5 @@ -/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ +/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */ + #define N 10000 void foo (int); int test () @@ -20,6 +21,5 @@ int test () foo (a[i][j]); } -/* Interchange is legal for loops 0 and 1 of the first two SCoPs */ -/* { dg-final { scan-tree-dump-times "Interchange valid for loops 0 and 1:" 2 "graphite"} } */ +/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/scop-17.c b/gcc/testsuite/gcc.dg/graphite/scop-17.c index 4c1b0ca2993..c2fec3fccaf 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-17.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-17.c @@ -1,4 +1,5 @@ -/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ +/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */ + #define N 10000 void foo (int); int test () @@ -19,6 +20,5 @@ int test () foo (a[i][j]); } -/* Interchange is not legal for loops 0 and 1 of SCoP 2. */ -/* { dg-final { scan-tree-dump-times "Interchange not valid for loops 0 and 1:" 1 "graphite"} } */ +/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gfortran.dg/graphite/pr38459.f90 b/gcc/testsuite/gfortran.dg/graphite/pr38459.f90 new file mode 100644 index 00000000000..1feb6e503eb --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/pr38459.f90 @@ -0,0 +1,14 @@ +! { dg-options "-O2 -fgraphite-identity" } +# 1 "mltfftsg.F" +# 1 "<built-in>" +SUBROUTINE mltfftsg ( a, ldax, lday, b, ldbx, ldby, & + n, m) + INTEGER, PARAMETER :: dbl = SELECTED_REAL_KIND ( 14, 200 ) + +! Arguments + INTEGER, INTENT ( IN ) :: ldbx, ldby, n, m + COMPLEX ( dbl ), INTENT ( INOUT ) :: b ( ldbx, ldby ) + + B(N+1:LDBX,1:M) = CMPLX(0._dbl,0._dbl,dbl) + +END SUBROUTINE mltfftsg |