1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-dependences.h"
55 /* This flag is set when an error occurred during the translation of
57 static bool gloog_error
;
59 /* Verifies properties that GRAPHITE should maintain during translation. */
62 graphite_verify (void)
64 #ifdef ENABLE_CHECKING
65 verify_loop_structure ();
66 verify_dominators (CDI_DOMINATORS
);
67 verify_dominators (CDI_POST_DOMINATORS
);
69 verify_loop_closed_ssa ();
73 /* Stores the INDEX in a vector for a given clast NAME. */
75 typedef struct clast_name_index
{
78 } *clast_name_index_p
;
80 /* Returns a pointer to a new element of type clast_name_index_p built
81 from NAME and INDEX. */
83 static inline clast_name_index_p
84 new_clast_name_index (const char *name
, int index
)
86 clast_name_index_p res
= XNEW (struct clast_name_index
);
93 /* For a given clast NAME, returns -1 if it does not correspond to any
94 parameter, or otherwise, returns the index in the PARAMS or
95 SCATTERING_DIMENSIONS vector. */
98 clast_name_to_index (const char *name
, htab_t index_table
)
100 struct clast_name_index tmp
;
104 slot
= htab_find_slot (index_table
, &tmp
, NO_INSERT
);
107 return ((struct clast_name_index
*) *slot
)->index
;
112 /* Records in INDEX_TABLE the INDEX for NAME. */
115 save_clast_name_index (htab_t index_table
, const char *name
, int index
)
117 struct clast_name_index tmp
;
121 slot
= htab_find_slot (index_table
, &tmp
, INSERT
);
128 *slot
= new_clast_name_index (name
, index
);
132 /* Print to stderr the element ELT. */
135 debug_clast_name_index (clast_name_index_p elt
)
137 fprintf (stderr
, "(index = %d, name = %s)\n", elt
->index
, elt
->name
);
140 /* Helper function for debug_rename_map. */
143 debug_clast_name_indexes_1 (void **slot
, void *s ATTRIBUTE_UNUSED
)
145 struct clast_name_index
*entry
= (struct clast_name_index
*) *slot
;
146 debug_clast_name_index (entry
);
150 /* Print to stderr all the elements of MAP. */
153 debug_clast_name_indexes (htab_t map
)
155 htab_traverse (map
, debug_clast_name_indexes_1
, NULL
);
158 /* Computes a hash function for database element ELT. */
160 static inline hashval_t
161 clast_name_index_elt_info (const void *elt
)
163 return htab_hash_pointer (((const struct clast_name_index
*) elt
)->name
);
166 /* Compares database elements E1 and E2. */
169 eq_clast_name_indexes (const void *e1
, const void *e2
)
171 const struct clast_name_index
*elt1
= (const struct clast_name_index
*) e1
;
172 const struct clast_name_index
*elt2
= (const struct clast_name_index
*) e2
;
174 return (elt1
->name
== elt2
->name
);
178 /* For a given loop DEPTH in the loop nest of the original black box
179 PBB, return the old induction variable associated to that loop. */
182 pbb_to_depth_to_oldiv (poly_bb_p pbb
, int depth
)
184 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
185 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
186 loop_p loop
= gbb_loop_at_index (gbb
, region
, depth
);
188 return loop
->single_iv
;
191 /* For a given scattering dimension, return the new induction variable
195 newivs_to_depth_to_newiv (VEC (tree
, heap
) *newivs
, int depth
)
197 return VEC_index (tree
, newivs
, depth
);
202 /* Returns the tree variable from the name NAME that was given in
203 Cloog representation. */
206 clast_name_to_gcc (const char *name
, sese region
, VEC (tree
, heap
) *newivs
,
207 htab_t newivs_index
, htab_t params_index
)
210 VEC (tree
, heap
) *params
= SESE_PARAMS (region
);
212 if (params
&& params_index
)
214 index
= clast_name_to_index (name
, params_index
);
217 return VEC_index (tree
, params
, index
);
220 gcc_assert (newivs
&& newivs_index
);
221 index
= clast_name_to_index (name
, newivs_index
);
222 gcc_assert (index
>= 0);
224 return newivs_to_depth_to_newiv (newivs
, index
);
227 /* Returns the maximal precision type for expressions E1 and E2. */
230 max_precision_type (tree e1
, tree e2
)
232 tree type1
= TREE_TYPE (e1
);
233 tree type2
= TREE_TYPE (e2
);
234 return TYPE_PRECISION (type1
) > TYPE_PRECISION (type2
) ? type1
: type2
;
238 clast_to_gcc_expression (tree
, struct clast_expr
*, sese
, VEC (tree
, heap
) *,
241 /* Converts a Cloog reduction expression R with reduction operation OP
242 to a GCC expression tree of type TYPE. */
245 clast_to_gcc_expression_red (tree type
, enum tree_code op
,
246 struct clast_reduction
*r
,
247 sese region
, VEC (tree
, heap
) *newivs
,
248 htab_t newivs_index
, htab_t params_index
)
251 tree res
= clast_to_gcc_expression (type
, r
->elts
[0], region
, newivs
,
252 newivs_index
, params_index
);
253 tree operand_type
= (op
== POINTER_PLUS_EXPR
) ? sizetype
: type
;
255 for (i
= 1; i
< r
->n
; i
++)
257 tree t
= clast_to_gcc_expression (operand_type
, r
->elts
[i
], region
,
258 newivs
, newivs_index
, params_index
);
259 res
= fold_build2 (op
, type
, res
, t
);
265 /* Converts a Cloog AST expression E back to a GCC expression tree of
269 clast_to_gcc_expression (tree type
, struct clast_expr
*e
,
270 sese region
, VEC (tree
, heap
) *newivs
,
271 htab_t newivs_index
, htab_t params_index
)
277 struct clast_term
*t
= (struct clast_term
*) e
;
281 if (value_one_p (t
->val
))
283 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
284 newivs_index
, params_index
);
286 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
287 name
= fold_convert (sizetype
, name
);
289 name
= fold_convert (type
, name
);
293 else if (value_mone_p (t
->val
))
295 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
296 newivs_index
, params_index
);
298 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
299 name
= fold_convert (sizetype
, name
);
301 name
= fold_convert (type
, name
);
303 return fold_build1 (NEGATE_EXPR
, type
, name
);
307 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
308 newivs_index
, params_index
);
309 tree cst
= gmp_cst_to_tree (type
, t
->val
);
311 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
312 name
= fold_convert (sizetype
, name
);
314 name
= fold_convert (type
, name
);
316 if (!POINTER_TYPE_P (type
))
317 return fold_build2 (MULT_EXPR
, type
, cst
, name
);
324 return gmp_cst_to_tree (type
, t
->val
);
329 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
334 return clast_to_gcc_expression_red
335 (type
, POINTER_TYPE_P (type
) ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
336 r
, region
, newivs
, newivs_index
, params_index
);
339 return clast_to_gcc_expression_red (type
, MIN_EXPR
, r
, region
,
340 newivs
, newivs_index
,
344 return clast_to_gcc_expression_red (type
, MAX_EXPR
, r
, region
,
345 newivs
, newivs_index
,
356 struct clast_binary
*b
= (struct clast_binary
*) e
;
357 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
358 tree tl
= clast_to_gcc_expression (type
, lhs
, region
, newivs
,
359 newivs_index
, params_index
);
360 tree tr
= gmp_cst_to_tree (type
, b
->RHS
);
365 return fold_build2 (FLOOR_DIV_EXPR
, type
, tl
, tr
);
368 return fold_build2 (CEIL_DIV_EXPR
, type
, tl
, tr
);
371 return fold_build2 (EXACT_DIV_EXPR
, type
, tl
, tr
);
374 return fold_build2 (TRUNC_MOD_EXPR
, type
, tl
, tr
);
388 /* Returns the type for the expression E. */
391 gcc_type_for_clast_expr (struct clast_expr
*e
,
392 sese region
, VEC (tree
, heap
) *newivs
,
393 htab_t newivs_index
, htab_t params_index
)
399 struct clast_term
*t
= (struct clast_term
*) e
;
402 return TREE_TYPE (clast_name_to_gcc (t
->var
, region
, newivs
,
403 newivs_index
, params_index
));
410 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
413 return gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
414 newivs_index
, params_index
);
418 for (i
= 0; i
< r
->n
; i
++)
420 tree type
= gcc_type_for_clast_expr (r
->elts
[i
], region
,
421 newivs
, newivs_index
,
432 struct clast_binary
*b
= (struct clast_binary
*) e
;
433 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
434 return gcc_type_for_clast_expr (lhs
, region
, newivs
,
435 newivs_index
, params_index
);
445 /* Returns the type for the equation CLEQ. */
448 gcc_type_for_clast_eq (struct clast_equation
*cleq
,
449 sese region
, VEC (tree
, heap
) *newivs
,
450 htab_t newivs_index
, htab_t params_index
)
452 tree type
= gcc_type_for_clast_expr (cleq
->LHS
, region
, newivs
,
453 newivs_index
, params_index
);
457 return gcc_type_for_clast_expr (cleq
->RHS
, region
, newivs
, newivs_index
,
461 /* Translates a clast equation CLEQ to a tree. */
464 graphite_translate_clast_equation (sese region
,
465 struct clast_equation
*cleq
,
466 VEC (tree
, heap
) *newivs
,
467 htab_t newivs_index
, htab_t params_index
)
470 tree type
= gcc_type_for_clast_eq (cleq
, region
, newivs
, newivs_index
,
472 tree lhs
= clast_to_gcc_expression (type
, cleq
->LHS
, region
, newivs
,
473 newivs_index
, params_index
);
474 tree rhs
= clast_to_gcc_expression (type
, cleq
->RHS
, region
, newivs
,
475 newivs_index
, params_index
);
480 else if (cleq
->sign
> 0)
486 return fold_build2 (comp
, boolean_type_node
, lhs
, rhs
);
489 /* Creates the test for the condition in STMT. */
492 graphite_create_guard_cond_expr (sese region
, struct clast_guard
*stmt
,
493 VEC (tree
, heap
) *newivs
,
494 htab_t newivs_index
, htab_t params_index
)
499 for (i
= 0; i
< stmt
->n
; i
++)
501 tree eq
= graphite_translate_clast_equation (region
, &stmt
->eq
[i
],
502 newivs
, newivs_index
,
506 cond
= fold_build2 (TRUTH_AND_EXPR
, TREE_TYPE (eq
), cond
, eq
);
514 /* Creates a new if region corresponding to Cloog's guard. */
517 graphite_create_new_guard (sese region
, edge entry_edge
,
518 struct clast_guard
*stmt
,
519 VEC (tree
, heap
) *newivs
,
520 htab_t newivs_index
, htab_t params_index
)
522 tree cond_expr
= graphite_create_guard_cond_expr (region
, stmt
, newivs
,
523 newivs_index
, params_index
);
524 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
528 /* Walks a CLAST and returns the first statement in the body of a
531 static struct clast_user_stmt
*
532 clast_get_body_of_loop (struct clast_stmt
*stmt
)
535 || CLAST_STMT_IS_A (stmt
, stmt_user
))
536 return (struct clast_user_stmt
*) stmt
;
538 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
539 return clast_get_body_of_loop (((struct clast_for
*) stmt
)->body
);
541 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
542 return clast_get_body_of_loop (((struct clast_guard
*) stmt
)->then
);
544 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
545 return clast_get_body_of_loop (((struct clast_block
*) stmt
)->body
);
550 /* Java does not initialize long_long_integer_type_node. */
551 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
553 /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
554 land. The selected type is big enough to include the original loop
555 iteration variable, but signed to work with the subtractions CLooG
556 may have introduced. If such a type is not available, we fail.
558 TODO: Do not always return long_long, but the smallest possible
559 type, that still holds the original type.
561 TODO: Get the types using CLooG instead. This enables further
562 optimizations, but needs CLooG support. */
565 gcc_type_for_cloog_iv (const char *cloog_iv
, gimple_bb_p gbb
)
567 struct ivtype_map_elt_s tmp
;
570 tmp
.cloog_iv
= cloog_iv
;
571 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, NO_INSERT
);
575 tree type
= ((ivtype_map_elt
) *slot
)->type
;
576 int type_precision
= TYPE_PRECISION (type
);
578 /* Find the smallest signed type possible. */
579 if (!TYPE_UNSIGNED (type
))
581 if (type_precision
<= TYPE_PRECISION (integer_type_node
))
582 return integer_type_node
;
584 if (type_precision
<= TYPE_PRECISION (long_integer_type_node
))
585 return long_integer_type_node
;
587 if (type_precision
<= TYPE_PRECISION (my_long_long
))
593 if (type_precision
< TYPE_PRECISION (integer_type_node
))
594 return integer_type_node
;
596 if (type_precision
< TYPE_PRECISION (long_integer_type_node
))
597 return long_integer_type_node
;
599 if (type_precision
< TYPE_PRECISION (my_long_long
))
602 /* There is no signed type available, that is large enough to hold the
612 /* Returns the induction variable for the loop that gets translated to
616 gcc_type_for_iv_of_clast_loop (struct clast_for
*stmt_for
)
618 struct clast_stmt
*stmt
= (struct clast_stmt
*) stmt_for
;
619 struct clast_user_stmt
*body
= clast_get_body_of_loop (stmt
);
620 const char *cloog_iv
= stmt_for
->iterator
;
621 CloogStatement
*cs
= body
->statement
;
622 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
624 return gcc_type_for_cloog_iv (cloog_iv
, PBB_BLACK_BOX (pbb
));
627 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
628 induction variable for the new LOOP. New LOOP is attached to CFG
629 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
630 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
631 CLooG's scattering name to the induction variable created for the
632 loop of STMT. The new induction variable is inserted in the NEWIVS
636 graphite_create_new_loop (sese region
, edge entry_edge
,
637 struct clast_for
*stmt
,
638 loop_p outer
, VEC (tree
, heap
) **newivs
,
639 htab_t newivs_index
, htab_t params_index
)
641 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
642 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, *newivs
,
643 newivs_index
, params_index
);
644 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, *newivs
,
645 newivs_index
, params_index
);
646 tree stride
= gmp_cst_to_tree (type
, stmt
->stride
);
647 tree ivvar
= create_tmp_var (type
, "graphite_IV");
648 tree iv
, iv_after_increment
;
649 loop_p loop
= create_empty_loop_on_edge
650 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
651 outer
? outer
: entry_edge
->src
->loop_father
);
653 add_referenced_var (ivvar
);
655 save_clast_name_index (newivs_index
, stmt
->iterator
,
656 VEC_length (tree
, *newivs
));
657 VEC_safe_push (tree
, heap
, *newivs
, iv
);
661 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
662 variables of the loops around GBB in SESE. */
665 build_iv_mapping (htab_t map
, sese region
,
666 VEC (tree
, heap
) *newivs
, htab_t newivs_index
,
667 struct clast_user_stmt
*user_stmt
,
670 struct clast_stmt
*t
;
672 CloogStatement
*cs
= user_stmt
->statement
;
673 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
675 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
677 struct clast_expr
*expr
= (struct clast_expr
*)
678 ((struct clast_assignment
*)t
)->RHS
;
679 tree type
= gcc_type_for_clast_expr (expr
, region
, newivs
,
680 newivs_index
, params_index
);
681 tree old_name
= pbb_to_depth_to_oldiv (pbb
, index
);
682 tree e
= clast_to_gcc_expression (type
, expr
, region
, newivs
,
683 newivs_index
, params_index
);
684 set_rename (map
, old_name
, e
);
688 /* Helper function for htab_traverse. */
691 copy_renames (void **slot
, void *s
)
693 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
694 htab_t res
= (htab_t
) s
;
695 tree old_name
= entry
->old_name
;
696 tree expr
= entry
->expr
;
697 struct rename_map_elt_s tmp
;
700 tmp
.old_name
= old_name
;
701 x
= htab_find_slot (res
, &tmp
, INSERT
);
704 *x
= new_rename_map_elt (old_name
, expr
);
709 /* Construct bb_pbb_def with BB and PBB. */
712 new_bb_pbb_def (basic_block bb
, poly_bb_p pbb
)
714 bb_pbb_def
*bb_pbb_p
;
716 bb_pbb_p
= XNEW (bb_pbb_def
);
723 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
726 mark_bb_with_pbb (poly_bb_p pbb
, basic_block bb
, htab_t bb_pbb_mapping
)
732 x
= htab_find_slot (bb_pbb_mapping
, &tmp
, INSERT
);
735 *x
= new_bb_pbb_def (bb
, pbb
);
738 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
741 find_pbb_via_hash (htab_t bb_pbb_mapping
, basic_block bb
)
747 slot
= htab_find_slot (bb_pbb_mapping
, &tmp
, NO_INSERT
);
750 return ((bb_pbb_def
*) *slot
)->pbb
;
755 /* Check data dependency in LOOP at scattering level LEVEL.
756 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
760 dependency_in_loop_p (loop_p loop
, htab_t bb_pbb_mapping
, int level
)
763 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
765 for (i
= 0; i
< loop
->num_nodes
; i
++)
767 poly_bb_p pbb1
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[i
]);
772 for (j
= 0; j
< loop
->num_nodes
; j
++)
774 poly_bb_p pbb2
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[j
]);
779 if (dependency_between_pbbs_p (pbb1
, pbb2
, level
))
793 translate_clast (sese
, loop_p
, struct clast_stmt
*, edge
, htab_t
,
794 VEC (tree
, heap
) **, htab_t
, htab_t
, int, htab_t
);
796 /* Translates a clast user statement STMT to gimple.
798 - REGION is the sese region we used to generate the scop.
799 - NEXT_E is the edge where new generated code should be attached.
800 - CONTEXT_LOOP is the loop in which the generated code will be placed
801 - RENAME_MAP contains a set of tuples of new names associated to
802 the original variables names.
803 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
804 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
807 translate_clast_user (sese region
, struct clast_user_stmt
*stmt
, edge next_e
,
808 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
809 htab_t newivs_index
, htab_t bb_pbb_mapping
,
814 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (stmt
->statement
);
815 gbb
= PBB_BLACK_BOX (pbb
);
817 if (GBB_BB (gbb
) == ENTRY_BLOCK_PTR
)
820 build_iv_mapping (rename_map
, region
, *newivs
, newivs_index
, stmt
,
822 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), region
,
824 new_bb
= next_e
->src
;
825 mark_bb_with_pbb (pbb
, new_bb
, bb_pbb_mapping
);
826 update_ssa (TODO_update_ssa
);
831 /* Creates a new if region protecting the loop to be executed, if the execution
832 count is zero (lb > ub). */
834 graphite_create_new_loop_guard (sese region
, edge entry_edge
,
835 struct clast_for
*stmt
,
836 VEC (tree
, heap
) *newivs
,
837 htab_t newivs_index
, htab_t params_index
)
841 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
842 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, newivs
,
843 newivs_index
, params_index
);
844 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, newivs
,
845 newivs_index
, params_index
);
847 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
848 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
849 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
850 However lb < ub + 1 is false, as expected.
851 There might be a problem with cases where ub is 2^32. */
854 value_init (gmp_one
);
855 value_set_si (gmp_one
, 1);
856 one
= gmp_cst_to_tree (type
, gmp_one
);
857 value_clear (gmp_one
);
859 ub
= fold_build2 (PLUS_EXPR
, type
, ub
, one
);
860 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, lb
, ub
);
862 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
868 /* Create the loop for a clast for statement.
870 - REGION is the sese region we used to generate the scop.
871 - NEXT_E is the edge where new generated code should be attached.
872 - RENAME_MAP contains a set of tuples of new names associated to
873 the original variables names.
874 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
875 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
878 translate_clast_for_loop (sese region
, loop_p context_loop
,
879 struct clast_for
*stmt
, edge next_e
,
880 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
881 htab_t newivs_index
, htab_t bb_pbb_mapping
,
882 int level
, htab_t params_index
)
884 struct loop
*loop
= graphite_create_new_loop (region
, next_e
, stmt
,
885 context_loop
, newivs
,
886 newivs_index
, params_index
);
887 edge last_e
= single_exit (loop
);
888 edge to_body
= single_succ_edge (loop
->header
);
889 basic_block after
= to_body
->dest
;
891 /* Create a basic block for loop close phi nodes. */
892 last_e
= single_succ_edge (split_edge (last_e
));
894 /* Translate the body of the loop. */
895 next_e
= translate_clast (region
, loop
, stmt
->body
, to_body
, rename_map
,
896 newivs
, newivs_index
, bb_pbb_mapping
, level
+ 1,
898 redirect_edge_succ_nodup (next_e
, after
);
899 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
901 /* Remove from rename_map all the tuples containing variables
902 defined in loop's body. */
903 insert_loop_close_phis (rename_map
, loop
);
905 if (flag_loop_parallelize_all
906 && !dependency_in_loop_p (loop
, bb_pbb_mapping
,
907 get_scattering_level (level
)))
908 loop
->can_be_parallel
= true;
913 /* Translates a clast for statement STMT to gimple. First a guard is created
914 protecting the loop, if it is executed zero times. In this guard we create
915 the real loop structure.
917 - REGION is the sese region we used to generate the scop.
918 - NEXT_E is the edge where new generated code should be attached.
919 - RENAME_MAP contains a set of tuples of new names associated to
920 the original variables names.
921 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
922 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
925 translate_clast_for (sese region
, loop_p context_loop
, struct clast_for
*stmt
,
926 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
927 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
930 edge last_e
= graphite_create_new_loop_guard (region
, next_e
, stmt
, *newivs
,
931 newivs_index
, params_index
);
933 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
934 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
935 edge exit_true_e
= single_succ_edge (true_e
->dest
);
936 edge exit_false_e
= single_succ_edge (false_e
->dest
);
938 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
939 eq_rename_map_elts
, free
);
940 htab_traverse (rename_map
, copy_renames
, before_guard
);
942 next_e
= translate_clast_for_loop (region
, context_loop
, stmt
, true_e
,
944 newivs_index
, bb_pbb_mapping
, level
,
947 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
948 before_guard
, rename_map
);
950 htab_delete (before_guard
);
955 /* Translates a clast guard statement STMT to gimple.
957 - REGION is the sese region we used to generate the scop.
958 - NEXT_E is the edge where new generated code should be attached.
959 - CONTEXT_LOOP is the loop in which the generated code will be placed
960 - RENAME_MAP contains a set of tuples of new names associated to
961 the original variables names.
962 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
963 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
966 translate_clast_guard (sese region
, loop_p context_loop
,
967 struct clast_guard
*stmt
, edge next_e
,
968 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
969 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
972 edge last_e
= graphite_create_new_guard (region
, next_e
, stmt
, *newivs
,
973 newivs_index
, params_index
);
975 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
976 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
977 edge exit_true_e
= single_succ_edge (true_e
->dest
);
978 edge exit_false_e
= single_succ_edge (false_e
->dest
);
980 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
981 eq_rename_map_elts
, free
);
982 htab_traverse (rename_map
, copy_renames
, before_guard
);
984 next_e
= translate_clast (region
, context_loop
, stmt
->then
, true_e
,
985 rename_map
, newivs
, newivs_index
, bb_pbb_mapping
,
986 level
, params_index
);
988 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
989 before_guard
, rename_map
);
991 htab_delete (before_guard
);
996 /* Translates a CLAST statement STMT to GCC representation in the
999 - NEXT_E is the edge where new generated code should be attached.
1000 - CONTEXT_LOOP is the loop in which the generated code will be placed
1001 - RENAME_MAP contains a set of tuples of new names associated to
1002 the original variables names.
1003 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1005 translate_clast (sese region
, loop_p context_loop
, struct clast_stmt
*stmt
,
1006 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
1007 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
1008 htab_t params_index
)
1013 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1016 else if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1017 next_e
= translate_clast_user (region
, (struct clast_user_stmt
*) stmt
,
1018 next_e
, rename_map
, newivs
, newivs_index
,
1019 bb_pbb_mapping
, params_index
);
1021 else if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1022 next_e
= translate_clast_for (region
, context_loop
,
1023 (struct clast_for
*) stmt
, next_e
,
1024 rename_map
, newivs
, newivs_index
,
1025 bb_pbb_mapping
, level
, params_index
);
1027 else if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1028 next_e
= translate_clast_guard (region
, context_loop
,
1029 (struct clast_guard
*) stmt
, next_e
,
1030 rename_map
, newivs
, newivs_index
,
1031 bb_pbb_mapping
, level
, params_index
);
1033 else if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1034 next_e
= translate_clast (region
, context_loop
,
1035 ((struct clast_block
*) stmt
)->body
,
1036 next_e
, rename_map
, newivs
, newivs_index
,
1037 bb_pbb_mapping
, level
, params_index
);
1041 recompute_all_dominators ();
1044 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
1045 rename_map
, newivs
, newivs_index
,
1046 bb_pbb_mapping
, level
, params_index
);
1049 /* Returns the first cloog name used in EXPR. */
1052 find_cloog_iv_in_expr (struct clast_expr
*expr
)
1054 struct clast_term
*term
= (struct clast_term
*) expr
;
1055 struct clast_reduction
*red
;
1058 if (expr
->type
== expr_term
)
1061 if (expr
->type
!= expr_red
)
1064 red
= (struct clast_reduction
*) expr
;
1065 for (i
= 0; i
< red
->n
; i
++)
1067 const char *res
= find_cloog_iv_in_expr (red
->elts
[i
]);
1076 /* Build for USER_STMT a map between the CLAST induction variables and
1077 the corresponding GCC old induction variables. This information is
1078 stored on each GRAPHITE_BB. */
1081 compute_cloog_iv_types_1 (poly_bb_p pbb
, struct clast_user_stmt
*user_stmt
)
1083 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1084 struct clast_stmt
*t
;
1087 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
1090 struct ivtype_map_elt_s tmp
;
1091 struct clast_expr
*expr
= (struct clast_expr
*)
1092 ((struct clast_assignment
*)t
)->RHS
;
1094 /* Create an entry (clast_var, type). */
1095 tmp
.cloog_iv
= find_cloog_iv_in_expr (expr
);
1099 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, INSERT
);
1103 tree oldiv
= pbb_to_depth_to_oldiv (pbb
, index
);
1104 tree type
= TREE_TYPE (oldiv
);
1105 *slot
= new_ivtype_map_elt (tmp
.cloog_iv
, type
);
1110 /* Walk the CLAST tree starting from STMT and build for each
1111 clast_user_stmt a map between the CLAST induction variables and the
1112 corresponding GCC old induction variables. This information is
1113 stored on each GRAPHITE_BB. */
1116 compute_cloog_iv_types (struct clast_stmt
*stmt
)
1121 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1124 if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1126 CloogStatement
*cs
= ((struct clast_user_stmt
*) stmt
)->statement
;
1127 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
1128 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1130 if (!GBB_CLOOG_IV_TYPES (gbb
))
1131 GBB_CLOOG_IV_TYPES (gbb
) = htab_create (10, ivtype_map_elt_info
,
1132 eq_ivtype_map_elts
, free
);
1134 compute_cloog_iv_types_1 (pbb
, (struct clast_user_stmt
*) stmt
);
1138 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1140 struct clast_stmt
*s
= ((struct clast_for
*) stmt
)->body
;
1141 compute_cloog_iv_types (s
);
1145 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1147 struct clast_stmt
*s
= ((struct clast_guard
*) stmt
)->then
;
1148 compute_cloog_iv_types (s
);
1152 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1154 struct clast_stmt
*s
= ((struct clast_block
*) stmt
)->body
;
1155 compute_cloog_iv_types (s
);
1162 compute_cloog_iv_types (stmt
->next
);
1165 /* Free the SCATTERING domain list. */
1168 free_scattering (CloogDomainList
*scattering
)
1172 CloogDomain
*dom
= cloog_domain (scattering
);
1173 CloogDomainList
*next
= cloog_next_domain (scattering
);
1175 cloog_domain_free (dom
);
1181 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1182 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1183 from 0 to scop_nb_loops (scop). */
1186 initialize_cloog_names (scop_p scop
, CloogProgram
*prog
)
1188 sese region
= SCOP_REGION (scop
);
1190 int nb_iterators
= scop_max_loop_depth (scop
);
1191 int nb_scattering
= cloog_program_nb_scattdims (prog
);
1192 int nb_parameters
= VEC_length (tree
, SESE_PARAMS (region
));
1193 char **iterators
= XNEWVEC (char *, nb_iterators
* 2);
1194 char **scattering
= XNEWVEC (char *, nb_scattering
);
1195 char **parameters
= XNEWVEC (char *, nb_parameters
);
1197 cloog_program_set_names (prog
, cloog_names_malloc ());
1199 for (i
= 0; i
< nb_parameters
; i
++)
1201 tree param
= VEC_index (tree
, SESE_PARAMS(region
), i
);
1202 const char *name
= get_name (param
);
1208 len
= strlen (name
);
1210 parameters
[i
] = XNEWVEC (char, len
+ 1);
1211 snprintf (parameters
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (param
));
1214 cloog_names_set_nb_parameters (cloog_program_names (prog
), nb_parameters
);
1215 cloog_names_set_parameters (cloog_program_names (prog
), parameters
);
1217 for (i
= 0; i
< nb_iterators
; i
++)
1220 iterators
[i
] = XNEWVEC (char, len
);
1221 snprintf (iterators
[i
], len
, "git_%d", i
);
1224 cloog_names_set_nb_iterators (cloog_program_names (prog
),
1226 cloog_names_set_iterators (cloog_program_names (prog
),
1229 for (i
= 0; i
< nb_scattering
; i
++)
1232 scattering
[i
] = XNEWVEC (char, len
);
1233 snprintf (scattering
[i
], len
, "scat_%d", i
);
1236 cloog_names_set_nb_scattering (cloog_program_names (prog
),
1238 cloog_names_set_scattering (cloog_program_names (prog
),
1242 /* Build cloog program for SCoP. */
1245 build_cloog_prog (scop_p scop
, CloogProgram
*prog
)
1248 int max_nb_loops
= scop_max_loop_depth (scop
);
1250 CloogLoop
*loop_list
= NULL
;
1251 CloogBlockList
*block_list
= NULL
;
1252 CloogDomainList
*scattering
= NULL
;
1253 int nbs
= 2 * max_nb_loops
+ 1;
1256 cloog_program_set_context
1257 (prog
, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop
)));
1258 nbs
= unify_scattering_dimensions (scop
);
1259 scaldims
= (int *) xmalloc (nbs
* (sizeof (int)));
1260 cloog_program_set_nb_scattdims (prog
, nbs
);
1261 initialize_cloog_names (scop
, prog
);
1263 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1265 CloogStatement
*stmt
;
1268 /* Dead code elimination: when the domain of a PBB is empty,
1269 don't generate code for the PBB. */
1270 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb
)))
1273 /* Build the new statement and its block. */
1274 stmt
= cloog_statement_alloc (pbb_index (pbb
));
1275 block
= cloog_block_alloc (stmt
, 0, NULL
, pbb_dim_iter_domain (pbb
));
1276 cloog_statement_set_usr (stmt
, pbb
);
1278 /* Build loop list. */
1280 CloogLoop
*new_loop_list
= cloog_loop_malloc ();
1281 cloog_loop_set_next (new_loop_list
, loop_list
);
1282 cloog_loop_set_domain
1284 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb
)));
1285 cloog_loop_set_block (new_loop_list
, block
);
1286 loop_list
= new_loop_list
;
1289 /* Build block list. */
1291 CloogBlockList
*new_block_list
= cloog_block_list_malloc ();
1293 cloog_block_list_set_next (new_block_list
, block_list
);
1294 cloog_block_list_set_block (new_block_list
, block
);
1295 block_list
= new_block_list
;
1298 /* Build scattering list. */
1300 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1301 CloogDomainList
*new_scattering
1302 = (CloogDomainList
*) xmalloc (sizeof (CloogDomainList
));
1303 ppl_Polyhedron_t scat
;
1306 scat
= PBB_TRANSFORMED_SCATTERING (pbb
);
1307 dom
= new_Cloog_Domain_from_ppl_Polyhedron (scat
);
1309 cloog_set_next_domain (new_scattering
, scattering
);
1310 cloog_set_domain (new_scattering
, dom
);
1311 scattering
= new_scattering
;
1315 cloog_program_set_loop (prog
, loop_list
);
1316 cloog_program_set_blocklist (prog
, block_list
);
1318 for (i
= 0; i
< nbs
; i
++)
1321 cloog_program_set_scaldims (prog
, scaldims
);
1323 /* Extract scalar dimensions to simplify the code generation problem. */
1324 cloog_program_extract_scalars (prog
, scattering
);
1326 /* Apply scattering. */
1327 cloog_program_scatter (prog
, scattering
);
1328 free_scattering (scattering
);
1330 /* Iterators corresponding to scalar dimensions have to be extracted. */
1331 cloog_names_scalarize (cloog_program_names (prog
), nbs
,
1332 cloog_program_scaldims (prog
));
1334 /* Free blocklist. */
1336 CloogBlockList
*next
= cloog_program_blocklist (prog
);
1340 CloogBlockList
*toDelete
= next
;
1341 next
= cloog_block_list_next (next
);
1342 cloog_block_list_set_next (toDelete
, NULL
);
1343 cloog_block_list_set_block (toDelete
, NULL
);
1344 cloog_block_list_free (toDelete
);
1346 cloog_program_set_blocklist (prog
, NULL
);
1350 /* Return the options that will be used in GLOOG. */
1352 static CloogOptions
*
1353 set_cloog_options (void)
1355 CloogOptions
*options
= cloog_options_malloc ();
1357 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1358 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1359 we pass an incomplete program to cloog. */
1360 options
->language
= LANGUAGE_C
;
1362 /* Enable complex equality spreading: removes dummy statements
1363 (assignments) in the generated code which repeats the
1364 substitution equations for statements. This is useless for
1368 /* Enable C pretty-printing mode: normalizes the substitution
1369 equations for statements. */
1372 /* Allow cloog to build strides with a stride width different to one.
1373 This example has stride = 4:
1375 for (i = 0; i < 20; i += 4)
1377 options
->strides
= 1;
1379 /* Disable optimizations and make cloog generate source code closer to the
1380 input. This is useful for debugging, but later we want the optimized
1383 XXX: We can not disable optimizations, as loop blocking is not working
1388 options
->l
= INT_MAX
;
1394 /* Prints STMT to STDERR. */
1397 print_clast_stmt (FILE *file
, struct clast_stmt
*stmt
)
1399 CloogOptions
*options
= set_cloog_options ();
1401 pprint (file
, stmt
, 0, options
);
1402 cloog_options_free (options
);
1405 /* Prints STMT to STDERR. */
1408 debug_clast_stmt (struct clast_stmt
*stmt
)
1410 print_clast_stmt (stderr
, stmt
);
1413 /* Translate SCOP to a CLooG program and clast. These two
1414 representations should be freed together: a clast cannot be used
1415 without a program. */
1418 scop_to_clast (scop_p scop
)
1420 CloogOptions
*options
= set_cloog_options ();
1421 cloog_prog_clast pc
;
1423 /* Connect new cloog prog generation to graphite. */
1424 pc
.prog
= cloog_program_malloc ();
1425 build_cloog_prog (scop
, pc
.prog
);
1426 pc
.prog
= cloog_program_generate (pc
.prog
, options
);
1427 pc
.stmt
= cloog_clast_create (pc
.prog
, options
);
1429 cloog_options_free (options
);
1433 /* Prints to FILE the code generated by CLooG for SCOP. */
1436 print_generated_program (FILE *file
, scop_p scop
)
1438 CloogOptions
*options
= set_cloog_options ();
1439 cloog_prog_clast pc
= scop_to_clast (scop
);
1441 fprintf (file
, " (prog: \n");
1442 cloog_program_print (file
, pc
.prog
);
1443 fprintf (file
, " )\n");
1445 fprintf (file
, " (clast: \n");
1446 pprint (file
, pc
.stmt
, 0, options
);
1447 fprintf (file
, " )\n");
1449 cloog_options_free (options
);
1450 cloog_clast_free (pc
.stmt
);
1451 cloog_program_free (pc
.prog
);
1454 /* Prints to STDERR the code generated by CLooG for SCOP. */
1457 debug_generated_program (scop_p scop
)
1459 print_generated_program (stderr
, scop
);
1462 /* Add CLooG names to parameter index. The index is used to translate
1463 back from CLooG names to GCC trees. */
1466 create_params_index (htab_t index_table
, CloogProgram
*prog
) {
1467 CloogNames
* names
= cloog_program_names (prog
);
1468 int nb_parameters
= cloog_names_nb_parameters (names
);
1469 char **parameters
= cloog_names_parameters (names
);
1472 for (i
= 0; i
< nb_parameters
; i
++)
1473 save_clast_name_index (index_table
, parameters
[i
], i
);
1476 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1477 the given SCOP. Return true if code generation succeeded.
1478 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1482 gloog (scop_p scop
, VEC (scop_p
, heap
) *scops
, htab_t bb_pbb_mapping
)
1484 VEC (tree
, heap
) *newivs
= VEC_alloc (tree
, heap
, 10);
1485 loop_p context_loop
;
1486 sese region
= SCOP_REGION (scop
);
1487 ifsese if_region
= NULL
;
1488 htab_t rename_map
, newivs_index
, params_index
;
1489 cloog_prog_clast pc
;
1492 timevar_push (TV_GRAPHITE_CODE_GEN
);
1493 gloog_error
= false;
1495 pc
= scop_to_clast (scop
);
1497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1499 fprintf (dump_file
, "\nCLAST generated by CLooG: \n");
1500 print_clast_stmt (dump_file
, pc
.stmt
);
1501 fprintf (dump_file
, "\n");
1504 recompute_all_dominators ();
1507 if_region
= move_sese_in_condition (region
);
1508 sese_insert_phis_for_liveouts (region
,
1509 if_region
->region
->exit
->src
,
1510 if_region
->false_region
->exit
,
1511 if_region
->true_region
->exit
);
1512 recompute_all_dominators ();
1515 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1516 compute_cloog_iv_types (pc
.stmt
);
1517 rename_map
= htab_create (10, rename_map_elt_info
, eq_rename_map_elts
, free
);
1518 newivs_index
= htab_create (10, clast_name_index_elt_info
,
1519 eq_clast_name_indexes
, free
);
1520 params_index
= htab_create (10, clast_name_index_elt_info
,
1521 eq_clast_name_indexes
, free
);
1523 create_params_index (params_index
, pc
.prog
);
1525 translate_clast (region
, context_loop
, pc
.stmt
,
1526 if_region
->true_region
->entry
,
1527 rename_map
, &newivs
, newivs_index
,
1528 bb_pbb_mapping
, 1, params_index
);
1530 sese_adjust_liveout_phis (region
, rename_map
,
1531 if_region
->region
->exit
->src
,
1532 if_region
->false_region
->exit
,
1533 if_region
->true_region
->exit
);
1535 rename_nb_iterations (rename_map
);
1537 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
1538 rename_sese_parameters (rename_map
, SCOP_REGION (scop
));
1540 recompute_all_dominators ();
1544 set_ifsese_condition (if_region
, integer_zero_node
);
1546 free (if_region
->true_region
);
1547 free (if_region
->region
);
1550 htab_delete (rename_map
);
1551 htab_delete (newivs_index
);
1552 htab_delete (params_index
);
1553 VEC_free (tree
, heap
, newivs
);
1554 cloog_clast_free (pc
.stmt
);
1555 cloog_program_free (pc
.prog
);
1556 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1562 int num_no_dependency
= 0;
1564 FOR_EACH_LOOP (li
, loop
, 0)
1565 if (loop
->can_be_parallel
)
1566 num_no_dependency
++;
1568 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1572 return !gloog_error
;