1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009 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"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-dependences.h"
55 /* This flag is set when an error occurred during the translation of
57 static bool gloog_error;
59 /* Verifies properties that GRAPHITE should maintain during translation. */
62 graphite_verify (void)
64 #ifdef ENABLE_CHECKING
65 verify_loop_structure ();
66 verify_dominators (CDI_DOMINATORS);
67 verify_dominators (CDI_POST_DOMINATORS);
69 verify_loop_closed_ssa ();
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 maximal precision type for expressions E1 and E2. */
230 max_precision_type (tree e1, tree e2)
232 tree type1 = TREE_TYPE (e1);
233 tree type2 = TREE_TYPE (e2);
234 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
238 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
241 /* Converts a Cloog reduction expression R with reduction operation OP
242 to a GCC expression tree of type TYPE. */
245 clast_to_gcc_expression_red (tree type, enum tree_code op,
246 struct clast_reduction *r,
247 sese region, VEC (tree, heap) *newivs,
248 htab_t newivs_index, htab_t params_index)
251 tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs,
252 newivs_index, params_index);
253 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
255 for (i = 1; i < r->n; i++)
257 tree t = clast_to_gcc_expression (operand_type, r->elts[i], region,
258 newivs, newivs_index, params_index);
259 res = fold_build2 (op, type, res, t);
265 /* Converts a Cloog AST expression E back to a GCC expression tree of
269 clast_to_gcc_expression (tree type, struct clast_expr *e,
270 sese region, VEC (tree, heap) *newivs,
271 htab_t newivs_index, htab_t params_index)
277 struct clast_term *t = (struct clast_term *) e;
281 if (value_one_p (t->val))
283 tree name = clast_name_to_gcc (t->var, region, newivs,
284 newivs_index, params_index);
285 return fold_convert (type, name);
288 else if (value_mone_p (t->val))
290 tree name = clast_name_to_gcc (t->var, region, newivs,
291 newivs_index, params_index);
292 name = fold_convert (type, name);
293 return fold_build1 (NEGATE_EXPR, type, name);
297 tree name = clast_name_to_gcc (t->var, region, newivs,
298 newivs_index, params_index);
299 tree cst = gmp_cst_to_tree (type, t->val);
300 name = fold_convert (type, name);
301 if (!POINTER_TYPE_P (type))
302 return fold_build2 (MULT_EXPR, type, cst, name);
309 return gmp_cst_to_tree (type, t->val);
314 struct clast_reduction *r = (struct clast_reduction *) e;
319 return clast_to_gcc_expression_red
320 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
321 r, region, newivs, newivs_index, params_index);
324 return clast_to_gcc_expression_red (type, MIN_EXPR, r, region,
325 newivs, newivs_index,
329 return clast_to_gcc_expression_red (type, MAX_EXPR, r, region,
330 newivs, newivs_index,
341 struct clast_binary *b = (struct clast_binary *) e;
342 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
343 tree tl = clast_to_gcc_expression (type, lhs, region, newivs,
344 newivs_index, params_index);
345 tree tr = gmp_cst_to_tree (type, b->RHS);
350 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
353 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
356 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
359 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
373 /* Returns the type for the expression E. */
376 gcc_type_for_clast_expr (struct clast_expr *e,
377 sese region, VEC (tree, heap) *newivs,
378 htab_t newivs_index, htab_t params_index)
384 struct clast_term *t = (struct clast_term *) e;
387 return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
388 newivs_index, params_index));
395 struct clast_reduction *r = (struct clast_reduction *) e;
398 return gcc_type_for_clast_expr (r->elts[0], region, newivs,
399 newivs_index, params_index);
403 for (i = 0; i < r->n; i++)
405 tree type = gcc_type_for_clast_expr (r->elts[i], region,
406 newivs, newivs_index,
417 struct clast_binary *b = (struct clast_binary *) e;
418 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
419 return gcc_type_for_clast_expr (lhs, region, newivs,
420 newivs_index, params_index);
430 /* Returns the type for the equation CLEQ. */
433 gcc_type_for_clast_eq (struct clast_equation *cleq,
434 sese region, VEC (tree, heap) *newivs,
435 htab_t newivs_index, htab_t params_index)
437 tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
438 newivs_index, params_index);
442 return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index,
446 /* Translates a clast equation CLEQ to a tree. */
449 graphite_translate_clast_equation (sese region,
450 struct clast_equation *cleq,
451 VEC (tree, heap) *newivs,
452 htab_t newivs_index, htab_t params_index)
455 tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index,
457 tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs,
458 newivs_index, params_index);
459 tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs,
460 newivs_index, params_index);
465 else if (cleq->sign > 0)
471 return fold_build2 (comp, boolean_type_node, lhs, rhs);
474 /* Creates the test for the condition in STMT. */
477 graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt,
478 VEC (tree, heap) *newivs,
479 htab_t newivs_index, htab_t params_index)
484 for (i = 0; i < stmt->n; i++)
486 tree eq = graphite_translate_clast_equation (region, &stmt->eq[i],
487 newivs, newivs_index,
491 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
499 /* Creates a new if region corresponding to Cloog's guard. */
502 graphite_create_new_guard (sese region, edge entry_edge,
503 struct clast_guard *stmt,
504 VEC (tree, heap) *newivs,
505 htab_t newivs_index, htab_t params_index)
507 tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs,
508 newivs_index, params_index);
509 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
513 /* Walks a CLAST and returns the first statement in the body of a
516 static struct clast_user_stmt *
517 clast_get_body_of_loop (struct clast_stmt *stmt)
520 || CLAST_STMT_IS_A (stmt, stmt_user))
521 return (struct clast_user_stmt *) stmt;
523 if (CLAST_STMT_IS_A (stmt, stmt_for))
524 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
526 if (CLAST_STMT_IS_A (stmt, stmt_guard))
527 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
529 if (CLAST_STMT_IS_A (stmt, stmt_block))
530 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
535 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
536 If the information is not available, i.e. in the case one of the
537 transforms created the loop, just return integer_type_node. */
540 gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
542 struct ivtype_map_elt_s tmp;
545 tmp.cloog_iv = cloog_iv;
546 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
549 return ((ivtype_map_elt) *slot)->type;
551 return integer_type_node;
554 /* Returns the induction variable for the loop that gets translated to
558 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
560 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
561 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
562 const char *cloog_iv = stmt_for->iterator;
563 CloogStatement *cs = body->statement;
564 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
566 return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
569 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
570 induction variable for the new LOOP. New LOOP is attached to CFG
571 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
572 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
573 CLooG's scattering name to the induction variable created for the
574 loop of STMT. The new induction variable is inserted in the NEWIVS
578 graphite_create_new_loop (sese region, edge entry_edge,
579 struct clast_for *stmt,
580 loop_p outer, VEC (tree, heap) **newivs,
581 htab_t newivs_index, htab_t params_index)
583 tree type = gcc_type_for_iv_of_clast_loop (stmt);
584 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
585 newivs_index, params_index);
586 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
587 newivs_index, params_index);
588 tree stride = gmp_cst_to_tree (type, stmt->stride);
589 tree ivvar = create_tmp_var (type, "graphite_IV");
590 tree iv, iv_after_increment;
591 loop_p loop = create_empty_loop_on_edge
592 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
593 outer ? outer : entry_edge->src->loop_father);
595 add_referenced_var (ivvar);
597 save_clast_name_index (newivs_index, stmt->iterator,
598 VEC_length (tree, *newivs));
599 VEC_safe_push (tree, heap, *newivs, iv);
603 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
604 variables of the loops around GBB in SESE. */
607 build_iv_mapping (htab_t map, sese region,
608 VEC (tree, heap) *newivs, htab_t newivs_index,
609 struct clast_user_stmt *user_stmt,
612 struct clast_stmt *t;
614 CloogStatement *cs = user_stmt->statement;
615 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
617 for (t = user_stmt->substitutions; t; t = t->next, index++)
619 struct clast_expr *expr = (struct clast_expr *)
620 ((struct clast_assignment *)t)->RHS;
621 tree type = gcc_type_for_clast_expr (expr, region, newivs,
622 newivs_index, params_index);
623 tree old_name = pbb_to_depth_to_oldiv (pbb, index);
624 tree e = clast_to_gcc_expression (type, expr, region, newivs,
625 newivs_index, params_index);
626 set_rename (map, old_name, e);
630 /* Helper function for htab_traverse. */
633 copy_renames (void **slot, void *s)
635 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
636 htab_t res = (htab_t) s;
637 tree old_name = entry->old_name;
638 tree expr = entry->expr;
639 struct rename_map_elt_s tmp;
642 tmp.old_name = old_name;
643 x = htab_find_slot (res, &tmp, INSERT);
646 *x = new_rename_map_elt (old_name, expr);
651 /* Construct bb_pbb_def with BB and PBB. */
654 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
656 bb_pbb_def *bb_pbb_p;
658 bb_pbb_p = XNEW (bb_pbb_def);
665 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
668 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
674 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
677 *x = new_bb_pbb_def (bb, pbb);
680 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
683 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
689 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
692 return ((bb_pbb_def *) *slot)->pbb;
697 /* Check data dependency in LOOP at scattering level LEVEL.
698 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
702 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
705 basic_block *bbs = get_loop_body_in_dom_order (loop);
707 for (i = 0; i < loop->num_nodes; i++)
709 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
714 for (j = 0; j < loop->num_nodes; j++)
716 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
721 if (dependency_between_pbbs_p (pbb1, pbb2, level))
735 translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t,
736 VEC (tree, heap) **, htab_t, htab_t, int, htab_t);
738 /* Translates a clast user statement STMT to gimple.
740 - REGION is the sese region we used to generate the scop.
741 - NEXT_E is the edge where new generated code should be attached.
742 - CONTEXT_LOOP is the loop in which the generated code will be placed
743 - RENAME_MAP contains a set of tuples of new names associated to
744 the original variables names.
745 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
746 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
749 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
750 htab_t rename_map, VEC (tree, heap) **newivs,
751 htab_t newivs_index, htab_t bb_pbb_mapping,
756 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
757 gbb = PBB_BLACK_BOX (pbb);
759 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
762 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
764 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
766 new_bb = next_e->src;
767 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
768 update_ssa (TODO_update_ssa);
773 static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
776 /* Creates a new if region protecting the loop to be executed, if the execution
777 count is zero (lb > ub). */
779 graphite_create_new_loop_guard (sese region, edge entry_edge,
780 struct clast_for *stmt,
781 VEC (tree, heap) *newivs,
782 htab_t newivs_index, htab_t params_index)
786 tree type = gcc_type_for_iv_of_clast_loop (stmt);
787 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
788 newivs_index, params_index);
789 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
790 newivs_index, params_index);
792 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
793 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
794 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
795 However lb < ub + 1 is false, as expected.
796 There might be a problem with cases where ub is 2^32. */
799 value_init (gmp_one);
800 value_set_si (gmp_one, 1);
801 one = gmp_cst_to_tree (type, gmp_one);
802 value_clear (gmp_one);
804 ub = fold_build2 (PLUS_EXPR, type, ub, one);
805 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
807 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
813 /* Create the loop for a clast for statement.
815 - REGION is the sese region we used to generate the scop.
816 - NEXT_E is the edge where new generated code should be attached.
817 - RENAME_MAP contains a set of tuples of new names associated to
818 the original variables names.
819 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
820 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
823 translate_clast_for_loop (sese region, loop_p context_loop,
824 struct clast_for *stmt, edge next_e,
825 htab_t rename_map, VEC (tree, heap) **newivs,
826 htab_t newivs_index, htab_t bb_pbb_mapping,
827 int level, htab_t params_index)
829 struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
830 context_loop, newivs,
831 newivs_index, params_index);
832 edge last_e = single_exit (loop);
833 edge to_body = single_succ_edge (loop->header);
834 basic_block after = to_body->dest;
836 /* Create a basic block for loop close phi nodes. */
837 last_e = single_succ_edge (split_edge (last_e));
839 /* Translate the body of the loop. */
840 next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
841 newivs, newivs_index, bb_pbb_mapping, level + 1,
843 redirect_edge_succ_nodup (next_e, after);
844 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
846 /* Remove from rename_map all the tuples containing variables
847 defined in loop's body. */
848 insert_loop_close_phis (rename_map, loop);
850 if (flag_loop_parallelize_all
851 && !dependency_in_loop_p (loop, bb_pbb_mapping,
852 get_scattering_level (level)))
853 loop->can_be_parallel = true;
858 /* Translates a clast for statement STMT to gimple. First a guard is created
859 protecting the loop, if it is executed zero times. In this guard we create
860 the real loop structure.
862 - REGION is the sese region we used to generate the scop.
863 - NEXT_E is the edge where new generated code should be attached.
864 - RENAME_MAP contains a set of tuples of new names associated to
865 the original variables names.
866 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
867 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
870 translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt,
871 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
872 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
875 edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
876 newivs_index, params_index);
878 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
879 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
880 edge exit_true_e = single_succ_edge (true_e->dest);
881 edge exit_false_e = single_succ_edge (false_e->dest);
883 htab_t before_guard = htab_create (10, rename_map_elt_info,
884 eq_rename_map_elts, free);
885 htab_traverse (rename_map, copy_renames, before_guard);
887 next_e = translate_clast_for_loop (region, context_loop, stmt, true_e,
889 newivs_index, bb_pbb_mapping, level,
892 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
893 before_guard, rename_map);
895 htab_delete (before_guard);
900 /* Translates a clast guard statement STMT to gimple.
902 - REGION is the sese region we used to generate the scop.
903 - NEXT_E is the edge where new generated code should be attached.
904 - CONTEXT_LOOP is the loop in which the generated code will be placed
905 - RENAME_MAP contains a set of tuples of new names associated to
906 the original variables names.
907 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
908 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
911 translate_clast_guard (sese region, loop_p context_loop,
912 struct clast_guard *stmt, edge next_e,
913 htab_t rename_map, VEC (tree, heap) **newivs,
914 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
917 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
918 newivs_index, params_index);
920 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
921 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
922 edge exit_true_e = single_succ_edge (true_e->dest);
923 edge exit_false_e = single_succ_edge (false_e->dest);
925 htab_t before_guard = htab_create (10, rename_map_elt_info,
926 eq_rename_map_elts, free);
927 htab_traverse (rename_map, copy_renames, before_guard);
929 next_e = translate_clast (region, context_loop, stmt->then, true_e,
930 rename_map, newivs, newivs_index, bb_pbb_mapping,
931 level, params_index);
933 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
934 before_guard, rename_map);
936 htab_delete (before_guard);
941 /* Translates a CLAST statement STMT to GCC representation in the
944 - NEXT_E is the edge where new generated code should be attached.
945 - CONTEXT_LOOP is the loop in which the generated code will be placed
946 - RENAME_MAP contains a set of tuples of new names associated to
947 the original variables names.
948 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
950 translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
951 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
952 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
955 if (!stmt || gloog_error)
958 if (CLAST_STMT_IS_A (stmt, stmt_root))
961 else if (CLAST_STMT_IS_A (stmt, stmt_user))
962 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
963 next_e, rename_map, newivs, newivs_index,
964 bb_pbb_mapping, params_index);
966 else if (CLAST_STMT_IS_A (stmt, stmt_for))
967 next_e = translate_clast_for (region, context_loop,
968 (struct clast_for *) stmt, next_e,
969 rename_map, newivs, newivs_index,
970 bb_pbb_mapping, level, params_index);
972 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
973 next_e = translate_clast_guard (region, context_loop,
974 (struct clast_guard *) stmt, next_e,
975 rename_map, newivs, newivs_index,
976 bb_pbb_mapping, level, params_index);
978 else if (CLAST_STMT_IS_A (stmt, stmt_block))
979 next_e = translate_clast (region, context_loop,
980 ((struct clast_block *) stmt)->body,
981 next_e, rename_map, newivs, newivs_index,
982 bb_pbb_mapping, level, params_index);
986 recompute_all_dominators ();
989 return translate_clast (region, context_loop, stmt->next, next_e,
990 rename_map, newivs, newivs_index,
991 bb_pbb_mapping, level, params_index);
994 /* Returns the first cloog name used in EXPR. */
997 find_cloog_iv_in_expr (struct clast_expr *expr)
999 struct clast_term *term = (struct clast_term *) expr;
1000 struct clast_reduction *red;
1003 if (expr->type == expr_term)
1006 if (expr->type != expr_red)
1009 red = (struct clast_reduction *) expr;
1010 for (i = 0; i < red->n; i++)
1012 const char *res = find_cloog_iv_in_expr (red->elts[i]);
1021 /* Build for USER_STMT a map between the CLAST induction variables and
1022 the corresponding GCC old induction variables. This information is
1023 stored on each GRAPHITE_BB. */
1026 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1028 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1029 struct clast_stmt *t;
1032 for (t = user_stmt->substitutions; t; t = t->next, index++)
1035 struct ivtype_map_elt_s tmp;
1036 struct clast_expr *expr = (struct clast_expr *)
1037 ((struct clast_assignment *)t)->RHS;
1039 /* Create an entry (clast_var, type). */
1040 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1044 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1048 tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1049 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
1050 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1055 /* Walk the CLAST tree starting from STMT and build for each
1056 clast_user_stmt a map between the CLAST induction variables and the
1057 corresponding GCC old induction variables. This information is
1058 stored on each GRAPHITE_BB. */
1061 compute_cloog_iv_types (struct clast_stmt *stmt)
1066 if (CLAST_STMT_IS_A (stmt, stmt_root))
1069 if (CLAST_STMT_IS_A (stmt, stmt_user))
1071 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1072 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1073 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1075 if (!GBB_CLOOG_IV_TYPES (gbb))
1076 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1077 eq_ivtype_map_elts, free);
1079 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1083 if (CLAST_STMT_IS_A (stmt, stmt_for))
1085 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1086 compute_cloog_iv_types (s);
1090 if (CLAST_STMT_IS_A (stmt, stmt_guard))
1092 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1093 compute_cloog_iv_types (s);
1097 if (CLAST_STMT_IS_A (stmt, stmt_block))
1099 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1100 compute_cloog_iv_types (s);
1107 compute_cloog_iv_types (stmt->next);
1110 /* Free the SCATTERING domain list. */
1113 free_scattering (CloogDomainList *scattering)
1117 CloogDomain *dom = cloog_domain (scattering);
1118 CloogDomainList *next = cloog_next_domain (scattering);
1120 cloog_domain_free (dom);
1126 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1127 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1128 from 0 to scop_nb_loops (scop). */
1131 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1133 sese region = SCOP_REGION (scop);
1135 int nb_iterators = scop_max_loop_depth (scop);
1136 int nb_scattering = cloog_program_nb_scattdims (prog);
1137 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1138 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1139 char **scattering = XNEWVEC (char *, nb_scattering);
1140 char **parameters= XNEWVEC (char *, nb_parameters);
1142 cloog_program_set_names (prog, cloog_names_malloc ());
1144 for (i = 0; i < nb_parameters; i++)
1146 tree param = VEC_index (tree, SESE_PARAMS(region), i);
1147 const char *name = get_name (param);
1153 len = strlen (name);
1155 parameters[i] = XNEWVEC (char, len + 1);
1156 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1159 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1160 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1162 for (i = 0; i < nb_iterators; i++)
1165 iterators[i] = XNEWVEC (char, len);
1166 snprintf (iterators[i], len, "git_%d", i);
1169 cloog_names_set_nb_iterators (cloog_program_names (prog),
1171 cloog_names_set_iterators (cloog_program_names (prog),
1174 for (i = 0; i < nb_scattering; i++)
1177 scattering[i] = XNEWVEC (char, len);
1178 snprintf (scattering[i], len, "scat_%d", i);
1181 cloog_names_set_nb_scattering (cloog_program_names (prog),
1183 cloog_names_set_scattering (cloog_program_names (prog),
1187 /* Build cloog program for SCoP. */
1190 build_cloog_prog (scop_p scop, CloogProgram *prog)
1193 int max_nb_loops = scop_max_loop_depth (scop);
1195 CloogLoop *loop_list = NULL;
1196 CloogBlockList *block_list = NULL;
1197 CloogDomainList *scattering = NULL;
1198 int nbs = 2 * max_nb_loops + 1;
1201 cloog_program_set_context
1202 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1203 nbs = unify_scattering_dimensions (scop);
1204 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1205 cloog_program_set_nb_scattdims (prog, nbs);
1206 initialize_cloog_names (scop, prog);
1208 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1210 CloogStatement *stmt;
1213 /* Dead code elimination: when the domain of a PBB is empty,
1214 don't generate code for the PBB. */
1215 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1218 /* Build the new statement and its block. */
1219 stmt = cloog_statement_alloc (pbb_index (pbb));
1220 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1221 cloog_statement_set_usr (stmt, pbb);
1223 /* Build loop list. */
1225 CloogLoop *new_loop_list = cloog_loop_malloc ();
1226 cloog_loop_set_next (new_loop_list, loop_list);
1227 cloog_loop_set_domain
1229 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1230 cloog_loop_set_block (new_loop_list, block);
1231 loop_list = new_loop_list;
1234 /* Build block list. */
1236 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1238 cloog_block_list_set_next (new_block_list, block_list);
1239 cloog_block_list_set_block (new_block_list, block);
1240 block_list = new_block_list;
1243 /* Build scattering list. */
1245 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1246 CloogDomainList *new_scattering
1247 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1248 ppl_Polyhedron_t scat;
1251 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1252 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1254 cloog_set_next_domain (new_scattering, scattering);
1255 cloog_set_domain (new_scattering, dom);
1256 scattering = new_scattering;
1260 cloog_program_set_loop (prog, loop_list);
1261 cloog_program_set_blocklist (prog, block_list);
1263 for (i = 0; i < nbs; i++)
1266 cloog_program_set_scaldims (prog, scaldims);
1268 /* Extract scalar dimensions to simplify the code generation problem. */
1269 cloog_program_extract_scalars (prog, scattering);
1271 /* Apply scattering. */
1272 cloog_program_scatter (prog, scattering);
1273 free_scattering (scattering);
1275 /* Iterators corresponding to scalar dimensions have to be extracted. */
1276 cloog_names_scalarize (cloog_program_names (prog), nbs,
1277 cloog_program_scaldims (prog));
1279 /* Free blocklist. */
1281 CloogBlockList *next = cloog_program_blocklist (prog);
1285 CloogBlockList *toDelete = next;
1286 next = cloog_block_list_next (next);
1287 cloog_block_list_set_next (toDelete, NULL);
1288 cloog_block_list_set_block (toDelete, NULL);
1289 cloog_block_list_free (toDelete);
1291 cloog_program_set_blocklist (prog, NULL);
1295 /* Return the options that will be used in GLOOG. */
1297 static CloogOptions *
1298 set_cloog_options (void)
1300 CloogOptions *options = cloog_options_malloc ();
1302 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1303 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1304 we pass an incomplete program to cloog. */
1305 options->language = LANGUAGE_C;
1307 /* Enable complex equality spreading: removes dummy statements
1308 (assignments) in the generated code which repeats the
1309 substitution equations for statements. This is useless for
1313 /* Enable C pretty-printing mode: normalizes the substitution
1314 equations for statements. */
1317 /* Allow cloog to build strides with a stride width different to one.
1318 This example has stride = 4:
1320 for (i = 0; i < 20; i += 4)
1322 options->strides = 1;
1324 /* Disable optimizations and make cloog generate source code closer to the
1325 input. This is useful for debugging, but later we want the optimized
1328 XXX: We can not disable optimizations, as loop blocking is not working
1333 options->l = INT_MAX;
1339 /* Prints STMT to STDERR. */
1342 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1344 CloogOptions *options = set_cloog_options ();
1346 pprint (file, stmt, 0, options);
1347 cloog_options_free (options);
1350 /* Prints STMT to STDERR. */
1353 debug_clast_stmt (struct clast_stmt *stmt)
1355 print_clast_stmt (stderr, stmt);
1358 /* Translate SCOP to a CLooG program and clast. These two
1359 representations should be freed together: a clast cannot be used
1360 without a program. */
1363 scop_to_clast (scop_p scop)
1365 CloogOptions *options = set_cloog_options ();
1366 cloog_prog_clast pc;
1368 /* Connect new cloog prog generation to graphite. */
1369 pc.prog = cloog_program_malloc ();
1370 build_cloog_prog (scop, pc.prog);
1371 pc.prog = cloog_program_generate (pc.prog, options);
1372 pc.stmt = cloog_clast_create (pc.prog, options);
1374 cloog_options_free (options);
1378 /* Prints to FILE the code generated by CLooG for SCOP. */
1381 print_generated_program (FILE *file, scop_p scop)
1383 CloogOptions *options = set_cloog_options ();
1384 cloog_prog_clast pc = scop_to_clast (scop);
1386 fprintf (file, " (prog: \n");
1387 cloog_program_print (file, pc.prog);
1388 fprintf (file, " )\n");
1390 fprintf (file, " (clast: \n");
1391 pprint (file, pc.stmt, 0, options);
1392 fprintf (file, " )\n");
1394 cloog_options_free (options);
1395 cloog_clast_free (pc.stmt);
1396 cloog_program_free (pc.prog);
1399 /* Prints to STDERR the code generated by CLooG for SCOP. */
1402 debug_generated_program (scop_p scop)
1404 print_generated_program (stderr, scop);
1407 /* Add CLooG names to parameter index. The index is used to translate
1408 back from CLooG names to GCC trees. */
1411 create_params_index (htab_t index_table, CloogProgram *prog) {
1412 CloogNames* names = cloog_program_names (prog);
1413 int nb_parameters = cloog_names_nb_parameters (names);
1414 char **parameters = cloog_names_parameters (names);
1417 for (i = 0; i < nb_parameters; i++)
1418 save_clast_name_index (index_table, parameters[i], i);
1421 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1422 the given SCOP. Return true if code generation succeeded.
1423 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1427 gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping)
1429 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1430 loop_p context_loop;
1431 sese region = SCOP_REGION (scop);
1432 ifsese if_region = NULL;
1433 htab_t rename_map, newivs_index, params_index;
1434 cloog_prog_clast pc;
1437 timevar_push (TV_GRAPHITE_CODE_GEN);
1438 gloog_error = false;
1440 pc = scop_to_clast (scop);
1442 if (dump_file && (dump_flags & TDF_DETAILS))
1444 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1445 print_clast_stmt (dump_file, pc.stmt);
1446 fprintf (dump_file, "\n");
1449 recompute_all_dominators ();
1452 if_region = move_sese_in_condition (region);
1453 sese_insert_phis_for_liveouts (region,
1454 if_region->region->exit->src,
1455 if_region->false_region->exit,
1456 if_region->true_region->exit);
1457 recompute_all_dominators ();
1460 context_loop = SESE_ENTRY (region)->src->loop_father;
1461 compute_cloog_iv_types (pc.stmt);
1462 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1463 newivs_index = htab_create (10, clast_name_index_elt_info,
1464 eq_clast_name_indexes, free);
1465 params_index = htab_create (10, clast_name_index_elt_info,
1466 eq_clast_name_indexes, free);
1468 create_params_index (params_index, pc.prog);
1470 translate_clast (region, context_loop, pc.stmt,
1471 if_region->true_region->entry,
1472 rename_map, &newivs, newivs_index,
1473 bb_pbb_mapping, 1, params_index);
1475 sese_adjust_liveout_phis (region, rename_map,
1476 if_region->region->exit->src,
1477 if_region->false_region->exit,
1478 if_region->true_region->exit);
1480 rename_nb_iterations (rename_map);
1482 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1483 rename_sese_parameters (rename_map, SCOP_REGION (scop));
1485 recompute_all_dominators ();
1489 set_ifsese_condition (if_region, integer_zero_node);
1491 free (if_region->true_region);
1492 free (if_region->region);
1495 htab_delete (rename_map);
1496 htab_delete (newivs_index);
1497 htab_delete (params_index);
1498 VEC_free (tree, heap, newivs);
1499 cloog_clast_free (pc.stmt);
1500 cloog_program_free (pc.prog);
1501 timevar_pop (TV_GRAPHITE_CODE_GEN);
1503 if (dump_file && (dump_flags & TDF_DETAILS))
1507 int num_no_dependency = 0;
1509 FOR_EACH_LOOP (li, loop, 0)
1510 if (loop->can_be_parallel)
1511 num_no_dependency++;
1513 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1517 return !gloog_error;