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
);
285 return fold_convert (type
, name
);
288 else if (value_mone_p (t
->val
))
290 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
291 newivs_index
, params_index
);
292 name
= fold_convert (type
, name
);
293 return fold_build1 (NEGATE_EXPR
, type
, name
);
297 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
298 newivs_index
, params_index
);
299 tree cst
= gmp_cst_to_tree (type
, t
->val
);
300 name
= fold_convert (type
, name
);
301 if (!POINTER_TYPE_P (type
))
302 return fold_build2 (MULT_EXPR
, type
, cst
, name
);
309 return gmp_cst_to_tree (type
, t
->val
);
314 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
319 return clast_to_gcc_expression_red
320 (type
, POINTER_TYPE_P (type
) ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
321 r
, region
, newivs
, newivs_index
, params_index
);
324 return clast_to_gcc_expression_red (type
, MIN_EXPR
, r
, region
,
325 newivs
, newivs_index
,
329 return clast_to_gcc_expression_red (type
, MAX_EXPR
, r
, region
,
330 newivs
, newivs_index
,
341 struct clast_binary
*b
= (struct clast_binary
*) e
;
342 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
343 tree tl
= clast_to_gcc_expression (type
, lhs
, region
, newivs
,
344 newivs_index
, params_index
);
345 tree tr
= gmp_cst_to_tree (type
, b
->RHS
);
350 return fold_build2 (FLOOR_DIV_EXPR
, type
, tl
, tr
);
353 return fold_build2 (CEIL_DIV_EXPR
, type
, tl
, tr
);
356 return fold_build2 (EXACT_DIV_EXPR
, type
, tl
, tr
);
359 return fold_build2 (TRUNC_MOD_EXPR
, type
, tl
, tr
);
373 /* Returns the type for the expression E. */
376 gcc_type_for_clast_expr (struct clast_expr
*e
,
377 sese region
, VEC (tree
, heap
) *newivs
,
378 htab_t newivs_index
, htab_t params_index
)
384 struct clast_term
*t
= (struct clast_term
*) e
;
387 return TREE_TYPE (clast_name_to_gcc (t
->var
, region
, newivs
,
388 newivs_index
, params_index
));
395 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
398 return gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
399 newivs_index
, params_index
);
403 for (i
= 0; i
< r
->n
; i
++)
405 tree type
= gcc_type_for_clast_expr (r
->elts
[i
], region
,
406 newivs
, newivs_index
,
417 struct clast_binary
*b
= (struct clast_binary
*) e
;
418 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
419 return gcc_type_for_clast_expr (lhs
, region
, newivs
,
420 newivs_index
, params_index
);
430 /* Returns the type for the equation CLEQ. */
433 gcc_type_for_clast_eq (struct clast_equation
*cleq
,
434 sese region
, VEC (tree
, heap
) *newivs
,
435 htab_t newivs_index
, htab_t params_index
)
437 tree type
= gcc_type_for_clast_expr (cleq
->LHS
, region
, newivs
,
438 newivs_index
, params_index
);
442 return gcc_type_for_clast_expr (cleq
->RHS
, region
, newivs
, newivs_index
,
446 /* Translates a clast equation CLEQ to a tree. */
449 graphite_translate_clast_equation (sese region
,
450 struct clast_equation
*cleq
,
451 VEC (tree
, heap
) *newivs
,
452 htab_t newivs_index
, htab_t params_index
)
455 tree type
= gcc_type_for_clast_eq (cleq
, region
, newivs
, newivs_index
,
457 tree lhs
= clast_to_gcc_expression (type
, cleq
->LHS
, region
, newivs
,
458 newivs_index
, params_index
);
459 tree rhs
= clast_to_gcc_expression (type
, cleq
->RHS
, region
, newivs
,
460 newivs_index
, params_index
);
465 else if (cleq
->sign
> 0)
471 return fold_build2 (comp
, boolean_type_node
, lhs
, rhs
);
474 /* Creates the test for the condition in STMT. */
477 graphite_create_guard_cond_expr (sese region
, struct clast_guard
*stmt
,
478 VEC (tree
, heap
) *newivs
,
479 htab_t newivs_index
, htab_t params_index
)
484 for (i
= 0; i
< stmt
->n
; i
++)
486 tree eq
= graphite_translate_clast_equation (region
, &stmt
->eq
[i
],
487 newivs
, newivs_index
,
491 cond
= fold_build2 (TRUTH_AND_EXPR
, TREE_TYPE (eq
), cond
, eq
);
499 /* Creates a new if region corresponding to Cloog's guard. */
502 graphite_create_new_guard (sese region
, edge entry_edge
,
503 struct clast_guard
*stmt
,
504 VEC (tree
, heap
) *newivs
,
505 htab_t newivs_index
, htab_t params_index
)
507 tree cond_expr
= graphite_create_guard_cond_expr (region
, stmt
, newivs
,
508 newivs_index
, params_index
);
509 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
513 /* Walks a CLAST and returns the first statement in the body of a
516 static struct clast_user_stmt
*
517 clast_get_body_of_loop (struct clast_stmt
*stmt
)
520 || CLAST_STMT_IS_A (stmt
, stmt_user
))
521 return (struct clast_user_stmt
*) stmt
;
523 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
524 return clast_get_body_of_loop (((struct clast_for
*) stmt
)->body
);
526 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
527 return clast_get_body_of_loop (((struct clast_guard
*) stmt
)->then
);
529 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
530 return clast_get_body_of_loop (((struct clast_block
*) stmt
)->body
);
535 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
536 If the information is not available, i.e. in the case one of the
537 transforms created the loop, just return integer_type_node. */
540 gcc_type_for_cloog_iv (const char *cloog_iv
, gimple_bb_p gbb
)
542 struct ivtype_map_elt_s tmp
;
546 tmp
.cloog_iv
= cloog_iv
;
547 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, NO_INSERT
);
551 type
= ((ivtype_map_elt
) *slot
)->type
;
552 if (TYPE_UNSIGNED (type
)
553 && (TYPE_SIZE (type
) == TYPE_SIZE (long_long_integer_type_node
)))
560 return long_long_integer_type_node
;
563 /* Returns the induction variable for the loop that gets translated to
567 gcc_type_for_iv_of_clast_loop (struct clast_for
*stmt_for
)
569 struct clast_stmt
*stmt
= (struct clast_stmt
*) stmt_for
;
570 struct clast_user_stmt
*body
= clast_get_body_of_loop (stmt
);
571 const char *cloog_iv
= stmt_for
->iterator
;
572 CloogStatement
*cs
= body
->statement
;
573 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
575 return gcc_type_for_cloog_iv (cloog_iv
, PBB_BLACK_BOX (pbb
));
578 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
579 induction variable for the new LOOP. New LOOP is attached to CFG
580 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
581 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
582 CLooG's scattering name to the induction variable created for the
583 loop of STMT. The new induction variable is inserted in the NEWIVS
587 graphite_create_new_loop (sese region
, edge entry_edge
,
588 struct clast_for
*stmt
,
589 loop_p outer
, VEC (tree
, heap
) **newivs
,
590 htab_t newivs_index
, htab_t params_index
)
592 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
593 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, *newivs
,
594 newivs_index
, params_index
);
595 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, *newivs
,
596 newivs_index
, params_index
);
597 tree stride
= gmp_cst_to_tree (type
, stmt
->stride
);
598 tree ivvar
= create_tmp_var (type
, "graphite_IV");
599 tree iv
, iv_after_increment
;
600 loop_p loop
= create_empty_loop_on_edge
601 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
602 outer
? outer
: entry_edge
->src
->loop_father
);
604 add_referenced_var (ivvar
);
606 save_clast_name_index (newivs_index
, stmt
->iterator
,
607 VEC_length (tree
, *newivs
));
608 VEC_safe_push (tree
, heap
, *newivs
, iv
);
612 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
613 variables of the loops around GBB in SESE. */
616 build_iv_mapping (htab_t map
, sese region
,
617 VEC (tree
, heap
) *newivs
, htab_t newivs_index
,
618 struct clast_user_stmt
*user_stmt
,
621 struct clast_stmt
*t
;
623 CloogStatement
*cs
= user_stmt
->statement
;
624 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
626 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
628 struct clast_expr
*expr
= (struct clast_expr
*)
629 ((struct clast_assignment
*)t
)->RHS
;
630 tree type
= gcc_type_for_clast_expr (expr
, region
, newivs
,
631 newivs_index
, params_index
);
632 tree old_name
= pbb_to_depth_to_oldiv (pbb
, index
);
633 tree e
= clast_to_gcc_expression (type
, expr
, region
, newivs
,
634 newivs_index
, params_index
);
635 set_rename (map
, old_name
, e
);
639 /* Helper function for htab_traverse. */
642 copy_renames (void **slot
, void *s
)
644 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
645 htab_t res
= (htab_t
) s
;
646 tree old_name
= entry
->old_name
;
647 tree expr
= entry
->expr
;
648 struct rename_map_elt_s tmp
;
651 tmp
.old_name
= old_name
;
652 x
= htab_find_slot (res
, &tmp
, INSERT
);
655 *x
= new_rename_map_elt (old_name
, expr
);
660 /* Construct bb_pbb_def with BB and PBB. */
663 new_bb_pbb_def (basic_block bb
, poly_bb_p pbb
)
665 bb_pbb_def
*bb_pbb_p
;
667 bb_pbb_p
= XNEW (bb_pbb_def
);
674 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
677 mark_bb_with_pbb (poly_bb_p pbb
, basic_block bb
, htab_t bb_pbb_mapping
)
683 x
= htab_find_slot (bb_pbb_mapping
, &tmp
, INSERT
);
686 *x
= new_bb_pbb_def (bb
, pbb
);
689 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
692 find_pbb_via_hash (htab_t bb_pbb_mapping
, basic_block bb
)
698 slot
= htab_find_slot (bb_pbb_mapping
, &tmp
, NO_INSERT
);
701 return ((bb_pbb_def
*) *slot
)->pbb
;
706 /* Check data dependency in LOOP at scattering level LEVEL.
707 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
711 dependency_in_loop_p (loop_p loop
, htab_t bb_pbb_mapping
, int level
)
714 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
716 for (i
= 0; i
< loop
->num_nodes
; i
++)
718 poly_bb_p pbb1
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[i
]);
723 for (j
= 0; j
< loop
->num_nodes
; j
++)
725 poly_bb_p pbb2
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[j
]);
730 if (dependency_between_pbbs_p (pbb1
, pbb2
, level
))
744 translate_clast (sese
, loop_p
, struct clast_stmt
*, edge
, htab_t
,
745 VEC (tree
, heap
) **, htab_t
, htab_t
, int, htab_t
);
747 /* Translates a clast user statement STMT to gimple.
749 - REGION is the sese region we used to generate the scop.
750 - NEXT_E is the edge where new generated code should be attached.
751 - CONTEXT_LOOP is the loop in which the generated code will be placed
752 - RENAME_MAP contains a set of tuples of new names associated to
753 the original variables names.
754 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
755 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
758 translate_clast_user (sese region
, struct clast_user_stmt
*stmt
, edge next_e
,
759 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
760 htab_t newivs_index
, htab_t bb_pbb_mapping
,
765 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (stmt
->statement
);
766 gbb
= PBB_BLACK_BOX (pbb
);
768 if (GBB_BB (gbb
) == ENTRY_BLOCK_PTR
)
771 build_iv_mapping (rename_map
, region
, *newivs
, newivs_index
, stmt
,
773 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), region
,
775 new_bb
= next_e
->src
;
776 mark_bb_with_pbb (pbb
, new_bb
, bb_pbb_mapping
);
777 update_ssa (TODO_update_ssa
);
782 static tree
gcc_type_for_iv_of_clast_loop (struct clast_for
*);
785 /* Creates a new if region protecting the loop to be executed, if the execution
786 count is zero (lb > ub). */
788 graphite_create_new_loop_guard (sese region
, edge entry_edge
,
789 struct clast_for
*stmt
,
790 VEC (tree
, heap
) *newivs
,
791 htab_t newivs_index
, htab_t params_index
)
795 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
796 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, newivs
,
797 newivs_index
, params_index
);
798 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, newivs
,
799 newivs_index
, params_index
);
801 /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a
802 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
803 2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
804 However lb < ub + 1 is false, as expected.
805 There might be a problem with cases where ub is 2^32. */
808 value_init (gmp_one
);
809 value_set_si (gmp_one
, 1);
810 one
= gmp_cst_to_tree (type
, gmp_one
);
811 value_clear (gmp_one
);
813 ub
= fold_build2 (PLUS_EXPR
, type
, ub
, one
);
814 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, lb
, ub
);
816 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
822 /* Create the loop for a clast for statement.
824 - REGION is the sese region we used to generate the scop.
825 - NEXT_E is the edge where new generated code should be attached.
826 - RENAME_MAP contains a set of tuples of new names associated to
827 the original variables names.
828 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
829 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
832 translate_clast_for_loop (sese region
, loop_p context_loop
,
833 struct clast_for
*stmt
, edge next_e
,
834 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
835 htab_t newivs_index
, htab_t bb_pbb_mapping
,
836 int level
, htab_t params_index
)
838 struct loop
*loop
= graphite_create_new_loop (region
, next_e
, stmt
,
839 context_loop
, newivs
,
840 newivs_index
, params_index
);
841 edge last_e
= single_exit (loop
);
842 edge to_body
= single_succ_edge (loop
->header
);
843 basic_block after
= to_body
->dest
;
845 /* Create a basic block for loop close phi nodes. */
846 last_e
= single_succ_edge (split_edge (last_e
));
848 /* Translate the body of the loop. */
849 next_e
= translate_clast (region
, loop
, stmt
->body
, to_body
, rename_map
,
850 newivs
, newivs_index
, bb_pbb_mapping
, level
+ 1,
852 redirect_edge_succ_nodup (next_e
, after
);
853 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
855 /* Remove from rename_map all the tuples containing variables
856 defined in loop's body. */
857 insert_loop_close_phis (rename_map
, loop
);
859 if (flag_loop_parallelize_all
860 && !dependency_in_loop_p (loop
, bb_pbb_mapping
,
861 get_scattering_level (level
)))
862 loop
->can_be_parallel
= true;
867 /* Translates a clast for statement STMT to gimple. First a guard is created
868 protecting the loop, if it is executed zero times. In this guard we create
869 the real loop structure.
871 - REGION is the sese region we used to generate the scop.
872 - NEXT_E is the edge where new generated code should be attached.
873 - RENAME_MAP contains a set of tuples of new names associated to
874 the original variables names.
875 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
876 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
879 translate_clast_for (sese region
, loop_p context_loop
, struct clast_for
*stmt
,
880 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
881 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
884 edge last_e
= graphite_create_new_loop_guard (region
, next_e
, stmt
, *newivs
,
885 newivs_index
, params_index
);
887 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
888 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
889 edge exit_true_e
= single_succ_edge (true_e
->dest
);
890 edge exit_false_e
= single_succ_edge (false_e
->dest
);
892 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
893 eq_rename_map_elts
, free
);
894 htab_traverse (rename_map
, copy_renames
, before_guard
);
896 next_e
= translate_clast_for_loop (region
, context_loop
, stmt
, true_e
,
898 newivs_index
, bb_pbb_mapping
, level
,
901 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
902 before_guard
, rename_map
);
904 htab_delete (before_guard
);
909 /* Translates a clast guard statement STMT to gimple.
911 - REGION is the sese region we used to generate the scop.
912 - NEXT_E is the edge where new generated code should be attached.
913 - CONTEXT_LOOP is the loop in which the generated code will be placed
914 - RENAME_MAP contains a set of tuples of new names associated to
915 the original variables names.
916 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
917 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
920 translate_clast_guard (sese region
, loop_p context_loop
,
921 struct clast_guard
*stmt
, edge next_e
,
922 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
923 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
926 edge last_e
= graphite_create_new_guard (region
, next_e
, stmt
, *newivs
,
927 newivs_index
, params_index
);
929 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
930 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
931 edge exit_true_e
= single_succ_edge (true_e
->dest
);
932 edge exit_false_e
= single_succ_edge (false_e
->dest
);
934 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
935 eq_rename_map_elts
, free
);
936 htab_traverse (rename_map
, copy_renames
, before_guard
);
938 next_e
= translate_clast (region
, context_loop
, stmt
->then
, true_e
,
939 rename_map
, newivs
, newivs_index
, bb_pbb_mapping
,
940 level
, params_index
);
942 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
943 before_guard
, rename_map
);
945 htab_delete (before_guard
);
950 /* Translates a CLAST statement STMT to GCC representation in the
953 - NEXT_E is the edge where new generated code should be attached.
954 - CONTEXT_LOOP is the loop in which the generated code will be placed
955 - RENAME_MAP contains a set of tuples of new names associated to
956 the original variables names.
957 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
959 translate_clast (sese region
, loop_p context_loop
, struct clast_stmt
*stmt
,
960 edge next_e
, htab_t rename_map
, VEC (tree
, heap
) **newivs
,
961 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
964 if (!stmt
|| gloog_error
)
967 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
970 else if (CLAST_STMT_IS_A (stmt
, stmt_user
))
971 next_e
= translate_clast_user (region
, (struct clast_user_stmt
*) stmt
,
972 next_e
, rename_map
, newivs
, newivs_index
,
973 bb_pbb_mapping
, params_index
);
975 else if (CLAST_STMT_IS_A (stmt
, stmt_for
))
976 next_e
= translate_clast_for (region
, context_loop
,
977 (struct clast_for
*) stmt
, next_e
,
978 rename_map
, newivs
, newivs_index
,
979 bb_pbb_mapping
, level
, params_index
);
981 else if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
982 next_e
= translate_clast_guard (region
, context_loop
,
983 (struct clast_guard
*) stmt
, next_e
,
984 rename_map
, newivs
, newivs_index
,
985 bb_pbb_mapping
, level
, params_index
);
987 else if (CLAST_STMT_IS_A (stmt
, stmt_block
))
988 next_e
= translate_clast (region
, context_loop
,
989 ((struct clast_block
*) stmt
)->body
,
990 next_e
, rename_map
, newivs
, newivs_index
,
991 bb_pbb_mapping
, level
, params_index
);
995 recompute_all_dominators ();
998 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
999 rename_map
, newivs
, newivs_index
,
1000 bb_pbb_mapping
, level
, params_index
);
1003 /* Returns the first cloog name used in EXPR. */
1006 find_cloog_iv_in_expr (struct clast_expr
*expr
)
1008 struct clast_term
*term
= (struct clast_term
*) expr
;
1010 if (expr
->type
== expr_term
1014 if (expr
->type
== expr_term
)
1017 if (expr
->type
== expr_red
)
1020 struct clast_reduction
*red
= (struct clast_reduction
*) expr
;
1022 for (i
= 0; i
< red
->n
; i
++)
1024 const char *res
= find_cloog_iv_in_expr ((red
)->elts
[i
]);
1034 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
1035 induction variables and the corresponding GCC old induction
1036 variables. This information is stored on each GRAPHITE_BB. */
1039 compute_cloog_iv_types_1 (poly_bb_p pbb
, struct clast_user_stmt
*user_stmt
)
1041 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1042 struct clast_stmt
*t
;
1045 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
1048 struct ivtype_map_elt_s tmp
;
1049 struct clast_expr
*expr
= (struct clast_expr
*)
1050 ((struct clast_assignment
*)t
)->RHS
;
1052 /* Create an entry (clast_var, type). */
1053 tmp
.cloog_iv
= find_cloog_iv_in_expr (expr
);
1057 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, INSERT
);
1061 tree oldiv
= pbb_to_depth_to_oldiv (pbb
, index
);
1062 tree type
= oldiv
? TREE_TYPE (oldiv
) : integer_type_node
;
1063 *slot
= new_ivtype_map_elt (tmp
.cloog_iv
, type
);
1068 /* Walk the CLAST tree starting from STMT and build for each
1069 clast_user_stmt a map between the CLAST induction variables and the
1070 corresponding GCC old induction variables. This information is
1071 stored on each GRAPHITE_BB. */
1074 compute_cloog_iv_types (struct clast_stmt
*stmt
)
1079 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1082 if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1084 CloogStatement
*cs
= ((struct clast_user_stmt
*) stmt
)->statement
;
1085 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
1086 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1088 if (!GBB_CLOOG_IV_TYPES (gbb
))
1089 GBB_CLOOG_IV_TYPES (gbb
) = htab_create (10, ivtype_map_elt_info
,
1090 eq_ivtype_map_elts
, free
);
1092 compute_cloog_iv_types_1 (pbb
, (struct clast_user_stmt
*) stmt
);
1096 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1098 struct clast_stmt
*s
= ((struct clast_for
*) stmt
)->body
;
1099 compute_cloog_iv_types (s
);
1103 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1105 struct clast_stmt
*s
= ((struct clast_guard
*) stmt
)->then
;
1106 compute_cloog_iv_types (s
);
1110 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1112 struct clast_stmt
*s
= ((struct clast_block
*) stmt
)->body
;
1113 compute_cloog_iv_types (s
);
1120 compute_cloog_iv_types (stmt
->next
);
1123 /* Free the SCATTERING domain list. */
1126 free_scattering (CloogDomainList
*scattering
)
1130 CloogDomain
*dom
= cloog_domain (scattering
);
1131 CloogDomainList
*next
= cloog_next_domain (scattering
);
1133 cloog_domain_free (dom
);
1139 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1140 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1141 from 0 to scop_nb_loops (scop). */
1144 initialize_cloog_names (scop_p scop
, CloogProgram
*prog
)
1146 sese region
= SCOP_REGION (scop
);
1148 int nb_iterators
= scop_max_loop_depth (scop
);
1149 int nb_scattering
= cloog_program_nb_scattdims (prog
);
1150 int nb_parameters
= VEC_length (tree
, SESE_PARAMS (region
));
1151 char **iterators
= XNEWVEC (char *, nb_iterators
* 2);
1152 char **scattering
= XNEWVEC (char *, nb_scattering
);
1153 char **parameters
= XNEWVEC (char *, nb_parameters
);
1155 cloog_program_set_names (prog
, cloog_names_malloc ());
1157 for (i
= 0; i
< nb_parameters
; i
++)
1159 tree param
= VEC_index (tree
, SESE_PARAMS(region
), i
);
1160 const char *name
= get_name (param
);
1166 len
= strlen (name
);
1168 parameters
[i
] = XNEWVEC (char, len
+ 1);
1169 snprintf (parameters
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (param
));
1172 cloog_names_set_nb_parameters (cloog_program_names (prog
), nb_parameters
);
1173 cloog_names_set_parameters (cloog_program_names (prog
), parameters
);
1175 for (i
= 0; i
< nb_iterators
; i
++)
1178 iterators
[i
] = XNEWVEC (char, len
);
1179 snprintf (iterators
[i
], len
, "git_%d", i
);
1182 cloog_names_set_nb_iterators (cloog_program_names (prog
),
1184 cloog_names_set_iterators (cloog_program_names (prog
),
1187 for (i
= 0; i
< nb_scattering
; i
++)
1190 scattering
[i
] = XNEWVEC (char, len
);
1191 snprintf (scattering
[i
], len
, "scat_%d", i
);
1194 cloog_names_set_nb_scattering (cloog_program_names (prog
),
1196 cloog_names_set_scattering (cloog_program_names (prog
),
1200 /* Build cloog program for SCoP. */
1203 build_cloog_prog (scop_p scop
, CloogProgram
*prog
)
1206 int max_nb_loops
= scop_max_loop_depth (scop
);
1208 CloogLoop
*loop_list
= NULL
;
1209 CloogBlockList
*block_list
= NULL
;
1210 CloogDomainList
*scattering
= NULL
;
1211 int nbs
= 2 * max_nb_loops
+ 1;
1214 cloog_program_set_context
1215 (prog
, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop
)));
1216 nbs
= unify_scattering_dimensions (scop
);
1217 scaldims
= (int *) xmalloc (nbs
* (sizeof (int)));
1218 cloog_program_set_nb_scattdims (prog
, nbs
);
1219 initialize_cloog_names (scop
, prog
);
1221 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1223 CloogStatement
*stmt
;
1226 /* Dead code elimination: when the domain of a PBB is empty,
1227 don't generate code for the PBB. */
1228 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb
)))
1231 /* Build the new statement and its block. */
1232 stmt
= cloog_statement_alloc (pbb_index (pbb
));
1233 block
= cloog_block_alloc (stmt
, 0, NULL
, pbb_dim_iter_domain (pbb
));
1234 cloog_statement_set_usr (stmt
, pbb
);
1236 /* Build loop list. */
1238 CloogLoop
*new_loop_list
= cloog_loop_malloc ();
1239 cloog_loop_set_next (new_loop_list
, loop_list
);
1240 cloog_loop_set_domain
1242 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb
)));
1243 cloog_loop_set_block (new_loop_list
, block
);
1244 loop_list
= new_loop_list
;
1247 /* Build block list. */
1249 CloogBlockList
*new_block_list
= cloog_block_list_malloc ();
1251 cloog_block_list_set_next (new_block_list
, block_list
);
1252 cloog_block_list_set_block (new_block_list
, block
);
1253 block_list
= new_block_list
;
1256 /* Build scattering list. */
1258 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1259 CloogDomainList
*new_scattering
1260 = (CloogDomainList
*) xmalloc (sizeof (CloogDomainList
));
1261 ppl_Polyhedron_t scat
;
1264 scat
= PBB_TRANSFORMED_SCATTERING (pbb
);
1265 dom
= new_Cloog_Domain_from_ppl_Polyhedron (scat
);
1267 cloog_set_next_domain (new_scattering
, scattering
);
1268 cloog_set_domain (new_scattering
, dom
);
1269 scattering
= new_scattering
;
1273 cloog_program_set_loop (prog
, loop_list
);
1274 cloog_program_set_blocklist (prog
, block_list
);
1276 for (i
= 0; i
< nbs
; i
++)
1279 cloog_program_set_scaldims (prog
, scaldims
);
1281 /* Extract scalar dimensions to simplify the code generation problem. */
1282 cloog_program_extract_scalars (prog
, scattering
);
1284 /* Apply scattering. */
1285 cloog_program_scatter (prog
, scattering
);
1286 free_scattering (scattering
);
1288 /* Iterators corresponding to scalar dimensions have to be extracted. */
1289 cloog_names_scalarize (cloog_program_names (prog
), nbs
,
1290 cloog_program_scaldims (prog
));
1292 /* Free blocklist. */
1294 CloogBlockList
*next
= cloog_program_blocklist (prog
);
1298 CloogBlockList
*toDelete
= next
;
1299 next
= cloog_block_list_next (next
);
1300 cloog_block_list_set_next (toDelete
, NULL
);
1301 cloog_block_list_set_block (toDelete
, NULL
);
1302 cloog_block_list_free (toDelete
);
1304 cloog_program_set_blocklist (prog
, NULL
);
1308 /* Return the options that will be used in GLOOG. */
1310 static CloogOptions
*
1311 set_cloog_options (void)
1313 CloogOptions
*options
= cloog_options_malloc ();
1315 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1316 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1317 we pass an incomplete program to cloog. */
1318 options
->language
= LANGUAGE_C
;
1320 /* Enable complex equality spreading: removes dummy statements
1321 (assignments) in the generated code which repeats the
1322 substitution equations for statements. This is useless for
1326 /* Enable C pretty-printing mode: normalizes the substitution
1327 equations for statements. */
1330 /* Allow cloog to build strides with a stride width different to one.
1331 This example has stride = 4:
1333 for (i = 0; i < 20; i += 4)
1335 options
->strides
= 1;
1337 /* Disable optimizations and make cloog generate source code closer to the
1338 input. This is useful for debugging, but later we want the optimized
1341 XXX: We can not disable optimizations, as loop blocking is not working
1343 if (!flag_graphite_cloog_opts
)
1346 options
->l
= INT_MAX
;
1352 /* Prints STMT to STDERR. */
1355 print_clast_stmt (FILE *file
, struct clast_stmt
*stmt
)
1357 CloogOptions
*options
= set_cloog_options ();
1359 pprint (file
, stmt
, 0, options
);
1360 cloog_options_free (options
);
1363 /* Prints STMT to STDERR. */
1366 debug_clast_stmt (struct clast_stmt
*stmt
)
1368 print_clast_stmt (stderr
, stmt
);
1371 /* Translate SCOP to a CLooG program and clast. These two
1372 representations should be freed together: a clast cannot be used
1373 without a program. */
1376 scop_to_clast (scop_p scop
)
1378 CloogOptions
*options
= set_cloog_options ();
1379 cloog_prog_clast pc
;
1381 /* Connect new cloog prog generation to graphite. */
1382 pc
.prog
= cloog_program_malloc ();
1383 build_cloog_prog (scop
, pc
.prog
);
1384 pc
.prog
= cloog_program_generate (pc
.prog
, options
);
1385 pc
.stmt
= cloog_clast_create (pc
.prog
, options
);
1387 cloog_options_free (options
);
1391 /* Prints to FILE the code generated by CLooG for SCOP. */
1394 print_generated_program (FILE *file
, scop_p scop
)
1396 CloogOptions
*options
= set_cloog_options ();
1397 cloog_prog_clast pc
= scop_to_clast (scop
);
1399 fprintf (file
, " (prog: \n");
1400 cloog_program_print (file
, pc
.prog
);
1401 fprintf (file
, " )\n");
1403 fprintf (file
, " (clast: \n");
1404 pprint (file
, pc
.stmt
, 0, options
);
1405 fprintf (file
, " )\n");
1407 cloog_options_free (options
);
1408 cloog_clast_free (pc
.stmt
);
1409 cloog_program_free (pc
.prog
);
1412 /* Prints to STDERR the code generated by CLooG for SCOP. */
1415 debug_generated_program (scop_p scop
)
1417 print_generated_program (stderr
, scop
);
1420 /* Add CLooG names to parameter index. The index is used to translate
1421 back from CLooG names to GCC trees. */
1424 create_params_index (htab_t index_table
, CloogProgram
*prog
) {
1425 CloogNames
* names
= cloog_program_names (prog
);
1426 int nb_parameters
= cloog_names_nb_parameters (names
);
1427 char **parameters
= cloog_names_parameters (names
);
1430 for (i
= 0; i
< nb_parameters
; i
++)
1431 save_clast_name_index (index_table
, parameters
[i
], i
);
1434 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1435 the given SCOP. Return true if code generation succeeded.
1436 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1440 gloog (scop_p scop
, htab_t bb_pbb_mapping
)
1442 edge new_scop_exit_edge
= NULL
;
1443 VEC (tree
, heap
) *newivs
= VEC_alloc (tree
, heap
, 10);
1444 loop_p context_loop
;
1445 sese region
= SCOP_REGION (scop
);
1446 ifsese if_region
= NULL
;
1447 htab_t rename_map
, newivs_index
, params_index
;
1448 cloog_prog_clast pc
;
1450 timevar_push (TV_GRAPHITE_CODE_GEN
);
1451 gloog_error
= false;
1453 pc
= scop_to_clast (scop
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 fprintf (dump_file
, "\nCLAST generated by CLooG: \n");
1458 print_clast_stmt (dump_file
, pc
.stmt
);
1459 fprintf (dump_file
, "\n");
1462 recompute_all_dominators ();
1465 if_region
= move_sese_in_condition (region
);
1466 sese_insert_phis_for_liveouts (region
,
1467 if_region
->region
->exit
->src
,
1468 if_region
->false_region
->exit
,
1469 if_region
->true_region
->exit
);
1470 recompute_all_dominators ();
1473 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1474 compute_cloog_iv_types (pc
.stmt
);
1475 rename_map
= htab_create (10, rename_map_elt_info
, eq_rename_map_elts
, free
);
1476 newivs_index
= htab_create (10, clast_name_index_elt_info
,
1477 eq_clast_name_indexes
, free
);
1478 params_index
= htab_create (10, clast_name_index_elt_info
,
1479 eq_clast_name_indexes
, free
);
1481 create_params_index (params_index
, pc
.prog
);
1483 new_scop_exit_edge
= translate_clast (region
, context_loop
, pc
.stmt
,
1484 if_region
->true_region
->entry
,
1485 rename_map
, &newivs
, newivs_index
,
1486 bb_pbb_mapping
, 1, params_index
);
1488 sese_adjust_liveout_phis (region
, rename_map
,
1489 if_region
->region
->exit
->src
,
1490 if_region
->false_region
->exit
,
1491 if_region
->true_region
->exit
);
1493 rename_nb_iterations (rename_map
);
1494 recompute_all_dominators ();
1498 set_ifsese_condition (if_region
, integer_zero_node
);
1500 free (if_region
->true_region
);
1501 free (if_region
->region
);
1504 htab_delete (rename_map
);
1505 htab_delete (newivs_index
);
1506 htab_delete (params_index
);
1507 VEC_free (tree
, heap
, newivs
);
1508 cloog_clast_free (pc
.stmt
);
1509 cloog_program_free (pc
.prog
);
1510 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1516 int num_no_dependency
= 0;
1518 FOR_EACH_LOOP (li
, loop
, 0)
1519 if (loop
->can_be_parallel
)
1520 num_no_dependency
++;
1522 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1526 return !gloog_error
;