1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-dependences.h"
55 /* This flag is set when an error occurred during the translation of
57 static bool gloog_error
;
59 /* Verifies properties that GRAPHITE should maintain during translation. */
62 graphite_verify (void)
64 #ifdef ENABLE_CHECKING
65 verify_loop_structure ();
66 verify_dominators (CDI_DOMINATORS
);
67 verify_dominators (CDI_POST_DOMINATORS
);
68 verify_loop_closed_ssa (true);
72 /* Stores the INDEX in a vector for a given clast NAME. */
74 typedef struct clast_name_index
{
77 } *clast_name_index_p
;
79 /* Returns a pointer to a new element of type clast_name_index_p built
80 from NAME and INDEX. */
82 static inline clast_name_index_p
83 new_clast_name_index (const char *name
, int index
)
85 clast_name_index_p res
= XNEW (struct clast_name_index
);
92 /* For a given clast NAME, returns -1 if it does not correspond to any
93 parameter, or otherwise, returns the index in the PARAMS or
94 SCATTERING_DIMENSIONS vector. */
97 clast_name_to_index (const char *name
, htab_t index_table
)
99 struct clast_name_index tmp
;
103 slot
= htab_find_slot (index_table
, &tmp
, NO_INSERT
);
106 return ((struct clast_name_index
*) *slot
)->index
;
111 /* Records in INDEX_TABLE the INDEX for NAME. */
114 save_clast_name_index (htab_t index_table
, const char *name
, int index
)
116 struct clast_name_index tmp
;
120 slot
= htab_find_slot (index_table
, &tmp
, INSERT
);
127 *slot
= new_clast_name_index (name
, index
);
131 /* Print to stderr the element ELT. */
134 debug_clast_name_index (clast_name_index_p elt
)
136 fprintf (stderr
, "(index = %d, name = %s)\n", elt
->index
, elt
->name
);
139 /* Helper function for debug_rename_map. */
142 debug_clast_name_indexes_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
144 struct clast_name_index
*entry
= (struct clast_name_index
*) *slot
;
145 debug_clast_name_index (entry
);
149 /* Print to stderr all the elements of MAP. */
152 debug_clast_name_indexes (htab_t map
)
154 htab_traverse (map
, debug_clast_name_indexes_1
, NULL
);
157 /* Computes a hash function for database element ELT. */
159 static inline hashval_t
160 clast_name_index_elt_info (const void *elt
)
162 return htab_hash_pointer (((const struct clast_name_index
*) elt
)->name
);
165 /* Compares database elements E1 and E2. */
168 eq_clast_name_indexes (const void *e1
, const void *e2
)
170 const struct clast_name_index
*elt1
= (const struct clast_name_index
*) e1
;
171 const struct clast_name_index
*elt2
= (const struct clast_name_index
*) e2
;
173 return (elt1
->name
== elt2
->name
);
177 /* For a given loop DEPTH in the loop nest of the original black box
178 PBB, return the old induction variable associated to that loop. */
181 pbb_to_depth_to_oldiv (poly_bb_p pbb
, int depth
)
183 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
184 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
185 loop_p loop
= gbb_loop_at_index (gbb
, region
, depth
);
187 return loop
->single_iv
;
190 /* For a given scattering dimension, return the new induction variable
194 newivs_to_depth_to_newiv (VEC (tree
, heap
) *newivs
, int depth
)
196 return VEC_index (tree
, newivs
, depth
);
201 /* Returns the tree variable from the name NAME that was given in
202 Cloog representation. */
205 clast_name_to_gcc (const char *name
, sese region
, VEC (tree
, heap
) *newivs
,
206 htab_t newivs_index
, htab_t params_index
)
209 VEC (tree
, heap
) *params
= SESE_PARAMS (region
);
211 if (params
&& params_index
)
213 index
= clast_name_to_index (name
, params_index
);
216 return VEC_index (tree
, params
, index
);
219 gcc_assert (newivs
&& newivs_index
);
220 index
= clast_name_to_index (name
, newivs_index
);
221 gcc_assert (index
>= 0);
223 return newivs_to_depth_to_newiv (newivs
, index
);
226 /* Returns the maximal precision type for expressions E1 and E2. */
229 max_precision_type (tree e1
, tree e2
)
231 tree type1
= TREE_TYPE (e1
);
232 tree type2
= TREE_TYPE (e2
);
233 return TYPE_PRECISION (type1
) > TYPE_PRECISION (type2
) ? type1
: type2
;
237 clast_to_gcc_expression (tree
, struct clast_expr
*, sese
, VEC (tree
, heap
) *,
240 /* Converts a Cloog reduction expression R with reduction operation OP
241 to a GCC expression tree of type TYPE. */
244 clast_to_gcc_expression_red (tree type
, enum tree_code op
,
245 struct clast_reduction
*r
,
246 sese region
, VEC (tree
, heap
) *newivs
,
247 htab_t newivs_index
, htab_t params_index
)
250 tree res
= clast_to_gcc_expression (type
, r
->elts
[0], region
, newivs
,
251 newivs_index
, params_index
);
252 tree operand_type
= (op
== POINTER_PLUS_EXPR
) ? sizetype
: type
;
254 for (i
= 1; i
< r
->n
; i
++)
256 tree t
= clast_to_gcc_expression (operand_type
, r
->elts
[i
], region
,
257 newivs
, newivs_index
, params_index
);
258 res
= fold_build2 (op
, type
, res
, t
);
264 /* Converts a Cloog AST expression E back to a GCC expression tree of
268 clast_to_gcc_expression (tree type
, struct clast_expr
*e
,
269 sese region
, VEC (tree
, heap
) *newivs
,
270 htab_t newivs_index
, htab_t params_index
)
276 struct clast_term
*t
= (struct clast_term
*) e
;
280 if (value_one_p (t
->val
))
282 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
283 newivs_index
, params_index
);
285 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
286 name
= fold_convert (sizetype
, name
);
288 name
= fold_convert (type
, name
);
292 else if (value_mone_p (t
->val
))
294 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
295 newivs_index
, params_index
);
297 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
298 name
= fold_convert (sizetype
, name
);
300 name
= fold_convert (type
, name
);
302 return fold_build1 (NEGATE_EXPR
, type
, name
);
306 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
307 newivs_index
, params_index
);
308 tree cst
= gmp_cst_to_tree (type
, t
->val
);
310 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
311 name
= fold_convert (sizetype
, name
);
313 name
= fold_convert (type
, name
);
315 if (!POINTER_TYPE_P (type
))
316 return fold_build2 (MULT_EXPR
, type
, cst
, name
);
323 return gmp_cst_to_tree (type
, t
->val
);
328 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
333 return clast_to_gcc_expression_red
334 (type
, POINTER_TYPE_P (type
) ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
335 r
, region
, newivs
, newivs_index
, params_index
);
338 return clast_to_gcc_expression_red (type
, MIN_EXPR
, r
, region
,
339 newivs
, newivs_index
,
343 return clast_to_gcc_expression_red (type
, MAX_EXPR
, r
, region
,
344 newivs
, newivs_index
,
355 struct clast_binary
*b
= (struct clast_binary
*) e
;
356 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
357 tree tl
= clast_to_gcc_expression (type
, lhs
, region
, newivs
,
358 newivs_index
, params_index
);
359 tree tr
= gmp_cst_to_tree (type
, b
->RHS
);
364 return fold_build2 (FLOOR_DIV_EXPR
, type
, tl
, tr
);
367 return fold_build2 (CEIL_DIV_EXPR
, type
, tl
, tr
);
370 return fold_build2 (EXACT_DIV_EXPR
, type
, tl
, tr
);
373 return fold_build2 (TRUNC_MOD_EXPR
, type
, tl
, tr
);
387 /* Returns the type for the expression E. */
390 gcc_type_for_clast_expr (struct clast_expr
*e
,
391 sese region
, VEC (tree
, heap
) *newivs
,
392 htab_t newivs_index
, htab_t params_index
)
398 struct clast_term
*t
= (struct clast_term
*) e
;
401 return TREE_TYPE (clast_name_to_gcc (t
->var
, region
, newivs
,
402 newivs_index
, params_index
));
409 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
412 return gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
413 newivs_index
, params_index
);
417 for (i
= 0; i
< r
->n
; i
++)
419 tree type
= gcc_type_for_clast_expr (r
->elts
[i
], region
,
420 newivs
, newivs_index
,
431 struct clast_binary
*b
= (struct clast_binary
*) e
;
432 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
433 return gcc_type_for_clast_expr (lhs
, region
, newivs
,
434 newivs_index
, params_index
);
444 /* Returns the type for the equation CLEQ. */
447 gcc_type_for_clast_eq (struct clast_equation
*cleq
,
448 sese region
, VEC (tree
, heap
) *newivs
,
449 htab_t newivs_index
, htab_t params_index
)
451 tree type
= gcc_type_for_clast_expr (cleq
->LHS
, region
, newivs
,
452 newivs_index
, params_index
);
456 return gcc_type_for_clast_expr (cleq
->RHS
, region
, newivs
, newivs_index
,
460 /* Translates a clast equation CLEQ to a tree. */
463 graphite_translate_clast_equation (sese region
,
464 struct clast_equation
*cleq
,
465 VEC (tree
, heap
) *newivs
,
466 htab_t newivs_index
, htab_t params_index
)
469 tree type
= gcc_type_for_clast_eq (cleq
, region
, newivs
, newivs_index
,
471 tree lhs
= clast_to_gcc_expression (type
, cleq
->LHS
, region
, newivs
,
472 newivs_index
, params_index
);
473 tree rhs
= clast_to_gcc_expression (type
, cleq
->RHS
, region
, newivs
,
474 newivs_index
, params_index
);
479 else if (cleq
->sign
> 0)
485 return fold_build2 (comp
, boolean_type_node
, lhs
, rhs
);
488 /* Creates the test for the condition in STMT. */
491 graphite_create_guard_cond_expr (sese region
, struct clast_guard
*stmt
,
492 VEC (tree
, heap
) *newivs
,
493 htab_t newivs_index
, htab_t params_index
)
498 for (i
= 0; i
< stmt
->n
; i
++)
500 tree eq
= graphite_translate_clast_equation (region
, &stmt
->eq
[i
],
501 newivs
, newivs_index
,
505 cond
= fold_build2 (TRUTH_AND_EXPR
, TREE_TYPE (eq
), cond
, eq
);
513 /* Creates a new if region corresponding to Cloog's guard. */
516 graphite_create_new_guard (sese region
, edge entry_edge
,
517 struct clast_guard
*stmt
,
518 VEC (tree
, heap
) *newivs
,
519 htab_t newivs_index
, htab_t params_index
)
521 tree cond_expr
= graphite_create_guard_cond_expr (region
, stmt
, newivs
,
522 newivs_index
, params_index
);
523 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
527 /* Walks a CLAST and returns the first statement in the body of a
530 static struct clast_user_stmt
*
531 clast_get_body_of_loop (struct clast_stmt
*stmt
)
534 || CLAST_STMT_IS_A (stmt
, stmt_user
))
535 return (struct clast_user_stmt
*) stmt
;
537 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
538 return clast_get_body_of_loop (((struct clast_for
*) stmt
)->body
);
540 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
541 return clast_get_body_of_loop (((struct clast_guard
*) stmt
)->then
);
543 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
544 return clast_get_body_of_loop (((struct clast_block
*) stmt
)->body
);
549 /* Java does not initialize long_long_integer_type_node. */
550 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
552 /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
553 land. The selected type is big enough to include the original loop
554 iteration variable, but signed to work with the subtractions CLooG
555 may have introduced. If such a type is not available, we fail.
557 TODO: Do not always return long_long, but the smallest possible
558 type, that still holds the original type.
560 TODO: Get the types using CLooG instead. This enables further
561 optimizations, but needs CLooG support. */
564 gcc_type_for_cloog_iv (const char *cloog_iv
, gimple_bb_p gbb
)
566 struct ivtype_map_elt_s tmp
;
569 tmp
.cloog_iv
= cloog_iv
;
570 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, NO_INSERT
);
574 tree type
= ((ivtype_map_elt
) *slot
)->type
;
575 int type_precision
= TYPE_PRECISION (type
);
577 /* Find the smallest signed type possible. */
578 if (!TYPE_UNSIGNED (type
))
580 if (type_precision
<= TYPE_PRECISION (integer_type_node
))
581 return integer_type_node
;
583 if (type_precision
<= TYPE_PRECISION (long_integer_type_node
))
584 return long_integer_type_node
;
586 if (type_precision
<= TYPE_PRECISION (my_long_long
))
592 if (type_precision
< TYPE_PRECISION (integer_type_node
))
593 return integer_type_node
;
595 if (type_precision
< TYPE_PRECISION (long_integer_type_node
))
596 return long_integer_type_node
;
598 if (type_precision
< TYPE_PRECISION (my_long_long
))
601 /* There is no signed type available, that is large enough to hold the
611 /* Returns the induction variable for the loop that gets translated to
615 gcc_type_for_iv_of_clast_loop (struct clast_for
*stmt_for
)
617 struct clast_stmt
*stmt
= (struct clast_stmt
*) stmt_for
;
618 struct clast_user_stmt
*body
= clast_get_body_of_loop (stmt
);
619 const char *cloog_iv
= stmt_for
->iterator
;
620 CloogStatement
*cs
= body
->statement
;
621 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
623 return gcc_type_for_cloog_iv (cloog_iv
, PBB_BLACK_BOX (pbb
));
626 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
627 induction variable for the new LOOP. New LOOP is attached to CFG
628 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
629 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
630 CLooG's scattering name to the induction variable created for the
631 loop of STMT. The new induction variable is inserted in the NEWIVS
635 graphite_create_new_loop (sese region
, edge entry_edge
,
636 struct clast_for
*stmt
,
637 loop_p outer
, VEC (tree
, heap
) **newivs
,
638 htab_t newivs_index
, htab_t params_index
)
640 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
641 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, *newivs
,
642 newivs_index
, params_index
);
643 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, *newivs
,
644 newivs_index
, params_index
);
645 tree stride
= gmp_cst_to_tree (type
, stmt
->stride
);
646 tree ivvar
= create_tmp_var (type
, "graphite_IV");
647 tree iv
, iv_after_increment
;
648 loop_p loop
= create_empty_loop_on_edge
649 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
650 outer
? outer
: entry_edge
->src
->loop_father
);
652 add_referenced_var (ivvar
);
654 save_clast_name_index (newivs_index
, stmt
->iterator
,
655 VEC_length (tree
, *newivs
));
656 VEC_safe_push (tree
, heap
, *newivs
, iv
);
660 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
661 variables of the loops around GBB in SESE. */
664 build_iv_mapping (htab_t map
, sese region
,
665 VEC (tree
, heap
) *newivs
, htab_t newivs_index
,
666 struct clast_user_stmt
*user_stmt
,
669 struct clast_stmt
*t
;
671 CloogStatement
*cs
= user_stmt
->statement
;
672 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
674 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
676 struct clast_expr
*expr
= (struct clast_expr
*)
677 ((struct clast_assignment
*)t
)->RHS
;
678 tree type
= gcc_type_for_clast_expr (expr
, region
, newivs
,
679 newivs_index
, params_index
);
680 tree old_name
= pbb_to_depth_to_oldiv (pbb
, index
);
681 tree e
= clast_to_gcc_expression (type
, expr
, region
, newivs
,
682 newivs_index
, params_index
);
683 set_rename (map
, old_name
, e
);
687 /* Helper function for htab_traverse. */
690 copy_renames (void **slot
, void *s
)
692 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
693 htab_t res
= (htab_t
) s
;
694 tree old_name
= entry
->old_name
;
695 tree expr
= entry
->expr
;
696 struct rename_map_elt_s tmp
;
699 tmp
.old_name
= old_name
;
700 x
= htab_find_slot (res
, &tmp
, INSERT
);
703 *x
= new_rename_map_elt (old_name
, expr
);
708 /* Construct bb_pbb_def with BB and PBB. */
711 new_bb_pbb_def (basic_block bb
, poly_bb_p pbb
)
713 bb_pbb_def
*bb_pbb_p
;
715 bb_pbb_p
= XNEW (bb_pbb_def
);
722 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
725 mark_bb_with_pbb (poly_bb_p pbb
, basic_block bb
, htab_t bb_pbb_mapping
)
731 x
= htab_find_slot (bb_pbb_mapping
, &tmp
, INSERT
);
734 *x
= new_bb_pbb_def (bb
, pbb
);
737 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
740 find_pbb_via_hash (htab_t bb_pbb_mapping
, basic_block bb
)
746 slot
= htab_find_slot (bb_pbb_mapping
, &tmp
, NO_INSERT
);
749 return ((bb_pbb_def
*) *slot
)->pbb
;
754 /* Check data dependency in LOOP at scattering level LEVEL.
755 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
759 dependency_in_loop_p (loop_p loop
, htab_t bb_pbb_mapping
, int level
)
762 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
764 for (i
= 0; i
< loop
->num_nodes
; i
++)
766 poly_bb_p pbb1
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[i
]);
771 for (j
= 0; j
< loop
->num_nodes
; j
++)
773 poly_bb_p pbb2
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[j
]);
778 if (dependency_between_pbbs_p (pbb1
, pbb2
, level
))
792 translate_clast (sese
, loop_p
, struct clast_stmt
*, edge
, htab_t
,
793 VEC (tree
, heap
) **, htab_t
, htab_t
, int, htab_t
);
795 /* Translates a clast user statement STMT to gimple.
797 - REGION is the sese region we used to generate the scop.
798 - NEXT_E is the edge where new generated code should be attached.
799 - CONTEXT_LOOP is the loop in which the generated code will be placed
800 - RENAME_MAP contains a set of tuples of new names associated to
801 the original variables names.
802 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
803 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
806 translate_clast_user (sese region
, struct clast_user_stmt
*stmt
, edge next_e
,
807 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
808 htab_t newivs_index
, htab_t bb_pbb_mapping
,
813 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (stmt
->statement
);
814 gbb
= PBB_BLACK_BOX (pbb
);
816 if (GBB_BB (gbb
) == ENTRY_BLOCK_PTR
)
819 build_iv_mapping (rename_map
, region
, *newivs
, newivs_index
, stmt
,
821 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), region
,
823 new_bb
= next_e
->src
;
824 mark_bb_with_pbb (pbb
, new_bb
, bb_pbb_mapping
);
825 update_ssa (TODO_update_ssa
);
830 /* Creates a new if region protecting the loop to be executed, if the execution
831 count is zero (lb > ub). */
833 graphite_create_new_loop_guard (sese region
, edge entry_edge
,
834 struct clast_for
*stmt
,
835 VEC (tree
, heap
) *newivs
,
836 htab_t newivs_index
, htab_t params_index
)
840 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
841 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, newivs
,
842 newivs_index
, params_index
);
843 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, newivs
,
844 newivs_index
, params_index
);
846 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
847 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
848 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
849 However lb < ub + 1 is false, as expected.
850 There might be a problem with cases where ub is 2^32. */
853 value_init (gmp_one
);
854 value_set_si (gmp_one
, 1);
855 one
= gmp_cst_to_tree (type
, gmp_one
);
856 value_clear (gmp_one
);
858 ub
= fold_build2 (PLUS_EXPR
, type
, ub
, one
);
859 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, lb
, ub
);
861 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
867 /* Create the loop for a clast for statement.
869 - REGION is the sese region we used to generate the scop.
870 - NEXT_E is the edge where new generated code should be attached.
871 - RENAME_MAP contains a set of tuples of new names associated to
872 the original variables names.
873 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
874 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
877 translate_clast_for_loop (sese region
, loop_p context_loop
,
878 struct clast_for
*stmt
, edge next_e
,
879 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
880 htab_t newivs_index
, htab_t bb_pbb_mapping
,
881 int level
, htab_t params_index
)
883 struct loop
*loop
= graphite_create_new_loop (region
, next_e
, stmt
,
884 context_loop
, newivs
,
885 newivs_index
, params_index
);
886 edge last_e
= single_exit (loop
);
887 edge to_body
= single_succ_edge (loop
->header
);
888 basic_block after
= to_body
->dest
;
890 /* Create a basic block for loop close phi nodes. */
891 last_e
= single_succ_edge (split_edge (last_e
));
893 /* Translate the body of the loop. */
894 next_e
= translate_clast (region
, loop
, stmt
->body
, to_body
, rename_map
,
895 newivs
, newivs_index
, bb_pbb_mapping
, level
+ 1,
897 redirect_edge_succ_nodup (next_e
, after
);
898 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
900 /* Remove from rename_map all the tuples containing variables
901 defined in loop's body. */
902 insert_loop_close_phis (rename_map
, loop
);
904 if (flag_loop_parallelize_all
905 && !dependency_in_loop_p (loop
, bb_pbb_mapping
,
906 get_scattering_level (level
)))
907 loop
->can_be_parallel
= true;
912 /* Translates a clast for statement STMT to gimple. First a guard is created
913 protecting the loop, if it is executed zero times. In this guard we create
914 the real loop structure.
916 - REGION is the sese region we used to generate the scop.
917 - NEXT_E is the edge where new generated code should be attached.
918 - RENAME_MAP contains a set of tuples of new names associated to
919 the original variables names.
920 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
921 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
924 translate_clast_for (sese region
, loop_p context_loop
, struct clast_for
*stmt
,
925 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
926 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
929 edge last_e
= graphite_create_new_loop_guard (region
, next_e
, stmt
, *newivs
,
930 newivs_index
, params_index
);
932 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
933 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
934 edge exit_true_e
= single_succ_edge (true_e
->dest
);
935 edge exit_false_e
= single_succ_edge (false_e
->dest
);
937 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
938 eq_rename_map_elts
, free
);
939 htab_traverse (rename_map
, copy_renames
, before_guard
);
941 next_e
= translate_clast_for_loop (region
, context_loop
, stmt
, true_e
,
943 newivs_index
, bb_pbb_mapping
, level
,
946 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
947 before_guard
, rename_map
);
949 htab_delete (before_guard
);
954 /* Translates a clast guard statement STMT to gimple.
956 - REGION is the sese region we used to generate the scop.
957 - NEXT_E is the edge where new generated code should be attached.
958 - CONTEXT_LOOP is the loop in which the generated code will be placed
959 - RENAME_MAP contains a set of tuples of new names associated to
960 the original variables names.
961 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
962 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
965 translate_clast_guard (sese region
, loop_p context_loop
,
966 struct clast_guard
*stmt
, edge next_e
,
967 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
968 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
971 edge last_e
= graphite_create_new_guard (region
, next_e
, stmt
, *newivs
,
972 newivs_index
, params_index
);
974 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
975 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
976 edge exit_true_e
= single_succ_edge (true_e
->dest
);
977 edge exit_false_e
= single_succ_edge (false_e
->dest
);
979 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
980 eq_rename_map_elts
, free
);
981 htab_traverse (rename_map
, copy_renames
, before_guard
);
983 next_e
= translate_clast (region
, context_loop
, stmt
->then
, true_e
,
984 rename_map
, newivs
, newivs_index
, bb_pbb_mapping
,
985 level
, params_index
);
987 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
988 before_guard
, rename_map
);
990 htab_delete (before_guard
);
995 /* Translates a CLAST statement STMT to GCC representation in the
998 - NEXT_E is the edge where new generated code should be attached.
999 - CONTEXT_LOOP is the loop in which the generated code will be placed
1000 - RENAME_MAP contains a set of tuples of new names associated to
1001 the original variables names.
1002 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1004 translate_clast (sese region
, loop_p context_loop
, struct clast_stmt
*stmt
,
1005 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
1006 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
1007 htab_t params_index
)
1012 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1015 else if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1016 next_e
= translate_clast_user (region
, (struct clast_user_stmt
*) stmt
,
1017 next_e
, rename_map
, newivs
, newivs_index
,
1018 bb_pbb_mapping
, params_index
);
1020 else if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1021 next_e
= translate_clast_for (region
, context_loop
,
1022 (struct clast_for
*) stmt
, next_e
,
1023 rename_map
, newivs
, newivs_index
,
1024 bb_pbb_mapping
, level
, params_index
);
1026 else if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1027 next_e
= translate_clast_guard (region
, context_loop
,
1028 (struct clast_guard
*) stmt
, next_e
,
1029 rename_map
, newivs
, newivs_index
,
1030 bb_pbb_mapping
, level
, params_index
);
1032 else if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1033 next_e
= translate_clast (region
, context_loop
,
1034 ((struct clast_block
*) stmt
)->body
,
1035 next_e
, rename_map
, newivs
, newivs_index
,
1036 bb_pbb_mapping
, level
, params_index
);
1040 recompute_all_dominators ();
1043 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
1044 rename_map
, newivs
, newivs_index
,
1045 bb_pbb_mapping
, level
, params_index
);
1048 /* Returns the first cloog name used in EXPR. */
1051 find_cloog_iv_in_expr (struct clast_expr
*expr
)
1053 struct clast_term
*term
= (struct clast_term
*) expr
;
1054 struct clast_reduction
*red
;
1057 if (expr
->type
== expr_term
)
1060 if (expr
->type
!= expr_red
)
1063 red
= (struct clast_reduction
*) expr
;
1064 for (i
= 0; i
< red
->n
; i
++)
1066 const char *res
= find_cloog_iv_in_expr (red
->elts
[i
]);
1075 /* Build for USER_STMT a map between the CLAST induction variables and
1076 the corresponding GCC old induction variables. This information is
1077 stored on each GRAPHITE_BB. */
1080 compute_cloog_iv_types_1 (poly_bb_p pbb
, struct clast_user_stmt
*user_stmt
)
1082 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1083 struct clast_stmt
*t
;
1086 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
1089 struct ivtype_map_elt_s tmp
;
1090 struct clast_expr
*expr
= (struct clast_expr
*)
1091 ((struct clast_assignment
*)t
)->RHS
;
1093 /* Create an entry (clast_var, type). */
1094 tmp
.cloog_iv
= find_cloog_iv_in_expr (expr
);
1098 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, INSERT
);
1102 tree oldiv
= pbb_to_depth_to_oldiv (pbb
, index
);
1103 tree type
= TREE_TYPE (oldiv
);
1104 *slot
= new_ivtype_map_elt (tmp
.cloog_iv
, type
);
1109 /* Walk the CLAST tree starting from STMT and build for each
1110 clast_user_stmt a map between the CLAST induction variables and the
1111 corresponding GCC old induction variables. This information is
1112 stored on each GRAPHITE_BB. */
1115 compute_cloog_iv_types (struct clast_stmt
*stmt
)
1120 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1123 if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1125 CloogStatement
*cs
= ((struct clast_user_stmt
*) stmt
)->statement
;
1126 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
1127 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1129 if (!GBB_CLOOG_IV_TYPES (gbb
))
1130 GBB_CLOOG_IV_TYPES (gbb
) = htab_create (10, ivtype_map_elt_info
,
1131 eq_ivtype_map_elts
, free
);
1133 compute_cloog_iv_types_1 (pbb
, (struct clast_user_stmt
*) stmt
);
1137 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1139 struct clast_stmt
*s
= ((struct clast_for
*) stmt
)->body
;
1140 compute_cloog_iv_types (s
);
1144 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1146 struct clast_stmt
*s
= ((struct clast_guard
*) stmt
)->then
;
1147 compute_cloog_iv_types (s
);
1151 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1153 struct clast_stmt
*s
= ((struct clast_block
*) stmt
)->body
;
1154 compute_cloog_iv_types (s
);
1161 compute_cloog_iv_types (stmt
->next
);
1164 /* Free the SCATTERING domain list. */
1167 free_scattering (CloogDomainList
*scattering
)
1171 CloogDomain
*dom
= cloog_domain (scattering
);
1172 CloogDomainList
*next
= cloog_next_domain (scattering
);
1174 cloog_domain_free (dom
);
1180 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1181 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1182 from 0 to scop_nb_loops (scop). */
1185 initialize_cloog_names (scop_p scop
, CloogProgram
*prog
)
1187 sese region
= SCOP_REGION (scop
);
1189 int nb_iterators
= scop_max_loop_depth (scop
);
1190 int nb_scattering
= cloog_program_nb_scattdims (prog
);
1191 int nb_parameters
= VEC_length (tree
, SESE_PARAMS (region
));
1192 char **iterators
= XNEWVEC (char *, nb_iterators
* 2);
1193 char **scattering
= XNEWVEC (char *, nb_scattering
);
1194 char **parameters
= XNEWVEC (char *, nb_parameters
);
1196 cloog_program_set_names (prog
, cloog_names_malloc ());
1198 for (i
= 0; i
< nb_parameters
; i
++)
1200 tree param
= VEC_index (tree
, SESE_PARAMS(region
), i
);
1201 const char *name
= get_name (param
);
1207 len
= strlen (name
);
1209 parameters
[i
] = XNEWVEC (char, len
+ 1);
1210 snprintf (parameters
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (param
));
1213 cloog_names_set_nb_parameters (cloog_program_names (prog
), nb_parameters
);
1214 cloog_names_set_parameters (cloog_program_names (prog
), parameters
);
1216 for (i
= 0; i
< nb_iterators
; i
++)
1219 iterators
[i
] = XNEWVEC (char, len
);
1220 snprintf (iterators
[i
], len
, "git_%d", i
);
1223 cloog_names_set_nb_iterators (cloog_program_names (prog
),
1225 cloog_names_set_iterators (cloog_program_names (prog
),
1228 for (i
= 0; i
< nb_scattering
; i
++)
1231 scattering
[i
] = XNEWVEC (char, len
);
1232 snprintf (scattering
[i
], len
, "scat_%d", i
);
1235 cloog_names_set_nb_scattering (cloog_program_names (prog
),
1237 cloog_names_set_scattering (cloog_program_names (prog
),
1241 /* Build cloog program for SCoP. */
1244 build_cloog_prog (scop_p scop
, CloogProgram
*prog
)
1247 int max_nb_loops
= scop_max_loop_depth (scop
);
1249 CloogLoop
*loop_list
= NULL
;
1250 CloogBlockList
*block_list
= NULL
;
1251 CloogDomainList
*scattering
= NULL
;
1252 int nbs
= 2 * max_nb_loops
+ 1;
1255 cloog_program_set_context
1256 (prog
, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop
)));
1257 nbs
= unify_scattering_dimensions (scop
);
1258 scaldims
= (int *) xmalloc (nbs
* (sizeof (int)));
1259 cloog_program_set_nb_scattdims (prog
, nbs
);
1260 initialize_cloog_names (scop
, prog
);
1262 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1264 CloogStatement
*stmt
;
1267 /* Dead code elimination: when the domain of a PBB is empty,
1268 don't generate code for the PBB. */
1269 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb
)))
1272 /* Build the new statement and its block. */
1273 stmt
= cloog_statement_alloc (pbb_index (pbb
));
1274 block
= cloog_block_alloc (stmt
, 0, NULL
, pbb_dim_iter_domain (pbb
));
1275 cloog_statement_set_usr (stmt
, pbb
);
1277 /* Build loop list. */
1279 CloogLoop
*new_loop_list
= cloog_loop_malloc ();
1280 cloog_loop_set_next (new_loop_list
, loop_list
);
1281 cloog_loop_set_domain
1283 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb
)));
1284 cloog_loop_set_block (new_loop_list
, block
);
1285 loop_list
= new_loop_list
;
1288 /* Build block list. */
1290 CloogBlockList
*new_block_list
= cloog_block_list_malloc ();
1292 cloog_block_list_set_next (new_block_list
, block_list
);
1293 cloog_block_list_set_block (new_block_list
, block
);
1294 block_list
= new_block_list
;
1297 /* Build scattering list. */
1299 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1300 CloogDomainList
*new_scattering
1301 = (CloogDomainList
*) xmalloc (sizeof (CloogDomainList
));
1302 ppl_Polyhedron_t scat
;
1305 scat
= PBB_TRANSFORMED_SCATTERING (pbb
);
1306 dom
= new_Cloog_Domain_from_ppl_Polyhedron (scat
);
1308 cloog_set_next_domain (new_scattering
, scattering
);
1309 cloog_set_domain (new_scattering
, dom
);
1310 scattering
= new_scattering
;
1314 cloog_program_set_loop (prog
, loop_list
);
1315 cloog_program_set_blocklist (prog
, block_list
);
1317 for (i
= 0; i
< nbs
; i
++)
1320 cloog_program_set_scaldims (prog
, scaldims
);
1322 /* Extract scalar dimensions to simplify the code generation problem. */
1323 cloog_program_extract_scalars (prog
, scattering
);
1325 /* Apply scattering. */
1326 cloog_program_scatter (prog
, scattering
);
1327 free_scattering (scattering
);
1329 /* Iterators corresponding to scalar dimensions have to be extracted. */
1330 cloog_names_scalarize (cloog_program_names (prog
), nbs
,
1331 cloog_program_scaldims (prog
));
1333 /* Free blocklist. */
1335 CloogBlockList
*next
= cloog_program_blocklist (prog
);
1339 CloogBlockList
*toDelete
= next
;
1340 next
= cloog_block_list_next (next
);
1341 cloog_block_list_set_next (toDelete
, NULL
);
1342 cloog_block_list_set_block (toDelete
, NULL
);
1343 cloog_block_list_free (toDelete
);
1345 cloog_program_set_blocklist (prog
, NULL
);
1349 /* Return the options that will be used in GLOOG. */
1351 static CloogOptions
*
1352 set_cloog_options (void)
1354 CloogOptions
*options
= cloog_options_malloc ();
1356 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1357 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1358 we pass an incomplete program to cloog. */
1359 options
->language
= LANGUAGE_C
;
1361 /* Enable complex equality spreading: removes dummy statements
1362 (assignments) in the generated code which repeats the
1363 substitution equations for statements. This is useless for
1367 /* Enable C pretty-printing mode: normalizes the substitution
1368 equations for statements. */
1371 /* Allow cloog to build strides with a stride width different to one.
1372 This example has stride = 4:
1374 for (i = 0; i < 20; i += 4)
1376 options
->strides
= 1;
1378 /* Disable optimizations and make cloog generate source code closer to the
1379 input. This is useful for debugging, but later we want the optimized
1382 XXX: We can not disable optimizations, as loop blocking is not working
1387 options
->l
= INT_MAX
;
1393 /* Prints STMT to STDERR. */
1396 print_clast_stmt (FILE *file
, struct clast_stmt
*stmt
)
1398 CloogOptions
*options
= set_cloog_options ();
1400 pprint (file
, stmt
, 0, options
);
1401 cloog_options_free (options
);
1404 /* Prints STMT to STDERR. */
1407 debug_clast_stmt (struct clast_stmt
*stmt
)
1409 print_clast_stmt (stderr
, stmt
);
1412 /* Translate SCOP to a CLooG program and clast. These two
1413 representations should be freed together: a clast cannot be used
1414 without a program. */
1417 scop_to_clast (scop_p scop
)
1419 CloogOptions
*options
= set_cloog_options ();
1420 cloog_prog_clast pc
;
1422 /* Connect new cloog prog generation to graphite. */
1423 pc
.prog
= cloog_program_malloc ();
1424 build_cloog_prog (scop
, pc
.prog
);
1425 pc
.prog
= cloog_program_generate (pc
.prog
, options
);
1426 pc
.stmt
= cloog_clast_create (pc
.prog
, options
);
1428 cloog_options_free (options
);
1432 /* Prints to FILE the code generated by CLooG for SCOP. */
1435 print_generated_program (FILE *file
, scop_p scop
)
1437 CloogOptions
*options
= set_cloog_options ();
1438 cloog_prog_clast pc
= scop_to_clast (scop
);
1440 fprintf (file
, " (prog: \n");
1441 cloog_program_print (file
, pc
.prog
);
1442 fprintf (file
, " )\n");
1444 fprintf (file
, " (clast: \n");
1445 pprint (file
, pc
.stmt
, 0, options
);
1446 fprintf (file
, " )\n");
1448 cloog_options_free (options
);
1449 cloog_clast_free (pc
.stmt
);
1450 cloog_program_free (pc
.prog
);
1453 /* Prints to STDERR the code generated by CLooG for SCOP. */
1456 debug_generated_program (scop_p scop
)
1458 print_generated_program (stderr
, scop
);
1461 /* Add CLooG names to parameter index. The index is used to translate
1462 back from CLooG names to GCC trees. */
1465 create_params_index (htab_t index_table
, CloogProgram
*prog
) {
1466 CloogNames
* names
= cloog_program_names (prog
);
1467 int nb_parameters
= cloog_names_nb_parameters (names
);
1468 char **parameters
= cloog_names_parameters (names
);
1471 for (i
= 0; i
< nb_parameters
; i
++)
1472 save_clast_name_index (index_table
, parameters
[i
], i
);
1475 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1476 the given SCOP. Return true if code generation succeeded.
1477 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1481 gloog (scop_p scop
, VEC (scop_p
, heap
) *scops
, htab_t bb_pbb_mapping
)
1483 VEC (tree
, heap
) *newivs
= VEC_alloc (tree
, heap
, 10);
1484 loop_p context_loop
;
1485 sese region
= SCOP_REGION (scop
);
1486 ifsese if_region
= NULL
;
1487 htab_t rename_map
, newivs_index
, params_index
;
1488 cloog_prog_clast pc
;
1491 timevar_push (TV_GRAPHITE_CODE_GEN
);
1492 gloog_error
= false;
1494 pc
= scop_to_clast (scop
);
1496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1498 fprintf (dump_file
, "\nCLAST generated by CLooG: \n");
1499 print_clast_stmt (dump_file
, pc
.stmt
);
1500 fprintf (dump_file
, "\n");
1503 recompute_all_dominators ();
1506 if_region
= move_sese_in_condition (region
);
1507 sese_insert_phis_for_liveouts (region
,
1508 if_region
->region
->exit
->src
,
1509 if_region
->false_region
->exit
,
1510 if_region
->true_region
->exit
);
1511 recompute_all_dominators ();
1514 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1515 compute_cloog_iv_types (pc
.stmt
);
1516 rename_map
= htab_create (10, rename_map_elt_info
, eq_rename_map_elts
, free
);
1517 newivs_index
= htab_create (10, clast_name_index_elt_info
,
1518 eq_clast_name_indexes
, free
);
1519 params_index
= htab_create (10, clast_name_index_elt_info
,
1520 eq_clast_name_indexes
, free
);
1522 create_params_index (params_index
, pc
.prog
);
1524 translate_clast (region
, context_loop
, pc
.stmt
,
1525 if_region
->true_region
->entry
,
1526 rename_map
, &newivs
, newivs_index
,
1527 bb_pbb_mapping
, 1, params_index
);
1529 sese_adjust_liveout_phis (region
, rename_map
,
1530 if_region
->region
->exit
->src
,
1531 if_region
->false_region
->exit
,
1532 if_region
->true_region
->exit
);
1534 rename_nb_iterations (rename_map
);
1536 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1537 rename_sese_parameters (rename_map
, SCOP_REGION (scop
));
1539 recompute_all_dominators ();
1543 set_ifsese_condition (if_region
, integer_zero_node
);
1545 free (if_region
->true_region
);
1546 free (if_region
->region
);
1549 htab_delete (rename_map
);
1550 htab_delete (newivs_index
);
1551 htab_delete (params_index
);
1552 VEC_free (tree
, heap
, newivs
);
1553 cloog_clast_free (pc
.stmt
);
1554 cloog_program_free (pc
.prog
);
1555 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1561 int num_no_dependency
= 0;
1563 FOR_EACH_LOOP (li
, loop
, 0)
1564 if (loop
->can_be_parallel
)
1565 num_no_dependency
++;
1567 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1571 return !gloog_error
;