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, loop_p, struct clast_stmt *, edge, htab_t,
728 VEC (tree, heap) **, htab_t, htab_t, int, 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 - CONTEXT_LOOP is the loop in which the generated code will be placed
735 - RENAME_MAP contains a set of tuples of new names associated to
736 the original variables names.
737 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
738 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
741 translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e,
742 htab_t rename_map, VEC (tree, heap) **newivs,
743 htab_t newivs_index, htab_t bb_pbb_mapping,
748 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
749 gbb = PBB_BLACK_BOX (pbb);
751 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
754 build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt,
756 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
758 new_bb = next_e->src;
759 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
760 update_ssa (TODO_update_ssa);
765 static tree gcc_type_for_iv_of_clast_loop (struct clast_for *);
768 /* Creates a new if region protecting the loop to be executed, if the execution
769 count is zero (lb > ub). */
771 graphite_create_new_loop_guard (sese region, edge entry_edge,
772 struct clast_for *stmt,
773 VEC (tree, heap) *newivs,
774 htab_t newivs_index, htab_t params_index)
778 tree type = gcc_type_for_iv_of_clast_loop (stmt);
779 tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs,
780 newivs_index, params_index);
781 tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
782 newivs_index, params_index);
784 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
785 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
786 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
787 However lb < ub + 1 is false, as expected.
788 There might be a problem with cases where ub is 2^32. */
791 value_init (gmp_one);
792 value_set_si (gmp_one, 1);
793 one = gmp_cst_to_tree (type, gmp_one);
794 value_clear (gmp_one);
796 ub = fold_build2 (PLUS_EXPR, type, ub, one);
797 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub);
799 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
805 /* Create the loop for a clast for statement.
807 - REGION is the sese region we used to generate the scop.
808 - NEXT_E is the edge where new generated code should be attached.
809 - RENAME_MAP contains a set of tuples of new names associated to
810 the original variables names.
811 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
812 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
815 translate_clast_for_loop (sese region, loop_p context_loop, struct clast_for *stmt, edge next_e,
816 htab_t rename_map, VEC (tree, heap) **newivs,
817 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
820 struct loop *loop = graphite_create_new_loop (region, next_e, stmt,
821 context_loop, newivs,
822 newivs_index, params_index);
823 edge last_e = single_exit (loop);
824 edge to_body = single_succ_edge (loop->header);
825 basic_block after = to_body->dest;
827 /* Create a basic block for loop close phi nodes. */
828 last_e = single_succ_edge (split_edge (last_e));
830 /* Translate the body of the loop. */
831 next_e = translate_clast (region, loop, stmt->body, to_body, rename_map,
832 newivs, newivs_index, bb_pbb_mapping, level + 1,
834 redirect_edge_succ_nodup (next_e, after);
835 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
837 /* Remove from rename_map all the tuples containing variables
838 defined in loop's body. */
839 insert_loop_close_phis (rename_map, loop);
841 if (flag_loop_parallelize_all
842 && !dependency_in_loop_p (loop, bb_pbb_mapping,
843 get_scattering_level (level)))
844 loop->can_be_parallel = true;
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, loop_p context_loop, 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, int level,
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, context_loop, stmt, true_e, rename_map, newivs,
879 newivs_index, bb_pbb_mapping, level,
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 - CONTEXT_LOOP is the loop in which the generated code will be placed
895 - RENAME_MAP contains a set of tuples of new names associated to
896 the original variables names.
897 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
898 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
901 translate_clast_guard (sese region, loop_p context_loop,
902 struct clast_guard *stmt, edge next_e,
903 htab_t rename_map, VEC (tree, heap) **newivs,
904 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
907 edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs,
908 newivs_index, params_index);
910 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
911 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
912 edge exit_true_e = single_succ_edge (true_e->dest);
913 edge exit_false_e = single_succ_edge (false_e->dest);
915 htab_t before_guard = htab_create (10, rename_map_elt_info,
916 eq_rename_map_elts, free);
917 htab_traverse (rename_map, copy_renames, before_guard);
919 next_e = translate_clast (region, context_loop, stmt->then, true_e,
920 rename_map, newivs, newivs_index, bb_pbb_mapping,
921 level, params_index);
923 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
924 before_guard, rename_map);
926 htab_delete (before_guard);
931 /* Translates a CLAST statement STMT to GCC representation in the
934 - NEXT_E is the edge where new generated code should be attached.
935 - CONTEXT_LOOP is the loop in which the generated code will be placed
936 - RENAME_MAP contains a set of tuples of new names associated to
937 the original variables names.
938 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
940 translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt,
941 edge next_e, htab_t rename_map, VEC (tree, heap) **newivs,
942 htab_t newivs_index, htab_t bb_pbb_mapping, int level,
948 if (CLAST_STMT_IS_A (stmt, stmt_root))
951 else if (CLAST_STMT_IS_A (stmt, stmt_user))
952 next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt,
953 next_e, rename_map, newivs, newivs_index,
954 bb_pbb_mapping, params_index);
956 else if (CLAST_STMT_IS_A (stmt, stmt_for))
957 next_e = translate_clast_for (region, context_loop,
958 (struct clast_for *) stmt, next_e,
959 rename_map, newivs, newivs_index,
960 bb_pbb_mapping, level, params_index);
962 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
963 next_e = translate_clast_guard (region, context_loop,
964 (struct clast_guard *) stmt, next_e,
965 rename_map, newivs, newivs_index,
966 bb_pbb_mapping, level, params_index);
968 else if (CLAST_STMT_IS_A (stmt, stmt_block))
969 next_e = translate_clast (region, context_loop,
970 ((struct clast_block *) stmt)->body,
971 next_e, rename_map, newivs, newivs_index,
972 bb_pbb_mapping, level, params_index);
976 recompute_all_dominators ();
979 return translate_clast (region, context_loop, stmt->next, next_e,
980 rename_map, newivs, newivs_index,
981 bb_pbb_mapping, level, params_index);
984 /* Returns the first cloog name used in EXPR. */
987 find_cloog_iv_in_expr (struct clast_expr *expr)
989 struct clast_term *term = (struct clast_term *) expr;
991 if (expr->type == expr_term
995 if (expr->type == expr_term)
998 if (expr->type == expr_red)
1001 struct clast_reduction *red = (struct clast_reduction *) expr;
1003 for (i = 0; i < red->n; i++)
1005 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
1015 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
1016 induction variables and the corresponding GCC old induction
1017 variables. This information is stored on each GRAPHITE_BB. */
1020 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
1022 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1023 struct clast_stmt *t;
1026 for (t = user_stmt->substitutions; t; t = t->next, index++)
1029 struct ivtype_map_elt_s tmp;
1030 struct clast_expr *expr = (struct clast_expr *)
1031 ((struct clast_assignment *)t)->RHS;
1033 /* Create an entry (clast_var, type). */
1034 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
1038 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
1042 tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
1043 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
1044 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
1049 /* Walk the CLAST tree starting from STMT and build for each
1050 clast_user_stmt a map between the CLAST induction variables and the
1051 corresponding GCC old induction variables. This information is
1052 stored on each GRAPHITE_BB. */
1055 compute_cloog_iv_types (struct clast_stmt *stmt)
1060 if (CLAST_STMT_IS_A (stmt, stmt_root))
1063 if (CLAST_STMT_IS_A (stmt, stmt_user))
1065 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
1066 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
1067 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1069 if (!GBB_CLOOG_IV_TYPES (gbb))
1070 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
1071 eq_ivtype_map_elts, free);
1073 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
1077 if (CLAST_STMT_IS_A (stmt, stmt_for))
1079 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
1080 compute_cloog_iv_types (s);
1084 if (CLAST_STMT_IS_A (stmt, stmt_guard))
1086 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
1087 compute_cloog_iv_types (s);
1091 if (CLAST_STMT_IS_A (stmt, stmt_block))
1093 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
1094 compute_cloog_iv_types (s);
1101 compute_cloog_iv_types (stmt->next);
1104 /* Free the SCATTERING domain list. */
1107 free_scattering (CloogDomainList *scattering)
1111 CloogDomain *dom = cloog_domain (scattering);
1112 CloogDomainList *next = cloog_next_domain (scattering);
1114 cloog_domain_free (dom);
1120 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1121 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1122 from 0 to scop_nb_loops (scop). */
1125 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1127 sese region = SCOP_REGION (scop);
1129 int nb_iterators = scop_max_loop_depth (scop);
1130 int nb_scattering = cloog_program_nb_scattdims (prog);
1131 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1132 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1133 char **scattering = XNEWVEC (char *, nb_scattering);
1134 char **parameters= XNEWVEC (char *, nb_parameters);
1136 cloog_program_set_names (prog, cloog_names_malloc ());
1138 for (i = 0; i < nb_parameters; i++)
1140 tree param = VEC_index (tree, SESE_PARAMS(region), i);
1141 const char *name = get_name (param);
1147 len = strlen (name);
1149 parameters[i] = XNEWVEC (char, len + 1);
1150 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1153 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1154 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1156 for (i = 0; i < nb_iterators; i++)
1159 iterators[i] = XNEWVEC (char, len);
1160 snprintf (iterators[i], len, "git_%d", i);
1163 cloog_names_set_nb_iterators (cloog_program_names (prog),
1165 cloog_names_set_iterators (cloog_program_names (prog),
1168 for (i = 0; i < nb_scattering; i++)
1171 scattering[i] = XNEWVEC (char, len);
1172 snprintf (scattering[i], len, "scat_%d", i);
1175 cloog_names_set_nb_scattering (cloog_program_names (prog),
1177 cloog_names_set_scattering (cloog_program_names (prog),
1181 /* Build cloog program for SCoP. */
1184 build_cloog_prog (scop_p scop, CloogProgram *prog)
1187 int max_nb_loops = scop_max_loop_depth (scop);
1189 CloogLoop *loop_list = NULL;
1190 CloogBlockList *block_list = NULL;
1191 CloogDomainList *scattering = NULL;
1192 int nbs = 2 * max_nb_loops + 1;
1195 cloog_program_set_context
1196 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
1197 nbs = unify_scattering_dimensions (scop);
1198 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1199 cloog_program_set_nb_scattdims (prog, nbs);
1200 initialize_cloog_names (scop, prog);
1202 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1204 CloogStatement *stmt;
1207 /* Dead code elimination: when the domain of a PBB is empty,
1208 don't generate code for the PBB. */
1209 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1212 /* Build the new statement and its block. */
1213 stmt = cloog_statement_alloc (pbb_index (pbb));
1214 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1215 cloog_statement_set_usr (stmt, pbb);
1217 /* Build loop list. */
1219 CloogLoop *new_loop_list = cloog_loop_malloc ();
1220 cloog_loop_set_next (new_loop_list, loop_list);
1221 cloog_loop_set_domain
1223 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
1224 cloog_loop_set_block (new_loop_list, block);
1225 loop_list = new_loop_list;
1228 /* Build block list. */
1230 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1232 cloog_block_list_set_next (new_block_list, block_list);
1233 cloog_block_list_set_block (new_block_list, block);
1234 block_list = new_block_list;
1237 /* Build scattering list. */
1239 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1240 CloogDomainList *new_scattering
1241 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
1242 ppl_Polyhedron_t scat;
1245 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1246 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
1248 cloog_set_next_domain (new_scattering, scattering);
1249 cloog_set_domain (new_scattering, dom);
1250 scattering = new_scattering;
1254 cloog_program_set_loop (prog, loop_list);
1255 cloog_program_set_blocklist (prog, block_list);
1257 for (i = 0; i < nbs; i++)
1260 cloog_program_set_scaldims (prog, scaldims);
1262 /* Extract scalar dimensions to simplify the code generation problem. */
1263 cloog_program_extract_scalars (prog, scattering);
1265 /* Apply scattering. */
1266 cloog_program_scatter (prog, scattering);
1267 free_scattering (scattering);
1269 /* Iterators corresponding to scalar dimensions have to be extracted. */
1270 cloog_names_scalarize (cloog_program_names (prog), nbs,
1271 cloog_program_scaldims (prog));
1273 /* Free blocklist. */
1275 CloogBlockList *next = cloog_program_blocklist (prog);
1279 CloogBlockList *toDelete = next;
1280 next = cloog_block_list_next (next);
1281 cloog_block_list_set_next (toDelete, NULL);
1282 cloog_block_list_set_block (toDelete, NULL);
1283 cloog_block_list_free (toDelete);
1285 cloog_program_set_blocklist (prog, NULL);
1289 /* Return the options that will be used in GLOOG. */
1291 static CloogOptions *
1292 set_cloog_options (void)
1294 CloogOptions *options = cloog_options_malloc ();
1296 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1297 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1298 we pass an incomplete program to cloog. */
1299 options->language = LANGUAGE_C;
1301 /* Enable complex equality spreading: removes dummy statements
1302 (assignments) in the generated code which repeats the
1303 substitution equations for statements. This is useless for
1307 /* Enable C pretty-printing mode: normalizes the substitution
1308 equations for statements. */
1311 /* Allow cloog to build strides with a stride width different to one.
1312 This example has stride = 4:
1314 for (i = 0; i < 20; i += 4)
1316 options->strides = 1;
1318 /* Disable optimizations and make cloog generate source code closer to the
1319 input. This is useful for debugging, but later we want the optimized
1322 XXX: We can not disable optimizations, as loop blocking is not working
1327 options->l = INT_MAX;
1333 /* Prints STMT to STDERR. */
1336 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1338 CloogOptions *options = set_cloog_options ();
1340 pprint (file, stmt, 0, options);
1341 cloog_options_free (options);
1344 /* Prints STMT to STDERR. */
1347 debug_clast_stmt (struct clast_stmt *stmt)
1349 print_clast_stmt (stderr, stmt);
1352 /* Translate SCOP to a CLooG program and clast. These two
1353 representations should be freed together: a clast cannot be used
1354 without a program. */
1357 scop_to_clast (scop_p scop)
1359 CloogOptions *options = set_cloog_options ();
1360 cloog_prog_clast pc;
1362 /* Connect new cloog prog generation to graphite. */
1363 pc.prog = cloog_program_malloc ();
1364 build_cloog_prog (scop, pc.prog);
1365 pc.prog = cloog_program_generate (pc.prog, options);
1366 pc.stmt = cloog_clast_create (pc.prog, options);
1368 cloog_options_free (options);
1372 /* Prints to FILE the code generated by CLooG for SCOP. */
1375 print_generated_program (FILE *file, scop_p scop)
1377 CloogOptions *options = set_cloog_options ();
1378 cloog_prog_clast pc = scop_to_clast (scop);
1380 fprintf (file, " (prog: \n");
1381 cloog_program_print (file, pc.prog);
1382 fprintf (file, " )\n");
1384 fprintf (file, " (clast: \n");
1385 pprint (file, pc.stmt, 0, options);
1386 fprintf (file, " )\n");
1388 cloog_options_free (options);
1389 cloog_clast_free (pc.stmt);
1390 cloog_program_free (pc.prog);
1393 /* Prints to STDERR the code generated by CLooG for SCOP. */
1396 debug_generated_program (scop_p scop)
1398 print_generated_program (stderr, scop);
1401 /* Add CLooG names to parameter index. The index is used to translate back from
1402 * CLooG names to GCC trees. */
1405 create_params_index (htab_t index_table, CloogProgram *prog) {
1406 CloogNames* names = cloog_program_names (prog);
1407 int nb_parameters = cloog_names_nb_parameters (names);
1408 char **parameters = cloog_names_parameters (names);
1411 for (i = 0; i < nb_parameters; i++)
1412 save_clast_name_index (index_table, parameters[i], i);
1415 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1416 the given SCOP. Return true if code generation succeeded.
1417 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1421 gloog (scop_p scop, htab_t bb_pbb_mapping)
1423 edge new_scop_exit_edge = NULL;
1424 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1425 loop_p context_loop;
1426 sese region = SCOP_REGION (scop);
1427 ifsese if_region = NULL;
1428 htab_t rename_map, newivs_index, params_index;
1429 cloog_prog_clast pc;
1431 timevar_push (TV_GRAPHITE_CODE_GEN);
1433 pc = scop_to_clast (scop);
1435 if (dump_file && (dump_flags & TDF_DETAILS))
1437 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1438 print_clast_stmt (dump_file, pc.stmt);
1439 fprintf (dump_file, "\n");
1442 recompute_all_dominators ();
1445 if_region = move_sese_in_condition (region);
1446 sese_insert_phis_for_liveouts (region,
1447 if_region->region->exit->src,
1448 if_region->false_region->exit,
1449 if_region->true_region->exit);
1450 recompute_all_dominators ();
1453 context_loop = SESE_ENTRY (region)->src->loop_father;
1454 compute_cloog_iv_types (pc.stmt);
1455 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1456 newivs_index = htab_create (10, clast_name_index_elt_info,
1457 eq_clast_name_indexes, free);
1458 params_index = htab_create (10, clast_name_index_elt_info,
1459 eq_clast_name_indexes, free);
1461 create_params_index (params_index, pc.prog);
1463 new_scop_exit_edge = translate_clast (region, context_loop, pc.stmt,
1464 if_region->true_region->entry,
1465 rename_map, &newivs, newivs_index,
1466 bb_pbb_mapping, 1, params_index);
1468 sese_adjust_liveout_phis (region, rename_map,
1469 if_region->region->exit->src,
1470 if_region->false_region->exit,
1471 if_region->true_region->exit);
1472 recompute_all_dominators ();
1475 free (if_region->true_region);
1476 free (if_region->region);
1479 htab_delete (rename_map);
1480 htab_delete (newivs_index);
1481 htab_delete (params_index);
1482 VEC_free (tree, heap, newivs);
1483 cloog_clast_free (pc.stmt);
1484 cloog_program_free (pc.prog);
1485 timevar_pop (TV_GRAPHITE_CODE_GEN);
1487 if (dump_file && (dump_flags & TDF_DETAILS))
1491 int num_no_dependency = 0;
1493 FOR_EACH_LOOP (li, loop, 0)
1494 if (loop->can_be_parallel)
1495 num_no_dependency++;
1497 fprintf (dump_file, "\n%d loops carried no dependency.\n",