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 /* For a given loop DEPTH in the loop nest of the original black box
70 PBB, return the old induction variable associated to that loop. */
73 pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth)
75 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
76 sese region = SCOP_REGION (PBB_SCOP (pbb));
77 loop_p loop = gbb_loop_at_index (gbb, region, depth);
79 return loop->single_iv;
82 /* For a given scattering dimension, return the new induction variable
86 newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth)
88 return VEC_index (tree, newivs, depth);
93 /* Returns the tree variable from the name NAME that was given in
94 Cloog representation. */
97 clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs,
101 VEC (tree, heap) *params = SESE_PARAMS (region);
102 htab_t params_index = SESE_PARAMS_INDEX (region);
104 if (params && params_index)
106 index = clast_name_to_index (name, params_index);
109 return VEC_index (tree, params, index);
112 gcc_assert (newivs && newivs_index);
113 index = clast_name_to_index (name, newivs_index);
114 gcc_assert (index >= 0);
116 return newivs_to_depth_to_newiv (newivs, index);
119 /* Returns the maximal precision type for expressions E1 and E2. */
122 max_precision_type (tree e1, tree e2)
124 tree type1 = TREE_TYPE (e1);
125 tree type2 = TREE_TYPE (e2);
126 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
130 clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *,
133 /* Converts a Cloog reduction expression R with reduction operation OP
134 to a GCC expression tree of type TYPE. */
137 clast_to_gcc_expression_red (tree type, enum tree_code op,
138 struct clast_reduction *r,
139 sese region, VEC (tree, heap) *newivs,
143 tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs,
145 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
147 for (i = 1; i < r->n; i++)
149 tree t = clast_to_gcc_expression (operand_type, r->elts[i], region,
150 newivs, newivs_index);
151 res = fold_build2 (op, type, res, t);
157 /* Converts a Cloog AST expression E back to a GCC expression tree of
161 clast_to_gcc_expression (tree type, struct clast_expr *e,
162 sese region, VEC (tree, heap) *newivs,
169 struct clast_term *t = (struct clast_term *) e;
173 if (value_one_p (t->val))
175 tree name = clast_name_to_gcc (t->var, region, newivs,
177 return fold_convert (type, name);
180 else if (value_mone_p (t->val))
182 tree name = clast_name_to_gcc (t->var, region, newivs,
184 name = fold_convert (type, name);
185 return fold_build1 (NEGATE_EXPR, type, name);
189 tree name = clast_name_to_gcc (t->var, region, newivs,
191 tree cst = gmp_cst_to_tree (type, t->val);
192 name = fold_convert (type, name);
193 return fold_build2 (MULT_EXPR, type, cst, name);
197 return gmp_cst_to_tree (type, t->val);
202 struct clast_reduction *r = (struct clast_reduction *) e;
207 return clast_to_gcc_expression_red
208 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
209 r, region, newivs, newivs_index);
212 return clast_to_gcc_expression_red (type, MIN_EXPR, r, region,
213 newivs, newivs_index);
216 return clast_to_gcc_expression_red (type, MAX_EXPR, r, region,
217 newivs, newivs_index);
227 struct clast_binary *b = (struct clast_binary *) e;
228 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
229 tree tl = clast_to_gcc_expression (type, lhs, region, newivs,
231 tree tr = gmp_cst_to_tree (type, b->RHS);
236 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
239 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
242 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
245 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
259 /* Returns the type for the expression E. */
262 gcc_type_for_clast_expr (struct clast_expr *e,
263 sese region, VEC (tree, heap) *newivs,
270 struct clast_term *t = (struct clast_term *) e;
273 return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs,
281 struct clast_reduction *r = (struct clast_reduction *) e;
284 return gcc_type_for_clast_expr (r->elts[0], region, newivs,
289 for (i = 0; i < r->n; i++)
291 tree type = gcc_type_for_clast_expr (r->elts[i], region,
292 newivs, newivs_index);
302 struct clast_binary *b = (struct clast_binary *) e;
303 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
304 return gcc_type_for_clast_expr (lhs, region, newivs,
315 /* Returns the type for the equation CLEQ. */
318 gcc_type_for_clast_eq (struct clast_equation *cleq,
319 sese region, VEC (tree, heap) *newivs,
322 tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs,
327 return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index);
330 /* Translates a clast equation CLEQ to a tree. */
333 graphite_translate_clast_equation (sese region,
334 struct clast_equation *cleq,
335 VEC (tree, heap) *newivs,
339 tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index);
340 tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs,
342 tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs,
348 else if (cleq->sign > 0)
354 return fold_build2 (comp, boolean_type_node, lhs, rhs);
357 /* Creates the test for the condition in STMT. */
360 graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt,
361 VEC (tree, heap) *newivs,
367 for (i = 0; i < stmt->n; i++)
369 tree eq = graphite_translate_clast_equation (region, &stmt->eq[i],
370 newivs, newivs_index);
373 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
381 /* Creates a new if region corresponding to Cloog's guard. */
384 graphite_create_new_guard (sese region, edge entry_edge,
385 struct clast_guard *stmt,
386 VEC (tree, heap) *newivs,
389 tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs,
391 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
395 /* Walks a CLAST and returns the first statement in the body of a
398 static struct clast_user_stmt *
399 clast_get_body_of_loop (struct clast_stmt *stmt)
402 || CLAST_STMT_IS_A (stmt, stmt_user))
403 return (struct clast_user_stmt *) stmt;
405 if (CLAST_STMT_IS_A (stmt, stmt_for))
406 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
408 if (CLAST_STMT_IS_A (stmt, stmt_guard))
409 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
411 if (CLAST_STMT_IS_A (stmt, stmt_block))
412 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
417 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
418 If the information is not available, i.e. in the case one of the
419 transforms created the loop, just return integer_type_node. */
422 gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
424 struct ivtype_map_elt_s tmp;
427 tmp.cloog_iv = cloog_iv;
428 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
431 return ((ivtype_map_elt) *slot)->type;
433 return integer_type_node;
436 /* Returns the induction variable for the loop that gets translated to
440 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
442 struct clast_stmt *stmt = (struct clast_stmt *) stmt_for;
443 struct clast_user_stmt *body = clast_get_body_of_loop (stmt);
444 const char *cloog_iv = stmt_for->iterator;
445 CloogStatement *cs = body->statement;
446 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
448 return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb));
451 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
452 induction variable for the new LOOP. New LOOP is attached to CFG
453 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
454 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
455 CLooG's scattering name to the induction variable created for the
456 loop of STMT. The new induction variable is inserted in the NEWIVS
460 graphite_create_new_loop (sese region, edge entry_edge,
461 struct clast_for *stmt,
462 loop_p outer, VEC (tree, heap) **newivs,
465 tree type = gcc_type_for_iv_of_clast_loop (stmt);
466 tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs,
468 tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs,
470 tree stride = gmp_cst_to_tree (type, stmt->stride);
471 tree ivvar = create_tmp_var (type, "graphite_IV");
472 tree iv, iv_after_increment;
473 loop_p loop = create_empty_loop_on_edge
474 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
475 outer ? outer : entry_edge->src->loop_father);
477 add_referenced_var (ivvar);
479 save_clast_name_index (newivs_index, stmt->iterator,
480 VEC_length (tree, *newivs));
481 VEC_safe_push (tree, heap, *newivs, iv);
485 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
486 variables of the loops around GBB in SESE. */
489 build_iv_mapping (htab_t map, sese region,
490 VEC (tree, heap) *newivs, htab_t newivs_index,
491 struct clast_user_stmt *user_stmt)
493 struct clast_stmt *t;
495 CloogStatement *cs = user_stmt->statement;
496 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
498 for (t = user_stmt->substitutions; t; t = t->next, index++)
500 struct clast_expr *expr = (struct clast_expr *)
501 ((struct clast_assignment *)t)->RHS;
502 tree type = gcc_type_for_clast_expr (expr, region, newivs,
504 tree old_name = pbb_to_depth_to_oldiv (pbb, index);
505 tree e = clast_to_gcc_expression (type, expr, region, newivs,
507 set_rename (map, old_name, e);
511 /* Helper function for htab_traverse. */
514 copy_renames (void **slot, void *s)
516 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
517 htab_t res = (htab_t) s;
518 tree old_name = entry->old_name;
519 tree expr = entry->expr;
520 struct rename_map_elt_s tmp;
523 tmp.old_name = old_name;
524 x = htab_find_slot (res, &tmp, INSERT);
527 *x = new_rename_map_elt (old_name, expr);
532 /* Construct bb_pbb_def with BB and PBB. */
535 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
537 bb_pbb_def *bb_pbb_p;
539 bb_pbb_p = XNEW (bb_pbb_def);
546 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
549 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
555 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
558 *x = new_bb_pbb_def (bb, pbb);
561 /* Translates a CLAST statement STMT to GCC representation in the
564 - NEXT_E is the edge where new generated code should be attached.
565 - CONTEXT_LOOP is the loop in which the generated code will be placed
566 - RENAME_MAP contains a set of tuples of new names associated to
567 the original variables names.
568 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
572 translate_clast (sese region, struct loop *context_loop,
573 struct clast_stmt *stmt, edge next_e,
574 htab_t rename_map, VEC (tree, heap) **newivs,
575 htab_t newivs_index, htab_t bb_pbb_mapping, int level)
580 if (CLAST_STMT_IS_A (stmt, stmt_root))
581 return translate_clast (region, context_loop, stmt->next, next_e,
582 rename_map, newivs, newivs_index,
583 bb_pbb_mapping, level);
585 if (CLAST_STMT_IS_A (stmt, stmt_user))
589 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
590 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
591 gbb = PBB_BLACK_BOX (pbb);
593 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
596 build_iv_mapping (rename_map, region, *newivs, newivs_index,
597 (struct clast_user_stmt *) stmt);
598 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region,
600 new_bb = next_e->src;
601 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
602 recompute_all_dominators ();
603 update_ssa (TODO_update_ssa);
605 return translate_clast (region, context_loop, stmt->next, next_e,
606 rename_map, newivs, newivs_index,
607 bb_pbb_mapping, level);
610 if (CLAST_STMT_IS_A (stmt, stmt_for))
612 struct clast_for *stmtfor = (struct clast_for *)stmt;
614 = graphite_create_new_loop (region, next_e, stmtfor,
615 context_loop, newivs, newivs_index);
616 edge last_e = single_exit (loop);
617 edge to_body = single_succ_edge (loop->header);
618 basic_block after = to_body->dest;
620 loop->aux = XNEW (int);
621 /* Pass scattering level information of the new loop by LOOP->AUX. */
622 *((int *)(loop->aux)) = get_scattering_level (level);
624 /* Create a basic block for loop close phi nodes. */
625 last_e = single_succ_edge (split_edge (last_e));
627 /* Translate the body of the loop. */
628 next_e = translate_clast
629 (region, loop, ((struct clast_for *) stmt)->body,
630 single_succ_edge (loop->header), rename_map, newivs,
631 newivs_index, bb_pbb_mapping, level + 1);
632 redirect_edge_succ_nodup (next_e, after);
633 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
635 /* Remove from rename_map all the tuples containing variables
636 defined in loop's body. */
637 insert_loop_close_phis (rename_map, loop);
639 recompute_all_dominators ();
641 return translate_clast (region, context_loop, stmt->next, last_e,
642 rename_map, newivs, newivs_index,
643 bb_pbb_mapping, level);
646 if (CLAST_STMT_IS_A (stmt, stmt_guard))
648 edge last_e = graphite_create_new_guard (region, next_e,
649 ((struct clast_guard *) stmt),
650 *newivs, newivs_index);
651 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
652 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
653 edge exit_true_e = single_succ_edge (true_e->dest);
654 edge exit_false_e = single_succ_edge (false_e->dest);
655 htab_t before_guard = htab_create (10, rename_map_elt_info,
656 eq_rename_map_elts, free);
658 htab_traverse (rename_map, copy_renames, before_guard);
659 next_e = translate_clast (region, context_loop,
660 ((struct clast_guard *) stmt)->then,
661 true_e, rename_map, newivs, newivs_index,
662 bb_pbb_mapping, level);
663 insert_guard_phis (last_e->src, exit_true_e, exit_false_e,
664 before_guard, rename_map);
666 htab_delete (before_guard);
667 recompute_all_dominators ();
670 return translate_clast (region, context_loop, stmt->next, last_e,
671 rename_map, newivs, newivs_index,
672 bb_pbb_mapping, level);
675 if (CLAST_STMT_IS_A (stmt, stmt_block))
677 next_e = translate_clast (region, context_loop,
678 ((struct clast_block *) stmt)->body,
679 next_e, rename_map, newivs, newivs_index,
680 bb_pbb_mapping, level);
681 recompute_all_dominators ();
683 return translate_clast (region, context_loop, stmt->next, next_e,
684 rename_map, newivs, newivs_index,
685 bb_pbb_mapping, level);
691 /* Returns the first cloog name used in EXPR. */
694 find_cloog_iv_in_expr (struct clast_expr *expr)
696 struct clast_term *term = (struct clast_term *) expr;
698 if (expr->type == expr_term
702 if (expr->type == expr_term)
705 if (expr->type == expr_red)
708 struct clast_reduction *red = (struct clast_reduction *) expr;
710 for (i = 0; i < red->n; i++)
712 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
722 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
723 induction variables and the corresponding GCC old induction
724 variables. This information is stored on each GRAPHITE_BB. */
727 compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
729 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
730 struct clast_stmt *t;
733 for (t = user_stmt->substitutions; t; t = t->next, index++)
736 struct ivtype_map_elt_s tmp;
737 struct clast_expr *expr = (struct clast_expr *)
738 ((struct clast_assignment *)t)->RHS;
740 /* Create an entry (clast_var, type). */
741 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
745 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
749 tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
750 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
751 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
756 /* Walk the CLAST tree starting from STMT and build for each
757 clast_user_stmt a map between the CLAST induction variables and the
758 corresponding GCC old induction variables. This information is
759 stored on each GRAPHITE_BB. */
762 compute_cloog_iv_types (struct clast_stmt *stmt)
767 if (CLAST_STMT_IS_A (stmt, stmt_root))
770 if (CLAST_STMT_IS_A (stmt, stmt_user))
772 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
773 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
774 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
776 if (!GBB_CLOOG_IV_TYPES (gbb))
777 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
778 eq_ivtype_map_elts, free);
780 compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt);
784 if (CLAST_STMT_IS_A (stmt, stmt_for))
786 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
787 compute_cloog_iv_types (s);
791 if (CLAST_STMT_IS_A (stmt, stmt_guard))
793 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
794 compute_cloog_iv_types (s);
798 if (CLAST_STMT_IS_A (stmt, stmt_block))
800 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
801 compute_cloog_iv_types (s);
808 compute_cloog_iv_types (stmt->next);
811 /* Free the SCATTERING domain list. */
814 free_scattering (CloogDomainList *scattering)
818 CloogDomain *dom = cloog_domain (scattering);
819 CloogDomainList *next = cloog_next_domain (scattering);
821 cloog_domain_free (dom);
827 /* Initialize Cloog's parameter names from the names used in GIMPLE.
828 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
829 from 0 to scop_nb_loops (scop). */
832 initialize_cloog_names (scop_p scop, CloogProgram *prog)
834 sese region = SCOP_REGION (scop);
836 int nb_iterators = scop_max_loop_depth (scop);
837 int nb_scattering = cloog_program_nb_scattdims (prog);
838 char **iterators = XNEWVEC (char *, nb_iterators * 2);
839 char **scattering = XNEWVEC (char *, nb_scattering);
841 cloog_program_set_names (prog, cloog_names_malloc ());
842 cloog_names_set_nb_parameters (cloog_program_names (prog),
843 VEC_length (tree, SESE_PARAMS (region)));
844 cloog_names_set_parameters (cloog_program_names (prog),
845 SESE_PARAMS_NAMES (region));
847 for (i = 0; i < nb_iterators; i++)
850 iterators[i] = XNEWVEC (char, len);
851 snprintf (iterators[i], len, "git_%d", i);
854 cloog_names_set_nb_iterators (cloog_program_names (prog),
856 cloog_names_set_iterators (cloog_program_names (prog),
859 for (i = 0; i < nb_scattering; i++)
862 scattering[i] = XNEWVEC (char, len);
863 snprintf (scattering[i], len, "scat_%d", i);
866 cloog_names_set_nb_scattering (cloog_program_names (prog),
868 cloog_names_set_scattering (cloog_program_names (prog),
872 /* Build cloog program for SCoP. */
875 build_cloog_prog (scop_p scop, CloogProgram *prog)
878 int max_nb_loops = scop_max_loop_depth (scop);
880 CloogLoop *loop_list = NULL;
881 CloogBlockList *block_list = NULL;
882 CloogDomainList *scattering = NULL;
883 int nbs = 2 * max_nb_loops + 1;
886 cloog_program_set_context
887 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop)));
888 nbs = unify_scattering_dimensions (scop);
889 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
890 cloog_program_set_nb_scattdims (prog, nbs);
891 initialize_cloog_names (scop, prog);
893 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
895 CloogStatement *stmt;
898 /* Dead code elimination: when the domain of a PBB is empty,
899 don't generate code for the PBB. */
900 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
903 /* Build the new statement and its block. */
904 stmt = cloog_statement_alloc (pbb_index (pbb));
905 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
906 cloog_statement_set_usr (stmt, pbb);
908 /* Build loop list. */
910 CloogLoop *new_loop_list = cloog_loop_malloc ();
911 cloog_loop_set_next (new_loop_list, loop_list);
912 cloog_loop_set_domain
914 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb)));
915 cloog_loop_set_block (new_loop_list, block);
916 loop_list = new_loop_list;
919 /* Build block list. */
921 CloogBlockList *new_block_list = cloog_block_list_malloc ();
923 cloog_block_list_set_next (new_block_list, block_list);
924 cloog_block_list_set_block (new_block_list, block);
925 block_list = new_block_list;
928 /* Build scattering list. */
930 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
931 CloogDomainList *new_scattering
932 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
933 ppl_Polyhedron_t scat;
936 scat = PBB_TRANSFORMED_SCATTERING (pbb);
937 dom = new_Cloog_Domain_from_ppl_Polyhedron (scat);
939 cloog_set_next_domain (new_scattering, scattering);
940 cloog_set_domain (new_scattering, dom);
941 scattering = new_scattering;
945 cloog_program_set_loop (prog, loop_list);
946 cloog_program_set_blocklist (prog, block_list);
948 for (i = 0; i < nbs; i++)
951 cloog_program_set_scaldims (prog, scaldims);
953 /* Extract scalar dimensions to simplify the code generation problem. */
954 cloog_program_extract_scalars (prog, scattering);
956 /* Apply scattering. */
957 cloog_program_scatter (prog, scattering);
958 free_scattering (scattering);
960 /* Iterators corresponding to scalar dimensions have to be extracted. */
961 cloog_names_scalarize (cloog_program_names (prog), nbs,
962 cloog_program_scaldims (prog));
964 /* Free blocklist. */
966 CloogBlockList *next = cloog_program_blocklist (prog);
970 CloogBlockList *toDelete = next;
971 next = cloog_block_list_next (next);
972 cloog_block_list_set_next (toDelete, NULL);
973 cloog_block_list_set_block (toDelete, NULL);
974 cloog_block_list_free (toDelete);
976 cloog_program_set_blocklist (prog, NULL);
980 /* Return the options that will be used in GLOOG. */
982 static CloogOptions *
983 set_cloog_options (void)
985 CloogOptions *options = cloog_options_malloc ();
987 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
988 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
989 we pass an incomplete program to cloog. */
990 options->language = LANGUAGE_C;
992 /* Enable complex equality spreading: removes dummy statements
993 (assignments) in the generated code which repeats the
994 substitution equations for statements. This is useless for
998 /* Enable C pretty-printing mode: normalizes the substitution
999 equations for statements. */
1002 /* Allow cloog to build strides with a stride width different to one.
1003 This example has stride = 4:
1005 for (i = 0; i < 20; i += 4)
1007 options->strides = 1;
1009 /* Disable optimizations and make cloog generate source code closer to the
1010 input. This is useful for debugging, but later we want the optimized
1013 XXX: We can not disable optimizations, as loop blocking is not working
1018 options->l = INT_MAX;
1024 /* Prints STMT to STDERR. */
1027 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1029 CloogOptions *options = set_cloog_options ();
1031 pprint (file, stmt, 0, options);
1032 cloog_options_free (options);
1035 /* Prints STMT to STDERR. */
1038 debug_clast_stmt (struct clast_stmt *stmt)
1040 print_clast_stmt (stderr, stmt);
1043 /* Translate SCOP to a CLooG program and clast. These two
1044 representations should be freed together: a clast cannot be used
1045 without a program. */
1048 scop_to_clast (scop_p scop)
1050 CloogOptions *options = set_cloog_options ();
1051 cloog_prog_clast pc;
1053 /* Connect new cloog prog generation to graphite. */
1054 pc.prog = cloog_program_malloc ();
1055 build_cloog_prog (scop, pc.prog);
1056 pc.prog = cloog_program_generate (pc.prog, options);
1057 pc.stmt = cloog_clast_create (pc.prog, options);
1059 cloog_options_free (options);
1063 /* Prints to FILE the code generated by CLooG for SCOP. */
1066 print_generated_program (FILE *file, scop_p scop)
1068 CloogOptions *options = set_cloog_options ();
1069 cloog_prog_clast pc = scop_to_clast (scop);
1071 fprintf (file, " (prog: \n");
1072 cloog_program_print (file, pc.prog);
1073 fprintf (file, " )\n");
1075 fprintf (file, " (clast: \n");
1076 pprint (file, pc.stmt, 0, options);
1077 fprintf (file, " )\n");
1079 cloog_options_free (options);
1080 cloog_clast_free (pc.stmt);
1081 cloog_program_free (pc.prog);
1084 /* Prints to STDERR the code generated by CLooG for SCOP. */
1087 debug_generated_program (scop_p scop)
1089 print_generated_program (stderr, scop);
1092 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1093 the given SCOP. Return true if code generation succeeded.
1094 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1098 gloog (scop_p scop, htab_t bb_pbb_mapping)
1100 edge new_scop_exit_edge = NULL;
1101 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1102 loop_p context_loop;
1103 sese region = SCOP_REGION (scop);
1104 ifsese if_region = NULL;
1105 htab_t rename_map, newivs_index;
1106 cloog_prog_clast pc;
1108 timevar_push (TV_GRAPHITE_CODE_GEN);
1110 pc = scop_to_clast (scop);
1112 if (dump_file && (dump_flags & TDF_DETAILS))
1114 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1115 print_clast_stmt (dump_file, pc.stmt);
1116 fprintf (dump_file, "\n");
1119 recompute_all_dominators ();
1122 if_region = move_sese_in_condition (region);
1123 sese_insert_phis_for_liveouts (region,
1124 if_region->region->exit->src,
1125 if_region->false_region->exit,
1126 if_region->true_region->exit);
1128 recompute_all_dominators ();
1130 context_loop = SESE_ENTRY (region)->src->loop_father;
1131 compute_cloog_iv_types (pc.stmt);
1133 rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
1134 newivs_index = htab_create (10, clast_name_index_elt_info,
1135 eq_clast_name_indexes, free);
1137 new_scop_exit_edge = translate_clast (region, context_loop, pc.stmt,
1138 if_region->true_region->entry,
1139 rename_map, &newivs, newivs_index,
1141 sese_reset_aux_in_loops (region);
1143 sese_adjust_liveout_phis (region, rename_map,
1144 if_region->region->exit->src,
1145 if_region->false_region->exit,
1146 if_region->true_region->exit);
1147 recompute_all_dominators ();
1150 htab_delete (rename_map);
1151 htab_delete (newivs_index);
1152 VEC_free (tree, heap, newivs);
1153 cloog_clast_free (pc.stmt);
1154 cloog_program_free (pc.prog);
1155 timevar_pop (TV_GRAPHITE_CODE_GEN);
1162 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
1165 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
1171 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
1174 return ((bb_pbb_def *) *slot)->pbb;
1179 /* Check data dependency in LOOP. BB_PBB_MAPPING is a basic_block and
1180 it's related poly_bb_p mapping.
1184 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping)
1188 basic_block *bbs = get_loop_body_in_dom_order (loop);
1190 level = *((int *)(loop->aux));
1192 for (i = 0; i < loop->num_nodes; i++)
1194 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
1199 for (j = 0; j < loop->num_nodes; j++)
1201 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
1206 if (dependency_between_pbbs_p (pbb1, pbb2, level))
1219 /* Mark loop as parallel if data dependency does not exist.
1220 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1223 void mark_loops_parallel (htab_t bb_pbb_mapping)
1227 int num_no_dependency = 0;
1229 FOR_EACH_LOOP (li, loop, 0)
1231 && !dependency_in_loop_p (loop, bb_pbb_mapping))
1233 loop->can_be_parallel = true;
1234 num_no_dependency++;
1237 if (dump_file && (dump_flags & TDF_DETAILS))
1238 fprintf (dump_file, "\n%d loops carried no dependency.\n",