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 /* Verifies properties that GRAPHITE should maintain during translation. */
58 graphite_verify (void)
60 #ifdef ENABLE_CHECKING
61 verify_loop_structure ();
62 verify_dominators (CDI_DOMINATORS);
63 verify_dominators (CDI_POST_DOMINATORS);
65 verify_loop_closed_ssa ();
69 /* Stores the INDEX in a vector for a given clast NAME. */
71 typedef struct clast_name_index {
74 } *clast_name_index_p;
76 /* Returns a pointer to a new element of type clast_name_index_p built
77 from NAME and INDEX. */
79 static inline clast_name_index_p
80 new_clast_name_index (const char *name, int index)
82 clast_name_index_p res = XNEW (struct clast_name_index);
89 /* For a given clast NAME, returns -1 if it does not correspond to any
90 parameter, or otherwise, returns the index in the PARAMS or
91 SCATTERING_DIMENSIONS vector. */
94 clast_name_to_index (const char *name, htab_t index_table)
96 struct clast_name_index tmp;
100 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
103 return ((struct clast_name_index *) *slot)->index;
108 /* Records in INDEX_TABLE the INDEX for NAME. */
111 save_clast_name_index (htab_t index_table, const char *name, int index)
113 struct clast_name_index tmp;
117 slot = htab_find_slot (index_table, &tmp, INSERT);
124 *slot = new_clast_name_index (name, index);
128 /* Print to stderr the element ELT. */
131 debug_clast_name_index (clast_name_index_p elt)
133 fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name);
136 /* Helper function for debug_rename_map. */
139 debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED)
141 struct clast_name_index *entry = (struct clast_name_index *) *slot;
142 debug_clast_name_index (entry);
146 /* Print to stderr all the elements of MAP. */
149 debug_clast_name_indexes (htab_t map)
151 htab_traverse (map, debug_clast_name_indexes_1, NULL);
154 /* Computes a hash function for database element ELT. */
156 static inline hashval_t
157 clast_name_index_elt_info (const void *elt)
159 return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
162 /* Compares database elements E1 and E2. */
165 eq_clast_name_indexes (const void *e1, const void *e2)
167 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
168 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
170 return (elt1->name == elt2->name);
174 /* For a given loop DEPTH in the loop nest of the original black box
175 PBB, return the old induction variable associated to that loop. */
178 pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth)
180 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
181 sese region = SCOP_REGION (PBB_SCOP (pbb));
182 loop_p loop = gbb_loop_at_index (gbb, region, depth);
184 return loop->single_iv;
187 /* For a given scattering dimension, return the new induction variable
191 newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth)
193 return VEC_index (tree, newivs, depth);
198 /* Returns the tree variable from the name NAME that was given in
199 Cloog representation. */
202 clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs,
203 htab_t newivs_index, htab_t params_index)
206 VEC (tree, heap) *params = SESE_PARAMS (region);
208 if (params && params_index)
210 index = clast_name_to_index (name, params_index);
213 return VEC_index (tree, params, index);
216 gcc_assert (newivs && newivs_index);
217 index = clast_name_to_index (name, newivs_index);
218 gcc_assert (index >= 0);
220 return newivs_to_depth_to_newiv (newivs, index);
223 /* Returns the maximal precision type for expressions E1 and E2. */
226 max_precision_type (tree e1, tree e2)
228 tree type1 = TREE_TYPE (e1);
229 tree type2 = TREE_TYPE (e2);
230 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
234 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
237 /* Converts a Cloog reduction expression R with reduction operation OP
238 to a GCC expression tree of type TYPE. */
241 clast_to_gcc_expression_red (tree type, enum tree_code op,
242 struct clast_reduction *r,
243 sese region, VEC (tree, heap) *newivs,
244 htab_t newivs_index, htab_t params_index)
247 tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs,
248 newivs_index, params_index);
249 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
251 for (i = 1; i < r->n; i++)
253 tree t = clast_to_gcc_expression (operand_type, r->elts[i], region,
254 newivs, newivs_index, params_index);
255 res = fold_build2 (op, type, res, t);
261 /* Converts a Cloog AST expression E back to a GCC expression tree of
265 clast_to_gcc_expression (tree type, struct clast_expr *e,
266 sese region, VEC (tree, heap) *newivs,
267 htab_t newivs_index, htab_t params_index)
273 struct clast_term *t = (struct clast_term *) e;
277 if (value_one_p (t->val))
279 tree name = clast_name_to_gcc (t->var, region, newivs,
280 newivs_index, params_index);
281 return fold_convert (type, name);
284 else if (value_mone_p (t->val))
286 tree name = clast_name_to_gcc (t->var, region, newivs,
287 newivs_index, params_index);
288 name = fold_convert (type, name);
289 return fold_build1 (NEGATE_EXPR, type, name);
293 tree name = clast_name_to_gcc (t->var, region, newivs,
294 newivs_index, params_index);
295 tree cst = gmp_cst_to_tree (type, t->val);
296 name = fold_convert (type, name);
297 return fold_build2 (MULT_EXPR, type, cst, name);
301 return gmp_cst_to_tree (type, t->val);
306 struct clast_reduction *r = (struct clast_reduction *) e;
311 return clast_to_gcc_expression_red
312 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
313 r, region, newivs, newivs_index, params_index);
316 return clast_to_gcc_expression_red (type, MIN_EXPR, r, region,
317 newivs, newivs_index,
321 return clast_to_gcc_expression_red (type, MAX_EXPR, r, region,
322 newivs, newivs_index,
333 struct clast_binary *b = (struct clast_binary *) e;
334 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
335 tree tl = clast_to_gcc_expression (type, lhs, region, newivs,
336 newivs_index, params_index);
337 tree tr = gmp_cst_to_tree (type, b->RHS);
342 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
345 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
348 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
351 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
365 /* Returns the type for the expression E. */
368 gcc_type_for_clast_expr (struct clast_expr *e,
369 sese region, VEC (tree, heap) *newivs,
370 htab_t newivs_index, htab_t params_index)
376 struct clast_term *t = (struct clast_term *) e;
379 return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
380 newivs_index, params_index));
387 struct clast_reduction *r = (struct clast_reduction *) e;
390 return gcc_type_for_clast_expr (r->elts[0], region, newivs,
391 newivs_index, params_index);
395 for (i = 0; i < r->n; i++)
397 tree type = gcc_type_for_clast_expr (r->elts[i], region,
398 newivs, newivs_index,
409 struct clast_binary *b = (struct clast_binary *) e;
410 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
411 return gcc_type_for_clast_expr (lhs, region, newivs,
412 newivs_index, params_index);
422 /* Returns the type for the equation CLEQ. */
425 gcc_type_for_clast_eq (struct clast_equation *cleq,
426 sese region, VEC (tree, heap) *newivs,
427 htab_t newivs_index, htab_t params_index)
429 tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
430 newivs_index, params_index);
434 return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index,
438 /* Translates a clast equation CLEQ to a tree. */
441 graphite_translate_clast_equation (sese region,
442 struct clast_equation *cleq,
443 VEC (tree, heap) *newivs,
444 htab_t newivs_index, htab_t params_index)
447 tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index,
449 tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs,
450 newivs_index, params_index);
451 tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs,
452 newivs_index, params_index);
457 else if (cleq->sign > 0)
463 return fold_build2 (comp, boolean_type_node, lhs, rhs);
466 /* Creates the test for the condition in STMT. */
469 graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt,
470 VEC (tree, heap) *newivs,
471 htab_t newivs_index, htab_t params_index)
476 for (i = 0; i < stmt->n; i++)
478 tree eq = graphite_translate_clast_equation (region, &stmt->eq[i],
479 newivs, newivs_index,
483 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
491 /* Creates a new if region corresponding to Cloog's guard. */
494 graphite_create_new_guard (sese region, edge entry_edge,
495 struct clast_guard *stmt,
496 VEC (tree, heap) *newivs,
497 htab_t newivs_index, htab_t params_index)
499 tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs,
500 newivs_index, params_index);
501 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
505 /* Walks a CLAST and returns the first statement in the body of a
508 static struct clast_user_stmt *
509 clast_get_body_of_loop (struct clast_stmt *stmt)
512 || CLAST_STMT_IS_A (stmt, stmt_user))
513 return (struct clast_user_stmt *) stmt;
515 if (CLAST_STMT_IS_A (stmt, stmt_for))
516 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
518 if (CLAST_STMT_IS_A (stmt, stmt_guard))
519 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
521 if (CLAST_STMT_IS_A (stmt, stmt_block))
522 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
527 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
528 If the information is not available, i.e. in the case one of the
529 transforms created the loop, just return integer_type_node. */
532 gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
534 struct ivtype_map_elt_s tmp;
537 tmp.cloog_iv = cloog_iv;
538 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
541 return ((ivtype_map_elt) *slot)->type;
543 return integer_type_node;
546 /* Returns the induction variable for the loop that gets translated to
550 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
552 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
553 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
554 const char *cloog_iv = stmt_for->iterator;
555 CloogStatement *cs = body->statement;
556 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
558 return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
561 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
562 induction variable for the new LOOP. New LOOP is attached to CFG
563 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
564 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
565 CLooG's scattering name to the induction variable created for the
566 loop of STMT. The new induction variable is inserted in the NEWIVS
570 graphite_create_new_loop (sese region, edge entry_edge,
571 struct clast_for *stmt,
572 loop_p outer, VEC (tree, heap) **newivs,
573 htab_t newivs_index, htab_t params_index)
575 tree type = gcc_type_for_iv_of_clast_loop (stmt);
576 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
577 newivs_index, params_index);
578 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
579 newivs_index, params_index);
580 tree stride = gmp_cst_to_tree (type, stmt->stride);
581 tree ivvar = create_tmp_var (type, "graphite_IV");
582 tree iv, iv_after_increment;
583 loop_p loop = create_empty_loop_on_edge
584 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
585 outer ? outer : entry_edge->src->loop_father);
587 add_referenced_var (ivvar);
589 save_clast_name_index (newivs_index, stmt->iterator,
590 VEC_length (tree, *newivs));
591 VEC_safe_push (tree, heap, *newivs, iv);
595 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
596 variables of the loops around GBB in SESE. */
599 build_iv_mapping (htab_t map, sese region,
600 VEC (tree, heap) *newivs, htab_t newivs_index,
601 struct clast_user_stmt *user_stmt,
604 struct clast_stmt *t;
606 CloogStatement *cs = user_stmt->statement;
607 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
609 for (t = user_stmt->substitutions; t; t = t->next, index++)
611 struct clast_expr *expr = (struct clast_expr *)
612 ((struct clast_assignment *)t)->RHS;
613 tree type = gcc_type_for_clast_expr (expr, region, newivs,
614 newivs_index, params_index);
615 tree old_name = pbb_to_depth_to_oldiv (pbb, index);
616 tree e = clast_to_gcc_expression (type, expr, region, newivs,
617 newivs_index, params_index);
618 set_rename (map, old_name, e);
622 /* Helper function for htab_traverse. */
625 copy_renames (void **slot, void *s)
627 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
628 htab_t res = (htab_t) s;
629 tree old_name = entry->old_name;
630 tree expr = entry->expr;
631 struct rename_map_elt_s tmp;
634 tmp.old_name = old_name;
635 x = htab_find_slot (res, &tmp, INSERT);
638 *x = new_rename_map_elt (old_name, expr);
643 /* Construct bb_pbb_def with BB and PBB. */
646 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
648 bb_pbb_def *bb_pbb_p;
650 bb_pbb_p = XNEW (bb_pbb_def);
657 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
660 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
666 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
669 *x = new_bb_pbb_def (bb, pbb);
672 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
675 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
681 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
684 return ((bb_pbb_def *) *slot)->pbb;
689 /* Check data dependency in LOOP at scattering level LEVEL.
690 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
694 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
697 basic_block *bbs = get_loop_body_in_dom_order (loop);
699 for (i = 0; i < loop->num_nodes; i++)
701 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
706 for (j = 0; j < loop->num_nodes; j++)
708 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
713 if (dependency_between_pbbs_p (pbb1, pbb2, level))
727 translate_clast (sese, struct clast_stmt *, edge, htab_t, VEC (tree, heap) **,
728 htab_t, htab_t, htab_t);
730 /* Translates a clast user statement STMT to gimple.
732 - REGION is the sese region we used to generate the scop.
733 - NEXT_E is the edge where new generated code should be attached.
734 - RENAME_MAP contains a set of tuples of new names associated to
735 the original variables names.
736 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
737 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
740 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
741 htab_t rename_map, VEC (tree, heap) **newivs,
742 htab_t newivs_index, htab_t bb_pbb_mapping,
745 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
746 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
748 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
751 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
753 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
755 mark_bb_with_pbb (pbb, next_e->src, bb_pbb_mapping);
756 update_ssa (TODO_update_ssa);
761 /* Mark a loop parallel, if the graphite dependency check cannot find any
762 dependencies. This triggers parallel code generation in the autopar pass.
765 try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping)
767 loop_p outermost_loop = SESE_ENTRY (region)->src->loop_father;
768 int level = loop_depth (loop) - loop_depth (outermost_loop);
770 if (flag_loop_parallelize_all
771 && !dependency_in_loop_p (loop, bb_pbb_mapping,
772 get_scattering_level (level)))
773 loop->can_be_parallel = true;
776 static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
779 /* Creates a new if region protecting the loop to be executed, if the execution
780 count is zero (lb > ub). */
782 graphite_create_new_loop_guard (sese region, edge entry_edge,
783 struct clast_for *stmt,
784 VEC (tree, heap) *newivs,
785 htab_t newivs_index, htab_t params_index)
789 tree type = gcc_type_for_iv_of_clast_loop (stmt);
790 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
791 newivs_index, params_index);
792 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
793 newivs_index, params_index);
795 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
796 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
797 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
798 However lb < ub + 1 is false, as expected.
799 There might be a problem with cases where ub is 2^32. */
802 value_init (gmp_one);
803 value_set_si (gmp_one, 1);
804 one = gmp_cst_to_tree (type, gmp_one);
805 value_clear (gmp_one);
807 ub = fold_build2 (PLUS_EXPR, type, ub, one);
808 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
810 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
816 /* Create the loop for a clast for statement.
818 - REGION is the sese region we used to generate the scop.
819 - NEXT_E is the edge where new generated code should be attached.
820 - RENAME_MAP contains a set of tuples of new names associated to
821 the original variables names.
822 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
823 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
826 translate_clast_for_loop (sese region, struct clast_for *stmt, edge next_e,
827 htab_t rename_map, VEC (tree, heap) **newivs,
828 htab_t newivs_index, htab_t bb_pbb_mapping,
831 loop_p context_loop = next_e->dest->loop_father;
832 loop_p loop = graphite_create_new_loop (region, next_e, stmt, context_loop,
833 newivs, newivs_index, params_index);
834 edge last_e = single_exit (loop);
835 edge body = single_succ_edge (loop->header);
837 next_e = translate_clast (region, stmt->body, body, rename_map, newivs,
838 newivs_index, bb_pbb_mapping, params_index);
840 /* Create a basic block for loop close phi nodes. */
841 last_e = single_succ_edge (split_edge (last_e));
842 insert_loop_close_phis (rename_map, loop);
844 try_mark_loop_parallel (region, loop, bb_pbb_mapping);
849 /* Translates a clast for statement STMT to gimple. First a guard is created
850 protecting the loop, if it is executed zero times. In this guard we create
851 the real loop structure.
853 - REGION is the sese region we used to generate the scop.
854 - NEXT_E is the edge where new generated code should be attached.
855 - RENAME_MAP contains a set of tuples of new names associated to
856 the original variables names.
857 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
858 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
861 translate_clast_for (sese region, struct clast_for *stmt, edge next_e,
862 htab_t rename_map, VEC (tree, heap) **newivs,
863 htab_t newivs_index, htab_t bb_pbb_mapping,
866 edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs,
867 newivs_index, params_index);
869 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
870 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
871 edge exit_true_e = single_succ_edge (true_e->dest);
872 edge exit_false_e = single_succ_edge (false_e->dest);
874 htab_t before_guard = htab_create (10, rename_map_elt_info,
875 eq_rename_map_elts, free);
876 htab_traverse (rename_map, copy_renames, before_guard);
878 next_e = translate_clast_for_loop (region, stmt, true_e, rename_map, newivs,
879 newivs_index, bb_pbb_mapping,
882 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
883 before_guard, rename_map);
885 htab_delete (before_guard);
890 /* Translates a clast guard statement STMT to gimple.
892 - REGION is the sese region we used to generate the scop.
893 - NEXT_E is the edge where new generated code should be attached.
894 - RENAME_MAP contains a set of tuples of new names associated to
895 the original variables names.
896 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
897 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
900 translate_clast_guard (sese region, struct clast_guard *stmt, edge next_e,
901 htab_t rename_map, VEC (tree, heap) **newivs,
902 htab_t newivs_index, htab_t bb_pbb_mapping,
905 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
906 newivs_index, params_index);
908 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
909 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
910 edge exit_true_e = single_succ_edge (true_e->dest);
911 edge exit_false_e = single_succ_edge (false_e->dest);
913 htab_t before_guard = htab_create (10, rename_map_elt_info,
914 eq_rename_map_elts, free);
915 htab_traverse (rename_map, copy_renames, before_guard);
917 next_e = translate_clast (region, stmt->then, true_e,
918 rename_map, newivs, newivs_index, bb_pbb_mapping,
921 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
922 before_guard, rename_map);
924 htab_delete (before_guard);
929 /* Translates a CLAST statement STMT to GCC representation in the
932 - NEXT_E is the edge where new generated code should be attached.
933 - RENAME_MAP contains a set of tuples of new names associated to
934 the original variables names.
935 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
937 translate_clast (sese region, struct clast_stmt *stmt,
938 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
939 htab_t newivs_index, htab_t bb_pbb_mapping,
945 if (CLAST_STMT_IS_A (stmt, stmt_root))
948 else if (CLAST_STMT_IS_A (stmt, stmt_user))
949 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
950 next_e, rename_map, newivs, newivs_index,
951 bb_pbb_mapping, params_index);
953 else if (CLAST_STMT_IS_A (stmt, stmt_for))
954 next_e = translate_clast_for (region,
955 (struct clast_for *) stmt, next_e, rename_map,
956 newivs, newivs_index, bb_pbb_mapping,
959 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
960 next_e = translate_clast_guard (region, (struct clast_guard *) stmt, next_e,
961 rename_map, newivs, newivs_index,
962 bb_pbb_mapping, params_index);
964 else if (CLAST_STMT_IS_A (stmt, stmt_block))
965 next_e = translate_clast (region, ((struct clast_block *) stmt)->body,
966 next_e, rename_map, newivs, newivs_index,
967 bb_pbb_mapping, params_index);
971 recompute_all_dominators ();
974 return translate_clast (region, stmt->next, next_e, rename_map, newivs,
975 newivs_index, bb_pbb_mapping, params_index);
978 /* Returns the first cloog name used in EXPR. */
981 find_cloog_iv_in_expr (struct clast_expr *expr)
983 struct clast_term *term = (struct clast_term *) expr;
985 if (expr->type == expr_term
989 if (expr->type == expr_term)
992 if (expr->type == expr_red)
995 struct clast_reduction *red = (struct clast_reduction *) expr;
997 for (i = 0; i < red->n; i++)
999 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
1009 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
1010 induction variables and the corresponding GCC old induction
1011 variables. This information is stored on each GRAPHITE_BB. */
1014 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1016 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1017 struct clast_stmt *t;
1020 for (t = user_stmt->substitutions; t; t = t->next, index++)
1023 struct ivtype_map_elt_s tmp;
1024 struct clast_expr *expr = (struct clast_expr *)
1025 ((struct clast_assignment *)t)->RHS;
1027 /* Create an entry (clast_var, type). */
1028 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1032 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1036 tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1037 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
1038 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1043 /* Walk the CLAST tree starting from STMT and build for each
1044 clast_user_stmt a map between the CLAST induction variables and the
1045 corresponding GCC old induction variables. This information is
1046 stored on each GRAPHITE_BB. */
1049 compute_cloog_iv_types (struct clast_stmt *stmt)
1054 if (CLAST_STMT_IS_A (stmt, stmt_root))
1057 if (CLAST_STMT_IS_A (stmt, stmt_user))
1059 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1060 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1061 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1063 if (!GBB_CLOOG_IV_TYPES (gbb))
1064 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1065 eq_ivtype_map_elts, free);
1067 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1071 if (CLAST_STMT_IS_A (stmt, stmt_for))
1073 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1074 compute_cloog_iv_types (s);
1078 if (CLAST_STMT_IS_A (stmt, stmt_guard))
1080 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1081 compute_cloog_iv_types (s);
1085 if (CLAST_STMT_IS_A (stmt, stmt_block))
1087 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1088 compute_cloog_iv_types (s);
1095 compute_cloog_iv_types (stmt->next);
1098 /* Free the SCATTERING domain list. */
1101 free_scattering (CloogDomainList *scattering)
1105 CloogDomain *dom = cloog_domain (scattering);
1106 CloogDomainList *next = cloog_next_domain (scattering);
1108 cloog_domain_free (dom);
1114 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1115 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1116 from 0 to scop_nb_loops (scop). */
1119 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1121 sese region = SCOP_REGION (scop);
1123 int nb_iterators = scop_max_loop_depth (scop);
1124 int nb_scattering = cloog_program_nb_scattdims (prog);
1125 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1126 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1127 char **scattering = XNEWVEC (char *, nb_scattering);
1128 char **parameters= XNEWVEC (char *, nb_parameters);
1130 cloog_program_set_names (prog, cloog_names_malloc ());
1132 for (i = 0; i < nb_parameters; i++)
1134 tree param = VEC_index (tree, SESE_PARAMS(region), i);
1135 const char *name = get_name (param);
1141 len = strlen (name);
1143 parameters[i] = XNEWVEC (char, len + 1);
1144 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1147 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1148 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1150 for (i = 0; i < nb_iterators; i++)
1153 iterators[i] = XNEWVEC (char, len);
1154 snprintf (iterators[i], len, "git_%d", i);
1157 cloog_names_set_nb_iterators (cloog_program_names (prog),
1159 cloog_names_set_iterators (cloog_program_names (prog),
1162 for (i = 0; i < nb_scattering; i++)
1165 scattering[i] = XNEWVEC (char, len);
1166 snprintf (scattering[i], len, "scat_%d", i);
1169 cloog_names_set_nb_scattering (cloog_program_names (prog),
1171 cloog_names_set_scattering (cloog_program_names (prog),
1175 /* Build cloog program for SCoP. */
1178 build_cloog_prog (scop_p scop, CloogProgram *prog)
1181 int max_nb_loops = scop_max_loop_depth (scop);
1183 CloogLoop *loop_list = NULL;
1184 CloogBlockList *block_list = NULL;
1185 CloogDomainList *scattering = NULL;
1186 int nbs = 2 * max_nb_loops + 1;
1189 cloog_program_set_context
1190 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1191 nbs = unify_scattering_dimensions (scop);
1192 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1193 cloog_program_set_nb_scattdims (prog, nbs);
1194 initialize_cloog_names (scop, prog);
1196 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1198 CloogStatement *stmt;
1201 /* Dead code elimination: when the domain of a PBB is empty,
1202 don't generate code for the PBB. */
1203 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1206 /* Build the new statement and its block. */
1207 stmt = cloog_statement_alloc (pbb_index (pbb));
1208 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1209 cloog_statement_set_usr (stmt, pbb);
1211 /* Build loop list. */
1213 CloogLoop *new_loop_list = cloog_loop_malloc ();
1214 cloog_loop_set_next (new_loop_list, loop_list);
1215 cloog_loop_set_domain
1217 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1218 cloog_loop_set_block (new_loop_list, block);
1219 loop_list = new_loop_list;
1222 /* Build block list. */
1224 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1226 cloog_block_list_set_next (new_block_list, block_list);
1227 cloog_block_list_set_block (new_block_list, block);
1228 block_list = new_block_list;
1231 /* Build scattering list. */
1233 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1234 CloogDomainList *new_scattering
1235 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1236 ppl_Polyhedron_t scat;
1239 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1240 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1242 cloog_set_next_domain (new_scattering, scattering);
1243 cloog_set_domain (new_scattering, dom);
1244 scattering = new_scattering;
1248 cloog_program_set_loop (prog, loop_list);
1249 cloog_program_set_blocklist (prog, block_list);
1251 for (i = 0; i < nbs; i++)
1254 cloog_program_set_scaldims (prog, scaldims);
1256 /* Extract scalar dimensions to simplify the code generation problem. */
1257 cloog_program_extract_scalars (prog, scattering);
1259 /* Apply scattering. */
1260 cloog_program_scatter (prog, scattering);
1261 free_scattering (scattering);
1263 /* Iterators corresponding to scalar dimensions have to be extracted. */
1264 cloog_names_scalarize (cloog_program_names (prog), nbs,
1265 cloog_program_scaldims (prog));
1267 /* Free blocklist. */
1269 CloogBlockList *next = cloog_program_blocklist (prog);
1273 CloogBlockList *toDelete = next;
1274 next = cloog_block_list_next (next);
1275 cloog_block_list_set_next (toDelete, NULL);
1276 cloog_block_list_set_block (toDelete, NULL);
1277 cloog_block_list_free (toDelete);
1279 cloog_program_set_blocklist (prog, NULL);
1283 /* Return the options that will be used in GLOOG. */
1285 static CloogOptions *
1286 set_cloog_options (void)
1288 CloogOptions *options = cloog_options_malloc ();
1290 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1291 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1292 we pass an incomplete program to cloog. */
1293 options->language = LANGUAGE_C;
1295 /* Enable complex equality spreading: removes dummy statements
1296 (assignments) in the generated code which repeats the
1297 substitution equations for statements. This is useless for
1301 /* Enable C pretty-printing mode: normalizes the substitution
1302 equations for statements. */
1305 /* Allow cloog to build strides with a stride width different to one.
1306 This example has stride = 4:
1308 for (i = 0; i < 20; i += 4)
1310 options->strides = 1;
1312 /* Disable optimizations and make cloog generate source code closer to the
1313 input. This is useful for debugging, but later we want the optimized
1316 XXX: We can not disable optimizations, as loop blocking is not working
1321 options->l = INT_MAX;
1327 /* Prints STMT to STDERR. */
1330 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1332 CloogOptions *options = set_cloog_options ();
1334 pprint (file, stmt, 0, options);
1335 cloog_options_free (options);
1338 /* Prints STMT to STDERR. */
1341 debug_clast_stmt (struct clast_stmt *stmt)
1343 print_clast_stmt (stderr, stmt);
1346 /* Translate SCOP to a CLooG program and clast. These two
1347 representations should be freed together: a clast cannot be used
1348 without a program. */
1351 scop_to_clast (scop_p scop)
1353 CloogOptions *options = set_cloog_options ();
1354 cloog_prog_clast pc;
1356 /* Connect new cloog prog generation to graphite. */
1357 pc.prog = cloog_program_malloc ();
1358 build_cloog_prog (scop, pc.prog);
1359 pc.prog = cloog_program_generate (pc.prog, options);
1360 pc.stmt = cloog_clast_create (pc.prog, options);
1362 cloog_options_free (options);
1366 /* Prints to FILE the code generated by CLooG for SCOP. */
1369 print_generated_program (FILE *file, scop_p scop)
1371 CloogOptions *options = set_cloog_options ();
1372 cloog_prog_clast pc = scop_to_clast (scop);
1374 fprintf (file, " (prog: \n");
1375 cloog_program_print (file, pc.prog);
1376 fprintf (file, " )\n");
1378 fprintf (file, " (clast: \n");
1379 pprint (file, pc.stmt, 0, options);
1380 fprintf (file, " )\n");
1382 cloog_options_free (options);
1383 cloog_clast_free (pc.stmt);
1384 cloog_program_free (pc.prog);
1387 /* Prints to STDERR the code generated by CLooG for SCOP. */
1390 debug_generated_program (scop_p scop)
1392 print_generated_program (stderr, scop);
1395 /* Add CLooG names to parameter index. The index is used to translate back from
1396 * CLooG names to GCC trees. */
1399 create_params_index (htab_t index_table, CloogProgram *prog) {
1400 CloogNames* names = cloog_program_names (prog);
1401 int nb_parameters = cloog_names_nb_parameters (names);
1402 char **parameters = cloog_names_parameters (names);
1405 for (i = 0; i < nb_parameters; i++)
1406 save_clast_name_index (index_table, parameters[i], i);
1409 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1410 the given SCOP. Return true if code generation succeeded.
1411 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1415 gloog (scop_p scop, htab_t bb_pbb_mapping)
1417 edge new_scop_exit_edge = NULL;
1418 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1419 sese region = SCOP_REGION (scop);
1420 ifsese if_region = NULL;
1421 htab_t rename_map, newivs_index, params_index;
1422 cloog_prog_clast pc;
1424 timevar_push (TV_GRAPHITE_CODE_GEN);
1426 pc = scop_to_clast (scop);
1428 if (dump_file && (dump_flags & TDF_DETAILS))
1430 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1431 print_clast_stmt (dump_file, pc.stmt);
1432 fprintf (dump_file, "\n");
1435 recompute_all_dominators ();
1438 if_region = move_sese_in_condition (region);
1439 sese_insert_phis_for_liveouts (region,
1440 if_region->region->exit->src,
1441 if_region->false_region->exit,
1442 if_region->true_region->exit);
1443 recompute_all_dominators ();
1446 compute_cloog_iv_types (pc.stmt);
1447 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1448 newivs_index = htab_create (10, clast_name_index_elt_info,
1449 eq_clast_name_indexes, free);
1450 params_index = htab_create (10, clast_name_index_elt_info,
1451 eq_clast_name_indexes, free);
1453 create_params_index (params_index, pc.prog);
1455 new_scop_exit_edge = translate_clast (region, pc.stmt,
1456 if_region->true_region->entry,
1457 rename_map, &newivs, newivs_index,
1458 bb_pbb_mapping, params_index);
1460 sese_adjust_liveout_phis (region, rename_map,
1461 if_region->region->exit->src,
1462 if_region->false_region->exit,
1463 if_region->true_region->exit);
1464 recompute_all_dominators ();
1467 free (if_region->true_region);
1468 free (if_region->region);
1471 htab_delete (rename_map);
1472 htab_delete (newivs_index);
1473 htab_delete (params_index);
1474 VEC_free (tree, heap, newivs);
1475 cloog_clast_free (pc.stmt);
1476 cloog_program_free (pc.prog);
1477 timevar_pop (TV_GRAPHITE_CODE_GEN);
1479 if (dump_file && (dump_flags & TDF_DETAILS))
1483 int num_no_dependency = 0;
1485 FOR_EACH_LOOP (li, loop, 0)
1486 if (loop->can_be_parallel)
1487 num_no_dependency++;
1489 fprintf (dump_file, "\n%d loops carried no dependency.\n",