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);
819 if (CLAST_STMT_IS_A (stmt, stmt_ass))
820 return clast_get_body_of_loop (stmt->next);
825 /* Returns the type for the induction variable for the loop translated
829 type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
832 tree lb_type, ub_type;
837 lb_type = type_for_clast_expr (stmt_for->LB, ip, v1, v2);
838 ub_type = type_for_clast_expr (stmt_for->UB, ip, v1, v2);
843 return max_precision_type (lb_type, ub_type);
846 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
847 induction variable for the new LOOP. New LOOP is attached to CFG
848 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
849 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
850 CLooG's scattering name to the induction variable created for the
851 loop of STMT. The new induction variable is inserted in the NEWIVS
852 vector and is of type TYPE. */
855 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
856 loop_p outer, tree type, tree lb, tree ub,
857 int level, ivs_params_p ip)
861 struct clast_user_stmt *body
862 = clast_get_body_of_loop ((struct clast_stmt *) stmt);
863 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
865 tree stride = gmp_cst_to_tree (type, stmt->stride);
866 tree ivvar = create_tmp_var (type, "graphite_IV");
867 tree iv, iv_after_increment;
868 loop_p loop = create_empty_loop_on_edge
869 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
870 outer ? outer : entry_edge->src->loop_father);
872 add_referenced_var (ivvar);
876 compute_bounds_for_level (pbb, level, low, up);
877 save_clast_name_index (ip->newivs_index, stmt->iterator,
878 VEC_length (tree, *(ip->newivs)), level, low, up);
881 VEC_safe_push (tree, heap, *(ip->newivs), iv);
885 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
886 induction variables of the loops around GBB in SESE. */
889 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
892 struct clast_stmt *t;
894 CloogStatement *cs = user_stmt->statement;
895 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
896 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
902 for (t = user_stmt->substitutions; t; t = t->next, depth++)
904 struct clast_expr *expr = (struct clast_expr *)
905 ((struct clast_assignment *)t)->RHS;
906 tree type = type_for_clast_expr (expr, ip, v1, v2);
907 tree new_name = clast_to_gcc_expression (type, expr, ip);
908 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
910 VEC_replace (tree, iv_map, old_loop->num, new_name);
917 /* Construct bb_pbb_def with BB and PBB. */
920 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
922 bb_pbb_def *bb_pbb_p;
924 bb_pbb_p = XNEW (bb_pbb_def);
931 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
934 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
940 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
943 *x = new_bb_pbb_def (bb, pbb);
946 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
949 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
955 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
958 return ((bb_pbb_def *) *slot)->pbb;
963 /* Check data dependency in LOOP at level LEVEL.
964 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
968 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
971 basic_block *bbs = get_loop_body_in_dom_order (loop);
973 for (i = 0; i < loop->num_nodes; i++)
975 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
980 for (j = 0; j < loop->num_nodes; j++)
982 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
987 if (dependency_between_pbbs_p (pbb1, pbb2, level))
1000 /* Translates a clast user statement STMT to gimple.
1002 - NEXT_E is the edge where new generated code should be attached.
1003 - CONTEXT_LOOP is the loop in which the generated code will be placed
1004 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1007 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1008 htab_t bb_pbb_mapping, ivs_params_p ip)
1012 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
1013 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1014 VEC (tree, heap) *iv_map;
1016 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1019 nb_loops = number_of_loops ();
1020 iv_map = VEC_alloc (tree, heap, nb_loops);
1021 for (i = 0; i < nb_loops; i++)
1022 VEC_quick_push (tree, iv_map, NULL_TREE);
1024 build_iv_mapping (iv_map, stmt, ip);
1025 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1026 next_e, iv_map, &gloog_error);
1027 VEC_free (tree, heap, iv_map);
1029 new_bb = next_e->src;
1030 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1031 update_ssa (TODO_update_ssa);
1036 /* Creates a new if region protecting the loop to be executed, if the execution
1037 count is zero (lb > ub). */
1040 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1041 tree *type, tree *lb, tree *ub,
1047 *type = type_for_clast_for (stmt, ip);
1048 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1049 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1051 /* When ub is simply a constant or a parameter, use lb <= ub. */
1052 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1053 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1056 tree one = (POINTER_TYPE_P (*type)
1058 : fold_convert (*type, integer_one_node));
1059 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1060 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
1061 2^k-1 due to integer overflow, and the condition lb <= ub is true,
1062 even if we do not want this. However lb < ub + 1 is false, as
1064 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1065 : PLUS_EXPR, *type, *ub, one);
1067 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1070 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1076 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1078 /* Create the loop for a clast for statement.
1080 - NEXT_E is the edge where new generated code should be attached.
1081 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1084 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1085 edge next_e, htab_t bb_pbb_mapping, int level,
1086 tree type, tree lb, tree ub, ivs_params_p ip)
1088 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1089 type, lb, ub, level, ip);
1090 edge last_e = single_exit (loop);
1091 edge to_body = single_succ_edge (loop->header);
1092 basic_block after = to_body->dest;
1094 /* Create a basic block for loop close phi nodes. */
1095 last_e = single_succ_edge (split_edge (last_e));
1097 /* Translate the body of the loop. */
1098 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1100 redirect_edge_succ_nodup (next_e, after);
1101 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1103 if (flag_loop_parallelize_all
1104 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
1105 loop->can_be_parallel = true;
1110 /* Translates a clast for statement STMT to gimple. First a guard is created
1111 protecting the loop, if it is executed zero times. In this guard we create
1112 the real loop structure.
1114 - NEXT_E is the edge where new generated code should be attached.
1115 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1118 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1119 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1122 edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1124 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1126 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1131 /* Translates a clast assignment STMT to gimple.
1133 - NEXT_E is the edge where new generated code should be attached.
1134 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1137 translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
1138 int level, ivs_params_p ip)
1142 tree type, new_name, var;
1143 edge res = single_succ_edge (split_edge (next_e));
1144 struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
1148 type = type_for_clast_expr (expr, ip, v1, v2);
1149 var = create_tmp_var (type, "graphite_var");
1150 new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
1152 add_referenced_var (var);
1155 gsi_insert_seq_on_edge (next_e, stmts);
1156 gsi_commit_edge_inserts ();
1159 save_clast_name_index (ip->newivs_index, stmt->LHS,
1160 VEC_length (tree, *(ip->newivs)), level, v1, v2);
1161 VEC_safe_push (tree, heap, *(ip->newivs), new_name);
1169 /* Translates a clast guard statement STMT to gimple.
1171 - NEXT_E is the edge where new generated code should be attached.
1172 - CONTEXT_LOOP is the loop in which the generated code will be placed
1173 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1176 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1177 edge next_e, htab_t bb_pbb_mapping, int level,
1180 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1181 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1183 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1187 /* Translates a CLAST statement STMT to GCC representation in the
1190 - NEXT_E is the edge where new generated code should be attached.
1191 - CONTEXT_LOOP is the loop in which the generated code will be placed
1192 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1195 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1196 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1201 if (CLAST_STMT_IS_A (stmt, stmt_root))
1204 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1205 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1206 next_e, bb_pbb_mapping, ip);
1208 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1209 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1210 next_e, bb_pbb_mapping, level, ip);
1212 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1213 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1214 next_e, bb_pbb_mapping, level, ip);
1216 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1217 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1218 next_e, bb_pbb_mapping, level, ip);
1220 else if (CLAST_STMT_IS_A (stmt, stmt_ass))
1221 next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
1226 recompute_all_dominators ();
1229 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1233 /* Free the SCATTERING domain list. */
1236 free_scattering (CloogScatteringList *scattering)
1240 CloogScattering *dom = cloog_scattering (scattering);
1241 CloogScatteringList *next = cloog_next_scattering (scattering);
1243 cloog_scattering_free (dom);
1249 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1250 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1251 from 0 to scop_nb_loops (scop). */
1254 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1256 sese region = SCOP_REGION (scop);
1258 int nb_iterators = scop_max_loop_depth (scop);
1259 int nb_scattering = cloog_program_nb_scattdims (prog);
1260 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1261 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1262 char **scattering = XNEWVEC (char *, nb_scattering);
1263 char **parameters= XNEWVEC (char *, nb_parameters);
1265 cloog_program_set_names (prog, cloog_names_malloc ());
1267 for (i = 0; i < nb_parameters; i++)
1269 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1270 const char *name = get_name (param);
1276 len = strlen (name);
1278 parameters[i] = XNEWVEC (char, len + 1);
1279 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1282 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1283 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1285 for (i = 0; i < nb_iterators; i++)
1288 iterators[i] = XNEWVEC (char, len);
1289 snprintf (iterators[i], len, "git_%d", i);
1292 cloog_names_set_nb_iterators (cloog_program_names (prog),
1294 cloog_names_set_iterators (cloog_program_names (prog),
1297 for (i = 0; i < nb_scattering; i++)
1300 scattering[i] = XNEWVEC (char, len);
1301 snprintf (scattering[i], len, "scat_%d", i);
1304 cloog_names_set_nb_scattering (cloog_program_names (prog),
1306 cloog_names_set_scattering (cloog_program_names (prog),
1310 /* Initialize a CLooG input file. */
1313 init_cloog_input_file (int scop_number)
1315 FILE *graphite_out_file;
1316 int len = strlen (dump_base_name);
1317 char *dumpname = XNEWVEC (char, len + 25);
1318 char *s_scop_number = XNEWVEC (char, 15);
1320 memcpy (dumpname, dump_base_name, len + 1);
1321 strip_off_ending (dumpname, len);
1322 sprintf (s_scop_number, ".%d", scop_number);
1323 strcat (dumpname, s_scop_number);
1324 strcat (dumpname, ".cloog");
1325 graphite_out_file = fopen (dumpname, "w+b");
1327 if (graphite_out_file == 0)
1328 fatal_error ("can%'t open %s for writing: %m", dumpname);
1332 return graphite_out_file;
1335 /* Build cloog program for SCoP. */
1338 build_cloog_prog (scop_p scop, CloogProgram *prog,
1339 CloogOptions *options)
1342 int max_nb_loops = scop_max_loop_depth (scop);
1344 CloogLoop *loop_list = NULL;
1345 CloogBlockList *block_list = NULL;
1346 CloogScatteringList *scattering = NULL;
1347 int nbs = 2 * max_nb_loops + 1;
1350 cloog_program_set_context
1351 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1352 scop_nb_params (scop), cloog_state));
1353 nbs = unify_scattering_dimensions (scop);
1354 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1355 cloog_program_set_nb_scattdims (prog, nbs);
1356 initialize_cloog_names (scop, prog);
1358 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1360 CloogStatement *stmt;
1364 /* Dead code elimination: when the domain of a PBB is empty,
1365 don't generate code for the PBB. */
1366 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1369 /* Build the new statement and its block. */
1370 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1371 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1372 scop_nb_params (scop),
1374 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1375 cloog_statement_set_usr (stmt, pbb);
1377 /* Build loop list. */
1379 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1380 cloog_loop_set_next (new_loop_list, loop_list);
1381 cloog_loop_set_domain (new_loop_list, dom);
1382 cloog_loop_set_block (new_loop_list, block);
1383 loop_list = new_loop_list;
1386 /* Build block list. */
1388 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1390 cloog_block_list_set_next (new_block_list, block_list);
1391 cloog_block_list_set_block (new_block_list, block);
1392 block_list = new_block_list;
1395 /* Build scattering list. */
1397 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1398 CloogScatteringList *new_scattering
1399 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1400 ppl_Polyhedron_t scat;
1401 CloogScattering *dom;
1403 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1404 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1405 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1408 cloog_set_next_scattering (new_scattering, scattering);
1409 cloog_set_scattering (new_scattering, dom);
1410 scattering = new_scattering;
1414 cloog_program_set_loop (prog, loop_list);
1415 cloog_program_set_blocklist (prog, block_list);
1417 for (i = 0; i < nbs; i++)
1420 cloog_program_set_scaldims (prog, scaldims);
1422 /* Extract scalar dimensions to simplify the code generation problem. */
1423 cloog_program_extract_scalars (prog, scattering, options);
1425 /* Dump a .cloog input file, if requested. This feature is only
1426 enabled in the Graphite branch. */
1429 static size_t file_scop_number = 0;
1430 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1432 cloog_program_dump_cloog (cloog_file, prog, scattering);
1436 /* Apply scattering. */
1437 cloog_program_scatter (prog, scattering, options);
1438 free_scattering (scattering);
1440 /* Iterators corresponding to scalar dimensions have to be extracted. */
1441 cloog_names_scalarize (cloog_program_names (prog), nbs,
1442 cloog_program_scaldims (prog));
1444 /* Free blocklist. */
1446 CloogBlockList *next = cloog_program_blocklist (prog);
1450 CloogBlockList *toDelete = next;
1451 next = cloog_block_list_next (next);
1452 cloog_block_list_set_next (toDelete, NULL);
1453 cloog_block_list_set_block (toDelete, NULL);
1454 cloog_block_list_free (toDelete);
1456 cloog_program_set_blocklist (prog, NULL);
1460 /* Return the options that will be used in GLOOG. */
1462 static CloogOptions *
1463 set_cloog_options (void)
1465 CloogOptions *options = cloog_options_malloc (cloog_state);
1467 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1468 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1469 we pass an incomplete program to cloog. */
1470 options->language = CLOOG_LANGUAGE_C;
1472 /* Enable complex equality spreading: removes dummy statements
1473 (assignments) in the generated code which repeats the
1474 substitution equations for statements. This is useless for
1479 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1482 /* Enable C pretty-printing mode: normalizes the substitution
1483 equations for statements. */
1487 /* Allow cloog to build strides with a stride width different to one.
1488 This example has stride = 4:
1490 for (i = 0; i < 20; i += 4)
1492 options->strides = 1;
1494 /* Disable optimizations and make cloog generate source code closer to the
1495 input. This is useful for debugging, but later we want the optimized
1498 XXX: We can not disable optimizations, as loop blocking is not working
1503 options->l = INT_MAX;
1509 /* Prints STMT to STDERR. */
1512 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1514 CloogOptions *options = set_cloog_options ();
1516 clast_pprint (file, stmt, 0, options);
1517 cloog_options_free (options);
1520 /* Prints STMT to STDERR. */
1523 debug_clast_stmt (struct clast_stmt *stmt)
1525 print_clast_stmt (stderr, stmt);
1528 /* Translate SCOP to a CLooG program and clast. These two
1529 representations should be freed together: a clast cannot be used
1530 without a program. */
1533 scop_to_clast (scop_p scop)
1535 CloogOptions *options = set_cloog_options ();
1536 cloog_prog_clast pc;
1538 /* Connect new cloog prog generation to graphite. */
1539 pc.prog = cloog_program_malloc ();
1540 build_cloog_prog (scop, pc.prog, options);
1541 pc.prog = cloog_program_generate (pc.prog, options);
1542 pc.stmt = cloog_clast_create (pc.prog, options);
1544 cloog_options_free (options);
1548 /* Prints to FILE the code generated by CLooG for SCOP. */
1551 print_generated_program (FILE *file, scop_p scop)
1553 CloogOptions *options = set_cloog_options ();
1555 cloog_prog_clast pc = scop_to_clast (scop);
1557 fprintf (file, " (prog: \n");
1558 cloog_program_print (file, pc.prog);
1559 fprintf (file, " )\n");
1561 fprintf (file, " (clast: \n");
1562 clast_pprint (file, pc.stmt, 0, options);
1563 fprintf (file, " )\n");
1565 cloog_options_free (options);
1566 cloog_clast_free (pc.stmt);
1567 cloog_program_free (pc.prog);
1570 /* Prints to STDERR the code generated by CLooG for SCOP. */
1573 debug_generated_program (scop_p scop)
1575 print_generated_program (stderr, scop);
1578 /* Add CLooG names to parameter index. The index is used to translate
1579 back from CLooG names to GCC trees. */
1582 create_params_index (scop_p scop, htab_t index_table, CloogProgram *prog) {
1583 CloogNames* names = cloog_program_names (prog);
1584 int nb_parameters = cloog_names_nb_parameters (names);
1585 char **parameters = cloog_names_parameters (names);
1592 for (i = 0; i < nb_parameters; i++)
1594 compute_bounds_for_param (scop, i, lb, ub);
1595 save_clast_name_index (index_table, parameters[i], i, i, lb, ub);
1602 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1603 the given SCOP. Return true if code generation succeeded.
1604 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1608 gloog (scop_p scop, htab_t bb_pbb_mapping)
1610 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1611 loop_p context_loop;
1612 sese region = SCOP_REGION (scop);
1613 ifsese if_region = NULL;
1614 htab_t newivs_index, params_index;
1615 cloog_prog_clast pc;
1616 struct ivs_params ip;
1618 timevar_push (TV_GRAPHITE_CODE_GEN);
1619 gloog_error = false;
1621 pc = scop_to_clast (scop);
1623 if (dump_file && (dump_flags & TDF_DETAILS))
1625 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1626 print_clast_stmt (dump_file, pc.stmt);
1627 fprintf (dump_file, "\n");
1630 recompute_all_dominators ();
1633 if_region = move_sese_in_condition (region);
1634 sese_insert_phis_for_liveouts (region,
1635 if_region->region->exit->src,
1636 if_region->false_region->exit,
1637 if_region->true_region->exit);
1638 recompute_all_dominators ();
1641 context_loop = SESE_ENTRY (region)->src->loop_father;
1642 newivs_index = htab_create (10, clast_name_index_elt_info,
1643 eq_clast_name_indexes, free_clast_name_index);
1644 params_index = htab_create (10, clast_name_index_elt_info,
1645 eq_clast_name_indexes, free_clast_name_index);
1647 create_params_index (scop, params_index, pc.prog);
1649 ip.newivs = &newivs;
1650 ip.newivs_index = newivs_index;
1651 ip.params = SESE_PARAMS (region);
1652 ip.params_index = params_index;
1655 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1656 bb_pbb_mapping, 0, &ip);
1659 recompute_all_dominators ();
1663 set_ifsese_condition (if_region, integer_zero_node);
1665 free (if_region->true_region);
1666 free (if_region->region);
1669 htab_delete (newivs_index);
1670 htab_delete (params_index);
1671 VEC_free (tree, heap, newivs);
1672 cloog_clast_free (pc.stmt);
1673 cloog_program_free (pc.prog);
1674 timevar_pop (TV_GRAPHITE_CODE_GEN);
1676 if (dump_file && (dump_flags & TDF_DETAILS))
1680 int num_no_dependency = 0;
1682 FOR_EACH_LOOP (li, loop, 0)
1683 if (loop->can_be_parallel)
1684 num_no_dependency++;
1686 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1690 return !gloog_error;