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"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
43 #include "langhooks.h"
47 #include "cloog/cloog.h"
49 #include "graphite-ppl.h"
51 #include "graphite-poly.h"
52 #include "graphite-scop-detection.h"
53 #include "graphite-clast-to-gimple.h"
54 #include "graphite-dependences.h"
56 /* This flag is set when an error occurred during the translation of
58 static bool gloog_error;
60 /* Verifies properties that GRAPHITE should maintain during translation. */
63 graphite_verify (void)
65 #ifdef ENABLE_CHECKING
66 verify_loop_structure ();
67 verify_dominators (CDI_DOMINATORS);
68 verify_dominators (CDI_POST_DOMINATORS);
69 verify_loop_closed_ssa (true);
73 /* Stores the INDEX in a vector for a given clast NAME. */
75 typedef struct clast_name_index {
78 } *clast_name_index_p;
80 /* Returns a pointer to a new element of type clast_name_index_p built
81 from NAME and INDEX. */
83 static inline clast_name_index_p
84 new_clast_name_index (const char *name, int index)
86 clast_name_index_p res = XNEW (struct clast_name_index);
93 /* For a given clast NAME, returns -1 if it does not correspond to any
94 parameter, or otherwise, returns the index in the PARAMS or
95 SCATTERING_DIMENSIONS vector. */
98 clast_name_to_index (const char *name, htab_t index_table)
100 struct clast_name_index tmp;
104 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
107 return ((struct clast_name_index *) *slot)->index;
112 /* Records in INDEX_TABLE the INDEX for NAME. */
115 save_clast_name_index (htab_t index_table, const char *name, int index)
117 struct clast_name_index tmp;
121 slot = htab_find_slot (index_table, &tmp, INSERT);
128 *slot = new_clast_name_index (name, index);
132 /* Print to stderr the element ELT. */
135 debug_clast_name_index (clast_name_index_p elt)
137 fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name);
140 /* Helper function for debug_rename_map. */
143 debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED)
145 struct clast_name_index *entry = (struct clast_name_index *) *slot;
146 debug_clast_name_index (entry);
150 /* Print to stderr all the elements of MAP. */
153 debug_clast_name_indexes (htab_t map)
155 htab_traverse (map, debug_clast_name_indexes_1, NULL);
158 /* Computes a hash function for database element ELT. */
160 static inline hashval_t
161 clast_name_index_elt_info (const void *elt)
163 return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
166 /* Compares database elements E1 and E2. */
169 eq_clast_name_indexes (const void *e1, const void *e2)
171 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
172 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
174 return (elt1->name == elt2->name);
178 /* For a given loop DEPTH in the loop nest of the original black box
179 PBB, return the old induction variable associated to that loop. */
182 pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth)
184 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
185 sese region = SCOP_REGION (PBB_SCOP (pbb));
186 loop_p loop = gbb_loop_at_index (gbb, region, depth);
188 return loop->single_iv;
191 /* For a given scattering dimension, return the new induction variable
195 newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth)
197 return VEC_index (tree, newivs, depth);
202 /* Returns the tree variable from the name NAME that was given in
203 Cloog representation. */
206 clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs,
207 htab_t newivs_index, htab_t params_index)
210 VEC (tree, heap) *params = SESE_PARAMS (region);
212 if (params && params_index)
214 index = clast_name_to_index (name, params_index);
217 return VEC_index (tree, params, index);
220 gcc_assert (newivs && newivs_index);
221 index = clast_name_to_index (name, newivs_index);
222 gcc_assert (index >= 0);
224 return newivs_to_depth_to_newiv (newivs, index);
227 /* Returns the signed maximal precision type for expressions TYPE1 and TYPE2. */
230 max_signed_precision_type (tree type1, tree type2)
232 int p1 = TYPE_PRECISION (type1);
233 int p2 = TYPE_PRECISION (type2);
238 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
240 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
242 type = lang_hooks.types.type_for_size (precision, false);
247 return integer_type_node;
252 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
255 max_precision_type (tree type1, tree type2)
257 if (POINTER_TYPE_P (type1))
260 if (POINTER_TYPE_P (type2))
263 if (!TYPE_UNSIGNED (type1)
264 || !TYPE_UNSIGNED (type2))
265 return max_signed_precision_type (type1, type2);
267 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
271 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
274 /* Converts a Cloog reduction expression R with reduction operation OP
275 to a GCC expression tree of type TYPE. */
278 clast_to_gcc_expression_red (tree type, enum tree_code op,
279 struct clast_reduction *r,
280 sese region, VEC (tree, heap) *newivs,
281 htab_t newivs_index, htab_t params_index)
284 tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs,
285 newivs_index, params_index);
286 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
288 for (i = 1; i < r->n; i++)
290 tree t = clast_to_gcc_expression (operand_type, r->elts[i], region,
291 newivs, newivs_index, params_index);
292 res = fold_build2 (op, type, res, t);
298 /* Converts a Cloog AST expression E back to a GCC expression tree of
302 clast_to_gcc_expression (tree type, struct clast_expr *e,
303 sese region, VEC (tree, heap) *newivs,
304 htab_t newivs_index, htab_t params_index)
310 struct clast_term *t = (struct clast_term *) e;
314 if (mpz_cmp_si (t->val, 1) == 0)
316 tree name = clast_name_to_gcc (t->var, region, newivs,
317 newivs_index, params_index);
319 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
320 name = fold_convert (sizetype, name);
322 name = fold_convert (type, name);
326 else if (mpz_cmp_si (t->val, -1) == 0)
328 tree name = clast_name_to_gcc (t->var, region, newivs,
329 newivs_index, params_index);
331 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
332 name = fold_convert (sizetype, name);
334 name = fold_convert (type, name);
336 return fold_build1 (NEGATE_EXPR, type, name);
340 tree name = clast_name_to_gcc (t->var, region, newivs,
341 newivs_index, params_index);
342 tree cst = gmp_cst_to_tree (type, t->val);
344 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
345 name = fold_convert (sizetype, name);
347 name = fold_convert (type, name);
349 if (!POINTER_TYPE_P (type))
350 return fold_build2 (MULT_EXPR, type, cst, name);
357 return gmp_cst_to_tree (type, t->val);
362 struct clast_reduction *r = (struct clast_reduction *) e;
367 return clast_to_gcc_expression_red
368 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
369 r, region, newivs, newivs_index, params_index);
372 return clast_to_gcc_expression_red (type, MIN_EXPR, r, region,
373 newivs, newivs_index,
377 return clast_to_gcc_expression_red (type, MAX_EXPR, r, region,
378 newivs, newivs_index,
389 struct clast_binary *b = (struct clast_binary *) e;
390 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
391 tree tl = clast_to_gcc_expression (type, lhs, region, newivs,
392 newivs_index, params_index);
393 tree tr = gmp_cst_to_tree (type, b->RHS);
398 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
401 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
404 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
407 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
421 /* Return the precision needed to represent the value VAL. */
424 precision_for_value (mpz_t val)
433 value_assign (y, val);
434 value_set_si (two, 2);
440 while (value_gt (y, x))
442 value_multiply (x, x, two);
453 /* Return the precision needed to represent the values between LOW and
457 precision_for_interval (mpz_t low, mpz_t up)
462 gcc_assert (value_le (low, up));
465 value_subtract (diff, up, low);
466 precision = precision_for_value (diff);
472 /* Return a type that could represent the integer value VAL, or
473 otherwise return NULL_TREE. */
476 gcc_type_for_interval (mpz_t low, mpz_t up, tree old_type)
478 bool unsigned_p = true;
479 int precision, prec_up, prec_int;
482 gcc_assert (value_le (low, up));
484 /* Preserve the signedness of the old IV. */
485 if ((old_type && !TYPE_UNSIGNED (old_type))
486 || value_neg_p (low))
489 prec_up = precision_for_value (up);
490 prec_int = precision_for_interval (low, up);
491 precision = prec_up > prec_int ? prec_up : prec_int;
493 type = lang_hooks.types.type_for_size (precision, unsigned_p);
497 return integer_type_node;
503 /* Return a type that could represent the integer value VAL, or
504 otherwise return NULL_TREE. */
507 gcc_type_for_value (mpz_t val)
509 return gcc_type_for_interval (val, val, NULL_TREE);
512 /* Return the type for the clast_term T used in STMT. */
515 gcc_type_for_clast_term (struct clast_term *t,
516 sese region, VEC (tree, heap) *newivs,
517 htab_t newivs_index, htab_t params_index)
519 gcc_assert (t->expr.type == expr_term);
522 return gcc_type_for_value (t->val);
524 return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
525 newivs_index, params_index));
529 gcc_type_for_clast_expr (struct clast_expr *, sese,
530 VEC (tree, heap) *, htab_t, htab_t);
532 /* Return the type for the clast_reduction R used in STMT. */
535 gcc_type_for_clast_red (struct clast_reduction *r, sese region,
536 VEC (tree, heap) *newivs,
537 htab_t newivs_index, htab_t params_index)
540 tree type = NULL_TREE;
543 return gcc_type_for_clast_expr (r->elts[0], region, newivs,
544 newivs_index, params_index);
551 type = gcc_type_for_clast_expr (r->elts[0], region, newivs,
552 newivs_index, params_index);
553 for (i = 1; i < r->n; i++)
554 type = max_precision_type (type, gcc_type_for_clast_expr
555 (r->elts[i], region, newivs,
556 newivs_index, params_index));
568 /* Return the type for the clast_binary B used in STMT. */
571 gcc_type_for_clast_bin (struct clast_binary *b,
572 sese region, VEC (tree, heap) *newivs,
573 htab_t newivs_index, htab_t params_index)
575 tree l = gcc_type_for_clast_expr ((struct clast_expr *) b->LHS, region,
576 newivs, newivs_index, params_index);
577 tree r = gcc_type_for_value (b->RHS);
578 return max_signed_precision_type (l, r);
581 /* Returns the type for the CLAST expression E when used in statement
585 gcc_type_for_clast_expr (struct clast_expr *e,
586 sese region, VEC (tree, heap) *newivs,
587 htab_t newivs_index, htab_t params_index)
592 return gcc_type_for_clast_term ((struct clast_term *) e, region,
593 newivs, newivs_index, params_index);
596 return gcc_type_for_clast_red ((struct clast_reduction *) e, region,
597 newivs, newivs_index, params_index);
600 return gcc_type_for_clast_bin ((struct clast_binary *) e, region,
601 newivs, newivs_index, params_index);
610 /* Returns the type for the equation CLEQ. */
613 gcc_type_for_clast_eq (struct clast_equation *cleq,
614 sese region, VEC (tree, heap) *newivs,
615 htab_t newivs_index, htab_t params_index)
617 tree l = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
618 newivs_index, params_index);
619 tree r = gcc_type_for_clast_expr (cleq->RHS, region, newivs,
620 newivs_index, params_index);
621 return max_precision_type (l, r);
624 /* Translates a clast equation CLEQ to a tree. */
627 graphite_translate_clast_equation (sese region,
628 struct clast_equation *cleq,
629 VEC (tree, heap) *newivs,
630 htab_t newivs_index, htab_t params_index)
633 tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index,
635 tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs,
636 newivs_index, params_index);
637 tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs,
638 newivs_index, params_index);
643 else if (cleq->sign > 0)
649 return fold_build2 (comp, boolean_type_node, lhs, rhs);
652 /* Creates the test for the condition in STMT. */
655 graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt,
656 VEC (tree, heap) *newivs,
657 htab_t newivs_index, htab_t params_index)
662 for (i = 0; i < stmt->n; i++)
664 tree eq = graphite_translate_clast_equation (region, &stmt->eq[i],
665 newivs, newivs_index,
669 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
677 /* Creates a new if region corresponding to Cloog's guard. */
680 graphite_create_new_guard (sese region, edge entry_edge,
681 struct clast_guard *stmt,
682 VEC (tree, heap) *newivs,
683 htab_t newivs_index, htab_t params_index)
685 tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs,
686 newivs_index, params_index);
687 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
691 /* Compute the lower bound LOW and upper bound UP for the induction
692 variable at LEVEL for the statement PBB, based on the transformed
693 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
694 the iteration domain, and G the context parameters. */
697 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
699 ppl_Pointset_Powerset_C_Polyhedron_t ps;
700 ppl_Linear_Expression_t le;
702 combine_context_id_scat (&ps, pbb, false);
704 /* Prepare the linear expression corresponding to the level that we
705 want to maximize/minimize. */
707 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
708 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
710 ppl_new_Linear_Expression_with_dimension (&le, dim);
711 ppl_set_coef (le, 2 * level + 1, 1);
714 ppl_max_for_le_pointset (ps, le, up);
715 ppl_min_for_le_pointset (ps, le, low);
718 /* Compute the type for the induction variable at LEVEL for the
719 statement PBB, based on the transformed schedule of PBB. OLD_TYPE
720 is the type of the old induction variable for that loop. */
721 /* Java does not initialize long_long_integer_type_node. */
722 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
724 /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
725 land. The selected type is big enough to include the original loop
726 iteration variable, but signed to work with the subtractions CLooG
727 may have introduced. If such a type is not available, we fail.
730 compute_type_for_level_1 (poly_bb_p pbb, int level, tree old_type)
738 compute_bounds_for_level (pbb, level, low, up);
739 type = gcc_type_for_interval (low, up, old_type);
746 /* Compute the type for the induction variable at LEVEL for the
747 statement PBB, based on the transformed schedule of PBB. */
750 compute_type_for_level (poly_bb_p pbb, int level)
752 tree oldiv = pbb_to_depth_to_oldiv (pbb, level);
753 tree type = TREE_TYPE (oldiv);
755 if (type && POINTER_TYPE_P (type))
757 #ifdef ENABLE_CHECKING
758 tree ctype = compute_type_for_level_1 (pbb, level, type);
760 /* In the case of a pointer type, check that after the loop
761 transform, the lower and the upper bounds of the type fit the
762 oldiv pointer type. */
763 gcc_assert (TYPE_PRECISION (type) >= TYPE_PRECISION (ctype)
764 && integer_zerop (lower_bound_in_type (ctype, ctype)));
769 return compute_type_for_level_1 (pbb, level, type);
772 /* Walks a CLAST and returns the first statement in the body of a
775 static struct clast_user_stmt *
776 clast_get_body_of_loop (struct clast_stmt *stmt)
779 || CLAST_STMT_IS_A (stmt, stmt_user))
780 return (struct clast_user_stmt *) stmt;
782 if (CLAST_STMT_IS_A (stmt, stmt_for))
783 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
785 if (type_precision < TYPE_PRECISION (my_long_long))
788 if (CLAST_STMT_IS_A (stmt, stmt_block))
789 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
796 /* Returns the induction variable for the loop that gets translated to
800 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for, int level,
801 tree lb_type, tree ub_type)
803 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
804 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
805 CloogStatement *cs = body->statement;
806 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
808 return max_signed_precision_type (lb_type, max_precision_type
809 (ub_type, compute_type_for_level
813 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
814 induction variable for the new LOOP. New LOOP is attached to CFG
815 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
816 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
817 CLooG's scattering name to the induction variable created for the
818 loop of STMT. The new induction variable is inserted in the NEWIVS
822 graphite_create_new_loop (sese region, edge entry_edge,
823 struct clast_for *stmt,
824 loop_p outer, VEC (tree, heap) **newivs,
825 htab_t newivs_index, htab_t params_index, int level)
827 tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, *newivs,
828 newivs_index, params_index);
829 tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, *newivs,
830 newivs_index, params_index);
831 tree type = gcc_type_for_iv_of_clast_loop (stmt, level, lb_type, ub_type);
832 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
833 newivs_index, params_index);
834 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
835 newivs_index, params_index);
836 tree stride = gmp_cst_to_tree (type, stmt->stride);
837 tree ivvar = create_tmp_var (type, "graphite_IV");
838 tree iv, iv_after_increment;
839 loop_p loop = create_empty_loop_on_edge
840 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
841 outer ? outer : entry_edge->src->loop_father);
843 add_referenced_var (ivvar);
845 save_clast_name_index (newivs_index, stmt->iterator,
846 VEC_length (tree, *newivs));
847 VEC_safe_push (tree, heap, *newivs, iv);
851 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
852 variables of the loops around GBB in SESE. */
855 build_iv_mapping (htab_t map, sese region,
856 VEC (tree, heap) *newivs, htab_t newivs_index,
857 struct clast_user_stmt *user_stmt,
860 struct clast_stmt *t;
862 CloogStatement *cs = user_stmt->statement;
863 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
865 for (t = user_stmt->substitutions; t; t = t->next, index++)
867 struct clast_expr *expr = (struct clast_expr *)
868 ((struct clast_assignment *)t)->RHS;
869 tree type = gcc_type_for_clast_expr (expr, region, newivs,
870 newivs_index, params_index);
871 tree old_name = pbb_to_depth_to_oldiv (pbb, index);
872 tree e = clast_to_gcc_expression (type, expr, region, newivs,
873 newivs_index, params_index);
874 set_rename (map, old_name, e);
878 /* Helper function for htab_traverse. */
881 copy_renames (void **slot, void *s)
883 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
884 htab_t res = (htab_t) s;
885 tree old_name = entry->old_name;
886 tree expr = entry->expr;
887 struct rename_map_elt_s tmp;
890 tmp.old_name = old_name;
891 x = htab_find_slot (res, &tmp, INSERT);
894 *x = new_rename_map_elt (old_name, expr);
899 /* Construct bb_pbb_def with BB and PBB. */
902 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
904 bb_pbb_def *bb_pbb_p;
906 bb_pbb_p = XNEW (bb_pbb_def);
913 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
916 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
922 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
925 *x = new_bb_pbb_def (bb, pbb);
928 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
931 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
937 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
940 return ((bb_pbb_def *) *slot)->pbb;
945 /* Check data dependency in LOOP at scattering level LEVEL.
946 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
950 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
953 basic_block *bbs = get_loop_body_in_dom_order (loop);
955 for (i = 0; i < loop->num_nodes; i++)
957 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
962 for (j = 0; j < loop->num_nodes; j++)
964 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
969 if (dependency_between_pbbs_p (pbb1, pbb2, level))
983 translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t,
984 VEC (tree, heap) **, htab_t, htab_t, int, htab_t);
986 /* Translates a clast user statement STMT to gimple.
988 - REGION is the sese region we used to generate the scop.
989 - NEXT_E is the edge where new generated code should be attached.
990 - CONTEXT_LOOP is the loop in which the generated code will be placed
991 - RENAME_MAP contains a set of tuples of new names associated to
992 the original variables names.
993 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
994 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
997 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
998 htab_t rename_map, VEC (tree, heap) **newivs,
999 htab_t newivs_index, htab_t bb_pbb_mapping,
1000 htab_t params_index)
1004 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
1005 gbb = PBB_BLACK_BOX (pbb);
1007 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1010 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
1012 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
1013 next_e, rename_map);
1014 new_bb = next_e->src;
1015 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1016 update_ssa (TODO_update_ssa);
1021 /* Creates a new if region protecting the loop to be executed, if the execution
1022 count is zero (lb > ub). */
1024 graphite_create_new_loop_guard (sese region, edge entry_edge,
1025 struct clast_for *stmt,
1026 VEC (tree, heap) *newivs,
1027 htab_t newivs_index, htab_t params_index)
1031 tree lb_type = gcc_type_for_clast_expr (stmt->LB, region, newivs,
1032 newivs_index, params_index);
1033 tree ub_type = gcc_type_for_clast_expr (stmt->UB, region, newivs,
1034 newivs_index, params_index);
1035 tree type = max_precision_type (lb_type, ub_type);
1036 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
1037 newivs_index, params_index);
1038 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
1039 newivs_index, params_index);
1042 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1043 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
1044 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
1045 However lb < ub + 1 is false, as expected. */
1050 mpz_set_si (gmp_one, 1);
1051 one = gmp_cst_to_tree (type, gmp_one);
1052 mpz_clear (gmp_one);
1054 ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
1057 /* When ub + 1 wraps around, use lb <= ub. */
1058 if (integer_zerop (ub_one))
1059 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, lb, ub);
1061 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
1063 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1069 /* Create the loop for a clast for statement.
1071 - REGION is the sese region we used to generate the scop.
1072 - NEXT_E is the edge where new generated code should be attached.
1073 - RENAME_MAP contains a set of tuples of new names associated to
1074 the original variables names.
1075 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
1076 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
1079 translate_clast_for_loop (sese region, loop_p context_loop,
1080 struct clast_for *stmt, edge next_e,
1081 htab_t rename_map, VEC (tree, heap) **newivs,
1082 htab_t newivs_index, htab_t bb_pbb_mapping,
1083 int level, htab_t params_index)
1085 struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
1086 context_loop, newivs,
1087 newivs_index, params_index,
1089 edge last_e = single_exit (loop);
1090 edge to_body = single_succ_edge (loop->header);
1091 basic_block after = to_body->dest;
1093 /* Create a basic block for loop close phi nodes. */
1094 last_e = single_succ_edge (split_edge (last_e));
1096 /* Translate the body of the loop. */
1097 next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
1098 newivs, newivs_index, bb_pbb_mapping, level + 1,
1100 redirect_edge_succ_nodup (next_e, after);
1101 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1103 /* Remove from rename_map all the tuples containing variables
1104 defined in loop's body. */
1105 insert_loop_close_phis (rename_map, loop);
1107 if (flag_loop_parallelize_all
1108 && !dependency_in_loop_p (loop, bb_pbb_mapping,
1109 get_scattering_level (level)))
1110 loop->can_be_parallel = true;
1115 /* Translates a clast for statement STMT to gimple. First a guard is created
1116 protecting the loop, if it is executed zero times. In this guard we create
1117 the real loop structure.
1119 - REGION is the sese region we used to generate the scop.
1120 - NEXT_E is the edge where new generated code should be attached.
1121 - RENAME_MAP contains a set of tuples of new names associated to
1122 the original variables names.
1123 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
1124 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
1127 translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
1128 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
1129 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
1130 htab_t params_index)
1132 edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
1133 newivs_index, params_index);
1135 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1136 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
1137 edge exit_true_e = single_succ_edge (true_e->dest);
1138 edge exit_false_e = single_succ_edge (false_e->dest);
1140 htab_t before_guard = htab_create (10, rename_map_elt_info,
1141 eq_rename_map_elts, free);
1142 htab_traverse (rename_map, copy_renames, before_guard);
1144 next_e = translate_clast_for_loop (region, context_loop, stmt, true_e,
1146 newivs_index, bb_pbb_mapping, level,
1149 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
1150 before_guard, rename_map);
1152 htab_delete (before_guard);
1157 /* Translates a clast guard statement STMT to gimple.
1159 - REGION is the sese region we used to generate the scop.
1160 - NEXT_E is the edge where new generated code should be attached.
1161 - CONTEXT_LOOP is the loop in which the generated code will be placed
1162 - RENAME_MAP contains a set of tuples of new names associated to
1163 the original variables names.
1164 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
1165 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
1168 translate_clast_guard (sese region, loop_p context_loop,
1169 struct clast_guard *stmt, edge next_e,
1170 htab_t rename_map, VEC (tree, heap) **newivs,
1171 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
1172 htab_t params_index)
1174 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
1175 newivs_index, params_index);
1177 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1178 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
1179 edge exit_true_e = single_succ_edge (true_e->dest);
1180 edge exit_false_e = single_succ_edge (false_e->dest);
1182 htab_t before_guard = htab_create (10, rename_map_elt_info,
1183 eq_rename_map_elts, free);
1184 htab_traverse (rename_map, copy_renames, before_guard);
1186 next_e = translate_clast (region, context_loop, stmt->then, true_e,
1187 rename_map, newivs, newivs_index, bb_pbb_mapping,
1188 level, params_index);
1190 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
1191 before_guard, rename_map);
1193 htab_delete (before_guard);
1198 /* Translates a CLAST statement STMT to GCC representation in the
1201 - NEXT_E is the edge where new generated code should be attached.
1202 - CONTEXT_LOOP is the loop in which the generated code will be placed
1203 - RENAME_MAP contains a set of tuples of new names associated to
1204 the original variables names.
1205 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1207 translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
1208 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
1209 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
1210 htab_t params_index)
1215 if (CLAST_STMT_IS_A (stmt, stmt_root))
1218 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1219 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
1220 next_e, rename_map, newivs, newivs_index,
1221 bb_pbb_mapping, params_index);
1223 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1224 next_e = translate_clast_for (region, context_loop,
1225 (struct clast_for *) stmt, next_e,
1226 rename_map, newivs, newivs_index,
1227 bb_pbb_mapping, level, params_index);
1229 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1230 next_e = translate_clast_guard (region, context_loop,
1231 (struct clast_guard *) stmt, next_e,
1232 rename_map, newivs, newivs_index,
1233 bb_pbb_mapping, level, params_index);
1235 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1236 next_e = translate_clast (region, context_loop,
1237 ((struct clast_block *) stmt)->body,
1238 next_e, rename_map, newivs, newivs_index,
1239 bb_pbb_mapping, level, params_index);
1243 recompute_all_dominators ();
1246 return translate_clast (region, context_loop, stmt->next, next_e,
1247 rename_map, newivs, newivs_index,
1248 bb_pbb_mapping, level, params_index);
1251 /* Free the SCATTERING domain list. */
1254 free_scattering (CloogDomainList *scattering)
1258 CloogDomain *dom = cloog_domain (scattering);
1259 CloogDomainList *next = cloog_next_domain (scattering);
1261 cloog_domain_free (dom);
1267 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1268 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1269 from 0 to scop_nb_loops (scop). */
1272 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1274 sese region = SCOP_REGION (scop);
1276 int nb_iterators = scop_max_loop_depth (scop);
1277 int nb_scattering = cloog_program_nb_scattdims (prog);
1278 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1279 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1280 char **scattering = XNEWVEC (char *, nb_scattering);
1281 char **parameters= XNEWVEC (char *, nb_parameters);
1283 cloog_program_set_names (prog, cloog_names_malloc ());
1285 for (i = 0; i < nb_parameters; i++)
1287 tree param = VEC_index (tree, SESE_PARAMS(region), i);
1288 const char *name = get_name (param);
1294 len = strlen (name);
1296 parameters[i] = XNEWVEC (char, len + 1);
1297 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1300 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1301 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1303 for (i = 0; i < nb_iterators; i++)
1306 iterators[i] = XNEWVEC (char, len);
1307 snprintf (iterators[i], len, "git_%d", i);
1310 cloog_names_set_nb_iterators (cloog_program_names (prog),
1312 cloog_names_set_iterators (cloog_program_names (prog),
1315 for (i = 0; i < nb_scattering; i++)
1318 scattering[i] = XNEWVEC (char, len);
1319 snprintf (scattering[i], len, "scat_%d", i);
1322 cloog_names_set_nb_scattering (cloog_program_names (prog),
1324 cloog_names_set_scattering (cloog_program_names (prog),
1328 /* Build cloog program for SCoP. */
1331 build_cloog_prog (scop_p scop, CloogProgram *prog)
1334 int max_nb_loops = scop_max_loop_depth (scop);
1336 CloogLoop *loop_list = NULL;
1337 CloogBlockList *block_list = NULL;
1338 CloogDomainList *scattering = NULL;
1339 int nbs = 2 * max_nb_loops + 1;
1342 cloog_program_set_context
1343 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1344 nbs = unify_scattering_dimensions (scop);
1345 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1346 cloog_program_set_nb_scattdims (prog, nbs);
1347 initialize_cloog_names (scop, prog);
1349 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1351 CloogStatement *stmt;
1354 /* Dead code elimination: when the domain of a PBB is empty,
1355 don't generate code for the PBB. */
1356 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1359 /* Build the new statement and its block. */
1360 stmt = cloog_statement_alloc (pbb_index (pbb));
1361 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1362 cloog_statement_set_usr (stmt, pbb);
1364 /* Build loop list. */
1366 CloogLoop *new_loop_list = cloog_loop_malloc ();
1367 cloog_loop_set_next (new_loop_list, loop_list);
1368 cloog_loop_set_domain
1370 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1371 cloog_loop_set_block (new_loop_list, block);
1372 loop_list = new_loop_list;
1375 /* Build block list. */
1377 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1379 cloog_block_list_set_next (new_block_list, block_list);
1380 cloog_block_list_set_block (new_block_list, block);
1381 block_list = new_block_list;
1384 /* Build scattering list. */
1386 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1387 CloogDomainList *new_scattering
1388 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1389 ppl_Polyhedron_t scat;
1392 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1393 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1395 cloog_set_next_domain (new_scattering, scattering);
1396 cloog_set_domain (new_scattering, dom);
1397 scattering = new_scattering;
1401 cloog_program_set_loop (prog, loop_list);
1402 cloog_program_set_blocklist (prog, block_list);
1404 for (i = 0; i < nbs; i++)
1407 cloog_program_set_scaldims (prog, scaldims);
1409 /* Extract scalar dimensions to simplify the code generation problem. */
1410 cloog_program_extract_scalars (prog, scattering);
1412 /* Apply scattering. */
1413 cloog_program_scatter (prog, scattering);
1414 free_scattering (scattering);
1416 /* Iterators corresponding to scalar dimensions have to be extracted. */
1417 cloog_names_scalarize (cloog_program_names (prog), nbs,
1418 cloog_program_scaldims (prog));
1420 /* Free blocklist. */
1422 CloogBlockList *next = cloog_program_blocklist (prog);
1426 CloogBlockList *toDelete = next;
1427 next = cloog_block_list_next (next);
1428 cloog_block_list_set_next (toDelete, NULL);
1429 cloog_block_list_set_block (toDelete, NULL);
1430 cloog_block_list_free (toDelete);
1432 cloog_program_set_blocklist (prog, NULL);
1436 /* Return the options that will be used in GLOOG. */
1438 static CloogOptions *
1439 set_cloog_options (void)
1441 CloogOptions *options = cloog_options_malloc ();
1443 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1444 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1445 we pass an incomplete program to cloog. */
1446 options->language = LANGUAGE_C;
1448 /* Enable complex equality spreading: removes dummy statements
1449 (assignments) in the generated code which repeats the
1450 substitution equations for statements. This is useless for
1454 /* Enable C pretty-printing mode: normalizes the substitution
1455 equations for statements. */
1458 /* Allow cloog to build strides with a stride width different to one.
1459 This example has stride = 4:
1461 for (i = 0; i < 20; i += 4)
1463 options->strides = 1;
1465 /* Disable optimizations and make cloog generate source code closer to the
1466 input. This is useful for debugging, but later we want the optimized
1469 XXX: We can not disable optimizations, as loop blocking is not working
1474 options->l = INT_MAX;
1480 /* Prints STMT to STDERR. */
1483 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1485 CloogOptions *options = set_cloog_options ();
1487 pprint (file, stmt, 0, options);
1488 cloog_options_free (options);
1491 /* Prints STMT to STDERR. */
1494 debug_clast_stmt (struct clast_stmt *stmt)
1496 print_clast_stmt (stderr, stmt);
1499 /* Translate SCOP to a CLooG program and clast. These two
1500 representations should be freed together: a clast cannot be used
1501 without a program. */
1504 scop_to_clast (scop_p scop)
1506 CloogOptions *options = set_cloog_options ();
1507 cloog_prog_clast pc;
1509 /* Connect new cloog prog generation to graphite. */
1510 pc.prog = cloog_program_malloc ();
1511 build_cloog_prog (scop, pc.prog);
1512 pc.prog = cloog_program_generate (pc.prog, options);
1513 pc.stmt = cloog_clast_create (pc.prog, options);
1515 cloog_options_free (options);
1519 /* Prints to FILE the code generated by CLooG for SCOP. */
1522 print_generated_program (FILE *file, scop_p scop)
1524 CloogOptions *options = set_cloog_options ();
1525 cloog_prog_clast pc = scop_to_clast (scop);
1527 fprintf (file, " (prog: \n");
1528 cloog_program_print (file, pc.prog);
1529 fprintf (file, " )\n");
1531 fprintf (file, " (clast: \n");
1532 pprint (file, pc.stmt, 0, options);
1533 fprintf (file, " )\n");
1535 cloog_options_free (options);
1536 cloog_clast_free (pc.stmt);
1537 cloog_program_free (pc.prog);
1540 /* Prints to STDERR the code generated by CLooG for SCOP. */
1543 debug_generated_program (scop_p scop)
1545 print_generated_program (stderr, scop);
1548 /* Add CLooG names to parameter index. The index is used to translate
1549 back from CLooG names to GCC trees. */
1552 create_params_index (htab_t index_table, CloogProgram *prog) {
1553 CloogNames* names = cloog_program_names (prog);
1554 int nb_parameters = cloog_names_nb_parameters (names);
1555 char **parameters = cloog_names_parameters (names);
1558 for (i = 0; i < nb_parameters; i++)
1559 save_clast_name_index (index_table, parameters[i], i);
1562 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1563 the given SCOP. Return true if code generation succeeded.
1564 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1568 gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping)
1570 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1571 loop_p context_loop;
1572 sese region = SCOP_REGION (scop);
1573 ifsese if_region = NULL;
1574 htab_t rename_map, newivs_index, params_index;
1575 cloog_prog_clast pc;
1578 timevar_push (TV_GRAPHITE_CODE_GEN);
1579 gloog_error = false;
1581 pc = scop_to_clast (scop);
1583 if (dump_file && (dump_flags & TDF_DETAILS))
1585 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1586 print_clast_stmt (dump_file, pc.stmt);
1587 fprintf (dump_file, "\n");
1590 recompute_all_dominators ();
1593 if_region = move_sese_in_condition (region);
1594 sese_insert_phis_for_liveouts (region,
1595 if_region->region->exit->src,
1596 if_region->false_region->exit,
1597 if_region->true_region->exit);
1598 recompute_all_dominators ();
1601 context_loop = SESE_ENTRY (region)->src->loop_father;
1602 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1603 newivs_index = htab_create (10, clast_name_index_elt_info,
1604 eq_clast_name_indexes, free);
1605 params_index = htab_create (10, clast_name_index_elt_info,
1606 eq_clast_name_indexes, free);
1608 create_params_index (params_index, pc.prog);
1610 translate_clast (region, context_loop, pc.stmt,
1611 if_region->true_region->entry,
1612 rename_map, &newivs, newivs_index,
1613 bb_pbb_mapping, 1, params_index);
1615 sese_adjust_liveout_phis (region, rename_map,
1616 if_region->region->exit->src,
1617 if_region->false_region->exit,
1618 if_region->true_region->exit);
1620 rename_nb_iterations (rename_map);
1622 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1623 rename_sese_parameters (rename_map, SCOP_REGION (scop));
1625 recompute_all_dominators ();
1629 set_ifsese_condition (if_region, integer_zero_node);
1631 free (if_region->true_region);
1632 free (if_region->region);
1635 htab_delete (rename_map);
1636 htab_delete (newivs_index);
1637 htab_delete (params_index);
1638 VEC_free (tree, heap, newivs);
1639 cloog_clast_free (pc.stmt);
1640 cloog_program_free (pc.prog);
1641 timevar_pop (TV_GRAPHITE_CODE_GEN);
1643 if (dump_file && (dump_flags & TDF_DETAILS))
1647 int num_no_dependency = 0;
1649 FOR_EACH_LOOP (li, loop, 0)
1650 if (loop->can_be_parallel)
1651 num_no_dependency++;
1653 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1657 return !gloog_error;