Hi Tobias,
could you please advise me how to verify the results of gimple code
generation? I've written the first draft of the generation of loops
with empty bodies and tried to verify gimple code using the
representation, which is dumped at the end of the generation of the
dump_file. If we consider the following example, we'll see that cloog
and isl code generator generate similar representation (representation
generated by isl code generator doesn't have body of the loop, as was
expected).
int
main (int n, int *a)
{
int i;
for (i = 0; i < 100; i++)
a[i] = i;
return 0;
}
gcc/graphite-isl-ast-to-gimple.c
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 })
{
<bb 2>:
}
bb_5 (preds = {bb_3 }, succs = {bb_1 })
{
<bb 5>:
# .MEM_10 = PHI <.MEM_3(D)(3)>
# VUSE <.MEM_10>
return 0;
}
loop_2 (header = 3, latch = 4, niter = )
{
bb_3 (preds = {bb_2 bb_4 }, succs = {bb_4 bb_5 })
{
<bb 3>:
# graphite_IV.3_1 = PHI <0(2), graphite_IV.3_14(4)>
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto <bb 4>;
else
goto <bb 5>;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
<bb 4>:
goto <bb 3>;
}
}
}
graphite-clast-to-gimple.c
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 })
{
<bb 2>:
}
bb_5 (preds = {bb_3 }, succs = {bb_1 })
{
<bb 5>:
# .MEM_18 = PHI <.MEM_11(3)>
# VUSE <.MEM_18>
return 0;
}
loop_2 (header = 3, latch = 4, niter = )
{
bb_3 (preds = {bb_2 bb_4 }, succs = {bb_4 bb_5 })
{
<bb 3>:
# graphite_IV.3_1 = PHI <0(2), graphite_IV.3_14(4)>
# .MEM_19 = PHI <.MEM_3(D)(2), .MEM_11(4)>
_2 = (sizetype) graphite_IV.3_1;
_15 = _2 * 4;
_16 = a_6(D) + _15;
_17 = (int) graphite_IV.3_1;
# .MEM_11 = VDEF <.MEM_19>
*_16 = _17;
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto <bb 4>;
else
goto <bb 5>;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
<bb 4>:
goto <bb 3>;
}
}
}
However, this form doesn't have loop guards which are generated by
graphite_create_new_loop_guard in gcc/graphite-isl-ast-to-gimple.c and
by graphite_create_new_loop_guard in graphite-clast-to-gimple.c.
Below is the code of this generation (It still uses isl_int for
generation of isl_expr_int, because the error related to isl/val_gmp.h
still arises. I've tried to use isl 0.12.2 and 0.13, but gotten the
same error).
--
Cheers, Roman Gareev
Index: gcc/graphite-isl-ast-to-gimple.c
===================================================================
--- gcc/graphite-isl-ast-to-gimple.c (revision 212194)
+++ gcc/graphite-isl-ast-to-gimple.c (working copy)
@@ -42,16 +42,620 @@
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
#ifdef HAVE_cloog
#include "graphite-poly.h"
#include "graphite-isl-ast-to-gimple.h"
+#include "graphite-htab.h"
/* This flag is set when an error occurred during the translation of
ISL AST to Gimple. */
static bool graphite_regenerate_error;
+/* Converts a GMP constant VAL to a tree and returns it. */
+
+static tree
+gmp_cst_to_tree (tree type, mpz_t val)
+{
+ tree t = type ? type : integer_type_node;
+ mpz_t tmp;
+
+ mpz_init (tmp);
+ mpz_set (tmp, val);
+ wide_int wi = wi::from_mpz (t, tmp, true);
+ mpz_clear (tmp);
+
+ return wide_int_to_tree (t, wi);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation. */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+ verify_loop_structure ();
+ verify_loop_closed_ssa (true);
+#endif
+}
+
+/* Stores the INDEX in a vector and the loop nesting LEVEL for a given
+ isl_id NAME. BOUND_ONE and BOUND_TWO represent the exact lower and
+ upper bounds that can be inferred from the polyhedral representation. */
+
+typedef struct ast_isl_name_index {
+ int index;
+ int level;
+ const char *name;
+ /* If free_name is set, the content of name was allocated by us and needs
+ to be freed. */
+ char *free_name;
+} *ast_isl_name_index_p;
+
+/* Helper for hashing ast_isl_name_index. */
+
+struct ast_isl_index_hasher
+{
+ typedef ast_isl_name_index value_type;
+ typedef ast_isl_name_index compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+ static inline void remove (value_type *);
+};
+
+/* Computes a hash function for database element E. */
+
+inline hashval_t
+ast_isl_index_hasher::hash (const value_type *e)
+{
+ hashval_t hash = 0;
+
+ int length = strlen (e->name);
+ int i;
+
+ for (i = 0; i < length; ++i)
+ hash = hash | (e->name[i] << (i % 4));
+
+ return hash;
+}
+
+/* Compares database elements ELT1 and ELT2. */
+
+inline bool
+ast_isl_index_hasher::equal (const value_type *elt1, const compare_type *elt2)
+{
+ return strcmp (elt1->name, elt2->name) == 0;
+}
+
+/* Free the memory taken by a ast_isl_name_index struct. */
+
+inline void
+ast_isl_index_hasher::remove (value_type *c)
+{
+ if (c->free_name)
+ free (c->free_name);
+ free (c);
+}
+
+typedef hash_table<ast_isl_index_hasher> ast_isl_index_htab_type;
+
+/* Returns a pointer to a new element of type ast_isl_name_index_p built
+ from NAME, INDEX, LEVEL. */
+
+static inline ast_isl_name_index_p
+new_ast_isl_name_index (const char *name, int index, int level)
+{
+ ast_isl_name_index_p res = XNEW (struct ast_isl_name_index);
+ char *new_name = XNEWVEC (char, strlen (name) + 1);
+ strcpy (new_name, name);
+
+ res->name = new_name;
+ res->free_name = new_name;
+ res->level = level;
+ res->index = index;
+ return res;
+}
+
+/* For a given name of the isl_id, which is stored in the isl_ast_expr EXPR_ID,
+ returns -1 if it does not correspond to any parameter, or otherwise, returns
+ the index in the PARAMS or SCATTERING_DIMENSIONS vector. */
+
+static inline int
+ast_expr_id_to_index (__isl_keep isl_ast_expr *expr_id,
+ ast_isl_index_htab_type *index_table)
+{
+ struct ast_isl_name_index tmp;
+ ast_isl_name_index **slot;
+
+ isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
+ tmp.name = isl_id_get_name (tmp_isl_id);
+ tmp.free_name = NULL;
+
+ slot = index_table->find_slot (&tmp, NO_INSERT);
+
+ isl_id_free (tmp_isl_id);
+ if (slot && *slot)
+ return (*slot)->index;
+
+ return -1;
+}
+
+/* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
+
+static inline void
+save_isl_id_name_index (ast_isl_index_htab_type *index_table,
+ const char *name, int index, int level)
+{
+ struct ast_isl_name_index tmp;
+ ast_isl_name_index **slot;
+
+ tmp.name = name;
+ tmp.free_name = NULL;
+ slot = index_table->find_slot (&tmp, INSERT);
+
+ if (slot)
+ {
+ free (*slot);
+ *slot = new_ast_isl_name_index (name, index, level);
+ }
+}
+
+/* NEWIVS_INDEX binds ISL's scattering name to the index of the tree
+ induction variable in NEWIVS.
+
+ PARAMS_INDEX binds ISL's parameter name to the index of the tree
+ parameter in PARAMS. */
+
+typedef struct ivs_params {
+ vec<tree> params, *newivs;
+ ast_isl_index_htab_type *newivs_index, *params_index;
+ sese region;
+} *ivs_params_p;
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *,
+ ivs_params_p ip);
+
+/* Returns the tree variable from the name of isl_id, which is stored
+ in the isl_ast_expr EXPR_ID that was given in ISL representation. */
+
+static tree
+gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id,
+ ivs_params_p ip)
+{
+ gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
+ int index;
+
+ if (ip->params.exists () && ip->params_index)
+ {
+ index = ast_expr_id_to_index (expr_id, ip->params_index);
+
+ if (index >= 0)
+ return ip->params[index];
+ }
+
+ gcc_assert (ip->newivs && ip->newivs_index);
+ index = ast_expr_id_to_index (expr_id, ip->newivs_index);
+ gcc_assert (index >= 0);
+
+ return (*ip->newivs)[index];
+}
+
+/* Converts a isl_ast_expr_int expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr)
+{
+ gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
+ isl_int val;
+ isl_int_init (val);
+ if (isl_ast_expr_get_int (expr, &val) == -1)
+ {
+ isl_int_clear (val);
+ return NULL_TREE;
+ }
+ else
+ return gmp_cst_to_tree (type, val);
+}
+
+/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+ tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ case isl_ast_op_add:
+ return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_sub:
+ return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_mul:
+ return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_div:
+ return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_fdiv_q:
+ return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_and:
+ return fold_build2 (TRUTH_ANDIF_EXPR, type,
+ tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_or:
+ return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_eq:
+ return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_le:
+ return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_lt:
+ return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_ge:
+ return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ case isl_ast_op_gt:
+ return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+ternary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+ gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_first_expr
+ = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 1);
+ tree tree_second_expr
+ = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ arg_expr = isl_ast_expr_get_op_arg (expr, 2);
+ tree tree_third_expr
+ = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ return fold_build3 (COND_EXPR, type, tree_first_expr,
+ tree_second_expr, tree_third_expr);
+}
+
+/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+unary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+ gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_cond);
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ return fold_build1 (NEGATE_EXPR, type, tree_expr);
+}
+
+/* Converts a isl_ast_expr_op expression E with unknown number of arguments
+ to a GCC expression tree of type TYPE. */
+
+static tree
+nary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip)
+{
+ enum tree_code op_code;
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ case isl_ast_op_max:
+ op_code = MAX_EXPR;
+ break;
+
+ case isl_ast_op_min:
+ op_code = MIN_EXPR;
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
+ tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ isl_ast_expr_free (arg_expr);
+ int i;
+ for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
+ {
+ arg_expr = isl_ast_expr_get_op_arg (expr, i);
+ tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
+ res = fold_build2 (op_code, type, res, t);
+ isl_ast_expr_free (arg_expr);
+ }
+ return res;
+}
+
+
+/* Converts a isl_ast_expr_op expression E to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expr_op (tree type, __isl_keep isl_ast_expr *expr,
+ ivs_params_p ip)
+{
+ gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
+ switch (isl_ast_expr_get_op_type (expr))
+ {
+ /* These isl ast expressions are not supported yet. */
+ case isl_ast_op_error:
+ case isl_ast_op_call:
+ case isl_ast_op_and_then:
+ case isl_ast_op_or_else:
+ case isl_ast_op_pdiv_q:
+ case isl_ast_op_pdiv_r:
+ case isl_ast_op_select:
+ gcc_unreachable ();
+
+ case isl_ast_op_max:
+ case isl_ast_op_min:
+ return nary_op_to_tree (type, expr, ip);
+
+ case isl_ast_op_add:
+ case isl_ast_op_sub:
+ case isl_ast_op_mul:
+ case isl_ast_op_div:
+ case isl_ast_op_fdiv_q:
+ case isl_ast_op_and:
+ case isl_ast_op_or:
+ case isl_ast_op_eq:
+ case isl_ast_op_le:
+ case isl_ast_op_lt:
+ case isl_ast_op_ge:
+ case isl_ast_op_gt:
+ return binary_op_to_tree (type, expr, ip);
+
+ case isl_ast_op_minus:
+ return unary_op_to_tree (type, expr, ip);
+
+ case isl_ast_op_cond:
+ return ternary_op_to_tree (type, expr, ip);
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
+
+/* Converts a ISL AST expression E back to a GCC expression tree of
+ type TYPE. */
+
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *expr,
+ ivs_params_p ip)
+{
+ switch (isl_ast_expr_get_type (expr))
+ {
+ case isl_ast_expr_id:
+ return gcc_expression_from_isl_ast_expr_id (expr, ip);
+
+ case isl_ast_expr_int:
+ return gcc_expression_from_isl_expr_int (type, expr);
+
+ case isl_ast_expr_op:
+ return gcc_expression_from_isl_expr_op (type, expr, ip);
+
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
+
+/* Creates a new LOOP corresponding to isl_ast_node_for. 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
+ becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
+ ISL's scattering name to the induction variable created for the
+ loop of STMT. The new induction variable is inserted in the NEWIVS
+ vector and is of type TYPE. */
+
+static struct loop *
+graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
+ loop_p outer, tree type, tree lb, tree ub,
+ int level, ivs_params_p ip)
+{
+ isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
+ tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
+ isl_ast_expr_free (for_inc);
+ tree ivvar = create_tmp_var (type, "graphite_IV");
+ tree iv, iv_after_increment;
+ loop_p loop = create_empty_loop_on_edge
+ (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
+ outer ? outer : entry_edge->src->loop_father);
+
+ isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
+ isl_id *id = isl_ast_expr_get_id (for_iterator);
+ save_isl_id_name_index (ip->newivs_index, isl_id_get_name (id),
+ (*ip->newivs).length (), level);
+ isl_id_free (id);
+ isl_ast_expr_free (for_iterator);
+ (*ip->newivs).safe_push (iv);
+ return loop;
+}
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+ edge next_e, int level, ivs_params_p ip);
+
+/* Create the loop for a isl_ast_node_for.
+
+ - NEXT_E is the edge where new generated code should be attached. */
+
+static edge
+translate_isl_ast_for_loop (loop_p context_loop,
+ __isl_keep isl_ast_node *node_for, edge next_e,
+ int level, tree type, tree lb, tree ub,
+ ivs_params_p ip)
+{
+ gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+ struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
+ type, lb, ub, level, ip);
+ edge last_e = single_exit (loop);
+ edge to_body = single_succ_edge (loop->header);
+ basic_block after = to_body->dest;
+
+ /* Create a basic block for loop close phi nodes. */
+ last_e = single_succ_edge (split_edge (last_e));
+
+ /* Translate the body of the loop. */
+ isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
+ next_e = translate_isl_ast (loop, for_body, to_body,
+ level + 1, ip);
+ isl_ast_node_free (for_body);
+ redirect_edge_succ_nodup (next_e, after);
+ set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
+
+ /* TODO: Add checking for the loop parallelism. */
+
+ return last_e;
+}
+
+/* Get upper bound from the cond of the for */
+
+static __isl_give isl_ast_expr *
+get_upper_bound (__isl_keep isl_ast_node *node_for)
+{
+ gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+ isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
+ gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
+ isl_ast_expr *res;
+ switch (isl_ast_expr_get_op_type (for_cond))
+ {
+ case isl_ast_op_le:
+ res = isl_ast_expr_get_op_arg (for_cond, 1);
+ break;
+
+ case isl_ast_op_lt:
+ {
+ // (iteraotr < ub) => (iterator <= ub - 1)
+ isl_val *one = isl_val_int_from_si(isl_ast_expr_get_ctx (for_cond), 1);
+ isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
+ res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
+ break;
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+ isl_ast_expr_free (for_cond);
+ return res;
+}
+
+/* Creates a new if region protecting the loop to be executed, if the execution
+ count is zero (lb > ub). */
+
+static edge
+graphite_create_new_loop_guard (edge entry_edge,
+ __isl_keep isl_ast_node *node_for, tree *type,
+ tree *lb, tree *ub, ivs_params_p ip)
+{
+ gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
+ tree cond_expr;
+ edge exit_edge;
+
+ *type = build_nonstandard_integer_type (128, 0);
+ isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
+ *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
+ isl_ast_expr_free (for_init);
+ isl_ast_expr *upper_bound = get_upper_bound (node_for);
+ *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
+ isl_ast_expr_free (upper_bound);
+
+ /* When ub is simply a constant or a parameter, use lb <= ub. */
+ if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
+ cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
+ else
+ {
+ tree one = (POINTER_TYPE_P (*type)
+ ? convert_to_ptrofftype (integer_one_node)
+ : fold_convert (*type, integer_one_node));
+ /* Adding +1 and using LT_EXPR helps with loop latches that have a
+ loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
+ becomes 2^k-1 due to integer overflow, and the condition lb <= ub
+ is true, even if we do not want this. However lb < ub + 1 is false,
+ as expected. */
+ tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
+ : PLUS_EXPR, *type, *ub, one);
+
+ cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
+ }
+
+ exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
+
+ return exit_edge;
+}
+
+/* Translates a isl_ast_node_for to Gimple. */
+
+static edge
+translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
+ edge next_e, int level, ivs_params_p ip)
+{
+ gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
+ tree type, lb, ub;
+ edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
+ &lb, &ub, ip);
+ edge true_e = get_true_edge_from_guard_bb (next_e->dest);
+
+ translate_isl_ast_for_loop (context_loop, node, true_e,
+ level, type, lb, ub, ip);
+ return last_e;
+}
+
+/* Translates a ISL AST node NODE to GCC representation in the
+ context of a SESE. */
+
+static edge
+translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
+ edge next_e, int level, ivs_params_p ip)
+{
+ switch (isl_ast_node_get_type (node))
+ {
+ case isl_ast_node_error:
+ gcc_unreachable ();
+
+ case isl_ast_node_for:
+ return translate_isl_ast_node_for (context_loop, node,
+ next_e, level, ip);
+
+ case isl_ast_node_if:
+ return next_e;
+
+ case isl_ast_node_user:
+ return next_e;
+
+ case isl_ast_node_block:
+ return next_e;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
/* Prints NODE to FILE. */
void
@@ -65,25 +669,95 @@
isl_printer_free (prn);
}
+/* Rename parameters of the schedule_isl according to the SSA form. */
+
+static __isl_give isl_map *
+add_names_to_schedule_isl (scop_p scop, __isl_take isl_map *schedule_isl,
+ ast_isl_index_htab_type *params_index)
+{
+ sese region = SCOP_REGION (scop);
+ int i;
+ int nb_parameters = SESE_PARAMS (region).length ();
+ gcc_assert (nb_parameters == (short) isl_map_dim (schedule_isl,
+ isl_dim_param));
+
+ for (i = 0; i < nb_parameters; i++)
+ {
+ tree param = SESE_PARAMS (region)[i];
+ const char *name = get_name (param);
+ int len;
+ char *parameter;
+
+ if (!name)
+ name = "T";
+
+ len = strlen (name);
+ len += 17;
+ parameter = XNEWVEC (char, len + 1);
+ snprintf (parameter, len, "%s_%d", name, SSA_NAME_VERSION (param));
+ save_isl_id_name_index (params_index, parameter, i, i);
+
+ schedule_isl = isl_map_set_dim_name (schedule_isl, isl_dim_param, i,
+ parameter);
+ free (parameter);
+ }
+
+ return schedule_isl;
+}
+
+/* Rename parameters of the context according to the SSA form. */
+
+static __isl_give isl_set *
+add_names_to_context_isl (scop_p scop, __isl_take isl_set *context_isl)
+{
+ sese region = SCOP_REGION (scop);
+ int i;
+ int nb_parameters = SESE_PARAMS (region).length ();
+ gcc_assert (nb_parameters == (short) isl_set_dim (context_isl,
+ isl_dim_param));
+
+ for (i = 0; i < nb_parameters; i++)
+ {
+ tree param = SESE_PARAMS (region)[i];
+ const char *name = get_name (param);
+ int len;
+ char *parameter;
+
+ if (!name)
+ name = "T";
+
+ len = strlen (name);
+ len += 17;
+ parameter = XNEWVEC (char, len + 1);
+ snprintf (parameter, len, "%s_%d", name, SSA_NAME_VERSION (param));
+ context_isl = isl_set_set_dim_name (context_isl, isl_dim_param, i,
+ parameter);
+ free (parameter);
+ }
+
+ return context_isl;
+}
+
/* Generates a build, which specifies the constraints on the parameters. */
-static isl_ast_build *
+static __isl_give isl_ast_build *
generate_isl_context (scop_p scop)
{
isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
+ context_isl = add_names_to_context_isl (scop, context_isl);
return isl_ast_build_from_context (context_isl);
}
/* Generates a schedule, which specifies an order used to
visit elements in a domain. */
-static isl_union_map *
+static __isl_give isl_map *
generate_isl_schedule (scop_p scop)
{
int i;
poly_bb_p pbb;
- isl_union_map *schedule_isl =
- isl_union_map_empty (isl_set_get_space (scop->context));
+ isl_map *schedule_isl =
+ isl_map_empty (isl_set_get_space (scop->context));
FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
{
@@ -96,19 +770,26 @@
bb_schedule = isl_map_intersect_domain (bb_schedule,
isl_set_copy (pbb->domain));
schedule_isl =
- isl_union_map_union (schedule_isl,
- isl_union_map_from_map (bb_schedule));
+ isl_map_union (schedule_isl, bb_schedule);
}
return schedule_isl;
}
-static isl_ast_node *
-scop_to_isl_ast (scop_p scop)
+static __isl_give isl_ast_node *
+scop_to_isl_ast (scop_p scop, ast_isl_index_htab_type *params_index)
{
- isl_union_map *schedule_isl = generate_isl_schedule (scop);
+ /* Generate loop upper bounds that consist of the current loop iterator,
+ an operator (< or <=) and an expression not involving the iterator.
+ If this option is not set, then the current loop iterator may appear several
+ times in the upper bound. See the isl manual for more details. */
+ isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
+
+ isl_map *schedule_isl = generate_isl_schedule (scop);
+ schedule_isl = add_names_to_schedule_isl (scop, schedule_isl, params_index);
isl_ast_build *context_isl = generate_isl_context (scop);
- isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
- schedule_isl);
+ isl_ast_node *ast_isl
+ = isl_ast_build_ast_from_schedule (context_isl,
+ isl_union_map_from_map (schedule_isl));
isl_ast_build_free (context_isl);
return ast_isl;
}
@@ -117,21 +798,74 @@
the given SCOP. Return true if code generation succeeded.
FIXME: This is not yet a full implementation of the code generator
- with ISL ASTs. Generation of GIMPLE code is have to be added. */
+ with ISL ASTs. Generation of GIMPLE code is have to be completed. */
bool
graphite_regenerate_ast_isl (scop_p scop)
{
+ auto_vec<tree, 10> newivs;
+ loop_p context_loop;
+ sese region = SCOP_REGION (scop);
+ ifsese if_region = NULL;
+ ast_isl_index_htab_type *newivs_index, *params_index;
+ isl_ast_node *root_node;
+ struct ivs_params ip;
+
timevar_push (TV_GRAPHITE_CODE_GEN);
graphite_regenerate_error = false;
- isl_ast_node *root_node = scop_to_isl_ast (scop);
+
+ params_index = new ast_isl_index_htab_type (10);
+
+ root_node = scop_to_isl_ast (scop, params_index);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nISL AST generated by ISL: \n");
print_isl_ast_node (dump_file, root_node, scop->ctx);
+ fprintf (dump_file, "\n");
}
+
+ recompute_all_dominators ();
+ graphite_verify ();
+
+ if_region = move_sese_in_condition (region);
+ sese_insert_phis_for_liveouts (region,
+ if_region->region->exit->src,
+ if_region->false_region->exit,
+ if_region->true_region->exit);
+ recompute_all_dominators ();
+ graphite_verify ();
+
+ context_loop = SESE_ENTRY (region)->src->loop_father;
+ newivs_index = new ast_isl_index_htab_type (10);
+
+ ip.newivs = &newivs;
+ ip.newivs_index = newivs_index;
+ ip.params = SESE_PARAMS (region);
+ ip.params_index = params_index;
+ ip.region = region;
+
+ translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
+ 0, &ip);
+ graphite_verify ();
+ scev_reset ();
+ recompute_all_dominators ();
+ graphite_verify ();
+
+ if (graphite_regenerate_error)
+ set_ifsese_condition (if_region, integer_zero_node);
+
+ free (if_region->true_region);
+ free (if_region->region);
+ free (if_region);
+
+ delete newivs_index;
+ newivs_index = NULL;
+ delete params_index;
+ params_index = NULL;
isl_ast_node_free (root_node);
timevar_pop (TV_GRAPHITE_CODE_GEN);
+ /* TODO: Add dump */
return !graphite_regenerate_error;
}
#endif
