1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
24 #include "diagnostic-core.h"
25 #include "tree-flow.h"
26 #include "tree-dump.h"
28 #include "tree-chrec.h"
29 #include "tree-data-ref.h"
30 #include "tree-scalar-evolution.h"
34 #include "cloog/cloog.h"
36 #include "graphite-cloog-util.h"
37 #include "graphite-ppl.h"
38 #include "graphite-poly.h"
39 #include "graphite-clast-to-gimple.h"
40 #include "graphite-dependences.h"
41 #include "graphite-cloog-compat.h"
43 #ifndef CLOOG_LANGUAGE_C
44 #define CLOOG_LANGUAGE_C LANGUAGE_C
47 /* This flag is set when an error occurred during the translation of
49 static bool gloog_error;
51 /* Verifies properties that GRAPHITE should maintain during translation. */
54 graphite_verify (void)
56 #ifdef ENABLE_CHECKING
57 verify_loop_structure ();
58 verify_dominators (CDI_DOMINATORS);
59 verify_loop_closed_ssa (true);
63 /* Stores the INDEX in a vector and the loop nesting LEVEL for a given
64 clast NAME. LB and UB represent the exact lower and upper bounds
65 that can be inferred from the polyhedral representation. */
67 typedef struct clast_name_index {
72 } *clast_name_index_p;
74 /* Returns a pointer to a new element of type clast_name_index_p built
75 from NAME, INDEX, LEVEL, LB, and UB. */
77 static inline clast_name_index_p
78 new_clast_name_index (const char *name, int index, int level,
81 clast_name_index_p res = XNEW (struct clast_name_index);
88 mpz_set (res->lb, lb);
89 mpz_set (res->ub, ub);
93 /* Free the memory taken by a clast_name_index struct. */
96 free_clast_name_index (void *ptr)
98 struct clast_name_index *c = (struct clast_name_index *) ptr;
104 /* For a given clast NAME, returns -1 if NAME is not in the
105 INDEX_TABLE, otherwise returns the loop level for the induction
106 variable NAME, or if it is a parameter, the parameter number in the
107 vector of parameters. */
110 clast_name_to_level (clast_name_p name, htab_t index_table)
112 struct clast_name_index tmp;
116 gcc_assert (name->type == clast_expr_name);
117 tmp.name = ((const struct clast_name *) name)->name;
122 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
125 return ((struct clast_name_index *) *slot)->level;
130 /* For a given clast NAME, returns -1 if it does not correspond to any
131 parameter, or otherwise, returns the index in the PARAMS or
132 SCATTERING_DIMENSIONS vector. */
135 clast_name_to_index (clast_name_p name, htab_t index_table)
137 struct clast_name_index tmp;
141 gcc_assert (name->type == clast_expr_name);
142 tmp.name = ((const struct clast_name *) name)->name;
147 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
150 return ((struct clast_name_index *) *slot)->index;
155 /* For a given clast NAME, initializes the lower and upper bounds LB
156 and UB stored in the INDEX_TABLE. Returns true when NAME has been
157 found in the INDEX_TABLE, false otherwise. */
160 clast_name_to_lb_ub (clast_name_p name, htab_t index_table, mpz_t lb, mpz_t ub)
162 struct clast_name_index tmp;
166 gcc_assert (name->type == clast_expr_name);
167 tmp.name = ((const struct clast_name *) name)->name;
172 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
176 mpz_set (lb, ((struct clast_name_index *) *slot)->lb);
177 mpz_set (ub, ((struct clast_name_index *) *slot)->ub);
184 /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
187 save_clast_name_index (htab_t index_table, const char *name,
188 int index, int level, mpz_t lb, mpz_t ub)
190 struct clast_name_index tmp;
194 slot = htab_find_slot (index_table, &tmp, INSERT);
200 *slot = new_clast_name_index (name, index, level, lb, ub);
204 /* Computes a hash function for database element ELT. */
206 static inline hashval_t
207 clast_name_index_elt_info (const void *elt)
209 return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
212 /* Compares database elements E1 and E2. */
215 eq_clast_name_indexes (const void *e1, const void *e2)
217 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
218 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
220 return (elt1->name == elt2->name);
225 /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
226 induction variable in NEWIVS.
228 PARAMS_INDEX binds CLooG's parameter name to the index of the tree
229 parameter in PARAMS. */
231 typedef struct ivs_params {
232 VEC (tree, heap) *params, **newivs;
233 htab_t newivs_index, params_index;
237 /* Returns the tree variable from the name NAME that was given in
238 Cloog representation. */
241 clast_name_to_gcc (clast_name_p name, ivs_params_p ip)
245 if (ip->params && ip->params_index)
247 index = clast_name_to_index (name, ip->params_index);
250 return VEC_index (tree, ip->params, index);
253 gcc_assert (*(ip->newivs) && ip->newivs_index);
254 index = clast_name_to_index (name, ip->newivs_index);
255 gcc_assert (index >= 0);
257 return VEC_index (tree, *(ip->newivs), index);
260 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
263 max_precision_type (tree type1, tree type2)
265 enum machine_mode mode;
266 int p1, p2, precision;
269 if (POINTER_TYPE_P (type1))
272 if (POINTER_TYPE_P (type2))
275 if (TYPE_UNSIGNED (type1)
276 && TYPE_UNSIGNED (type2))
277 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
279 p1 = TYPE_PRECISION (type1);
280 p2 = TYPE_PRECISION (type2);
283 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
285 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
287 if (precision > BITS_PER_WORD)
290 return integer_type_node;
293 mode = smallest_mode_for_size (precision, MODE_INT);
294 precision = GET_MODE_PRECISION (mode);
295 type = build_nonstandard_integer_type (precision, false);
300 return integer_type_node;
307 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
309 /* Converts a Cloog reduction expression R with reduction operation OP
310 to a GCC expression tree of type TYPE. */
313 clast_to_gcc_expression_red (tree type, enum tree_code op,
314 struct clast_reduction *r, ivs_params_p ip)
317 tree res = clast_to_gcc_expression (type, r->elts[0], ip);
318 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
320 for (i = 1; i < r->n; i++)
322 tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
323 res = fold_build2 (op, type, res, t);
329 /* Converts a Cloog AST expression E back to a GCC expression tree of
333 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
337 case clast_expr_term:
339 struct clast_term *t = (struct clast_term *) e;
343 if (mpz_cmp_si (t->val, 1) == 0)
345 tree name = clast_name_to_gcc (t->var, ip);
347 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
348 name = fold_convert (sizetype, name);
350 name = fold_convert (type, name);
354 else if (mpz_cmp_si (t->val, -1) == 0)
356 tree name = clast_name_to_gcc (t->var, ip);
358 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
359 name = fold_convert (sizetype, name);
361 name = fold_convert (type, name);
363 return fold_build1 (NEGATE_EXPR, type, name);
367 tree name = clast_name_to_gcc (t->var, ip);
368 tree cst = gmp_cst_to_tree (type, t->val);
370 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
371 name = fold_convert (sizetype, name);
373 name = fold_convert (type, name);
375 if (!POINTER_TYPE_P (type))
376 return fold_build2 (MULT_EXPR, type, cst, name);
383 return gmp_cst_to_tree (type, t->val);
388 struct clast_reduction *r = (struct clast_reduction *) e;
393 return clast_to_gcc_expression_red
394 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
398 return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
401 return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
411 struct clast_binary *b = (struct clast_binary *) e;
412 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
413 tree tl = clast_to_gcc_expression (type, lhs, ip);
414 tree tr = gmp_cst_to_tree (type, b->RHS);
419 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
422 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
425 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
428 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
442 /* Return a type that could represent the values between V1 and V2. */
445 type_for_interval (mpz_t v1, mpz_t v2)
449 enum machine_mode mode;
451 int precision = MAX (mpz_sizeinbase (v1, 2),
452 mpz_sizeinbase (v2, 2));
454 if (precision > BITS_PER_WORD)
457 return integer_type_node;
460 if (mpz_cmp (v1, v2) <= 0)
461 unsigned_p = (mpz_sgn (v1) >= 0);
463 unsigned_p = (mpz_sgn (v2) >= 0);
465 mode = smallest_mode_for_size (precision, MODE_INT);
466 wider_precision = GET_MODE_PRECISION (mode);
468 /* As we want to generate signed types as much as possible, try to
469 fit the interval [v1, v2] in a signed type. For example,
470 supposing that we have the interval [0, 100], instead of
471 generating unsigned char, we want to generate a signed char. */
472 if (unsigned_p && precision < wider_precision)
475 type = build_nonstandard_integer_type (wider_precision, unsigned_p);
480 return integer_type_node;
486 /* Return a type that could represent the integer value VAL, or
487 otherwise return NULL_TREE. */
490 type_for_value (mpz_t val)
492 return type_for_interval (val, val);
495 /* Return the type for the clast_term T. Initializes V1 and V2 to the
496 bounds of the term. */
499 type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t v1, mpz_t v2)
501 clast_name_p name = t->var;
504 gcc_assert (t->expr.type == clast_expr_term);
508 mpz_set (v1, t->val);
509 mpz_set (v2, t->val);
510 return type_for_value (t->val);
513 if (ip->params && ip->params_index)
514 found = clast_name_to_lb_ub (name, ip->params_index, v1, v2);
518 gcc_assert (*(ip->newivs) && ip->newivs_index);
519 found = clast_name_to_lb_ub (name, ip->newivs_index, v1, v2);
523 mpz_mul (v1, v1, t->val);
524 mpz_mul (v2, v2, t->val);
526 return TREE_TYPE (clast_name_to_gcc (name, ip));
530 type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t);
532 /* Return the type for the clast_reduction R. Initializes V1 and V2
533 to the bounds of the reduction expression. */
536 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip,
540 tree type = type_for_clast_expr (r->elts[0], ip, v1, v2);
541 mpz_t b1, b2, m1, m2;
551 for (i = 1; i < r->n; i++)
553 tree t = type_for_clast_expr (r->elts[i], ip, b1, b2);
554 type = max_precision_type (type, t);
559 value_min (m1, v1, v2);
560 value_min (m2, b1, b2);
561 mpz_add (v1, m1, m2);
563 value_max (m1, v1, v2);
564 value_max (m2, b1, b2);
565 mpz_add (v2, m1, m2);
569 value_min (v1, v1, v2);
570 value_min (v2, b1, b2);
574 value_max (v1, v1, v2);
575 value_max (v2, b1, b2);
589 /* Return a type that can represent the result of the reduction. */
590 return max_precision_type (type, type_for_interval (v1, v2));
593 /* Return the type for the clast_binary B used in STMT. */
596 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t v1, mpz_t v2)
599 tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip, v1, v2);
600 tree r = type_for_value (b->RHS);
601 tree type = max_precision_type (l, r);
606 mpz_mdiv (v1, v1, b->RHS);
607 mpz_mdiv (v2, v2, b->RHS);
611 mpz_mdiv (v1, v1, b->RHS);
612 mpz_mdiv (v2, v2, b->RHS);
614 mpz_add (v1, v1, one);
615 mpz_add (v2, v2, one);
620 mpz_div (v1, v1, b->RHS);
621 mpz_div (v2, v2, b->RHS);
625 mpz_mod (v1, v1, b->RHS);
626 mpz_mod (v2, v2, b->RHS);
633 /* Return a type that can represent the result of the reduction. */
634 return max_precision_type (type, type_for_interval (v1, v2));
637 /* Returns the type for the CLAST expression E when used in statement
641 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t v1, mpz_t v2)
645 case clast_expr_term:
646 return type_for_clast_term ((struct clast_term *) e, ip, v1, v2);
649 return type_for_clast_red ((struct clast_reduction *) e, ip, v1, v2);
652 return type_for_clast_bin ((struct clast_binary *) e, ip, v1, v2);
661 /* Returns the type for the equation CLEQ. */
664 type_for_clast_eq (struct clast_equation *cleq, ivs_params_p ip)
672 l = type_for_clast_expr (cleq->LHS, ip, v1, v2);
673 r = type_for_clast_expr (cleq->RHS, ip, v1, v2);
677 return max_precision_type (l, r);
680 /* Translates a clast equation CLEQ to a tree. */
683 graphite_translate_clast_equation (struct clast_equation *cleq,
687 tree type = type_for_clast_eq (cleq, ip);
688 tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
689 tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
694 else if (cleq->sign > 0)
700 return fold_build2 (comp, boolean_type_node, lhs, rhs);
703 /* Creates the test for the condition in STMT. */
706 graphite_create_guard_cond_expr (struct clast_guard *stmt,
712 for (i = 0; i < stmt->n; i++)
714 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
717 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
725 /* Creates a new if region corresponding to Cloog's guard. */
728 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
731 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
732 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
736 /* Compute the lower bound LOW and upper bound UP for the parameter
737 PARAM in scop SCOP based on the constraints in the context. */
740 compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
742 ppl_Linear_Expression_t le;
744 /* Prepare the linear expression corresponding to the parameter that
745 we want to maximize/minimize. */
746 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
747 ppl_set_coef (le, param, 1);
749 ppl_max_for_le_pointset (SCOP_CONTEXT (scop), le, up);
750 ppl_min_for_le_pointset (SCOP_CONTEXT (scop), le, low);
751 ppl_delete_Linear_Expression (le);
754 /* Compute the lower bound LOW and upper bound UP for the induction
755 variable at LEVEL for the statement PBB, based on the transformed
756 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
757 the iteration domain, and G the context parameters. */
760 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
762 ppl_Pointset_Powerset_C_Polyhedron_t ps;
763 ppl_Linear_Expression_t le;
765 combine_context_id_scat (&ps, pbb, false);
767 /* Prepare the linear expression corresponding to the level that we
768 want to maximize/minimize. */
770 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
771 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
773 ppl_new_Linear_Expression_with_dimension (&le, dim);
774 ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
777 ppl_max_for_le_pointset (ps, le, up);
778 ppl_min_for_le_pointset (ps, le, low);
779 ppl_delete_Linear_Expression (le);
780 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
783 /* Walks a CLAST and returns the first statement in the body of a
786 FIXME: This function should not be used to get a PBB in the STMT
787 loop in order to find out the iteration domain of the loop: the
788 counter example from Tobias is:
790 | for (i = 0; i < 100; i++)
797 This function would return S1 whose iteration domain contains only
798 one point "i = 0", whereas the iteration domain of S2 has 100 points.
800 This should be implemented using some functionality existing in
803 static struct clast_user_stmt *
804 clast_get_body_of_loop (struct clast_stmt *stmt)
807 || CLAST_STMT_IS_A (stmt, stmt_user))
808 return (struct clast_user_stmt *) stmt;
810 if (CLAST_STMT_IS_A (stmt, stmt_for))
811 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
813 if (CLAST_STMT_IS_A (stmt, stmt_guard))
814 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
816 if (CLAST_STMT_IS_A (stmt, stmt_block))
817 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
822 /* Returns the type for the induction variable for the loop translated
826 type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
829 tree lb_type, ub_type;
834 lb_type = type_for_clast_expr (stmt_for->LB, ip, v1, v2);
835 ub_type = type_for_clast_expr (stmt_for->UB, ip, v1, v2);
840 return max_precision_type (lb_type, ub_type);
843 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
844 induction variable for the new LOOP. New LOOP is attached to CFG
845 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
846 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
847 CLooG's scattering name to the induction variable created for the
848 loop of STMT. The new induction variable is inserted in the NEWIVS
849 vector and is of type TYPE. */
852 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
853 loop_p outer, tree type, tree lb, tree ub,
854 int level, ivs_params_p ip)
858 struct clast_user_stmt *body
859 = clast_get_body_of_loop ((struct clast_stmt *) stmt);
860 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
862 tree stride = gmp_cst_to_tree (type, stmt->stride);
863 tree ivvar = create_tmp_var (type, "graphite_IV");
864 tree iv, iv_after_increment;
865 loop_p loop = create_empty_loop_on_edge
866 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
867 outer ? outer : entry_edge->src->loop_father);
869 add_referenced_var (ivvar);
873 compute_bounds_for_level (pbb, level, low, up);
874 save_clast_name_index (ip->newivs_index, stmt->iterator,
875 VEC_length (tree, *(ip->newivs)), level, low, up);
878 VEC_safe_push (tree, heap, *(ip->newivs), iv);
882 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
883 induction variables of the loops around GBB in SESE. */
886 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
889 struct clast_stmt *t;
891 CloogStatement *cs = user_stmt->statement;
892 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
893 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
899 for (t = user_stmt->substitutions; t; t = t->next, depth++)
901 struct clast_expr *expr = (struct clast_expr *)
902 ((struct clast_assignment *)t)->RHS;
903 tree type = type_for_clast_expr (expr, ip, v1, v2);
904 tree new_name = clast_to_gcc_expression (type, expr, ip);
905 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
907 VEC_replace (tree, iv_map, old_loop->num, new_name);
914 /* Construct bb_pbb_def with BB and PBB. */
917 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
919 bb_pbb_def *bb_pbb_p;
921 bb_pbb_p = XNEW (bb_pbb_def);
928 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
931 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
937 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
940 *x = new_bb_pbb_def (bb, pbb);
943 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
946 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
952 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
955 return ((bb_pbb_def *) *slot)->pbb;
960 /* Check data dependency in LOOP at level LEVEL.
961 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
965 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
968 basic_block *bbs = get_loop_body_in_dom_order (loop);
970 for (i = 0; i < loop->num_nodes; i++)
972 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
977 for (j = 0; j < loop->num_nodes; j++)
979 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
984 if (dependency_between_pbbs_p (pbb1, pbb2, level))
997 /* Translates a clast user statement STMT to gimple.
999 - NEXT_E is the edge where new generated code should be attached.
1000 - CONTEXT_LOOP is the loop in which the generated code will be placed
1001 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1004 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1005 htab_t bb_pbb_mapping, ivs_params_p ip)
1009 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
1010 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1011 VEC (tree, heap) *iv_map;
1013 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1016 nb_loops = number_of_loops ();
1017 iv_map = VEC_alloc (tree, heap, nb_loops);
1018 for (i = 0; i < nb_loops; i++)
1019 VEC_quick_push (tree, iv_map, NULL_TREE);
1021 build_iv_mapping (iv_map, stmt, ip);
1022 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1024 VEC_free (tree, heap, iv_map);
1026 new_bb = next_e->src;
1027 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1028 update_ssa (TODO_update_ssa);
1033 /* Creates a new if region protecting the loop to be executed, if the execution
1034 count is zero (lb > ub). */
1037 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1038 tree *type, tree *lb, tree *ub,
1044 *type = type_for_clast_for (stmt, ip);
1045 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1046 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1048 /* When ub is simply a constant or a parameter, use lb <= ub. */
1049 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1050 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1053 tree one = (POINTER_TYPE_P (*type)
1055 : fold_convert (*type, integer_one_node));
1056 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1057 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
1058 2^k-1 due to integer overflow, and the condition lb <= ub is true,
1059 even if we do not want this. However lb < ub + 1 is false, as
1061 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1062 : PLUS_EXPR, *type, *ub, one);
1064 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1067 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1073 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1075 /* Create the loop for a clast for statement.
1077 - NEXT_E is the edge where new generated code should be attached.
1078 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1081 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1082 edge next_e, htab_t bb_pbb_mapping, int level,
1083 tree type, tree lb, tree ub, ivs_params_p ip)
1085 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1086 type, lb, ub, level, ip);
1087 edge last_e = single_exit (loop);
1088 edge to_body = single_succ_edge (loop->header);
1089 basic_block after = to_body->dest;
1091 /* Create a basic block for loop close phi nodes. */
1092 last_e = single_succ_edge (split_edge (last_e));
1094 /* Translate the body of the loop. */
1095 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1097 redirect_edge_succ_nodup (next_e, after);
1098 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1100 if (flag_loop_parallelize_all
1101 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
1102 loop->can_be_parallel = true;
1107 /* Translates a clast for statement STMT to gimple. First a guard is created
1108 protecting the loop, if it is executed zero times. In this guard we create
1109 the real loop structure.
1111 - NEXT_E is the edge where new generated code should be attached.
1112 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1115 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1116 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1119 edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1121 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1123 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1128 /* Translates a clast guard statement STMT to gimple.
1130 - NEXT_E is the edge where new generated code should be attached.
1131 - CONTEXT_LOOP is the loop in which the generated code will be placed
1132 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1135 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1136 edge next_e, htab_t bb_pbb_mapping, int level,
1139 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1140 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1142 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1146 /* Translates a CLAST statement STMT to GCC representation in the
1149 - NEXT_E is the edge where new generated code should be attached.
1150 - CONTEXT_LOOP is the loop in which the generated code will be placed
1151 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1154 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1155 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1160 if (CLAST_STMT_IS_A (stmt, stmt_root))
1163 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1164 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1165 next_e, bb_pbb_mapping, ip);
1167 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1168 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1169 next_e, bb_pbb_mapping, level, ip);
1171 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1172 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1173 next_e, bb_pbb_mapping, level, ip);
1175 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1176 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1177 next_e, bb_pbb_mapping, level, ip);
1181 recompute_all_dominators ();
1184 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1188 /* Free the SCATTERING domain list. */
1191 free_scattering (CloogScatteringList *scattering)
1195 CloogScattering *dom = cloog_scattering (scattering);
1196 CloogScatteringList *next = cloog_next_scattering (scattering);
1198 cloog_scattering_free (dom);
1204 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1205 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1206 from 0 to scop_nb_loops (scop). */
1209 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1211 sese region = SCOP_REGION (scop);
1213 int nb_iterators = scop_max_loop_depth (scop);
1214 int nb_scattering = cloog_program_nb_scattdims (prog);
1215 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1216 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1217 char **scattering = XNEWVEC (char *, nb_scattering);
1218 char **parameters= XNEWVEC (char *, nb_parameters);
1220 cloog_program_set_names (prog, cloog_names_malloc ());
1222 for (i = 0; i < nb_parameters; i++)
1224 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1225 const char *name = get_name (param);
1231 len = strlen (name);
1233 parameters[i] = XNEWVEC (char, len + 1);
1234 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1237 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1238 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1240 for (i = 0; i < nb_iterators; i++)
1243 iterators[i] = XNEWVEC (char, len);
1244 snprintf (iterators[i], len, "git_%d", i);
1247 cloog_names_set_nb_iterators (cloog_program_names (prog),
1249 cloog_names_set_iterators (cloog_program_names (prog),
1252 for (i = 0; i < nb_scattering; i++)
1255 scattering[i] = XNEWVEC (char, len);
1256 snprintf (scattering[i], len, "scat_%d", i);
1259 cloog_names_set_nb_scattering (cloog_program_names (prog),
1261 cloog_names_set_scattering (cloog_program_names (prog),
1265 /* Initialize a CLooG input file. */
1268 init_cloog_input_file (int scop_number)
1270 FILE *graphite_out_file;
1271 int len = strlen (dump_base_name);
1272 char *dumpname = XNEWVEC (char, len + 25);
1273 char *s_scop_number = XNEWVEC (char, 15);
1275 memcpy (dumpname, dump_base_name, len + 1);
1276 strip_off_ending (dumpname, len);
1277 sprintf (s_scop_number, ".%d", scop_number);
1278 strcat (dumpname, s_scop_number);
1279 strcat (dumpname, ".cloog");
1280 graphite_out_file = fopen (dumpname, "w+b");
1282 if (graphite_out_file == 0)
1283 fatal_error ("can%'t open %s for writing: %m", dumpname);
1287 return graphite_out_file;
1290 /* Build cloog program for SCoP. */
1293 build_cloog_prog (scop_p scop, CloogProgram *prog,
1294 CloogOptions *options)
1297 int max_nb_loops = scop_max_loop_depth (scop);
1299 CloogLoop *loop_list = NULL;
1300 CloogBlockList *block_list = NULL;
1301 CloogScatteringList *scattering = NULL;
1302 int nbs = 2 * max_nb_loops + 1;
1305 cloog_program_set_context
1306 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1307 scop_nb_params (scop), cloog_state));
1308 nbs = unify_scattering_dimensions (scop);
1309 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1310 cloog_program_set_nb_scattdims (prog, nbs);
1311 initialize_cloog_names (scop, prog);
1313 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1315 CloogStatement *stmt;
1319 /* Dead code elimination: when the domain of a PBB is empty,
1320 don't generate code for the PBB. */
1321 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1324 /* Build the new statement and its block. */
1325 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1326 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1327 scop_nb_params (scop),
1329 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1330 cloog_statement_set_usr (stmt, pbb);
1332 /* Build loop list. */
1334 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1335 cloog_loop_set_next (new_loop_list, loop_list);
1336 cloog_loop_set_domain (new_loop_list, dom);
1337 cloog_loop_set_block (new_loop_list, block);
1338 loop_list = new_loop_list;
1341 /* Build block list. */
1343 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1345 cloog_block_list_set_next (new_block_list, block_list);
1346 cloog_block_list_set_block (new_block_list, block);
1347 block_list = new_block_list;
1350 /* Build scattering list. */
1352 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1353 CloogScatteringList *new_scattering
1354 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1355 ppl_Polyhedron_t scat;
1356 CloogScattering *dom;
1358 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1359 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1360 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1363 cloog_set_next_scattering (new_scattering, scattering);
1364 cloog_set_scattering (new_scattering, dom);
1365 scattering = new_scattering;
1369 cloog_program_set_loop (prog, loop_list);
1370 cloog_program_set_blocklist (prog, block_list);
1372 for (i = 0; i < nbs; i++)
1375 cloog_program_set_scaldims (prog, scaldims);
1377 /* Extract scalar dimensions to simplify the code generation problem. */
1378 cloog_program_extract_scalars (prog, scattering, options);
1380 /* Dump a .cloog input file, if requested. This feature is only
1381 enabled in the Graphite branch. */
1384 static size_t file_scop_number = 0;
1385 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1387 cloog_program_dump_cloog (cloog_file, prog, scattering);
1391 /* Apply scattering. */
1392 cloog_program_scatter (prog, scattering, options);
1393 free_scattering (scattering);
1395 /* Iterators corresponding to scalar dimensions have to be extracted. */
1396 cloog_names_scalarize (cloog_program_names (prog), nbs,
1397 cloog_program_scaldims (prog));
1399 /* Free blocklist. */
1401 CloogBlockList *next = cloog_program_blocklist (prog);
1405 CloogBlockList *toDelete = next;
1406 next = cloog_block_list_next (next);
1407 cloog_block_list_set_next (toDelete, NULL);
1408 cloog_block_list_set_block (toDelete, NULL);
1409 cloog_block_list_free (toDelete);
1411 cloog_program_set_blocklist (prog, NULL);
1415 /* Return the options that will be used in GLOOG. */
1417 static CloogOptions *
1418 set_cloog_options (void)
1420 CloogOptions *options = cloog_options_malloc (cloog_state);
1422 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1423 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1424 we pass an incomplete program to cloog. */
1425 options->language = CLOOG_LANGUAGE_C;
1427 /* Enable complex equality spreading: removes dummy statements
1428 (assignments) in the generated code which repeats the
1429 substitution equations for statements. This is useless for
1434 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1437 /* Enable C pretty-printing mode: normalizes the substitution
1438 equations for statements. */
1442 /* Allow cloog to build strides with a stride width different to one.
1443 This example has stride = 4:
1445 for (i = 0; i < 20; i += 4)
1447 options->strides = 1;
1449 /* Disable optimizations and make cloog generate source code closer to the
1450 input. This is useful for debugging, but later we want the optimized
1453 XXX: We can not disable optimizations, as loop blocking is not working
1458 options->l = INT_MAX;
1464 /* Prints STMT to STDERR. */
1467 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1469 CloogOptions *options = set_cloog_options ();
1471 clast_pprint (file, stmt, 0, options);
1472 cloog_options_free (options);
1475 /* Prints STMT to STDERR. */
1478 debug_clast_stmt (struct clast_stmt *stmt)
1480 print_clast_stmt (stderr, stmt);
1483 /* Translate SCOP to a CLooG program and clast. These two
1484 representations should be freed together: a clast cannot be used
1485 without a program. */
1488 scop_to_clast (scop_p scop)
1490 CloogOptions *options = set_cloog_options ();
1491 cloog_prog_clast pc;
1493 /* Connect new cloog prog generation to graphite. */
1494 pc.prog = cloog_program_malloc ();
1495 build_cloog_prog (scop, pc.prog, options);
1496 pc.prog = cloog_program_generate (pc.prog, options);
1497 pc.stmt = cloog_clast_create (pc.prog, options);
1499 cloog_options_free (options);
1503 /* Prints to FILE the code generated by CLooG for SCOP. */
1506 print_generated_program (FILE *file, scop_p scop)
1508 CloogOptions *options = set_cloog_options ();
1510 cloog_prog_clast pc = scop_to_clast (scop);
1512 fprintf (file, " (prog: \n");
1513 cloog_program_print (file, pc.prog);
1514 fprintf (file, " )\n");
1516 fprintf (file, " (clast: \n");
1517 clast_pprint (file, pc.stmt, 0, options);
1518 fprintf (file, " )\n");
1520 cloog_options_free (options);
1521 cloog_clast_free (pc.stmt);
1522 cloog_program_free (pc.prog);
1525 /* Prints to STDERR the code generated by CLooG for SCOP. */
1528 debug_generated_program (scop_p scop)
1530 print_generated_program (stderr, scop);
1533 /* Add CLooG names to parameter index. The index is used to translate
1534 back from CLooG names to GCC trees. */
1537 create_params_index (scop_p scop, htab_t index_table, CloogProgram *prog) {
1538 CloogNames* names = cloog_program_names (prog);
1539 int nb_parameters = cloog_names_nb_parameters (names);
1540 char **parameters = cloog_names_parameters (names);
1547 for (i = 0; i < nb_parameters; i++)
1549 compute_bounds_for_param (scop, i, lb, ub);
1550 save_clast_name_index (index_table, parameters[i], i, i, lb, ub);
1557 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1558 the given SCOP. Return true if code generation succeeded.
1559 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1563 gloog (scop_p scop, htab_t bb_pbb_mapping)
1565 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1566 loop_p context_loop;
1567 sese region = SCOP_REGION (scop);
1568 ifsese if_region = NULL;
1569 htab_t newivs_index, params_index;
1570 cloog_prog_clast pc;
1571 struct ivs_params ip;
1573 timevar_push (TV_GRAPHITE_CODE_GEN);
1574 gloog_error = false;
1576 pc = scop_to_clast (scop);
1578 if (dump_file && (dump_flags & TDF_DETAILS))
1580 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1581 print_clast_stmt (dump_file, pc.stmt);
1582 fprintf (dump_file, "\n");
1585 recompute_all_dominators ();
1588 if_region = move_sese_in_condition (region);
1589 sese_insert_phis_for_liveouts (region,
1590 if_region->region->exit->src,
1591 if_region->false_region->exit,
1592 if_region->true_region->exit);
1593 recompute_all_dominators ();
1596 context_loop = SESE_ENTRY (region)->src->loop_father;
1597 newivs_index = htab_create (10, clast_name_index_elt_info,
1598 eq_clast_name_indexes, free_clast_name_index);
1599 params_index = htab_create (10, clast_name_index_elt_info,
1600 eq_clast_name_indexes, free_clast_name_index);
1602 create_params_index (scop, params_index, pc.prog);
1604 ip.newivs = &newivs;
1605 ip.newivs_index = newivs_index;
1606 ip.params = SESE_PARAMS (region);
1607 ip.params_index = params_index;
1610 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1611 bb_pbb_mapping, 0, &ip);
1614 recompute_all_dominators ();
1618 set_ifsese_condition (if_region, integer_zero_node);
1620 free (if_region->true_region);
1621 free (if_region->region);
1624 htab_delete (newivs_index);
1625 htab_delete (params_index);
1626 VEC_free (tree, heap, newivs);
1627 cloog_clast_free (pc.stmt);
1628 cloog_program_free (pc.prog);
1629 timevar_pop (TV_GRAPHITE_CODE_GEN);
1631 if (dump_file && (dump_flags & TDF_DETAILS))
1635 int num_no_dependency = 0;
1637 FOR_EACH_LOOP (li, loop, 0)
1638 if (loop->can_be_parallel)
1639 num_no_dependency++;
1641 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1645 return !gloog_error;