@@ -1,5 +1,37 @@
2011-07-05 Sebastian Pop <sebastian.pop@amd.com>
+ PR tree-optimization/47654
+ PR middle-end/49649
+ * graphite-clast-to-gimple.c (struct clast_name_index): Add
+ a level field.
+ (new_clast_name_index): Add the level parameter.
+ (clast_name_to_level): New.
+ (save_clast_name_index): Add the level parameter.
+ (save_clast_name_index): Adjust call to new_clast_name_index.
+ (newivs_to_depth_to_newiv): Removed.
+ (clast_name_to_gcc): Inline code of newivs_to_depth_to_newiv.
+ (compute_bounds_for_level): Moved down.
+ (compute_type_for_level): Renamed gcc_type_for_clast_expr_from_lb_ub.
+ (clast_get_body_of_loop): Renamed clast_get_body_of.
+ (gcc_type_for_iv_of_clast_loop): Removed.
+ (graphite_create_new_loop): Add the level parameter. Adjust call
+ to save_clast_name_index.
+ (compute_bounds_for_param): New.
+ (lb_ub_for_name): New.
+ (lb_ub_for_term): New.
+ (lb_ub_for_red): New.
+ (lb_ub_for_bin): New.
+ (lb_ub_for_expr): New.
+ (graphite_create_new_loop_guard): Do not pass in the level in
+ parameter. Compute type as the max_precision_type of lb_type and
+ ub_type. Call gcc_type_for_clast_expr_from_lb_ub.
+ (translate_clast_for_loop): Adjust call to graphite_create_new_loop.
+ (translate_clast_for): Adjust call to graphite_create_new_loop_guard.
+ (create_params_index): Adjust call to save_clast_name_index.
+ * graphite-ppl.h (value_min): New.
+
+2011-07-05 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-clast-to-gimple.c (graphite_create_new_loop): Do not
recompute type, lb, and ub. Get them from...
(graphite_create_new_loop_guard): ...here. Pass in parameter
@@ -56,26 +56,55 @@ graphite_verify (void)
#endif
}
-/* Stores the INDEX in a vector for a given clast NAME. */
+/* Stores the INDEX in a vector and the loop nesting LEVEL for a given
+ clast NAME. */
typedef struct clast_name_index {
int index;
+ int level;
const char *name;
} *clast_name_index_p;
/* Returns a pointer to a new element of type clast_name_index_p built
- from NAME and INDEX. */
+ from NAME, LEVEL, and INDEX. */
static inline clast_name_index_p
-new_clast_name_index (const char *name, int index)
+new_clast_name_index (const char *name, int index, int level)
{
clast_name_index_p res = XNEW (struct clast_name_index);
res->name = name;
+ res->level = level;
res->index = index;
return res;
}
+/* For a given clast NAME, returns -1 if NAME is not in the
+ INDEX_TABLE, otherwise returns the loop level for the induction
+ variable NAME, or if it is a parameter, the parameter number in the
+ vector of parameters. */
+
+static inline int
+clast_name_to_level (clast_name_p name, htab_t index_table)
+{
+ struct clast_name_index tmp;
+ PTR *slot;
+
+#ifdef CLOOG_ORG
+ gcc_assert (name->type == clast_expr_name);
+ tmp.name = ((const struct clast_name *) name)->name;
+#else
+ tmp.name = name;
+#endif
+
+ slot = htab_find_slot (index_table, &tmp, NO_INSERT);
+
+ if (slot && *slot)
+ return ((struct clast_name_index *) *slot)->level;
+
+ return -1;
+}
+
/* For a given clast NAME, returns -1 if it does not correspond to any
parameter, or otherwise, returns the index in the PARAMS or
SCATTERING_DIMENSIONS vector. */
@@ -101,10 +130,11 @@ clast_name_to_index (clast_name_p name, htab_t index_table)
return -1;
}
-/* Records in INDEX_TABLE the INDEX for NAME. */
+/* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
static inline void
-save_clast_name_index (htab_t index_table, const char *name, int index)
+save_clast_name_index (htab_t index_table, const char *name,
+ int index, int level)
{
struct clast_name_index tmp;
PTR *slot;
@@ -116,7 +146,7 @@ save_clast_name_index (htab_t index_table, const char *name, int index)
{
free (*slot);
- *slot = new_clast_name_index (name, index);
+ *slot = new_clast_name_index (name, index, level);
}
}
@@ -139,15 +169,6 @@ eq_clast_name_indexes (const void *e1, const void *e2)
return (elt1->name == elt2->name);
}
-/* For a given scattering dimension, return the new induction variable
- associated to it. */
-
-static inline tree
-newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth)
-{
- return VEC_index (tree, newivs, depth);
-}
-
/* Returns the tree variable from the name NAME that was given in
@@ -172,7 +193,7 @@ clast_name_to_gcc (clast_name_p name, sese region, VEC (tree, heap) *newivs,
index = clast_name_to_index (name, newivs_index);
gcc_assert (index >= 0);
- return newivs_to_depth_to_newiv (newivs, index);
+ return VEC_index (tree, newivs, index);
}
/* Returns the signed maximal precision type for expressions TYPE1 and TYPE2. */
@@ -602,94 +623,6 @@ graphite_create_new_guard (sese region, edge entry_edge,
return exit_edge;
}
-/* Compute the lower bound LOW and upper bound UP for the induction
- variable at LEVEL for the statement PBB, based on the transformed
- scattering of PBB: T|I|G|Cst, with T the scattering transform, I
- the iteration domain, and G the context parameters. */
-
-static void
-compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
-{
- ppl_Pointset_Powerset_C_Polyhedron_t ps;
- ppl_Linear_Expression_t le;
-
- combine_context_id_scat (&ps, pbb, false);
-
- /* Prepare the linear expression corresponding to the level that we
- want to maximize/minimize. */
- {
- ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
- + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
-
- ppl_new_Linear_Expression_with_dimension (&le, dim);
- ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
- }
-
- ppl_max_for_le_pointset (ps, le, up);
- ppl_min_for_le_pointset (ps, le, low);
- ppl_delete_Linear_Expression (le);
- ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
-}
-
-/* Compute the type for the induction variable at LEVEL for the
- statement PBB, based on the transformed schedule of PBB. */
-
-static tree
-compute_type_for_level (poly_bb_p pbb, int level)
-{
- mpz_t low, up;
- tree type;
-
- mpz_init (low);
- mpz_init (up);
-
- compute_bounds_for_level (pbb, level, low, up);
- type = gcc_type_for_interval (low, up);
-
- mpz_clear (low);
- mpz_clear (up);
- return type;
-}
-
-/* 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 type for the induction variable for the loop translated
- from STMT_FOR. */
-
-static tree
-gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for, int level,
- tree lb_type, tree ub_type)
-{
- struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
- struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
- CloogStatement *cs = body->statement;
- poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
-
- return max_signed_precision_type (lb_type, max_precision_type
- (ub_type, compute_type_for_level
- (pbb, level)));
-}
-
/* 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 ENTRY_EDGE. LOOP is inserted into the loop tree and
@@ -703,7 +636,7 @@ graphite_create_new_loop (edge entry_edge,
struct clast_for *stmt,
loop_p outer, VEC (tree, heap) **newivs,
htab_t newivs_index,
- tree type, tree lb, tree ub)
+ tree type, tree lb, tree ub, int level)
{
tree stride = gmp_cst_to_tree (type, stmt->stride);
tree ivvar = create_tmp_var (type, "graphite_IV");
@@ -715,7 +648,7 @@ graphite_create_new_loop (edge entry_edge,
add_referenced_var (ivvar);
save_clast_name_index (newivs_index, stmt->iterator,
- VEC_length (tree, *newivs));
+ VEC_length (tree, *newivs), level);
VEC_safe_push (tree, heap, *newivs, iv);
return loop;
}
@@ -872,6 +805,270 @@ translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
return next_e;
}
+
+/* Compute the lower bound LOW and upper bound UP for the parameter
+ PARAM for the statement PBB, based on the transformed scattering of
+ PBB: T|I|G|Cst, with T the scattering transform, I the iteration
+ domain, and G the context parameters. */
+
+static void
+compute_bounds_for_param (poly_bb_p pbb, int param, mpz_t low, mpz_t up)
+{
+ ppl_Pointset_Powerset_C_Polyhedron_t ps;
+ ppl_Linear_Expression_t le;
+
+ combine_context_id_scat (&ps, pbb, false);
+
+ /* Prepare the linear expression corresponding to the parameter that
+ we want to maximize/minimize. */
+ {
+ ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
+ + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
+
+ ppl_new_Linear_Expression_with_dimension (&le, dim);
+ ppl_set_coef (le, psct_parameter_dim (pbb, param), 1);
+ }
+
+ ppl_max_for_le_pointset (ps, le, up);
+ ppl_min_for_le_pointset (ps, le, low);
+ ppl_delete_Linear_Expression (le);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
+}
+
+/* Compute the lower bound LOW and upper bound UP for the induction
+ variable at LEVEL for the statement PBB, based on the transformed
+ scattering of PBB: T|I|G|Cst, with T the scattering transform, I
+ the iteration domain, and G the context parameters. */
+
+static void
+compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
+{
+ ppl_Pointset_Powerset_C_Polyhedron_t ps;
+ ppl_Linear_Expression_t le;
+
+ combine_context_id_scat (&ps, pbb, false);
+
+ /* Prepare the linear expression corresponding to the level that we
+ want to maximize/minimize. */
+ {
+ ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
+ + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
+
+ ppl_new_Linear_Expression_with_dimension (&le, dim);
+ ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
+ }
+
+ ppl_max_for_le_pointset (ps, le, up);
+ ppl_min_for_le_pointset (ps, le, low);
+ ppl_delete_Linear_Expression (le);
+ ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
+}
+
+/* Return the lower bound LB and upper bound UB of the clast_name NAME. */
+
+static void
+lb_ub_for_name (clast_name_p name, htab_t newivs_index, htab_t params_index,
+ mpz_t lb, mpz_t ub, poly_bb_p pbb)
+{
+ int level;
+
+ if (params_index)
+ {
+ int param = clast_name_to_level (name, params_index);
+
+ if (param >= 0)
+ {
+ compute_bounds_for_param (pbb, param, lb, ub);
+ return;
+ }
+ }
+
+ gcc_assert (newivs_index);
+ level = clast_name_to_level (name, newivs_index);
+ gcc_assert (level >= 0);
+ compute_bounds_for_level (pbb, level, lb, ub);
+}
+
+/* Return the lower bound LB and upper bound UB of the clast_term T. */
+
+static void
+lb_ub_for_term (struct clast_term *t, htab_t newivs_index, htab_t params_index,
+ mpz_t lb, mpz_t ub, poly_bb_p pbb)
+{
+ gcc_assert (t->expr.type == clast_expr_term);
+
+ if (t->var)
+ {
+ mpz_t v;
+ lb_ub_for_name ((clast_name_p) (t->var),
+ newivs_index, params_index, lb, ub, pbb);
+ mpz_init (v);
+ mpz_abs (v, t->val);
+ mpz_mul (lb, lb, v);
+ mpz_mul (ub, ub, v);
+ mpz_clear (v);
+ }
+ else
+ {
+ mpz_set (lb, t->val);
+ mpz_set (ub, t->val);
+ }
+}
+
+static void
+lb_ub_for_expr (struct clast_expr *, htab_t, htab_t, mpz_t, mpz_t, poly_bb_p);
+
+/* Return the lower bound LB and upper bound UB of the clast_reduction R. */
+
+static void
+lb_ub_for_red (struct clast_reduction *r, htab_t newivs_index,
+ htab_t params_index, mpz_t lb, mpz_t ub, poly_bb_p pbb)
+{
+ int i;
+ mpz_t l, u;
+
+ lb_ub_for_expr (r->elts[0], newivs_index, params_index, lb, ub, pbb);
+
+ if (r->n == 1)
+ return;
+
+ mpz_init (l);
+ mpz_init (u);
+
+ for (i = 1; i < r->n; i++)
+ {
+ lb_ub_for_expr (r->elts[i], newivs_index, params_index, l, u, pbb);
+
+ /* As the interval [LB, UB] is used to compute a type for the
+ expression, it should include the bounds of each term of the
+ reduction expression: so take the min of lower bounds and the
+ max of upper bounds. */
+ value_min (lb, lb, l);
+ value_max (ub, ub, u);
+
+ switch (r->type)
+ {
+ case clast_red_sum:
+ /* The interval [LB, UB] should also include the result of
+ the sum. */
+ mpz_add (l, lb, l);
+ mpz_add (u, ub, u);
+ value_min (lb, lb, l);
+ value_max (ub, ub, u);
+ break;
+
+ case clast_red_min:
+ case clast_red_max:
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ mpz_clear (l);
+ mpz_clear (u);
+}
+
+/* Return the type for the clast_binary B used in STMT. */
+
+static void
+lb_ub_for_bin (struct clast_binary *b, htab_t newivs_index,
+ htab_t params_index, mpz_t lb, mpz_t ub, poly_bb_p pbb)
+{
+ lb_ub_for_expr ((struct clast_expr *) b->LHS, newivs_index, params_index,
+ lb, ub, pbb);
+
+ switch (b->type)
+ {
+ case clast_bin_cdiv:
+ case clast_bin_fdiv:
+ case clast_bin_div:
+ case clast_bin_mod:
+ value_min (lb, lb, b->RHS);
+ value_max (ub, ub, b->RHS);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Return the lower bound LB and upper bound UB of the clast_expr E. */
+
+static void
+lb_ub_for_expr (struct clast_expr *e, htab_t newivs_index, htab_t params_index,
+ mpz_t lb, mpz_t ub, poly_bb_p pbb)
+{
+ switch (e->type)
+ {
+ case clast_expr_term:
+ lb_ub_for_term ((struct clast_term *) e,
+ newivs_index, params_index, lb, ub, pbb);
+ break;
+
+ case clast_expr_red:
+ lb_ub_for_red ((struct clast_reduction *) e,
+ newivs_index, params_index, lb, ub, pbb);
+ break;
+
+ case clast_expr_bin:
+ lb_ub_for_bin ((struct clast_binary *) e,
+ newivs_index, params_index, lb, ub, pbb);
+ break;
+
+ case clast_expr_name:
+ lb_ub_for_name ((clast_name_p) e,
+ newivs_index, params_index, lb, ub, pbb);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Returns the type for the CLAST expression E in REGION. */
+
+static tree
+gcc_type_for_clast_expr_from_lb_ub (struct clast_expr *e, htab_t newivs_index,
+ htab_t params_index, poly_bb_p pbb)
+{
+ mpz_t lb, ub;
+ tree type;
+
+ mpz_init (lb);
+ mpz_init (ub);
+
+ lb_ub_for_expr (e, newivs_index, params_index, lb, ub, pbb);
+ type = gcc_type_for_interval (lb, ub);
+
+ mpz_clear (lb);
+ mpz_clear (ub);
+ return type;
+}
+
+/* Walks a CLAST and returns the first statement in the body of a
+ loop. */
+
+static struct clast_user_stmt *
+clast_get_body_of (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 (((struct clast_for *) stmt)->body);
+
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ return clast_get_body_of (((struct clast_guard *) stmt)->then);
+
+ if (CLAST_STMT_IS_A (stmt, stmt_block))
+ return clast_get_body_of (((struct clast_block *) stmt)->body);
+
+ gcc_unreachable ();
+}
+
/* Creates a new if region protecting the loop to be executed, if the execution
count is zero (lb > ub). */
@@ -880,16 +1077,19 @@ graphite_create_new_loop_guard (sese region, edge entry_edge,
struct clast_for *stmt,
VEC (tree, heap) *newivs,
htab_t newivs_index, htab_t params_index,
- int level, tree *type, tree *lb, tree *ub)
+ tree *type, tree *lb, tree *ub)
{
tree cond_expr;
edge exit_edge;
- tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, newivs,
- newivs_index, params_index);
- tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, newivs,
- newivs_index, params_index);
-
- *type = gcc_type_for_iv_of_clast_loop (stmt, level, lb_type, ub_type);
+ struct clast_stmt *cstmt = (struct clast_stmt *) stmt;
+ struct clast_user_stmt *body = clast_get_body_of (cstmt);
+ CloogStatement *cs = body->statement;
+ poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
+ tree lb_type = gcc_type_for_clast_expr_from_lb_ub (stmt->LB, newivs_index,
+ params_index, pbb);
+ tree ub_type = gcc_type_for_clast_expr_from_lb_ub (stmt->UB, newivs_index,
+ params_index, pbb);
+ *type = max_precision_type (lb_type, ub_type);
*lb = clast_to_gcc_expression (*type, stmt->LB, region, newivs,
newivs_index, params_index);
*ub = clast_to_gcc_expression (*type, stmt->UB, region, newivs,
@@ -942,7 +1142,7 @@ translate_clast_for_loop (sese region, loop_p context_loop,
struct loop *loop = graphite_create_new_loop (next_e, stmt,
context_loop, newivs,
newivs_index,
- type, lb, ub);
+ type, lb, ub, level);
edge last_e = single_exit (loop);
edge to_body = single_succ_edge (loop->header);
basic_block after = to_body->dest;
@@ -982,7 +1182,7 @@ translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
tree type, lb, ub;
edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
newivs_index, params_index,
- level, &type, &lb, &ub);
+ &type, &lb, &ub);
edge true_e = get_true_edge_from_guard_bb (next_e->dest);
translate_clast_for_loop (region, context_loop, stmt, true_e, newivs,
@@ -1423,7 +1623,7 @@ create_params_index (htab_t index_table, CloogProgram *prog) {
int i;
for (i = 0; i < nb_parameters; i++)
- save_clast_name_index (index_table, parameters[i], i);
+ save_clast_name_index (index_table, parameters[i], i, i);
}
/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
@@ -124,6 +124,17 @@ ppl_set_coef_tree (ppl_Linear_Expression_t e, ppl_dimension_type i, tree x)
mpz_clear (v);
}
+/* Sets RES to the min of V1 and V2. */
+
+static inline void
+value_min (mpz_t res, mpz_t v1, mpz_t v2)
+{
+ if (mpz_cmp (v1, v2) < 0)
+ mpz_set (res, v1);
+ else
+ mpz_set (res, v2);
+}
+
/* Sets RES to the max of V1 and V2. */
static inline void
@@ -1,6 +1,11 @@
2011-07-05 Sebastian Pop <sebastian.pop@amd.com>
PR tree-optimization/47654
+ * gcc.dg/graphite/run-id-pr47654.c
+
+2011-07-05 Sebastian Pop <sebastian.pop@amd.com>
+
+ PR tree-optimization/47654
* gcc.dg/graphite/block-pr47654.c: New.
2011-07-05 Jason Merrill <jason@redhat.com>
new file mode 100644
@@ -0,0 +1,24 @@
+/* { dg-options "-O -floop-block" } */
+
+int a[128][40];
+
+void __attribute__ ((noinline, noclone))
+foo (void)
+{
+ int i, j;
+ for (i = 0; i < 40; i++)
+ for (j = 0; j < 128; j++)
+ a[j][i] = 4;
+}
+
+int
+main ()
+{
+ int i, j;
+ foo ();
+ for (i = 0; i < 40; i++)
+ for (j = 0; j < 128; j++)
+ if (a[j][i] != 4)
+ __builtin_abort ();
+ return 0;
+}