1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009, 2010 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 /* This flag is set when an error occurred during the translation of
45 static bool gloog_error;
47 /* Verifies properties that GRAPHITE should maintain during translation. */
50 graphite_verify (void)
52 #ifdef ENABLE_CHECKING
53 verify_loop_structure ();
54 verify_dominators (CDI_DOMINATORS);
55 verify_loop_closed_ssa (true);
59 /* Stores the INDEX in a vector and the loop nesting LEVEL for a given
62 typedef struct clast_name_index {
66 } *clast_name_index_p;
68 /* Returns a pointer to a new element of type clast_name_index_p built
69 from NAME, LEVEL, and INDEX. */
71 static inline clast_name_index_p
72 new_clast_name_index (const char *name, int index, int level)
74 clast_name_index_p res = XNEW (struct clast_name_index);
82 /* For a given clast NAME, returns -1 if NAME is not in the
83 INDEX_TABLE, otherwise returns the loop level for the induction
84 variable NAME, or if it is a parameter, the parameter number in the
85 vector of parameters. */
88 clast_name_to_level (clast_name_p name, htab_t index_table)
90 struct clast_name_index tmp;
94 gcc_assert (name->type == clast_expr_name);
95 tmp.name = ((const struct clast_name *) name)->name;
100 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
103 return ((struct clast_name_index *) *slot)->level;
108 /* For a given clast NAME, returns -1 if it does not correspond to any
109 parameter, or otherwise, returns the index in the PARAMS or
110 SCATTERING_DIMENSIONS vector. */
113 clast_name_to_index (clast_name_p name, htab_t index_table)
115 struct clast_name_index tmp;
119 gcc_assert (name->type == clast_expr_name);
120 tmp.name = ((const struct clast_name *) name)->name;
125 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
128 return ((struct clast_name_index *) *slot)->index;
133 /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
136 save_clast_name_index (htab_t index_table, const char *name,
137 int index, int level)
139 struct clast_name_index tmp;
143 slot = htab_find_slot (index_table, &tmp, INSERT);
149 *slot = new_clast_name_index (name, index, level);
153 /* Computes a hash function for database element ELT. */
155 static inline hashval_t
156 clast_name_index_elt_info (const void *elt)
158 return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
161 /* Compares database elements E1 and E2. */
164 eq_clast_name_indexes (const void *e1, const void *e2)
166 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
167 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
169 return (elt1->name == elt2->name);
174 /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
175 induction variable in NEWIVS.
177 PARAMS_INDEX binds CLooG's parameter name to the index of the tree
178 parameter in PARAMS. */
180 typedef struct ivs_params {
181 VEC (tree, heap) *params, **newivs;
182 htab_t newivs_index, params_index;
186 /* Returns the tree variable from the name NAME that was given in
187 Cloog representation. */
190 clast_name_to_gcc (clast_name_p name, ivs_params_p ip)
194 if (ip->params && ip->params_index)
196 index = clast_name_to_index (name, ip->params_index);
199 return VEC_index (tree, ip->params, index);
202 gcc_assert (*(ip->newivs) && ip->newivs_index);
203 index = clast_name_to_index (name, ip->newivs_index);
204 gcc_assert (index >= 0);
206 return VEC_index (tree, *(ip->newivs), index);
209 /* Returns the signed maximal precision type for expressions TYPE1 and TYPE2. */
212 max_signed_precision_type (tree type1, tree type2)
214 int p1 = TYPE_PRECISION (type1);
215 int p2 = TYPE_PRECISION (type2);
218 enum machine_mode mode;
221 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
223 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
225 if (precision > BITS_PER_WORD)
228 return integer_type_node;
231 mode = smallest_mode_for_size (precision, MODE_INT);
232 precision = GET_MODE_PRECISION (mode);
233 type = build_nonstandard_integer_type (precision, false);
238 return integer_type_node;
244 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
247 max_precision_type (tree type1, tree type2)
249 if (POINTER_TYPE_P (type1))
252 if (POINTER_TYPE_P (type2))
255 if (!TYPE_UNSIGNED (type1)
256 || !TYPE_UNSIGNED (type2))
257 return max_signed_precision_type (type1, type2);
259 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
263 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
265 /* Converts a Cloog reduction expression R with reduction operation OP
266 to a GCC expression tree of type TYPE. */
269 clast_to_gcc_expression_red (tree type, enum tree_code op,
270 struct clast_reduction *r, ivs_params_p ip)
273 tree res = clast_to_gcc_expression (type, r->elts[0], ip);
274 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
276 for (i = 1; i < r->n; i++)
278 tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
279 res = fold_build2 (op, type, res, t);
285 /* Converts a Cloog AST expression E back to a GCC expression tree of
289 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
293 case clast_expr_term:
295 struct clast_term *t = (struct clast_term *) e;
299 if (mpz_cmp_si (t->val, 1) == 0)
301 tree name = clast_name_to_gcc (t->var, ip);
303 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
304 name = fold_convert (sizetype, name);
306 name = fold_convert (type, name);
310 else if (mpz_cmp_si (t->val, -1) == 0)
312 tree name = clast_name_to_gcc (t->var, ip);
314 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
315 name = fold_convert (sizetype, name);
317 name = fold_convert (type, name);
319 return fold_build1 (NEGATE_EXPR, type, name);
323 tree name = clast_name_to_gcc (t->var, ip);
324 tree cst = gmp_cst_to_tree (type, t->val);
326 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
327 name = fold_convert (sizetype, name);
329 name = fold_convert (type, name);
331 if (!POINTER_TYPE_P (type))
332 return fold_build2 (MULT_EXPR, type, cst, name);
339 return gmp_cst_to_tree (type, t->val);
344 struct clast_reduction *r = (struct clast_reduction *) e;
349 return clast_to_gcc_expression_red
350 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
354 return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
357 return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
367 struct clast_binary *b = (struct clast_binary *) e;
368 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
369 tree tl = clast_to_gcc_expression (type, lhs, ip);
370 tree tr = gmp_cst_to_tree (type, b->RHS);
375 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
378 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
381 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
384 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
398 /* Return a type that could represent the values between V1 and V2. */
401 gcc_type_for_interval (mpz_t v1, mpz_t v2)
405 enum machine_mode mode;
406 int precision = MAX (mpz_sizeinbase (v1, 2),
407 mpz_sizeinbase (v2, 2));
409 if (precision > BITS_PER_WORD)
412 return integer_type_node;
415 if (mpz_cmp (v1, v2) <= 0)
416 unsigned_p = (mpz_sgn (v1) >= 0);
418 unsigned_p = (mpz_sgn (v2) >= 0);
420 mode = smallest_mode_for_size (precision, MODE_INT);
421 precision = GET_MODE_PRECISION (mode);
422 type = build_nonstandard_integer_type (precision, unsigned_p);
427 return integer_type_node;
433 /* Return a type that could represent the integer value VAL, or
434 otherwise return NULL_TREE. */
437 gcc_type_for_value (mpz_t val)
439 return gcc_type_for_interval (val, val);
442 /* Return the type for the clast_term T used in STMT. */
445 gcc_type_for_clast_term (struct clast_term *t,
448 gcc_assert (t->expr.type == clast_expr_term);
451 return gcc_type_for_value (t->val);
453 return TREE_TYPE (clast_name_to_gcc (t->var, ip));
457 gcc_type_for_clast_expr (struct clast_expr *, ivs_params_p);
459 /* Return the type for the clast_reduction R used in STMT. */
462 gcc_type_for_clast_red (struct clast_reduction *r,
466 tree type = NULL_TREE;
469 return gcc_type_for_clast_expr (r->elts[0], ip);
476 type = gcc_type_for_clast_expr (r->elts[0], ip);
477 for (i = 1; i < r->n; i++)
478 type = max_precision_type (type, gcc_type_for_clast_expr
491 /* Return the type for the clast_binary B used in STMT. */
494 gcc_type_for_clast_bin (struct clast_binary *b, ivs_params_p ip)
496 tree l = gcc_type_for_clast_expr ((struct clast_expr *) b->LHS, ip);
497 tree r = gcc_type_for_value (b->RHS);
498 return max_signed_precision_type (l, r);
501 /* Returns the type for the CLAST expression E when used in statement
505 gcc_type_for_clast_expr (struct clast_expr *e,
510 case clast_expr_term:
511 return gcc_type_for_clast_term ((struct clast_term *) e, ip);
514 return gcc_type_for_clast_red ((struct clast_reduction *) e, ip);
517 return gcc_type_for_clast_bin ((struct clast_binary *) e, ip);
526 /* Returns the type for the equation CLEQ. */
529 gcc_type_for_clast_eq (struct clast_equation *cleq,
532 tree l = gcc_type_for_clast_expr (cleq->LHS, ip);
533 tree r = gcc_type_for_clast_expr (cleq->RHS, ip);
534 return max_precision_type (l, r);
537 /* Translates a clast equation CLEQ to a tree. */
540 graphite_translate_clast_equation (struct clast_equation *cleq,
544 tree type = gcc_type_for_clast_eq (cleq, ip);
545 tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
546 tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
551 else if (cleq->sign > 0)
557 return fold_build2 (comp, boolean_type_node, lhs, rhs);
560 /* Creates the test for the condition in STMT. */
563 graphite_create_guard_cond_expr (struct clast_guard *stmt,
569 for (i = 0; i < stmt->n; i++)
571 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
574 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
582 /* Creates a new if region corresponding to Cloog's guard. */
585 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
588 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
589 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
593 /* Compute the lower bound LOW and upper bound UP for the induction
594 variable at LEVEL for the statement PBB, based on the transformed
595 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
596 the iteration domain, and G the context parameters. */
599 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
601 ppl_Pointset_Powerset_C_Polyhedron_t ps;
602 ppl_Linear_Expression_t le;
604 combine_context_id_scat (&ps, pbb, false);
606 /* Prepare the linear expression corresponding to the level that we
607 want to maximize/minimize. */
609 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
610 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
612 ppl_new_Linear_Expression_with_dimension (&le, dim);
613 ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
616 ppl_max_for_le_pointset (ps, le, up);
617 ppl_min_for_le_pointset (ps, le, low);
618 ppl_delete_Linear_Expression (le);
619 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
622 /* Compute the type for the induction variable at LEVEL for the
623 statement PBB, based on the transformed schedule of PBB. */
626 compute_type_for_level (poly_bb_p pbb, int level)
634 compute_bounds_for_level (pbb, level, low, up);
635 type = gcc_type_for_interval (low, up);
642 /* Walks a CLAST and returns the first statement in the body of a
645 FIXME: This function should not be used to get a PBB in the STMT
646 loop in order to find out the iteration domain of the loop: the
647 counter example from Tobias is:
649 | for (i = 0; i < 100; i++)
656 This function would return S1 whose iteration domain contains only
657 one point "i = 0", whereas the iteration domain of S2 has 100 points.
659 This should be implemented using some functionality existing in
662 static struct clast_user_stmt *
663 clast_get_body_of_loop (struct clast_stmt *stmt)
666 || CLAST_STMT_IS_A (stmt, stmt_user))
667 return (struct clast_user_stmt *) stmt;
669 if (CLAST_STMT_IS_A (stmt, stmt_for))
670 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
672 if (CLAST_STMT_IS_A (stmt, stmt_guard))
673 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
675 if (CLAST_STMT_IS_A (stmt, stmt_block))
676 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
681 /* Returns the type for the induction variable for the loop translated
685 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for, int level,
686 tree lb_type, tree ub_type)
688 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
689 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
690 CloogStatement *cs = body->statement;
691 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
693 return max_signed_precision_type (lb_type, max_precision_type
694 (ub_type, compute_type_for_level
698 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
699 induction variable for the new LOOP. New LOOP is attached to CFG
700 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
701 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
702 CLooG's scattering name to the induction variable created for the
703 loop of STMT. The new induction variable is inserted in the NEWIVS
704 vector and is of type TYPE. */
707 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
708 loop_p outer, tree type, tree lb, tree ub,
709 int level, ivs_params_p ip)
711 tree stride = gmp_cst_to_tree (type, stmt->stride);
712 tree ivvar = create_tmp_var (type, "graphite_IV");
713 tree iv, iv_after_increment;
714 loop_p loop = create_empty_loop_on_edge
715 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
716 outer ? outer : entry_edge->src->loop_father);
718 add_referenced_var (ivvar);
720 save_clast_name_index (ip->newivs_index, stmt->iterator,
721 VEC_length (tree, *(ip->newivs)), level);
722 VEC_safe_push (tree, heap, *(ip->newivs), iv);
726 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
727 induction variables of the loops around GBB in SESE. */
730 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
733 struct clast_stmt *t;
735 CloogStatement *cs = user_stmt->statement;
736 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
737 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
739 for (t = user_stmt->substitutions; t; t = t->next, depth++)
741 struct clast_expr *expr = (struct clast_expr *)
742 ((struct clast_assignment *)t)->RHS;
743 tree type = gcc_type_for_clast_expr (expr, ip);
744 tree new_name = clast_to_gcc_expression (type, expr, ip);
745 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
747 VEC_replace (tree, iv_map, old_loop->num, new_name);
751 /* Construct bb_pbb_def with BB and PBB. */
754 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
756 bb_pbb_def *bb_pbb_p;
758 bb_pbb_p = XNEW (bb_pbb_def);
765 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
768 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
774 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
777 *x = new_bb_pbb_def (bb, pbb);
780 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
783 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
789 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
792 return ((bb_pbb_def *) *slot)->pbb;
797 /* Check data dependency in LOOP at level LEVEL.
798 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
802 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
805 basic_block *bbs = get_loop_body_in_dom_order (loop);
807 for (i = 0; i < loop->num_nodes; i++)
809 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
814 for (j = 0; j < loop->num_nodes; j++)
816 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
821 if (dependency_between_pbbs_p (pbb1, pbb2, level))
834 /* Translates a clast user statement STMT to gimple.
836 - NEXT_E is the edge where new generated code should be attached.
837 - CONTEXT_LOOP is the loop in which the generated code will be placed
838 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
841 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
842 htab_t bb_pbb_mapping, ivs_params_p ip)
846 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
847 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
848 VEC (tree, heap) *iv_map;
850 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
853 nb_loops = number_of_loops ();
854 iv_map = VEC_alloc (tree, heap, nb_loops);
855 for (i = 0; i < nb_loops; i++)
856 VEC_quick_push (tree, iv_map, NULL_TREE);
858 build_iv_mapping (iv_map, stmt, ip);
859 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
861 VEC_free (tree, heap, iv_map);
863 new_bb = next_e->src;
864 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
865 update_ssa (TODO_update_ssa);
870 /* Creates a new if region protecting the loop to be executed, if the execution
871 count is zero (lb > ub). */
874 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
875 int level, tree *type, tree *lb, tree *ub,
880 tree lb_type = gcc_type_for_clast_expr (stmt->LB, ip);
881 tree ub_type = gcc_type_for_clast_expr (stmt->UB, ip);
883 *type = gcc_type_for_iv_of_clast_loop (stmt, level, lb_type, ub_type);
884 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
885 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
887 /* When ub is simply a constant or a parameter, use lb <= ub. */
888 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
889 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
892 tree one = (POINTER_TYPE_P (*type)
894 : fold_convert (*type, integer_one_node));
895 /* Adding +1 and using LT_EXPR helps with loop latches that have a
896 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
897 2^k-1 due to integer overflow, and the condition lb <= ub is true,
898 even if we do not want this. However lb < ub + 1 is false, as
900 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
901 : PLUS_EXPR, *type, *ub, one);
903 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
906 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
912 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
914 /* Create the loop for a clast for statement.
916 - NEXT_E is the edge where new generated code should be attached.
917 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
920 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
921 edge next_e, htab_t bb_pbb_mapping, int level,
922 tree type, tree lb, tree ub, ivs_params_p ip)
924 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
925 type, lb, ub, level, ip);
926 edge last_e = single_exit (loop);
927 edge to_body = single_succ_edge (loop->header);
928 basic_block after = to_body->dest;
930 /* Create a basic block for loop close phi nodes. */
931 last_e = single_succ_edge (split_edge (last_e));
933 /* Translate the body of the loop. */
934 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
936 redirect_edge_succ_nodup (next_e, after);
937 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
939 if (flag_loop_parallelize_all
940 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
941 loop->can_be_parallel = true;
946 /* Translates a clast for statement STMT to gimple. First a guard is created
947 protecting the loop, if it is executed zero times. In this guard we create
948 the real loop structure.
950 - NEXT_E is the edge where new generated code should be attached.
951 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
954 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
955 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
958 edge last_e = graphite_create_new_loop_guard (next_e, stmt, level, &type,
960 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
962 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
967 /* Translates a clast guard statement STMT to gimple.
969 - NEXT_E is the edge where new generated code should be attached.
970 - CONTEXT_LOOP is the loop in which the generated code will be placed
971 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
974 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
975 edge next_e, htab_t bb_pbb_mapping, int level,
978 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
979 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
981 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
985 /* Translates a CLAST statement STMT to GCC representation in the
988 - NEXT_E is the edge where new generated code should be attached.
989 - CONTEXT_LOOP is the loop in which the generated code will be placed
990 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
993 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
994 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
999 if (CLAST_STMT_IS_A (stmt, stmt_root))
1002 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1003 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1004 next_e, bb_pbb_mapping, ip);
1006 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1007 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1008 next_e, bb_pbb_mapping, level, ip);
1010 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1011 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1012 next_e, bb_pbb_mapping, level, ip);
1014 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1015 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1016 next_e, bb_pbb_mapping, level, ip);
1020 recompute_all_dominators ();
1023 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1027 /* Free the SCATTERING domain list. */
1030 free_scattering (CloogScatteringList *scattering)
1034 CloogScattering *dom = cloog_scattering (scattering);
1035 CloogScatteringList *next = cloog_next_scattering (scattering);
1037 cloog_scattering_free (dom);
1043 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1044 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1045 from 0 to scop_nb_loops (scop). */
1048 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1050 sese region = SCOP_REGION (scop);
1052 int nb_iterators = scop_max_loop_depth (scop);
1053 int nb_scattering = cloog_program_nb_scattdims (prog);
1054 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1055 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1056 char **scattering = XNEWVEC (char *, nb_scattering);
1057 char **parameters= XNEWVEC (char *, nb_parameters);
1059 cloog_program_set_names (prog, cloog_names_malloc ());
1061 for (i = 0; i < nb_parameters; i++)
1063 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1064 const char *name = get_name (param);
1070 len = strlen (name);
1072 parameters[i] = XNEWVEC (char, len + 1);
1073 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1076 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1077 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1079 for (i = 0; i < nb_iterators; i++)
1082 iterators[i] = XNEWVEC (char, len);
1083 snprintf (iterators[i], len, "git_%d", i);
1086 cloog_names_set_nb_iterators (cloog_program_names (prog),
1088 cloog_names_set_iterators (cloog_program_names (prog),
1091 for (i = 0; i < nb_scattering; i++)
1094 scattering[i] = XNEWVEC (char, len);
1095 snprintf (scattering[i], len, "scat_%d", i);
1098 cloog_names_set_nb_scattering (cloog_program_names (prog),
1100 cloog_names_set_scattering (cloog_program_names (prog),
1104 /* Initialize a CLooG input file. */
1107 init_cloog_input_file (int scop_number)
1109 FILE *graphite_out_file;
1110 int len = strlen (dump_base_name);
1111 char *dumpname = XNEWVEC (char, len + 25);
1112 char *s_scop_number = XNEWVEC (char, 15);
1114 memcpy (dumpname, dump_base_name, len + 1);
1115 strip_off_ending (dumpname, len);
1116 sprintf (s_scop_number, ".%d", scop_number);
1117 strcat (dumpname, s_scop_number);
1118 strcat (dumpname, ".cloog");
1119 graphite_out_file = fopen (dumpname, "w+b");
1121 if (graphite_out_file == 0)
1122 fatal_error ("can%'t open %s for writing: %m", dumpname);
1126 return graphite_out_file;
1129 /* Build cloog program for SCoP. */
1132 build_cloog_prog (scop_p scop, CloogProgram *prog,
1133 CloogOptions *options)
1136 int max_nb_loops = scop_max_loop_depth (scop);
1138 CloogLoop *loop_list = NULL;
1139 CloogBlockList *block_list = NULL;
1140 CloogScatteringList *scattering = NULL;
1141 int nbs = 2 * max_nb_loops + 1;
1144 cloog_program_set_context
1145 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1146 scop_nb_params (scop), cloog_state));
1147 nbs = unify_scattering_dimensions (scop);
1148 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1149 cloog_program_set_nb_scattdims (prog, nbs);
1150 initialize_cloog_names (scop, prog);
1152 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1154 CloogStatement *stmt;
1158 /* Dead code elimination: when the domain of a PBB is empty,
1159 don't generate code for the PBB. */
1160 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1163 /* Build the new statement and its block. */
1164 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1165 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1166 scop_nb_params (scop),
1168 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1169 cloog_statement_set_usr (stmt, pbb);
1171 /* Build loop list. */
1173 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1174 cloog_loop_set_next (new_loop_list, loop_list);
1175 cloog_loop_set_domain (new_loop_list, dom);
1176 cloog_loop_set_block (new_loop_list, block);
1177 loop_list = new_loop_list;
1180 /* Build block list. */
1182 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1184 cloog_block_list_set_next (new_block_list, block_list);
1185 cloog_block_list_set_block (new_block_list, block);
1186 block_list = new_block_list;
1189 /* Build scattering list. */
1191 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1192 CloogScatteringList *new_scattering
1193 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1194 ppl_Polyhedron_t scat;
1195 CloogScattering *dom;
1197 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1198 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1199 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1202 cloog_set_next_scattering (new_scattering, scattering);
1203 cloog_set_scattering (new_scattering, dom);
1204 scattering = new_scattering;
1208 cloog_program_set_loop (prog, loop_list);
1209 cloog_program_set_blocklist (prog, block_list);
1211 for (i = 0; i < nbs; i++)
1214 cloog_program_set_scaldims (prog, scaldims);
1216 /* Extract scalar dimensions to simplify the code generation problem. */
1217 cloog_program_extract_scalars (prog, scattering, options);
1219 /* Dump a .cloog input file, if requested. This feature is only
1220 enabled in the Graphite branch. */
1223 static size_t file_scop_number = 0;
1224 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1226 cloog_program_dump_cloog (cloog_file, prog, scattering);
1230 /* Apply scattering. */
1231 cloog_program_scatter (prog, scattering, options);
1232 free_scattering (scattering);
1234 /* Iterators corresponding to scalar dimensions have to be extracted. */
1235 cloog_names_scalarize (cloog_program_names (prog), nbs,
1236 cloog_program_scaldims (prog));
1238 /* Free blocklist. */
1240 CloogBlockList *next = cloog_program_blocklist (prog);
1244 CloogBlockList *toDelete = next;
1245 next = cloog_block_list_next (next);
1246 cloog_block_list_set_next (toDelete, NULL);
1247 cloog_block_list_set_block (toDelete, NULL);
1248 cloog_block_list_free (toDelete);
1250 cloog_program_set_blocklist (prog, NULL);
1254 /* Return the options that will be used in GLOOG. */
1256 static CloogOptions *
1257 set_cloog_options (void)
1259 CloogOptions *options = cloog_options_malloc (cloog_state);
1261 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1262 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1263 we pass an incomplete program to cloog. */
1264 options->language = LANGUAGE_C;
1266 /* Enable complex equality spreading: removes dummy statements
1267 (assignments) in the generated code which repeats the
1268 substitution equations for statements. This is useless for
1273 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1276 /* Enable C pretty-printing mode: normalizes the substitution
1277 equations for statements. */
1281 /* Allow cloog to build strides with a stride width different to one.
1282 This example has stride = 4:
1284 for (i = 0; i < 20; i += 4)
1286 options->strides = 1;
1288 /* Disable optimizations and make cloog generate source code closer to the
1289 input. This is useful for debugging, but later we want the optimized
1292 XXX: We can not disable optimizations, as loop blocking is not working
1297 options->l = INT_MAX;
1303 /* Prints STMT to STDERR. */
1306 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1308 CloogOptions *options = set_cloog_options ();
1310 clast_pprint (file, stmt, 0, options);
1311 cloog_options_free (options);
1314 /* Prints STMT to STDERR. */
1317 debug_clast_stmt (struct clast_stmt *stmt)
1319 print_clast_stmt (stderr, stmt);
1322 /* Translate SCOP to a CLooG program and clast. These two
1323 representations should be freed together: a clast cannot be used
1324 without a program. */
1327 scop_to_clast (scop_p scop)
1329 CloogOptions *options = set_cloog_options ();
1330 cloog_prog_clast pc;
1332 /* Connect new cloog prog generation to graphite. */
1333 pc.prog = cloog_program_malloc ();
1334 build_cloog_prog (scop, pc.prog, options);
1335 pc.prog = cloog_program_generate (pc.prog, options);
1336 pc.stmt = cloog_clast_create (pc.prog, options);
1338 cloog_options_free (options);
1342 /* Prints to FILE the code generated by CLooG for SCOP. */
1345 print_generated_program (FILE *file, scop_p scop)
1347 CloogOptions *options = set_cloog_options ();
1349 cloog_prog_clast pc = scop_to_clast (scop);
1351 fprintf (file, " (prog: \n");
1352 cloog_program_print (file, pc.prog);
1353 fprintf (file, " )\n");
1355 fprintf (file, " (clast: \n");
1356 clast_pprint (file, pc.stmt, 0, options);
1357 fprintf (file, " )\n");
1359 cloog_options_free (options);
1360 cloog_clast_free (pc.stmt);
1361 cloog_program_free (pc.prog);
1364 /* Prints to STDERR the code generated by CLooG for SCOP. */
1367 debug_generated_program (scop_p scop)
1369 print_generated_program (stderr, scop);
1372 /* Add CLooG names to parameter index. The index is used to translate
1373 back from CLooG names to GCC trees. */
1376 create_params_index (htab_t index_table, CloogProgram *prog) {
1377 CloogNames* names = cloog_program_names (prog);
1378 int nb_parameters = cloog_names_nb_parameters (names);
1379 char **parameters = cloog_names_parameters (names);
1382 for (i = 0; i < nb_parameters; i++)
1383 save_clast_name_index (index_table, parameters[i], i, i);
1386 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1387 the given SCOP. Return true if code generation succeeded.
1388 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1392 gloog (scop_p scop, htab_t bb_pbb_mapping)
1394 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1395 loop_p context_loop;
1396 sese region = SCOP_REGION (scop);
1397 ifsese if_region = NULL;
1398 htab_t newivs_index, params_index;
1399 cloog_prog_clast pc;
1400 struct ivs_params ip;
1402 timevar_push (TV_GRAPHITE_CODE_GEN);
1403 gloog_error = false;
1405 pc = scop_to_clast (scop);
1407 if (dump_file && (dump_flags & TDF_DETAILS))
1409 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1410 print_clast_stmt (dump_file, pc.stmt);
1411 fprintf (dump_file, "\n");
1414 recompute_all_dominators ();
1417 if_region = move_sese_in_condition (region);
1418 sese_insert_phis_for_liveouts (region,
1419 if_region->region->exit->src,
1420 if_region->false_region->exit,
1421 if_region->true_region->exit);
1422 recompute_all_dominators ();
1425 context_loop = SESE_ENTRY (region)->src->loop_father;
1426 newivs_index = htab_create (10, clast_name_index_elt_info,
1427 eq_clast_name_indexes, free);
1428 params_index = htab_create (10, clast_name_index_elt_info,
1429 eq_clast_name_indexes, free);
1431 create_params_index (params_index, pc.prog);
1433 ip.newivs = &newivs;
1434 ip.newivs_index = newivs_index;
1435 ip.params = SESE_PARAMS (region);
1436 ip.params_index = params_index;
1439 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1440 bb_pbb_mapping, 0, &ip);
1443 recompute_all_dominators ();
1447 set_ifsese_condition (if_region, integer_zero_node);
1449 free (if_region->true_region);
1450 free (if_region->region);
1453 htab_delete (newivs_index);
1454 htab_delete (params_index);
1455 VEC_free (tree, heap, newivs);
1456 cloog_clast_free (pc.stmt);
1457 cloog_program_free (pc.prog);
1458 timevar_pop (TV_GRAPHITE_CODE_GEN);
1460 if (dump_file && (dump_flags & TDF_DETAILS))
1464 int num_no_dependency = 0;
1466 FOR_EACH_LOOP (li, loop, 0)
1467 if (loop->can_be_parallel)
1468 num_no_dependency++;
1470 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1474 return !gloog_error;