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 maximal precision type for expressions TYPE1 and TYPE2. */
212 max_precision_type (tree type1, tree type2)
214 enum machine_mode mode;
215 int p1, p2, precision;
218 if (POINTER_TYPE_P (type1))
221 if (POINTER_TYPE_P (type2))
224 if (TYPE_UNSIGNED (type1)
225 && TYPE_UNSIGNED (type2))
226 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
228 p1 = TYPE_PRECISION (type1);
229 p2 = TYPE_PRECISION (type2);
232 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
234 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
236 if (precision > BITS_PER_WORD)
239 return integer_type_node;
242 mode = smallest_mode_for_size (precision, MODE_INT);
243 precision = GET_MODE_PRECISION (mode);
244 type = build_nonstandard_integer_type (precision, false);
249 return integer_type_node;
256 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
258 /* Converts a Cloog reduction expression R with reduction operation OP
259 to a GCC expression tree of type TYPE. */
262 clast_to_gcc_expression_red (tree type, enum tree_code op,
263 struct clast_reduction *r, ivs_params_p ip)
266 tree res = clast_to_gcc_expression (type, r->elts[0], ip);
267 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
269 for (i = 1; i < r->n; i++)
271 tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
272 res = fold_build2 (op, type, res, t);
278 /* Converts a Cloog AST expression E back to a GCC expression tree of
282 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
286 case clast_expr_term:
288 struct clast_term *t = (struct clast_term *) e;
292 if (mpz_cmp_si (t->val, 1) == 0)
294 tree name = clast_name_to_gcc (t->var, ip);
296 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
297 name = fold_convert (sizetype, name);
299 name = fold_convert (type, name);
303 else if (mpz_cmp_si (t->val, -1) == 0)
305 tree name = clast_name_to_gcc (t->var, ip);
307 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
308 name = fold_convert (sizetype, name);
310 name = fold_convert (type, name);
312 return fold_build1 (NEGATE_EXPR, type, name);
316 tree name = clast_name_to_gcc (t->var, ip);
317 tree cst = gmp_cst_to_tree (type, t->val);
319 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
320 name = fold_convert (sizetype, name);
322 name = fold_convert (type, name);
324 if (!POINTER_TYPE_P (type))
325 return fold_build2 (MULT_EXPR, type, cst, name);
332 return gmp_cst_to_tree (type, t->val);
337 struct clast_reduction *r = (struct clast_reduction *) e;
342 return clast_to_gcc_expression_red
343 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
347 return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
350 return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
360 struct clast_binary *b = (struct clast_binary *) e;
361 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
362 tree tl = clast_to_gcc_expression (type, lhs, ip);
363 tree tr = gmp_cst_to_tree (type, b->RHS);
368 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
371 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
374 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
377 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
391 /* Return a type that could represent the values between V1 and V2. */
394 type_for_interval (mpz_t v1, mpz_t v2)
398 enum machine_mode mode;
399 int precision = MAX (mpz_sizeinbase (v1, 2),
400 mpz_sizeinbase (v2, 2));
402 if (precision > BITS_PER_WORD)
405 return integer_type_node;
408 if (mpz_cmp (v1, v2) <= 0)
409 unsigned_p = (mpz_sgn (v1) >= 0);
411 unsigned_p = (mpz_sgn (v2) >= 0);
413 mode = smallest_mode_for_size (precision, MODE_INT);
414 precision = GET_MODE_PRECISION (mode);
415 type = build_nonstandard_integer_type (precision, unsigned_p);
420 return integer_type_node;
426 /* Return a type that could represent the integer value VAL, or
427 otherwise return NULL_TREE. */
430 type_for_value (mpz_t val)
432 return type_for_interval (val, val);
435 /* Return the type for the clast_term T used in STMT. */
438 type_for_clast_term (struct clast_term *t, ivs_params_p ip)
440 gcc_assert (t->expr.type == clast_expr_term);
443 return type_for_value (t->val);
445 return TREE_TYPE (clast_name_to_gcc (t->var, ip));
449 type_for_clast_expr (struct clast_expr *, ivs_params_p);
451 /* Return the type for the clast_reduction R used in STMT. */
454 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip)
457 tree type = NULL_TREE;
460 return type_for_clast_expr (r->elts[0], ip);
467 type = type_for_clast_expr (r->elts[0], ip);
468 for (i = 1; i < r->n; i++)
469 type = max_precision_type
470 (type, type_for_clast_expr (r->elts[i], ip));
482 /* Return the type for the clast_binary B used in STMT. */
485 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip)
487 tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip);
488 tree r = type_for_value (b->RHS);
489 return max_precision_type (l, r);
492 /* Returns the type for the CLAST expression E when used in statement
496 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip)
500 case clast_expr_term:
501 return type_for_clast_term ((struct clast_term *) e, ip);
504 return type_for_clast_red ((struct clast_reduction *) e, ip);
507 return type_for_clast_bin ((struct clast_binary *) e, ip);
516 /* Returns the type for the equation CLEQ. */
519 type_for_clast_eq (struct clast_equation *cleq, ivs_params_p ip)
521 tree l = type_for_clast_expr (cleq->LHS, ip);
522 tree r = type_for_clast_expr (cleq->RHS, ip);
523 return max_precision_type (l, r);
526 /* Translates a clast equation CLEQ to a tree. */
529 graphite_translate_clast_equation (struct clast_equation *cleq,
533 tree type = type_for_clast_eq (cleq, ip);
534 tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
535 tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
540 else if (cleq->sign > 0)
546 return fold_build2 (comp, boolean_type_node, lhs, rhs);
549 /* Creates the test for the condition in STMT. */
552 graphite_create_guard_cond_expr (struct clast_guard *stmt,
558 for (i = 0; i < stmt->n; i++)
560 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
563 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
571 /* Creates a new if region corresponding to Cloog's guard. */
574 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
577 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
578 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
582 /* Compute the lower bound LOW and upper bound UP for the induction
583 variable at LEVEL for the statement PBB, based on the transformed
584 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
585 the iteration domain, and G the context parameters. */
588 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
590 ppl_Pointset_Powerset_C_Polyhedron_t ps;
591 ppl_Linear_Expression_t le;
593 combine_context_id_scat (&ps, pbb, false);
595 /* Prepare the linear expression corresponding to the level that we
596 want to maximize/minimize. */
598 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
599 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
601 ppl_new_Linear_Expression_with_dimension (&le, dim);
602 ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
605 ppl_max_for_le_pointset (ps, le, up);
606 ppl_min_for_le_pointset (ps, le, low);
607 ppl_delete_Linear_Expression (le);
608 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
611 /* Compute the type for the induction variable at LEVEL for the
612 statement PBB, based on the transformed schedule of PBB. */
615 type_for_level (poly_bb_p pbb, int level)
623 compute_bounds_for_level (pbb, level, low, up);
624 type = type_for_interval (low, up);
631 /* Walks a CLAST and returns the first statement in the body of a
634 FIXME: This function should not be used to get a PBB in the STMT
635 loop in order to find out the iteration domain of the loop: the
636 counter example from Tobias is:
638 | for (i = 0; i < 100; i++)
645 This function would return S1 whose iteration domain contains only
646 one point "i = 0", whereas the iteration domain of S2 has 100 points.
648 This should be implemented using some functionality existing in
651 static struct clast_user_stmt *
652 clast_get_body_of_loop (struct clast_stmt *stmt)
655 || CLAST_STMT_IS_A (stmt, stmt_user))
656 return (struct clast_user_stmt *) stmt;
658 if (CLAST_STMT_IS_A (stmt, stmt_for))
659 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
661 if (CLAST_STMT_IS_A (stmt, stmt_guard))
662 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
664 if (CLAST_STMT_IS_A (stmt, stmt_block))
665 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
670 /* Returns the type for the induction variable for the loop translated
674 type_for_clast_for (struct clast_for *stmt_for, int level,
677 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
678 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
679 CloogStatement *cs = body->statement;
680 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
681 tree lb_type = type_for_clast_expr (stmt_for->LB, ip);
682 tree ub_type = type_for_clast_expr (stmt_for->UB, ip);
684 return max_precision_type
685 (lb_type, max_precision_type (ub_type, type_for_level (pbb, level)));
688 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
689 induction variable for the new LOOP. New LOOP is attached to CFG
690 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
691 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
692 CLooG's scattering name to the induction variable created for the
693 loop of STMT. The new induction variable is inserted in the NEWIVS
694 vector and is of type TYPE. */
697 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
698 loop_p outer, tree type, tree lb, tree ub,
699 int level, ivs_params_p ip)
701 tree stride = gmp_cst_to_tree (type, stmt->stride);
702 tree ivvar = create_tmp_var (type, "graphite_IV");
703 tree iv, iv_after_increment;
704 loop_p loop = create_empty_loop_on_edge
705 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
706 outer ? outer : entry_edge->src->loop_father);
708 add_referenced_var (ivvar);
710 save_clast_name_index (ip->newivs_index, stmt->iterator,
711 VEC_length (tree, *(ip->newivs)), level);
712 VEC_safe_push (tree, heap, *(ip->newivs), iv);
716 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
717 induction variables of the loops around GBB in SESE. */
720 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
723 struct clast_stmt *t;
725 CloogStatement *cs = user_stmt->statement;
726 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
727 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
729 for (t = user_stmt->substitutions; t; t = t->next, depth++)
731 struct clast_expr *expr = (struct clast_expr *)
732 ((struct clast_assignment *)t)->RHS;
733 tree type = type_for_clast_expr (expr, ip);
734 tree new_name = clast_to_gcc_expression (type, expr, ip);
735 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
737 VEC_replace (tree, iv_map, old_loop->num, new_name);
741 /* Construct bb_pbb_def with BB and PBB. */
744 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
746 bb_pbb_def *bb_pbb_p;
748 bb_pbb_p = XNEW (bb_pbb_def);
755 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
758 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
764 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
767 *x = new_bb_pbb_def (bb, pbb);
770 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
773 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
779 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
782 return ((bb_pbb_def *) *slot)->pbb;
787 /* Check data dependency in LOOP at level LEVEL.
788 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
792 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
795 basic_block *bbs = get_loop_body_in_dom_order (loop);
797 for (i = 0; i < loop->num_nodes; i++)
799 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
804 for (j = 0; j < loop->num_nodes; j++)
806 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
811 if (dependency_between_pbbs_p (pbb1, pbb2, level))
824 /* Translates a clast user statement STMT to gimple.
826 - NEXT_E is the edge where new generated code should be attached.
827 - CONTEXT_LOOP is the loop in which the generated code will be placed
828 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
831 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
832 htab_t bb_pbb_mapping, ivs_params_p ip)
836 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
837 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
838 VEC (tree, heap) *iv_map;
840 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
843 nb_loops = number_of_loops ();
844 iv_map = VEC_alloc (tree, heap, nb_loops);
845 for (i = 0; i < nb_loops; i++)
846 VEC_quick_push (tree, iv_map, NULL_TREE);
848 build_iv_mapping (iv_map, stmt, ip);
849 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
851 VEC_free (tree, heap, iv_map);
853 new_bb = next_e->src;
854 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
855 update_ssa (TODO_update_ssa);
860 /* Creates a new if region protecting the loop to be executed, if the execution
861 count is zero (lb > ub). */
864 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
865 int level, tree *type, tree *lb, tree *ub,
871 *type = type_for_clast_for (stmt, level, ip);
872 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
873 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
875 /* When ub is simply a constant or a parameter, use lb <= ub. */
876 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
877 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
880 tree one = (POINTER_TYPE_P (*type)
882 : fold_convert (*type, integer_one_node));
883 /* Adding +1 and using LT_EXPR helps with loop latches that have a
884 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
885 2^k-1 due to integer overflow, and the condition lb <= ub is true,
886 even if we do not want this. However lb < ub + 1 is false, as
888 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
889 : PLUS_EXPR, *type, *ub, one);
891 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
894 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
900 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
902 /* Create the loop for a clast for statement.
904 - NEXT_E is the edge where new generated code should be attached.
905 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
908 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
909 edge next_e, htab_t bb_pbb_mapping, int level,
910 tree type, tree lb, tree ub, ivs_params_p ip)
912 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
913 type, lb, ub, level, ip);
914 edge last_e = single_exit (loop);
915 edge to_body = single_succ_edge (loop->header);
916 basic_block after = to_body->dest;
918 /* Create a basic block for loop close phi nodes. */
919 last_e = single_succ_edge (split_edge (last_e));
921 /* Translate the body of the loop. */
922 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
924 redirect_edge_succ_nodup (next_e, after);
925 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
927 if (flag_loop_parallelize_all
928 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
929 loop->can_be_parallel = true;
934 /* Translates a clast for statement STMT to gimple. First a guard is created
935 protecting the loop, if it is executed zero times. In this guard we create
936 the real loop structure.
938 - NEXT_E is the edge where new generated code should be attached.
939 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
942 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
943 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
946 edge last_e = graphite_create_new_loop_guard (next_e, stmt, level, &type,
948 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
950 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
955 /* Translates a clast guard statement STMT to gimple.
957 - NEXT_E is the edge where new generated code should be attached.
958 - CONTEXT_LOOP is the loop in which the generated code will be placed
959 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
962 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
963 edge next_e, htab_t bb_pbb_mapping, int level,
966 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
967 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
969 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
973 /* Translates a CLAST statement STMT to GCC representation in the
976 - NEXT_E is the edge where new generated code should be attached.
977 - CONTEXT_LOOP is the loop in which the generated code will be placed
978 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
981 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
982 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
987 if (CLAST_STMT_IS_A (stmt, stmt_root))
990 else if (CLAST_STMT_IS_A (stmt, stmt_user))
991 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
992 next_e, bb_pbb_mapping, ip);
994 else if (CLAST_STMT_IS_A (stmt, stmt_for))
995 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
996 next_e, bb_pbb_mapping, level, ip);
998 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
999 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1000 next_e, bb_pbb_mapping, level, ip);
1002 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1003 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1004 next_e, bb_pbb_mapping, level, ip);
1008 recompute_all_dominators ();
1011 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1015 /* Free the SCATTERING domain list. */
1018 free_scattering (CloogScatteringList *scattering)
1022 CloogScattering *dom = cloog_scattering (scattering);
1023 CloogScatteringList *next = cloog_next_scattering (scattering);
1025 cloog_scattering_free (dom);
1031 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1032 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1033 from 0 to scop_nb_loops (scop). */
1036 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1038 sese region = SCOP_REGION (scop);
1040 int nb_iterators = scop_max_loop_depth (scop);
1041 int nb_scattering = cloog_program_nb_scattdims (prog);
1042 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1043 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1044 char **scattering = XNEWVEC (char *, nb_scattering);
1045 char **parameters= XNEWVEC (char *, nb_parameters);
1047 cloog_program_set_names (prog, cloog_names_malloc ());
1049 for (i = 0; i < nb_parameters; i++)
1051 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1052 const char *name = get_name (param);
1058 len = strlen (name);
1060 parameters[i] = XNEWVEC (char, len + 1);
1061 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1064 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1065 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1067 for (i = 0; i < nb_iterators; i++)
1070 iterators[i] = XNEWVEC (char, len);
1071 snprintf (iterators[i], len, "git_%d", i);
1074 cloog_names_set_nb_iterators (cloog_program_names (prog),
1076 cloog_names_set_iterators (cloog_program_names (prog),
1079 for (i = 0; i < nb_scattering; i++)
1082 scattering[i] = XNEWVEC (char, len);
1083 snprintf (scattering[i], len, "scat_%d", i);
1086 cloog_names_set_nb_scattering (cloog_program_names (prog),
1088 cloog_names_set_scattering (cloog_program_names (prog),
1092 /* Initialize a CLooG input file. */
1095 init_cloog_input_file (int scop_number)
1097 FILE *graphite_out_file;
1098 int len = strlen (dump_base_name);
1099 char *dumpname = XNEWVEC (char, len + 25);
1100 char *s_scop_number = XNEWVEC (char, 15);
1102 memcpy (dumpname, dump_base_name, len + 1);
1103 strip_off_ending (dumpname, len);
1104 sprintf (s_scop_number, ".%d", scop_number);
1105 strcat (dumpname, s_scop_number);
1106 strcat (dumpname, ".cloog");
1107 graphite_out_file = fopen (dumpname, "w+b");
1109 if (graphite_out_file == 0)
1110 fatal_error ("can%'t open %s for writing: %m", dumpname);
1114 return graphite_out_file;
1117 /* Build cloog program for SCoP. */
1120 build_cloog_prog (scop_p scop, CloogProgram *prog,
1121 CloogOptions *options)
1124 int max_nb_loops = scop_max_loop_depth (scop);
1126 CloogLoop *loop_list = NULL;
1127 CloogBlockList *block_list = NULL;
1128 CloogScatteringList *scattering = NULL;
1129 int nbs = 2 * max_nb_loops + 1;
1132 cloog_program_set_context
1133 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1134 scop_nb_params (scop), cloog_state));
1135 nbs = unify_scattering_dimensions (scop);
1136 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1137 cloog_program_set_nb_scattdims (prog, nbs);
1138 initialize_cloog_names (scop, prog);
1140 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1142 CloogStatement *stmt;
1146 /* Dead code elimination: when the domain of a PBB is empty,
1147 don't generate code for the PBB. */
1148 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1151 /* Build the new statement and its block. */
1152 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1153 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1154 scop_nb_params (scop),
1156 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1157 cloog_statement_set_usr (stmt, pbb);
1159 /* Build loop list. */
1161 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1162 cloog_loop_set_next (new_loop_list, loop_list);
1163 cloog_loop_set_domain (new_loop_list, dom);
1164 cloog_loop_set_block (new_loop_list, block);
1165 loop_list = new_loop_list;
1168 /* Build block list. */
1170 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1172 cloog_block_list_set_next (new_block_list, block_list);
1173 cloog_block_list_set_block (new_block_list, block);
1174 block_list = new_block_list;
1177 /* Build scattering list. */
1179 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1180 CloogScatteringList *new_scattering
1181 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1182 ppl_Polyhedron_t scat;
1183 CloogScattering *dom;
1185 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1186 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1187 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1190 cloog_set_next_scattering (new_scattering, scattering);
1191 cloog_set_scattering (new_scattering, dom);
1192 scattering = new_scattering;
1196 cloog_program_set_loop (prog, loop_list);
1197 cloog_program_set_blocklist (prog, block_list);
1199 for (i = 0; i < nbs; i++)
1202 cloog_program_set_scaldims (prog, scaldims);
1204 /* Extract scalar dimensions to simplify the code generation problem. */
1205 cloog_program_extract_scalars (prog, scattering, options);
1207 /* Dump a .cloog input file, if requested. This feature is only
1208 enabled in the Graphite branch. */
1211 static size_t file_scop_number = 0;
1212 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1214 cloog_program_dump_cloog (cloog_file, prog, scattering);
1218 /* Apply scattering. */
1219 cloog_program_scatter (prog, scattering, options);
1220 free_scattering (scattering);
1222 /* Iterators corresponding to scalar dimensions have to be extracted. */
1223 cloog_names_scalarize (cloog_program_names (prog), nbs,
1224 cloog_program_scaldims (prog));
1226 /* Free blocklist. */
1228 CloogBlockList *next = cloog_program_blocklist (prog);
1232 CloogBlockList *toDelete = next;
1233 next = cloog_block_list_next (next);
1234 cloog_block_list_set_next (toDelete, NULL);
1235 cloog_block_list_set_block (toDelete, NULL);
1236 cloog_block_list_free (toDelete);
1238 cloog_program_set_blocklist (prog, NULL);
1242 /* Return the options that will be used in GLOOG. */
1244 static CloogOptions *
1245 set_cloog_options (void)
1247 CloogOptions *options = cloog_options_malloc (cloog_state);
1249 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1250 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1251 we pass an incomplete program to cloog. */
1252 options->language = LANGUAGE_C;
1254 /* Enable complex equality spreading: removes dummy statements
1255 (assignments) in the generated code which repeats the
1256 substitution equations for statements. This is useless for
1261 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1264 /* Enable C pretty-printing mode: normalizes the substitution
1265 equations for statements. */
1269 /* Allow cloog to build strides with a stride width different to one.
1270 This example has stride = 4:
1272 for (i = 0; i < 20; i += 4)
1274 options->strides = 1;
1276 /* Disable optimizations and make cloog generate source code closer to the
1277 input. This is useful for debugging, but later we want the optimized
1280 XXX: We can not disable optimizations, as loop blocking is not working
1285 options->l = INT_MAX;
1291 /* Prints STMT to STDERR. */
1294 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1296 CloogOptions *options = set_cloog_options ();
1298 clast_pprint (file, stmt, 0, options);
1299 cloog_options_free (options);
1302 /* Prints STMT to STDERR. */
1305 debug_clast_stmt (struct clast_stmt *stmt)
1307 print_clast_stmt (stderr, stmt);
1310 /* Translate SCOP to a CLooG program and clast. These two
1311 representations should be freed together: a clast cannot be used
1312 without a program. */
1315 scop_to_clast (scop_p scop)
1317 CloogOptions *options = set_cloog_options ();
1318 cloog_prog_clast pc;
1320 /* Connect new cloog prog generation to graphite. */
1321 pc.prog = cloog_program_malloc ();
1322 build_cloog_prog (scop, pc.prog, options);
1323 pc.prog = cloog_program_generate (pc.prog, options);
1324 pc.stmt = cloog_clast_create (pc.prog, options);
1326 cloog_options_free (options);
1330 /* Prints to FILE the code generated by CLooG for SCOP. */
1333 print_generated_program (FILE *file, scop_p scop)
1335 CloogOptions *options = set_cloog_options ();
1337 cloog_prog_clast pc = scop_to_clast (scop);
1339 fprintf (file, " (prog: \n");
1340 cloog_program_print (file, pc.prog);
1341 fprintf (file, " )\n");
1343 fprintf (file, " (clast: \n");
1344 clast_pprint (file, pc.stmt, 0, options);
1345 fprintf (file, " )\n");
1347 cloog_options_free (options);
1348 cloog_clast_free (pc.stmt);
1349 cloog_program_free (pc.prog);
1352 /* Prints to STDERR the code generated by CLooG for SCOP. */
1355 debug_generated_program (scop_p scop)
1357 print_generated_program (stderr, scop);
1360 /* Add CLooG names to parameter index. The index is used to translate
1361 back from CLooG names to GCC trees. */
1364 create_params_index (htab_t index_table, CloogProgram *prog) {
1365 CloogNames* names = cloog_program_names (prog);
1366 int nb_parameters = cloog_names_nb_parameters (names);
1367 char **parameters = cloog_names_parameters (names);
1370 for (i = 0; i < nb_parameters; i++)
1371 save_clast_name_index (index_table, parameters[i], i, i);
1374 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1375 the given SCOP. Return true if code generation succeeded.
1376 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1380 gloog (scop_p scop, htab_t bb_pbb_mapping)
1382 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1383 loop_p context_loop;
1384 sese region = SCOP_REGION (scop);
1385 ifsese if_region = NULL;
1386 htab_t newivs_index, params_index;
1387 cloog_prog_clast pc;
1388 struct ivs_params ip;
1390 timevar_push (TV_GRAPHITE_CODE_GEN);
1391 gloog_error = false;
1393 pc = scop_to_clast (scop);
1395 if (dump_file && (dump_flags & TDF_DETAILS))
1397 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1398 print_clast_stmt (dump_file, pc.stmt);
1399 fprintf (dump_file, "\n");
1402 recompute_all_dominators ();
1405 if_region = move_sese_in_condition (region);
1406 sese_insert_phis_for_liveouts (region,
1407 if_region->region->exit->src,
1408 if_region->false_region->exit,
1409 if_region->true_region->exit);
1410 recompute_all_dominators ();
1413 context_loop = SESE_ENTRY (region)->src->loop_father;
1414 newivs_index = htab_create (10, clast_name_index_elt_info,
1415 eq_clast_name_indexes, free);
1416 params_index = htab_create (10, clast_name_index_elt_info,
1417 eq_clast_name_indexes, free);
1419 create_params_index (params_index, pc.prog);
1421 ip.newivs = &newivs;
1422 ip.newivs_index = newivs_index;
1423 ip.params = SESE_PARAMS (region);
1424 ip.params_index = params_index;
1427 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1428 bb_pbb_mapping, 0, &ip);
1431 recompute_all_dominators ();
1435 set_ifsese_condition (if_region, integer_zero_node);
1437 free (if_region->true_region);
1438 free (if_region->region);
1441 htab_delete (newivs_index);
1442 htab_delete (params_index);
1443 VEC_free (tree, heap, newivs);
1444 cloog_clast_free (pc.stmt);
1445 cloog_program_free (pc.prog);
1446 timevar_pop (TV_GRAPHITE_CODE_GEN);
1448 if (dump_file && (dump_flags & TDF_DETAILS))
1452 int num_no_dependency = 0;
1454 FOR_EACH_LOOP (li, loop, 0)
1455 if (loop->can_be_parallel)
1456 num_no_dependency++;
1458 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1462 return !gloog_error;