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;
1001 if (expr->type == expr_term
1005 if (expr->type == expr_term)
1008 if (expr->type == expr_red)
1011 struct clast_reduction *red = (struct clast_reduction *) expr;
1013 for (i = 0; i < red->n; i++)
1015 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
1025 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
1026 induction variables and the corresponding GCC old induction
1027 variables. This information is stored on each GRAPHITE_BB. */
1030 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1032 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1033 struct clast_stmt *t;
1036 for (t = user_stmt->substitutions; t; t = t->next, index++)
1039 struct ivtype_map_elt_s tmp;
1040 struct clast_expr *expr = (struct clast_expr *)
1041 ((struct clast_assignment *)t)->RHS;
1043 /* Create an entry (clast_var, type). */
1044 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1048 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1052 tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1053 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
1054 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1059 /* Walk the CLAST tree starting from STMT and build for each
1060 clast_user_stmt a map between the CLAST induction variables and the
1061 corresponding GCC old induction variables. This information is
1062 stored on each GRAPHITE_BB. */
1065 compute_cloog_iv_types (struct clast_stmt *stmt)
1070 if (CLAST_STMT_IS_A (stmt, stmt_root))
1073 if (CLAST_STMT_IS_A (stmt, stmt_user))
1075 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1076 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1077 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1079 if (!GBB_CLOOG_IV_TYPES (gbb))
1080 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1081 eq_ivtype_map_elts, free);
1083 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1087 if (CLAST_STMT_IS_A (stmt, stmt_for))
1089 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1090 compute_cloog_iv_types (s);
1094 if (CLAST_STMT_IS_A (stmt, stmt_guard))
1096 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1097 compute_cloog_iv_types (s);
1101 if (CLAST_STMT_IS_A (stmt, stmt_block))
1103 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1104 compute_cloog_iv_types (s);
1111 compute_cloog_iv_types (stmt->next);
1114 /* Free the SCATTERING domain list. */
1117 free_scattering (CloogDomainList *scattering)
1121 CloogDomain *dom = cloog_domain (scattering);
1122 CloogDomainList *next = cloog_next_domain (scattering);
1124 cloog_domain_free (dom);
1130 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1131 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1132 from 0 to scop_nb_loops (scop). */
1135 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1137 sese region = SCOP_REGION (scop);
1139 int nb_iterators = scop_max_loop_depth (scop);
1140 int nb_scattering = cloog_program_nb_scattdims (prog);
1141 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1142 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1143 char **scattering = XNEWVEC (char *, nb_scattering);
1144 char **parameters= XNEWVEC (char *, nb_parameters);
1146 cloog_program_set_names (prog, cloog_names_malloc ());
1148 for (i = 0; i < nb_parameters; i++)
1150 tree param = VEC_index (tree, SESE_PARAMS(region), i);
1151 const char *name = get_name (param);
1157 len = strlen (name);
1159 parameters[i] = XNEWVEC (char, len + 1);
1160 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1163 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1164 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1166 for (i = 0; i < nb_iterators; i++)
1169 iterators[i] = XNEWVEC (char, len);
1170 snprintf (iterators[i], len, "git_%d", i);
1173 cloog_names_set_nb_iterators (cloog_program_names (prog),
1175 cloog_names_set_iterators (cloog_program_names (prog),
1178 for (i = 0; i < nb_scattering; i++)
1181 scattering[i] = XNEWVEC (char, len);
1182 snprintf (scattering[i], len, "scat_%d", i);
1185 cloog_names_set_nb_scattering (cloog_program_names (prog),
1187 cloog_names_set_scattering (cloog_program_names (prog),
1191 /* Build cloog program for SCoP. */
1194 build_cloog_prog (scop_p scop, CloogProgram *prog)
1197 int max_nb_loops = scop_max_loop_depth (scop);
1199 CloogLoop *loop_list = NULL;
1200 CloogBlockList *block_list = NULL;
1201 CloogDomainList *scattering = NULL;
1202 int nbs = 2 * max_nb_loops + 1;
1205 cloog_program_set_context
1206 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1207 nbs = unify_scattering_dimensions (scop);
1208 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1209 cloog_program_set_nb_scattdims (prog, nbs);
1210 initialize_cloog_names (scop, prog);
1212 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1214 CloogStatement *stmt;
1217 /* Dead code elimination: when the domain of a PBB is empty,
1218 don't generate code for the PBB. */
1219 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1222 /* Build the new statement and its block. */
1223 stmt = cloog_statement_alloc (pbb_index (pbb));
1224 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1225 cloog_statement_set_usr (stmt, pbb);
1227 /* Build loop list. */
1229 CloogLoop *new_loop_list = cloog_loop_malloc ();
1230 cloog_loop_set_next (new_loop_list, loop_list);
1231 cloog_loop_set_domain
1233 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1234 cloog_loop_set_block (new_loop_list, block);
1235 loop_list = new_loop_list;
1238 /* Build block list. */
1240 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1242 cloog_block_list_set_next (new_block_list, block_list);
1243 cloog_block_list_set_block (new_block_list, block);
1244 block_list = new_block_list;
1247 /* Build scattering list. */
1249 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1250 CloogDomainList *new_scattering
1251 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1252 ppl_Polyhedron_t scat;
1255 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1256 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1258 cloog_set_next_domain (new_scattering, scattering);
1259 cloog_set_domain (new_scattering, dom);
1260 scattering = new_scattering;
1264 cloog_program_set_loop (prog, loop_list);
1265 cloog_program_set_blocklist (prog, block_list);
1267 for (i = 0; i < nbs; i++)
1270 cloog_program_set_scaldims (prog, scaldims);
1272 /* Extract scalar dimensions to simplify the code generation problem. */
1273 cloog_program_extract_scalars (prog, scattering);
1275 /* Apply scattering. */
1276 cloog_program_scatter (prog, scattering);
1277 free_scattering (scattering);
1279 /* Iterators corresponding to scalar dimensions have to be extracted. */
1280 cloog_names_scalarize (cloog_program_names (prog), nbs,
1281 cloog_program_scaldims (prog));
1283 /* Free blocklist. */
1285 CloogBlockList *next = cloog_program_blocklist (prog);
1289 CloogBlockList *toDelete = next;
1290 next = cloog_block_list_next (next);
1291 cloog_block_list_set_next (toDelete, NULL);
1292 cloog_block_list_set_block (toDelete, NULL);
1293 cloog_block_list_free (toDelete);
1295 cloog_program_set_blocklist (prog, NULL);
1299 /* Return the options that will be used in GLOOG. */
1301 static CloogOptions *
1302 set_cloog_options (void)
1304 CloogOptions *options = cloog_options_malloc ();
1306 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1307 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1308 we pass an incomplete program to cloog. */
1309 options->language = LANGUAGE_C;
1311 /* Enable complex equality spreading: removes dummy statements
1312 (assignments) in the generated code which repeats the
1313 substitution equations for statements. This is useless for
1317 /* Enable C pretty-printing mode: normalizes the substitution
1318 equations for statements. */
1321 /* Allow cloog to build strides with a stride width different to one.
1322 This example has stride = 4:
1324 for (i = 0; i < 20; i += 4)
1326 options->strides = 1;
1328 /* Disable optimizations and make cloog generate source code closer to the
1329 input. This is useful for debugging, but later we want the optimized
1332 XXX: We can not disable optimizations, as loop blocking is not working
1337 options->l = INT_MAX;
1343 /* Prints STMT to STDERR. */
1346 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1348 CloogOptions *options = set_cloog_options ();
1350 pprint (file, stmt, 0, options);
1351 cloog_options_free (options);
1354 /* Prints STMT to STDERR. */
1357 debug_clast_stmt (struct clast_stmt *stmt)
1359 print_clast_stmt (stderr, stmt);
1362 /* Translate SCOP to a CLooG program and clast. These two
1363 representations should be freed together: a clast cannot be used
1364 without a program. */
1367 scop_to_clast (scop_p scop)
1369 CloogOptions *options = set_cloog_options ();
1370 cloog_prog_clast pc;
1372 /* Connect new cloog prog generation to graphite. */
1373 pc.prog = cloog_program_malloc ();
1374 build_cloog_prog (scop, pc.prog);
1375 pc.prog = cloog_program_generate (pc.prog, options);
1376 pc.stmt = cloog_clast_create (pc.prog, options);
1378 cloog_options_free (options);
1382 /* Prints to FILE the code generated by CLooG for SCOP. */
1385 print_generated_program (FILE *file, scop_p scop)
1387 CloogOptions *options = set_cloog_options ();
1388 cloog_prog_clast pc = scop_to_clast (scop);
1390 fprintf (file, " (prog: \n");
1391 cloog_program_print (file, pc.prog);
1392 fprintf (file, " )\n");
1394 fprintf (file, " (clast: \n");
1395 pprint (file, pc.stmt, 0, options);
1396 fprintf (file, " )\n");
1398 cloog_options_free (options);
1399 cloog_clast_free (pc.stmt);
1400 cloog_program_free (pc.prog);
1403 /* Prints to STDERR the code generated by CLooG for SCOP. */
1406 debug_generated_program (scop_p scop)
1408 print_generated_program (stderr, scop);
1411 /* Add CLooG names to parameter index. The index is used to translate
1412 back from CLooG names to GCC trees. */
1415 create_params_index (htab_t index_table, CloogProgram *prog) {
1416 CloogNames* names = cloog_program_names (prog);
1417 int nb_parameters = cloog_names_nb_parameters (names);
1418 char **parameters = cloog_names_parameters (names);
1421 for (i = 0; i < nb_parameters; i++)
1422 save_clast_name_index (index_table, parameters[i], i);
1425 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1426 the given SCOP. Return true if code generation succeeded.
1427 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1431 gloog (scop_p scop, htab_t bb_pbb_mapping)
1433 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1434 loop_p context_loop;
1435 sese region = SCOP_REGION (scop);
1436 ifsese if_region = NULL;
1437 htab_t rename_map, newivs_index, params_index;
1438 cloog_prog_clast pc;
1440 timevar_push (TV_GRAPHITE_CODE_GEN);
1441 gloog_error = false;
1443 pc = scop_to_clast (scop);
1445 if (dump_file && (dump_flags & TDF_DETAILS))
1447 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1448 print_clast_stmt (dump_file, pc.stmt);
1449 fprintf (dump_file, "\n");
1452 recompute_all_dominators ();
1455 if_region = move_sese_in_condition (region);
1456 sese_insert_phis_for_liveouts (region,
1457 if_region->region->exit->src,
1458 if_region->false_region->exit,
1459 if_region->true_region->exit);
1460 recompute_all_dominators ();
1463 context_loop = SESE_ENTRY (region)->src->loop_father;
1464 compute_cloog_iv_types (pc.stmt);
1465 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1466 newivs_index = htab_create (10, clast_name_index_elt_info,
1467 eq_clast_name_indexes, free);
1468 params_index = htab_create (10, clast_name_index_elt_info,
1469 eq_clast_name_indexes, free);
1471 create_params_index (params_index, pc.prog);
1473 translate_clast (region, context_loop, pc.stmt,
1474 if_region->true_region->entry,
1475 rename_map, &newivs, newivs_index,
1476 bb_pbb_mapping, 1, params_index);
1478 sese_adjust_liveout_phis (region, rename_map,
1479 if_region->region->exit->src,
1480 if_region->false_region->exit,
1481 if_region->true_region->exit);
1483 rename_nb_iterations (rename_map);
1484 recompute_all_dominators ();
1488 set_ifsese_condition (if_region, integer_zero_node);
1490 free (if_region->true_region);
1491 free (if_region->region);
1494 htab_delete (rename_map);
1495 htab_delete (newivs_index);
1496 htab_delete (params_index);
1497 VEC_free (tree, heap, newivs);
1498 cloog_clast_free (pc.stmt);
1499 cloog_program_free (pc.prog);
1500 timevar_pop (TV_GRAPHITE_CODE_GEN);
1502 if (dump_file && (dump_flags & TDF_DETAILS))
1506 int num_no_dependency = 0;
1508 FOR_EACH_LOOP (li, loop, 0)
1509 if (loop->can_be_parallel)
1510 num_no_dependency++;
1512 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1516 return !gloog_error;