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 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 type_for_value (mpz_t val)
439 return type_for_interval (val, val);
442 /* Return the type for the clast_term T used in STMT. */
445 type_for_clast_term (struct clast_term *t, ivs_params_p ip)
447 gcc_assert (t->expr.type == clast_expr_term);
450 return type_for_value (t->val);
452 return TREE_TYPE (clast_name_to_gcc (t->var, ip));
456 type_for_clast_expr (struct clast_expr *, ivs_params_p);
458 /* Return the type for the clast_reduction R used in STMT. */
461 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip)
464 tree type = NULL_TREE;
467 return type_for_clast_expr (r->elts[0], ip);
474 type = type_for_clast_expr (r->elts[0], ip);
475 for (i = 1; i < r->n; i++)
476 type = max_precision_type (type, type_for_clast_expr
489 /* Return the type for the clast_binary B used in STMT. */
492 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip)
494 tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip);
495 tree r = type_for_value (b->RHS);
496 return max_signed_precision_type (l, r);
499 /* Returns the type for the CLAST expression E when used in statement
503 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip)
507 case clast_expr_term:
508 return type_for_clast_term ((struct clast_term *) e, ip);
511 return type_for_clast_red ((struct clast_reduction *) e, ip);
514 return type_for_clast_bin ((struct clast_binary *) e, ip);
523 /* Returns the type for the equation CLEQ. */
526 type_for_clast_eq (struct clast_equation *cleq, ivs_params_p ip)
528 tree l = type_for_clast_expr (cleq->LHS, ip);
529 tree r = type_for_clast_expr (cleq->RHS, ip);
530 return max_precision_type (l, r);
533 /* Translates a clast equation CLEQ to a tree. */
536 graphite_translate_clast_equation (struct clast_equation *cleq,
540 tree type = type_for_clast_eq (cleq, ip);
541 tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
542 tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
547 else if (cleq->sign > 0)
553 return fold_build2 (comp, boolean_type_node, lhs, rhs);
556 /* Creates the test for the condition in STMT. */
559 graphite_create_guard_cond_expr (struct clast_guard *stmt,
565 for (i = 0; i < stmt->n; i++)
567 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
570 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
578 /* Creates a new if region corresponding to Cloog's guard. */
581 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
584 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
585 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
589 /* Compute the lower bound LOW and upper bound UP for the induction
590 variable at LEVEL for the statement PBB, based on the transformed
591 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
592 the iteration domain, and G the context parameters. */
595 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
597 ppl_Pointset_Powerset_C_Polyhedron_t ps;
598 ppl_Linear_Expression_t le;
600 combine_context_id_scat (&ps, pbb, false);
602 /* Prepare the linear expression corresponding to the level that we
603 want to maximize/minimize. */
605 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
606 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
608 ppl_new_Linear_Expression_with_dimension (&le, dim);
609 ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
612 ppl_max_for_le_pointset (ps, le, up);
613 ppl_min_for_le_pointset (ps, le, low);
614 ppl_delete_Linear_Expression (le);
615 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
618 /* Compute the type for the induction variable at LEVEL for the
619 statement PBB, based on the transformed schedule of PBB. */
622 type_for_level (poly_bb_p pbb, int level)
630 compute_bounds_for_level (pbb, level, low, up);
631 type = type_for_interval (low, up);
638 /* Walks a CLAST and returns the first statement in the body of a
641 FIXME: This function should not be used to get a PBB in the STMT
642 loop in order to find out the iteration domain of the loop: the
643 counter example from Tobias is:
645 | for (i = 0; i < 100; i++)
652 This function would return S1 whose iteration domain contains only
653 one point "i = 0", whereas the iteration domain of S2 has 100 points.
655 This should be implemented using some functionality existing in
658 static struct clast_user_stmt *
659 clast_get_body_of_loop (struct clast_stmt *stmt)
662 || CLAST_STMT_IS_A (stmt, stmt_user))
663 return (struct clast_user_stmt *) stmt;
665 if (CLAST_STMT_IS_A (stmt, stmt_for))
666 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
668 if (CLAST_STMT_IS_A (stmt, stmt_guard))
669 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
671 if (CLAST_STMT_IS_A (stmt, stmt_block))
672 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
677 /* Returns the type for the induction variable for the loop translated
681 type_for_clast_for (struct clast_for *stmt_for, int level,
684 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
685 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
686 CloogStatement *cs = body->statement;
687 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
688 tree lb_type = type_for_clast_expr (stmt_for->LB, ip);
689 tree ub_type = type_for_clast_expr (stmt_for->UB, ip);
691 return max_signed_precision_type (lb_type, max_precision_type
692 (ub_type, type_for_level (pbb, level)));
695 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
696 induction variable for the new LOOP. New LOOP is attached to CFG
697 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
698 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
699 CLooG's scattering name to the induction variable created for the
700 loop of STMT. The new induction variable is inserted in the NEWIVS
701 vector and is of type TYPE. */
704 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
705 loop_p outer, tree type, tree lb, tree ub,
706 int level, ivs_params_p ip)
708 tree stride = gmp_cst_to_tree (type, stmt->stride);
709 tree ivvar = create_tmp_var (type, "graphite_IV");
710 tree iv, iv_after_increment;
711 loop_p loop = create_empty_loop_on_edge
712 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
713 outer ? outer : entry_edge->src->loop_father);
715 add_referenced_var (ivvar);
717 save_clast_name_index (ip->newivs_index, stmt->iterator,
718 VEC_length (tree, *(ip->newivs)), level);
719 VEC_safe_push (tree, heap, *(ip->newivs), iv);
723 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
724 induction variables of the loops around GBB in SESE. */
727 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
730 struct clast_stmt *t;
732 CloogStatement *cs = user_stmt->statement;
733 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
734 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
736 for (t = user_stmt->substitutions; t; t = t->next, depth++)
738 struct clast_expr *expr = (struct clast_expr *)
739 ((struct clast_assignment *)t)->RHS;
740 tree type = type_for_clast_expr (expr, ip);
741 tree new_name = clast_to_gcc_expression (type, expr, ip);
742 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
744 VEC_replace (tree, iv_map, old_loop->num, new_name);
748 /* Construct bb_pbb_def with BB and PBB. */
751 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
753 bb_pbb_def *bb_pbb_p;
755 bb_pbb_p = XNEW (bb_pbb_def);
762 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
765 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
771 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
774 *x = new_bb_pbb_def (bb, pbb);
777 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
780 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
786 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
789 return ((bb_pbb_def *) *slot)->pbb;
794 /* Check data dependency in LOOP at level LEVEL.
795 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
799 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
802 basic_block *bbs = get_loop_body_in_dom_order (loop);
804 for (i = 0; i < loop->num_nodes; i++)
806 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
811 for (j = 0; j < loop->num_nodes; j++)
813 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
818 if (dependency_between_pbbs_p (pbb1, pbb2, level))
831 /* Translates a clast user statement STMT to gimple.
833 - NEXT_E is the edge where new generated code should be attached.
834 - CONTEXT_LOOP is the loop in which the generated code will be placed
835 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
838 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
839 htab_t bb_pbb_mapping, ivs_params_p ip)
843 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
844 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
845 VEC (tree, heap) *iv_map;
847 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
850 nb_loops = number_of_loops ();
851 iv_map = VEC_alloc (tree, heap, nb_loops);
852 for (i = 0; i < nb_loops; i++)
853 VEC_quick_push (tree, iv_map, NULL_TREE);
855 build_iv_mapping (iv_map, stmt, ip);
856 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
858 VEC_free (tree, heap, iv_map);
860 new_bb = next_e->src;
861 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
862 update_ssa (TODO_update_ssa);
867 /* Creates a new if region protecting the loop to be executed, if the execution
868 count is zero (lb > ub). */
871 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
872 int level, tree *type, tree *lb, tree *ub,
878 *type = type_for_clast_for (stmt, level, ip);
879 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
880 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
882 /* When ub is simply a constant or a parameter, use lb <= ub. */
883 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
884 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
887 tree one = (POINTER_TYPE_P (*type)
889 : fold_convert (*type, integer_one_node));
890 /* Adding +1 and using LT_EXPR helps with loop latches that have a
891 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
892 2^k-1 due to integer overflow, and the condition lb <= ub is true,
893 even if we do not want this. However lb < ub + 1 is false, as
895 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
896 : PLUS_EXPR, *type, *ub, one);
898 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
901 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
907 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
909 /* Create the loop for a clast for statement.
911 - NEXT_E is the edge where new generated code should be attached.
912 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
915 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
916 edge next_e, htab_t bb_pbb_mapping, int level,
917 tree type, tree lb, tree ub, ivs_params_p ip)
919 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
920 type, lb, ub, level, ip);
921 edge last_e = single_exit (loop);
922 edge to_body = single_succ_edge (loop->header);
923 basic_block after = to_body->dest;
925 /* Create a basic block for loop close phi nodes. */
926 last_e = single_succ_edge (split_edge (last_e));
928 /* Translate the body of the loop. */
929 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
931 redirect_edge_succ_nodup (next_e, after);
932 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
934 if (flag_loop_parallelize_all
935 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
936 loop->can_be_parallel = true;
941 /* Translates a clast for statement STMT to gimple. First a guard is created
942 protecting the loop, if it is executed zero times. In this guard we create
943 the real loop structure.
945 - NEXT_E is the edge where new generated code should be attached.
946 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
949 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
950 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
953 edge last_e = graphite_create_new_loop_guard (next_e, stmt, level, &type,
955 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
957 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
962 /* Translates a clast guard statement STMT to gimple.
964 - NEXT_E is the edge where new generated code should be attached.
965 - CONTEXT_LOOP is the loop in which the generated code will be placed
966 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
969 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
970 edge next_e, htab_t bb_pbb_mapping, int level,
973 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
974 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
976 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
980 /* Translates a CLAST statement STMT to GCC representation in the
983 - NEXT_E is the edge where new generated code should be attached.
984 - CONTEXT_LOOP is the loop in which the generated code will be placed
985 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
988 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
989 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
994 if (CLAST_STMT_IS_A (stmt, stmt_root))
997 else if (CLAST_STMT_IS_A (stmt, stmt_user))
998 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
999 next_e, bb_pbb_mapping, ip);
1001 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1002 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1003 next_e, bb_pbb_mapping, level, ip);
1005 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1006 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1007 next_e, bb_pbb_mapping, level, ip);
1009 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1010 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1011 next_e, bb_pbb_mapping, level, ip);
1015 recompute_all_dominators ();
1018 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1022 /* Free the SCATTERING domain list. */
1025 free_scattering (CloogScatteringList *scattering)
1029 CloogScattering *dom = cloog_scattering (scattering);
1030 CloogScatteringList *next = cloog_next_scattering (scattering);
1032 cloog_scattering_free (dom);
1038 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1039 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1040 from 0 to scop_nb_loops (scop). */
1043 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1045 sese region = SCOP_REGION (scop);
1047 int nb_iterators = scop_max_loop_depth (scop);
1048 int nb_scattering = cloog_program_nb_scattdims (prog);
1049 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1050 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1051 char **scattering = XNEWVEC (char *, nb_scattering);
1052 char **parameters= XNEWVEC (char *, nb_parameters);
1054 cloog_program_set_names (prog, cloog_names_malloc ());
1056 for (i = 0; i < nb_parameters; i++)
1058 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1059 const char *name = get_name (param);
1065 len = strlen (name);
1067 parameters[i] = XNEWVEC (char, len + 1);
1068 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1071 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1072 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1074 for (i = 0; i < nb_iterators; i++)
1077 iterators[i] = XNEWVEC (char, len);
1078 snprintf (iterators[i], len, "git_%d", i);
1081 cloog_names_set_nb_iterators (cloog_program_names (prog),
1083 cloog_names_set_iterators (cloog_program_names (prog),
1086 for (i = 0; i < nb_scattering; i++)
1089 scattering[i] = XNEWVEC (char, len);
1090 snprintf (scattering[i], len, "scat_%d", i);
1093 cloog_names_set_nb_scattering (cloog_program_names (prog),
1095 cloog_names_set_scattering (cloog_program_names (prog),
1099 /* Initialize a CLooG input file. */
1102 init_cloog_input_file (int scop_number)
1104 FILE *graphite_out_file;
1105 int len = strlen (dump_base_name);
1106 char *dumpname = XNEWVEC (char, len + 25);
1107 char *s_scop_number = XNEWVEC (char, 15);
1109 memcpy (dumpname, dump_base_name, len + 1);
1110 strip_off_ending (dumpname, len);
1111 sprintf (s_scop_number, ".%d", scop_number);
1112 strcat (dumpname, s_scop_number);
1113 strcat (dumpname, ".cloog");
1114 graphite_out_file = fopen (dumpname, "w+b");
1116 if (graphite_out_file == 0)
1117 fatal_error ("can%'t open %s for writing: %m", dumpname);
1121 return graphite_out_file;
1124 /* Build cloog program for SCoP. */
1127 build_cloog_prog (scop_p scop, CloogProgram *prog,
1128 CloogOptions *options)
1131 int max_nb_loops = scop_max_loop_depth (scop);
1133 CloogLoop *loop_list = NULL;
1134 CloogBlockList *block_list = NULL;
1135 CloogScatteringList *scattering = NULL;
1136 int nbs = 2 * max_nb_loops + 1;
1139 cloog_program_set_context
1140 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1141 scop_nb_params (scop), cloog_state));
1142 nbs = unify_scattering_dimensions (scop);
1143 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1144 cloog_program_set_nb_scattdims (prog, nbs);
1145 initialize_cloog_names (scop, prog);
1147 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1149 CloogStatement *stmt;
1153 /* Dead code elimination: when the domain of a PBB is empty,
1154 don't generate code for the PBB. */
1155 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1158 /* Build the new statement and its block. */
1159 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1160 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1161 scop_nb_params (scop),
1163 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1164 cloog_statement_set_usr (stmt, pbb);
1166 /* Build loop list. */
1168 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1169 cloog_loop_set_next (new_loop_list, loop_list);
1170 cloog_loop_set_domain (new_loop_list, dom);
1171 cloog_loop_set_block (new_loop_list, block);
1172 loop_list = new_loop_list;
1175 /* Build block list. */
1177 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1179 cloog_block_list_set_next (new_block_list, block_list);
1180 cloog_block_list_set_block (new_block_list, block);
1181 block_list = new_block_list;
1184 /* Build scattering list. */
1186 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1187 CloogScatteringList *new_scattering
1188 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1189 ppl_Polyhedron_t scat;
1190 CloogScattering *dom;
1192 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1193 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1194 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1197 cloog_set_next_scattering (new_scattering, scattering);
1198 cloog_set_scattering (new_scattering, dom);
1199 scattering = new_scattering;
1203 cloog_program_set_loop (prog, loop_list);
1204 cloog_program_set_blocklist (prog, block_list);
1206 for (i = 0; i < nbs; i++)
1209 cloog_program_set_scaldims (prog, scaldims);
1211 /* Extract scalar dimensions to simplify the code generation problem. */
1212 cloog_program_extract_scalars (prog, scattering, options);
1214 /* Dump a .cloog input file, if requested. This feature is only
1215 enabled in the Graphite branch. */
1218 static size_t file_scop_number = 0;
1219 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1221 cloog_program_dump_cloog (cloog_file, prog, scattering);
1225 /* Apply scattering. */
1226 cloog_program_scatter (prog, scattering, options);
1227 free_scattering (scattering);
1229 /* Iterators corresponding to scalar dimensions have to be extracted. */
1230 cloog_names_scalarize (cloog_program_names (prog), nbs,
1231 cloog_program_scaldims (prog));
1233 /* Free blocklist. */
1235 CloogBlockList *next = cloog_program_blocklist (prog);
1239 CloogBlockList *toDelete = next;
1240 next = cloog_block_list_next (next);
1241 cloog_block_list_set_next (toDelete, NULL);
1242 cloog_block_list_set_block (toDelete, NULL);
1243 cloog_block_list_free (toDelete);
1245 cloog_program_set_blocklist (prog, NULL);
1249 /* Return the options that will be used in GLOOG. */
1251 static CloogOptions *
1252 set_cloog_options (void)
1254 CloogOptions *options = cloog_options_malloc (cloog_state);
1256 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1257 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1258 we pass an incomplete program to cloog. */
1259 options->language = LANGUAGE_C;
1261 /* Enable complex equality spreading: removes dummy statements
1262 (assignments) in the generated code which repeats the
1263 substitution equations for statements. This is useless for
1268 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1271 /* Enable C pretty-printing mode: normalizes the substitution
1272 equations for statements. */
1276 /* Allow cloog to build strides with a stride width different to one.
1277 This example has stride = 4:
1279 for (i = 0; i < 20; i += 4)
1281 options->strides = 1;
1283 /* Disable optimizations and make cloog generate source code closer to the
1284 input. This is useful for debugging, but later we want the optimized
1287 XXX: We can not disable optimizations, as loop blocking is not working
1292 options->l = INT_MAX;
1298 /* Prints STMT to STDERR. */
1301 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1303 CloogOptions *options = set_cloog_options ();
1305 clast_pprint (file, stmt, 0, options);
1306 cloog_options_free (options);
1309 /* Prints STMT to STDERR. */
1312 debug_clast_stmt (struct clast_stmt *stmt)
1314 print_clast_stmt (stderr, stmt);
1317 /* Translate SCOP to a CLooG program and clast. These two
1318 representations should be freed together: a clast cannot be used
1319 without a program. */
1322 scop_to_clast (scop_p scop)
1324 CloogOptions *options = set_cloog_options ();
1325 cloog_prog_clast pc;
1327 /* Connect new cloog prog generation to graphite. */
1328 pc.prog = cloog_program_malloc ();
1329 build_cloog_prog (scop, pc.prog, options);
1330 pc.prog = cloog_program_generate (pc.prog, options);
1331 pc.stmt = cloog_clast_create (pc.prog, options);
1333 cloog_options_free (options);
1337 /* Prints to FILE the code generated by CLooG for SCOP. */
1340 print_generated_program (FILE *file, scop_p scop)
1342 CloogOptions *options = set_cloog_options ();
1344 cloog_prog_clast pc = scop_to_clast (scop);
1346 fprintf (file, " (prog: \n");
1347 cloog_program_print (file, pc.prog);
1348 fprintf (file, " )\n");
1350 fprintf (file, " (clast: \n");
1351 clast_pprint (file, pc.stmt, 0, options);
1352 fprintf (file, " )\n");
1354 cloog_options_free (options);
1355 cloog_clast_free (pc.stmt);
1356 cloog_program_free (pc.prog);
1359 /* Prints to STDERR the code generated by CLooG for SCOP. */
1362 debug_generated_program (scop_p scop)
1364 print_generated_program (stderr, scop);
1367 /* Add CLooG names to parameter index. The index is used to translate
1368 back from CLooG names to GCC trees. */
1371 create_params_index (htab_t index_table, CloogProgram *prog) {
1372 CloogNames* names = cloog_program_names (prog);
1373 int nb_parameters = cloog_names_nb_parameters (names);
1374 char **parameters = cloog_names_parameters (names);
1377 for (i = 0; i < nb_parameters; i++)
1378 save_clast_name_index (index_table, parameters[i], i, i);
1381 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1382 the given SCOP. Return true if code generation succeeded.
1383 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1387 gloog (scop_p scop, htab_t bb_pbb_mapping)
1389 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1390 loop_p context_loop;
1391 sese region = SCOP_REGION (scop);
1392 ifsese if_region = NULL;
1393 htab_t newivs_index, params_index;
1394 cloog_prog_clast pc;
1395 struct ivs_params ip;
1397 timevar_push (TV_GRAPHITE_CODE_GEN);
1398 gloog_error = false;
1400 pc = scop_to_clast (scop);
1402 if (dump_file && (dump_flags & TDF_DETAILS))
1404 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1405 print_clast_stmt (dump_file, pc.stmt);
1406 fprintf (dump_file, "\n");
1409 recompute_all_dominators ();
1412 if_region = move_sese_in_condition (region);
1413 sese_insert_phis_for_liveouts (region,
1414 if_region->region->exit->src,
1415 if_region->false_region->exit,
1416 if_region->true_region->exit);
1417 recompute_all_dominators ();
1420 context_loop = SESE_ENTRY (region)->src->loop_father;
1421 newivs_index = htab_create (10, clast_name_index_elt_info,
1422 eq_clast_name_indexes, free);
1423 params_index = htab_create (10, clast_name_index_elt_info,
1424 eq_clast_name_indexes, free);
1426 create_params_index (params_index, pc.prog);
1428 ip.newivs = &newivs;
1429 ip.newivs_index = newivs_index;
1430 ip.params = SESE_PARAMS (region);
1431 ip.params_index = params_index;
1434 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1435 bb_pbb_mapping, 0, &ip);
1438 recompute_all_dominators ();
1442 set_ifsese_condition (if_region, integer_zero_node);
1444 free (if_region->true_region);
1445 free (if_region->region);
1448 htab_delete (newivs_index);
1449 htab_delete (params_index);
1450 VEC_free (tree, heap, newivs);
1451 cloog_clast_free (pc.stmt);
1452 cloog_program_free (pc.prog);
1453 timevar_pop (TV_GRAPHITE_CODE_GEN);
1455 if (dump_file && (dump_flags & TDF_DETAILS))
1459 int num_no_dependency = 0;
1461 FOR_EACH_LOOP (li, loop, 0)
1462 if (loop->can_be_parallel)
1463 num_no_dependency++;
1465 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1469 return !gloog_error;