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"
24 #include "diagnostic-core.h"
25 #include "tree-flow.h"
26 #include "tree-dump.h"
28 #include "tree-chrec.h"
29 #include "tree-data-ref.h"
30 #include "tree-scalar-evolution.h"
34 #include "cloog/cloog.h"
36 #include "graphite-cloog-util.h"
37 #include "graphite-ppl.h"
38 #include "graphite-poly.h"
39 #include "graphite-clast-to-gimple.h"
40 #include "graphite-dependences.h"
41 #include "graphite-cloog-compat.h"
43 /* This flag is set when an error occurred during the translation of
45 static bool gloog_error
;
47 /* Verifies properties that GRAPHITE should maintain during translation. */
50 graphite_verify (void)
52 #ifdef ENABLE_CHECKING
53 verify_loop_structure ();
54 verify_dominators (CDI_DOMINATORS
);
55 verify_loop_closed_ssa (true);
59 /* Stores the INDEX in a vector for a given clast NAME. */
61 typedef struct clast_name_index
{
64 } *clast_name_index_p
;
66 /* Returns a pointer to a new element of type clast_name_index_p built
67 from NAME and INDEX. */
69 static inline clast_name_index_p
70 new_clast_name_index (const char *name
, int index
)
72 clast_name_index_p res
= XNEW (struct clast_name_index
);
79 /* For a given clast NAME, returns -1 if it does not correspond to any
80 parameter, or otherwise, returns the index in the PARAMS or
81 SCATTERING_DIMENSIONS vector. */
84 clast_name_to_index (clast_name_p name
, htab_t index_table
)
86 struct clast_name_index tmp
;
90 gcc_assert (name
->type
== clast_expr_name
);
91 tmp
.name
= ((const struct clast_name
*) name
)->name
;
96 slot
= htab_find_slot (index_table
, &tmp
, NO_INSERT
);
99 return ((struct clast_name_index
*) *slot
)->index
;
104 /* Records in INDEX_TABLE the INDEX for NAME. */
107 save_clast_name_index (htab_t index_table
, const char *name
, int index
)
109 struct clast_name_index tmp
;
113 slot
= htab_find_slot (index_table
, &tmp
, INSERT
);
119 *slot
= new_clast_name_index (name
, index
);
123 /* Computes a hash function for database element ELT. */
125 static inline hashval_t
126 clast_name_index_elt_info (const void *elt
)
128 return htab_hash_pointer (((const struct clast_name_index
*) elt
)->name
);
131 /* Compares database elements E1 and E2. */
134 eq_clast_name_indexes (const void *e1
, const void *e2
)
136 const struct clast_name_index
*elt1
= (const struct clast_name_index
*) e1
;
137 const struct clast_name_index
*elt2
= (const struct clast_name_index
*) e2
;
139 return (elt1
->name
== elt2
->name
);
142 /* For a given scattering dimension, return the new induction variable
146 newivs_to_depth_to_newiv (VEC (tree
, heap
) *newivs
, int depth
)
148 return VEC_index (tree
, newivs
, depth
);
153 /* Returns the tree variable from the name NAME that was given in
154 Cloog representation. */
157 clast_name_to_gcc (clast_name_p name
, sese region
, VEC (tree
, heap
) *newivs
,
158 htab_t newivs_index
, htab_t params_index
)
161 VEC (tree
, heap
) *params
= SESE_PARAMS (region
);
163 if (params
&& params_index
)
165 index
= clast_name_to_index (name
, params_index
);
168 return VEC_index (tree
, params
, index
);
171 gcc_assert (newivs
&& newivs_index
);
172 index
= clast_name_to_index (name
, newivs_index
);
173 gcc_assert (index
>= 0);
175 return newivs_to_depth_to_newiv (newivs
, index
);
178 /* Returns the signed maximal precision type for expressions TYPE1 and TYPE2. */
181 max_signed_precision_type (tree type1
, tree type2
)
183 int p1
= TYPE_PRECISION (type1
);
184 int p2
= TYPE_PRECISION (type2
);
187 enum machine_mode mode
;
190 precision
= TYPE_UNSIGNED (type1
) ? p1
* 2 : p1
;
192 precision
= TYPE_UNSIGNED (type2
) ? p2
* 2 : p2
;
194 if (precision
> BITS_PER_WORD
)
197 return integer_type_node
;
200 mode
= smallest_mode_for_size (precision
, MODE_INT
);
201 precision
= GET_MODE_PRECISION (mode
);
202 type
= build_nonstandard_integer_type (precision
, false);
207 return integer_type_node
;
213 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
216 max_precision_type (tree type1
, tree type2
)
218 if (POINTER_TYPE_P (type1
))
221 if (POINTER_TYPE_P (type2
))
224 if (!TYPE_UNSIGNED (type1
)
225 || !TYPE_UNSIGNED (type2
))
226 return max_signed_precision_type (type1
, type2
);
228 return TYPE_PRECISION (type1
) > TYPE_PRECISION (type2
) ? type1
: type2
;
232 clast_to_gcc_expression (tree
, struct clast_expr
*, sese
, VEC (tree
, heap
) *,
235 /* Converts a Cloog reduction expression R with reduction operation OP
236 to a GCC expression tree of type TYPE. */
239 clast_to_gcc_expression_red (tree type
, enum tree_code op
,
240 struct clast_reduction
*r
,
241 sese region
, VEC (tree
, heap
) *newivs
,
242 htab_t newivs_index
, htab_t params_index
)
245 tree res
= clast_to_gcc_expression (type
, r
->elts
[0], region
, newivs
,
246 newivs_index
, params_index
);
247 tree operand_type
= (op
== POINTER_PLUS_EXPR
) ? sizetype
: type
;
249 for (i
= 1; i
< r
->n
; i
++)
251 tree t
= clast_to_gcc_expression (operand_type
, r
->elts
[i
], region
,
252 newivs
, newivs_index
, params_index
);
253 res
= fold_build2 (op
, type
, res
, t
);
259 /* Converts a Cloog AST expression E back to a GCC expression tree of
263 clast_to_gcc_expression (tree type
, struct clast_expr
*e
,
264 sese region
, VEC (tree
, heap
) *newivs
,
265 htab_t newivs_index
, htab_t params_index
)
269 case clast_expr_term
:
271 struct clast_term
*t
= (struct clast_term
*) e
;
275 if (mpz_cmp_si (t
->val
, 1) == 0)
277 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
278 newivs_index
, params_index
);
280 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
281 name
= fold_convert (sizetype
, name
);
283 name
= fold_convert (type
, name
);
287 else if (mpz_cmp_si (t
->val
, -1) == 0)
289 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
290 newivs_index
, params_index
);
292 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
293 name
= fold_convert (sizetype
, name
);
295 name
= fold_convert (type
, name
);
297 return fold_build1 (NEGATE_EXPR
, type
, name
);
301 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
302 newivs_index
, params_index
);
303 tree cst
= gmp_cst_to_tree (type
, t
->val
);
305 if (POINTER_TYPE_P (TREE_TYPE (name
)) != POINTER_TYPE_P (type
))
306 name
= fold_convert (sizetype
, name
);
308 name
= fold_convert (type
, name
);
310 if (!POINTER_TYPE_P (type
))
311 return fold_build2 (MULT_EXPR
, type
, cst
, name
);
318 return gmp_cst_to_tree (type
, t
->val
);
323 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
328 return clast_to_gcc_expression_red
329 (type
, POINTER_TYPE_P (type
) ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
330 r
, region
, newivs
, newivs_index
, params_index
);
333 return clast_to_gcc_expression_red (type
, MIN_EXPR
, r
, region
,
334 newivs
, newivs_index
,
338 return clast_to_gcc_expression_red (type
, MAX_EXPR
, r
, region
,
339 newivs
, newivs_index
,
350 struct clast_binary
*b
= (struct clast_binary
*) e
;
351 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
352 tree tl
= clast_to_gcc_expression (type
, lhs
, region
, newivs
,
353 newivs_index
, params_index
);
354 tree tr
= gmp_cst_to_tree (type
, b
->RHS
);
359 return fold_build2 (FLOOR_DIV_EXPR
, type
, tl
, tr
);
362 return fold_build2 (CEIL_DIV_EXPR
, type
, tl
, tr
);
365 return fold_build2 (EXACT_DIV_EXPR
, type
, tl
, tr
);
368 return fold_build2 (TRUNC_MOD_EXPR
, type
, tl
, tr
);
382 /* Return a type that could represent the values between V1 and V2. */
385 gcc_type_for_interval (mpz_t v1
, mpz_t v2
)
389 enum machine_mode mode
;
390 int precision
= MAX (mpz_sizeinbase (v1
, 2),
391 mpz_sizeinbase (v2
, 2));
393 if (precision
> BITS_PER_WORD
)
396 return integer_type_node
;
399 if (mpz_cmp (v1
, v2
) <= 0)
400 unsigned_p
= (mpz_sgn (v1
) >= 0);
402 unsigned_p
= (mpz_sgn (v2
) >= 0);
404 mode
= smallest_mode_for_size (precision
, MODE_INT
);
405 precision
= GET_MODE_PRECISION (mode
);
406 type
= build_nonstandard_integer_type (precision
, unsigned_p
);
411 return integer_type_node
;
417 /* Return a type that could represent the integer value VAL, or
418 otherwise return NULL_TREE. */
421 gcc_type_for_value (mpz_t val
)
423 return gcc_type_for_interval (val
, val
);
426 /* Return the type for the clast_term T used in STMT. */
429 gcc_type_for_clast_term (struct clast_term
*t
,
430 sese region
, VEC (tree
, heap
) *newivs
,
431 htab_t newivs_index
, htab_t params_index
)
433 gcc_assert (t
->expr
.type
== clast_expr_term
);
436 return gcc_type_for_value (t
->val
);
438 return TREE_TYPE (clast_name_to_gcc (t
->var
, region
, newivs
,
439 newivs_index
, params_index
));
443 gcc_type_for_clast_expr (struct clast_expr
*, sese
,
444 VEC (tree
, heap
) *, htab_t
, htab_t
);
446 /* Return the type for the clast_reduction R used in STMT. */
449 gcc_type_for_clast_red (struct clast_reduction
*r
, sese region
,
450 VEC (tree
, heap
) *newivs
,
451 htab_t newivs_index
, htab_t params_index
)
454 tree type
= NULL_TREE
;
457 return gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
458 newivs_index
, params_index
);
465 type
= gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
466 newivs_index
, params_index
);
467 for (i
= 1; i
< r
->n
; i
++)
468 type
= max_precision_type (type
, gcc_type_for_clast_expr
469 (r
->elts
[i
], region
, newivs
,
470 newivs_index
, params_index
));
482 /* Return the type for the clast_binary B used in STMT. */
485 gcc_type_for_clast_bin (struct clast_binary
*b
,
486 sese region
, VEC (tree
, heap
) *newivs
,
487 htab_t newivs_index
, htab_t params_index
)
489 tree l
= gcc_type_for_clast_expr ((struct clast_expr
*) b
->LHS
, region
,
490 newivs
, newivs_index
, params_index
);
491 tree r
= gcc_type_for_value (b
->RHS
);
492 return max_signed_precision_type (l
, r
);
495 /* Returns the type for the CLAST expression E when used in statement
499 gcc_type_for_clast_expr (struct clast_expr
*e
,
500 sese region
, VEC (tree
, heap
) *newivs
,
501 htab_t newivs_index
, htab_t params_index
)
505 case clast_expr_term
:
506 return gcc_type_for_clast_term ((struct clast_term
*) e
, region
,
507 newivs
, newivs_index
, params_index
);
510 return gcc_type_for_clast_red ((struct clast_reduction
*) e
, region
,
511 newivs
, newivs_index
, params_index
);
514 return gcc_type_for_clast_bin ((struct clast_binary
*) e
, region
,
515 newivs
, newivs_index
, params_index
);
524 /* Returns the type for the equation CLEQ. */
527 gcc_type_for_clast_eq (struct clast_equation
*cleq
,
528 sese region
, VEC (tree
, heap
) *newivs
,
529 htab_t newivs_index
, htab_t params_index
)
531 tree l
= gcc_type_for_clast_expr (cleq
->LHS
, region
, newivs
,
532 newivs_index
, params_index
);
533 tree r
= gcc_type_for_clast_expr (cleq
->RHS
, region
, newivs
,
534 newivs_index
, params_index
);
535 return max_precision_type (l
, r
);
538 /* Translates a clast equation CLEQ to a tree. */
541 graphite_translate_clast_equation (sese region
,
542 struct clast_equation
*cleq
,
543 VEC (tree
, heap
) *newivs
,
544 htab_t newivs_index
, htab_t params_index
)
547 tree type
= gcc_type_for_clast_eq (cleq
, region
, newivs
, newivs_index
,
549 tree lhs
= clast_to_gcc_expression (type
, cleq
->LHS
, region
, newivs
,
550 newivs_index
, params_index
);
551 tree rhs
= clast_to_gcc_expression (type
, cleq
->RHS
, region
, newivs
,
552 newivs_index
, params_index
);
557 else if (cleq
->sign
> 0)
563 return fold_build2 (comp
, boolean_type_node
, lhs
, rhs
);
566 /* Creates the test for the condition in STMT. */
569 graphite_create_guard_cond_expr (sese region
, struct clast_guard
*stmt
,
570 VEC (tree
, heap
) *newivs
,
571 htab_t newivs_index
, htab_t params_index
)
576 for (i
= 0; i
< stmt
->n
; i
++)
578 tree eq
= graphite_translate_clast_equation (region
, &stmt
->eq
[i
],
579 newivs
, newivs_index
,
583 cond
= fold_build2 (TRUTH_AND_EXPR
, TREE_TYPE (eq
), cond
, eq
);
591 /* Creates a new if region corresponding to Cloog's guard. */
594 graphite_create_new_guard (sese region
, edge entry_edge
,
595 struct clast_guard
*stmt
,
596 VEC (tree
, heap
) *newivs
,
597 htab_t newivs_index
, htab_t params_index
)
599 tree cond_expr
= graphite_create_guard_cond_expr (region
, stmt
, newivs
,
600 newivs_index
, params_index
);
601 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
605 /* Compute the lower bound LOW and upper bound UP for the induction
606 variable at LEVEL for the statement PBB, based on the transformed
607 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
608 the iteration domain, and G the context parameters. */
611 compute_bounds_for_level (poly_bb_p pbb
, int level
, mpz_t low
, mpz_t up
)
613 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
614 ppl_Linear_Expression_t le
;
616 combine_context_id_scat (&ps
, pbb
, false);
618 /* Prepare the linear expression corresponding to the level that we
619 want to maximize/minimize. */
621 ppl_dimension_type dim
= pbb_nb_scattering_transform (pbb
)
622 + pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
624 ppl_new_Linear_Expression_with_dimension (&le
, dim
);
625 ppl_set_coef (le
, psct_dynamic_dim (pbb
, level
), 1);
628 ppl_max_for_le_pointset (ps
, le
, up
);
629 ppl_min_for_le_pointset (ps
, le
, low
);
630 ppl_delete_Linear_Expression (le
);
631 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
634 /* Compute the type for the induction variable at LEVEL for the
635 statement PBB, based on the transformed schedule of PBB. */
638 compute_type_for_level (poly_bb_p pbb
, int level
)
646 compute_bounds_for_level (pbb
, level
, low
, up
);
647 type
= gcc_type_for_interval (low
, up
);
654 /* Walks a CLAST and returns the first statement in the body of a
657 static struct clast_user_stmt
*
658 clast_get_body_of_loop (struct clast_stmt
*stmt
)
661 || CLAST_STMT_IS_A (stmt
, stmt_user
))
662 return (struct clast_user_stmt
*) stmt
;
664 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
665 return clast_get_body_of_loop (((struct clast_for
*) stmt
)->body
);
667 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
668 return clast_get_body_of_loop (((struct clast_guard
*) stmt
)->then
);
670 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
671 return clast_get_body_of_loop (((struct clast_block
*) stmt
)->body
);
676 /* Returns the type for the induction variable for the loop translated
680 gcc_type_for_iv_of_clast_loop (struct clast_for
*stmt_for
, int level
,
681 tree lb_type
, tree ub_type
)
683 struct clast_stmt
*stmt
= (struct clast_stmt
*) stmt_for
;
684 struct clast_user_stmt
*body
= clast_get_body_of_loop (stmt
);
685 CloogStatement
*cs
= body
->statement
;
686 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
688 return max_signed_precision_type (lb_type
, max_precision_type
689 (ub_type
, compute_type_for_level
693 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
694 induction variable for the new LOOP. New LOOP is attached to CFG
695 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
696 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
697 CLooG's scattering name to the induction variable created for the
698 loop of STMT. The new induction variable is inserted in the NEWIVS
699 vector and is of type TYPE. */
702 graphite_create_new_loop (edge entry_edge
,
703 struct clast_for
*stmt
,
704 loop_p outer
, VEC (tree
, heap
) **newivs
,
706 tree type
, tree lb
, tree ub
)
708 tree stride
= gmp_cst_to_tree (type
, stmt
->stride
);
709 tree ivvar
= create_tmp_var (type
, "graphite_IV");
710 tree iv
, iv_after_increment
;
711 loop_p loop
= create_empty_loop_on_edge
712 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
713 outer
? outer
: entry_edge
->src
->loop_father
);
715 add_referenced_var (ivvar
);
717 save_clast_name_index (newivs_index
, stmt
->iterator
,
718 VEC_length (tree
, *newivs
));
719 VEC_safe_push (tree
, heap
, *newivs
, iv
);
723 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
724 induction variables of the loops around GBB in SESE. */
727 build_iv_mapping (VEC (tree
, heap
) *iv_map
, sese region
,
728 VEC (tree
, heap
) *newivs
, htab_t newivs_index
,
729 struct clast_user_stmt
*user_stmt
,
732 struct clast_stmt
*t
;
734 CloogStatement
*cs
= user_stmt
->statement
;
735 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
736 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
738 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, depth
++)
740 struct clast_expr
*expr
= (struct clast_expr
*)
741 ((struct clast_assignment
*)t
)->RHS
;
742 tree type
= gcc_type_for_clast_expr (expr
, region
, newivs
,
743 newivs_index
, params_index
);
744 tree new_name
= clast_to_gcc_expression (type
, expr
, region
, newivs
,
745 newivs_index
, params_index
);
746 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, depth
);
748 VEC_replace (tree
, iv_map
, old_loop
->num
, new_name
);
752 /* Construct bb_pbb_def with BB and PBB. */
755 new_bb_pbb_def (basic_block bb
, poly_bb_p pbb
)
757 bb_pbb_def
*bb_pbb_p
;
759 bb_pbb_p
= XNEW (bb_pbb_def
);
766 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
769 mark_bb_with_pbb (poly_bb_p pbb
, basic_block bb
, htab_t bb_pbb_mapping
)
775 x
= htab_find_slot (bb_pbb_mapping
, &tmp
, INSERT
);
778 *x
= new_bb_pbb_def (bb
, pbb
);
781 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
784 find_pbb_via_hash (htab_t bb_pbb_mapping
, basic_block bb
)
790 slot
= htab_find_slot (bb_pbb_mapping
, &tmp
, NO_INSERT
);
793 return ((bb_pbb_def
*) *slot
)->pbb
;
798 /* Check data dependency in LOOP at level LEVEL.
799 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
803 dependency_in_loop_p (loop_p loop
, htab_t bb_pbb_mapping
, int level
)
806 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
808 for (i
= 0; i
< loop
->num_nodes
; i
++)
810 poly_bb_p pbb1
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[i
]);
815 for (j
= 0; j
< loop
->num_nodes
; j
++)
817 poly_bb_p pbb2
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[j
]);
822 if (dependency_between_pbbs_p (pbb1
, pbb2
, level
))
835 /* Translates a clast user statement STMT to gimple.
837 - REGION is the sese region we used to generate the scop.
838 - NEXT_E is the edge where new generated code should be attached.
839 - CONTEXT_LOOP is the loop in which the generated code will be placed
840 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
841 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
844 translate_clast_user (sese region
, struct clast_user_stmt
*stmt
, edge next_e
,
845 VEC (tree
, heap
) **newivs
,
846 htab_t newivs_index
, htab_t bb_pbb_mapping
,
851 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (stmt
->statement
);
852 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
853 VEC (tree
, heap
) *iv_map
;
855 if (GBB_BB (gbb
) == ENTRY_BLOCK_PTR
)
858 nb_loops
= number_of_loops ();
859 iv_map
= VEC_alloc (tree
, heap
, nb_loops
);
860 for (i
= 0; i
< nb_loops
; i
++)
861 VEC_quick_push (tree
, iv_map
, NULL_TREE
);
863 build_iv_mapping (iv_map
, region
, *newivs
, newivs_index
, stmt
, params_index
);
864 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), region
,
866 VEC_free (tree
, heap
, iv_map
);
868 new_bb
= next_e
->src
;
869 mark_bb_with_pbb (pbb
, new_bb
, bb_pbb_mapping
);
870 update_ssa (TODO_update_ssa
);
875 /* Creates a new if region protecting the loop to be executed, if the execution
876 count is zero (lb > ub). */
879 graphite_create_new_loop_guard (sese region
, edge entry_edge
,
880 struct clast_for
*stmt
,
881 VEC (tree
, heap
) *newivs
,
882 htab_t newivs_index
, htab_t params_index
,
883 int level
, tree
*type
, tree
*lb
, tree
*ub
)
887 tree lb_type
= gcc_type_for_clast_expr (stmt
->LB
, region
, newivs
,
888 newivs_index
, params_index
);
889 tree ub_type
= gcc_type_for_clast_expr (stmt
->UB
, region
, newivs
,
890 newivs_index
, params_index
);
892 *type
= gcc_type_for_iv_of_clast_loop (stmt
, level
, lb_type
, ub_type
);
893 *lb
= clast_to_gcc_expression (*type
, stmt
->LB
, region
, newivs
,
894 newivs_index
, params_index
);
895 *ub
= clast_to_gcc_expression (*type
, stmt
->UB
, region
, newivs
,
896 newivs_index
, params_index
);
898 /* When ub is simply a constant or a parameter, use lb <= ub. */
899 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
900 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
903 tree one
= (POINTER_TYPE_P (*type
)
905 : fold_convert (*type
, integer_one_node
));
906 /* Adding +1 and using LT_EXPR helps with loop latches that have a
907 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
908 2^k-1 due to integer overflow, and the condition lb <= ub is true,
909 even if we do not want this. However lb < ub + 1 is false, as
911 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
912 : PLUS_EXPR
, *type
, *ub
, one
);
914 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
917 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
923 translate_clast (sese
, loop_p
, struct clast_stmt
*, edge
,
924 VEC (tree
, heap
) **, htab_t
, htab_t
, int, htab_t
);
926 /* Create the loop for a clast for statement.
928 - REGION is the sese region we used to generate the scop.
929 - NEXT_E is the edge where new generated code should be attached.
930 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
931 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
935 translate_clast_for_loop (sese region
, loop_p context_loop
,
936 struct clast_for
*stmt
, edge next_e
,
937 VEC (tree
, heap
) **newivs
,
938 htab_t newivs_index
, htab_t bb_pbb_mapping
,
939 int level
, htab_t params_index
, tree type
,
942 struct loop
*loop
= graphite_create_new_loop (next_e
, stmt
,
943 context_loop
, newivs
,
946 edge last_e
= single_exit (loop
);
947 edge to_body
= single_succ_edge (loop
->header
);
948 basic_block after
= to_body
->dest
;
950 /* Create a basic block for loop close phi nodes. */
951 last_e
= single_succ_edge (split_edge (last_e
));
953 /* Translate the body of the loop. */
954 next_e
= translate_clast (region
, loop
, stmt
->body
, to_body
,
955 newivs
, newivs_index
, bb_pbb_mapping
, level
+ 1,
957 redirect_edge_succ_nodup (next_e
, after
);
958 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
960 if (flag_loop_parallelize_all
961 && !dependency_in_loop_p (loop
, bb_pbb_mapping
, level
))
962 loop
->can_be_parallel
= true;
967 /* Translates a clast for statement STMT to gimple. First a guard is created
968 protecting the loop, if it is executed zero times. In this guard we create
969 the real loop structure.
971 - REGION is the sese region we used to generate the scop.
972 - NEXT_E is the edge where new generated code should be attached.
973 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
974 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
977 translate_clast_for (sese region
, loop_p context_loop
, struct clast_for
*stmt
,
978 edge next_e
, VEC (tree
, heap
) **newivs
,
979 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
983 edge last_e
= graphite_create_new_loop_guard (region
, next_e
, stmt
, *newivs
,
984 newivs_index
, params_index
,
985 level
, &type
, &lb
, &ub
);
986 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
988 translate_clast_for_loop (region
, context_loop
, stmt
, true_e
, newivs
,
989 newivs_index
, bb_pbb_mapping
, level
,
990 params_index
, type
, lb
, ub
);
994 /* Translates a clast guard statement STMT to gimple.
996 - REGION is the sese region we used to generate the scop.
997 - NEXT_E is the edge where new generated code should be attached.
998 - CONTEXT_LOOP is the loop in which the generated code will be placed
999 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
1000 - PARAMS_INDEX connects the cloog parameters with the gimple parameters in
1003 translate_clast_guard (sese region
, loop_p context_loop
,
1004 struct clast_guard
*stmt
, edge next_e
,
1005 VEC (tree
, heap
) **newivs
,
1006 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
1007 htab_t params_index
)
1009 edge last_e
= graphite_create_new_guard (region
, next_e
, stmt
, *newivs
,
1010 newivs_index
, params_index
);
1011 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1013 translate_clast (region
, context_loop
, stmt
->then
, true_e
,
1014 newivs
, newivs_index
, bb_pbb_mapping
,
1015 level
, params_index
);
1019 /* Translates a CLAST statement STMT to GCC representation in the
1022 - NEXT_E is the edge where new generated code should be attached.
1023 - CONTEXT_LOOP is the loop in which the generated code will be placed
1024 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1026 translate_clast (sese region
, loop_p context_loop
, struct clast_stmt
*stmt
,
1027 edge next_e
, VEC (tree
, heap
) **newivs
,
1028 htab_t newivs_index
, htab_t bb_pbb_mapping
, int level
,
1029 htab_t params_index
)
1034 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
1037 else if (CLAST_STMT_IS_A (stmt
, stmt_user
))
1038 next_e
= translate_clast_user (region
, (struct clast_user_stmt
*) stmt
,
1039 next_e
, newivs
, newivs_index
,
1040 bb_pbb_mapping
, params_index
);
1042 else if (CLAST_STMT_IS_A (stmt
, stmt_for
))
1043 next_e
= translate_clast_for (region
, context_loop
,
1044 (struct clast_for
*) stmt
, next_e
,
1045 newivs
, newivs_index
,
1046 bb_pbb_mapping
, level
, params_index
);
1048 else if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
1049 next_e
= translate_clast_guard (region
, context_loop
,
1050 (struct clast_guard
*) stmt
, next_e
,
1051 newivs
, newivs_index
,
1052 bb_pbb_mapping
, level
, params_index
);
1054 else if (CLAST_STMT_IS_A (stmt
, stmt_block
))
1055 next_e
= translate_clast (region
, context_loop
,
1056 ((struct clast_block
*) stmt
)->body
,
1057 next_e
, newivs
, newivs_index
,
1058 bb_pbb_mapping
, level
, params_index
);
1062 recompute_all_dominators ();
1065 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
1066 newivs
, newivs_index
,
1067 bb_pbb_mapping
, level
, params_index
);
1070 /* Free the SCATTERING domain list. */
1073 free_scattering (CloogScatteringList
*scattering
)
1077 CloogScattering
*dom
= cloog_scattering (scattering
);
1078 CloogScatteringList
*next
= cloog_next_scattering (scattering
);
1080 cloog_scattering_free (dom
);
1086 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1087 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1088 from 0 to scop_nb_loops (scop). */
1091 initialize_cloog_names (scop_p scop
, CloogProgram
*prog
)
1093 sese region
= SCOP_REGION (scop
);
1095 int nb_iterators
= scop_max_loop_depth (scop
);
1096 int nb_scattering
= cloog_program_nb_scattdims (prog
);
1097 int nb_parameters
= VEC_length (tree
, SESE_PARAMS (region
));
1098 char **iterators
= XNEWVEC (char *, nb_iterators
* 2);
1099 char **scattering
= XNEWVEC (char *, nb_scattering
);
1100 char **parameters
= XNEWVEC (char *, nb_parameters
);
1102 cloog_program_set_names (prog
, cloog_names_malloc ());
1104 for (i
= 0; i
< nb_parameters
; i
++)
1106 tree param
= VEC_index (tree
, SESE_PARAMS(region
), i
);
1107 const char *name
= get_name (param
);
1113 len
= strlen (name
);
1115 parameters
[i
] = XNEWVEC (char, len
+ 1);
1116 snprintf (parameters
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (param
));
1119 cloog_names_set_nb_parameters (cloog_program_names (prog
), nb_parameters
);
1120 cloog_names_set_parameters (cloog_program_names (prog
), parameters
);
1122 for (i
= 0; i
< nb_iterators
; i
++)
1125 iterators
[i
] = XNEWVEC (char, len
);
1126 snprintf (iterators
[i
], len
, "git_%d", i
);
1129 cloog_names_set_nb_iterators (cloog_program_names (prog
),
1131 cloog_names_set_iterators (cloog_program_names (prog
),
1134 for (i
= 0; i
< nb_scattering
; i
++)
1137 scattering
[i
] = XNEWVEC (char, len
);
1138 snprintf (scattering
[i
], len
, "scat_%d", i
);
1141 cloog_names_set_nb_scattering (cloog_program_names (prog
),
1143 cloog_names_set_scattering (cloog_program_names (prog
),
1147 /* Initialize a CLooG input file. */
1150 init_cloog_input_file (int scop_number
)
1152 FILE *graphite_out_file
;
1153 int len
= strlen (dump_base_name
);
1154 char *dumpname
= XNEWVEC (char, len
+ 25);
1155 char *s_scop_number
= XNEWVEC (char, 15);
1157 memcpy (dumpname
, dump_base_name
, len
+ 1);
1158 strip_off_ending (dumpname
, len
);
1159 sprintf (s_scop_number
, ".%d", scop_number
);
1160 strcat (dumpname
, s_scop_number
);
1161 strcat (dumpname
, ".cloog");
1162 graphite_out_file
= fopen (dumpname
, "w+b");
1164 if (graphite_out_file
== 0)
1165 fatal_error ("can%'t open %s for writing: %m", dumpname
);
1169 return graphite_out_file
;
1172 /* Build cloog program for SCoP. */
1175 build_cloog_prog (scop_p scop
, CloogProgram
*prog
,
1176 CloogOptions
*options
)
1179 int max_nb_loops
= scop_max_loop_depth (scop
);
1181 CloogLoop
*loop_list
= NULL
;
1182 CloogBlockList
*block_list
= NULL
;
1183 CloogScatteringList
*scattering
= NULL
;
1184 int nbs
= 2 * max_nb_loops
+ 1;
1187 cloog_program_set_context
1188 (prog
, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop
),
1189 scop_nb_params (scop
), cloog_state
));
1190 nbs
= unify_scattering_dimensions (scop
);
1191 scaldims
= (int *) xmalloc (nbs
* (sizeof (int)));
1192 cloog_program_set_nb_scattdims (prog
, nbs
);
1193 initialize_cloog_names (scop
, prog
);
1195 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1197 CloogStatement
*stmt
;
1201 /* Dead code elimination: when the domain of a PBB is empty,
1202 don't generate code for the PBB. */
1203 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb
)))
1206 /* Build the new statement and its block. */
1207 stmt
= cloog_statement_alloc (cloog_state
, pbb_index (pbb
));
1208 dom
= new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb
),
1209 scop_nb_params (scop
),
1211 block
= cloog_block_alloc (stmt
, 0, NULL
, pbb_dim_iter_domain (pbb
));
1212 cloog_statement_set_usr (stmt
, pbb
);
1214 /* Build loop list. */
1216 CloogLoop
*new_loop_list
= cloog_loop_malloc (cloog_state
);
1217 cloog_loop_set_next (new_loop_list
, loop_list
);
1218 cloog_loop_set_domain (new_loop_list
, dom
);
1219 cloog_loop_set_block (new_loop_list
, block
);
1220 loop_list
= new_loop_list
;
1223 /* Build block list. */
1225 CloogBlockList
*new_block_list
= cloog_block_list_malloc ();
1227 cloog_block_list_set_next (new_block_list
, block_list
);
1228 cloog_block_list_set_block (new_block_list
, block
);
1229 block_list
= new_block_list
;
1232 /* Build scattering list. */
1234 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1235 CloogScatteringList
*new_scattering
1236 = (CloogScatteringList
*) xmalloc (sizeof (CloogScatteringList
));
1237 ppl_Polyhedron_t scat
;
1238 CloogScattering
*dom
;
1240 scat
= PBB_TRANSFORMED_SCATTERING (pbb
);
1241 dom
= new_Cloog_Scattering_from_ppl_Polyhedron
1242 (scat
, scop_nb_params (scop
), pbb_nb_scattering_transform (pbb
),
1245 cloog_set_next_scattering (new_scattering
, scattering
);
1246 cloog_set_scattering (new_scattering
, dom
);
1247 scattering
= new_scattering
;
1251 cloog_program_set_loop (prog
, loop_list
);
1252 cloog_program_set_blocklist (prog
, block_list
);
1254 for (i
= 0; i
< nbs
; i
++)
1257 cloog_program_set_scaldims (prog
, scaldims
);
1259 /* Extract scalar dimensions to simplify the code generation problem. */
1260 cloog_program_extract_scalars (prog
, scattering
, options
);
1262 /* Dump a .cloog input file, if requested. This feature is only
1263 enabled in the Graphite branch. */
1266 static size_t file_scop_number
= 0;
1267 FILE *cloog_file
= init_cloog_input_file (file_scop_number
);
1269 cloog_program_dump_cloog (cloog_file
, prog
, scattering
);
1273 /* Apply scattering. */
1274 cloog_program_scatter (prog
, scattering
, options
);
1275 free_scattering (scattering
);
1277 /* Iterators corresponding to scalar dimensions have to be extracted. */
1278 cloog_names_scalarize (cloog_program_names (prog
), nbs
,
1279 cloog_program_scaldims (prog
));
1281 /* Free blocklist. */
1283 CloogBlockList
*next
= cloog_program_blocklist (prog
);
1287 CloogBlockList
*toDelete
= next
;
1288 next
= cloog_block_list_next (next
);
1289 cloog_block_list_set_next (toDelete
, NULL
);
1290 cloog_block_list_set_block (toDelete
, NULL
);
1291 cloog_block_list_free (toDelete
);
1293 cloog_program_set_blocklist (prog
, NULL
);
1297 /* Return the options that will be used in GLOOG. */
1299 static CloogOptions
*
1300 set_cloog_options (void)
1302 CloogOptions
*options
= cloog_options_malloc (cloog_state
);
1304 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1305 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1306 we pass an incomplete program to cloog. */
1307 options
->language
= LANGUAGE_C
;
1309 /* Enable complex equality spreading: removes dummy statements
1310 (assignments) in the generated code which repeats the
1311 substitution equations for statements. This is useless for
1316 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1319 /* Enable C pretty-printing mode: normalizes the substitution
1320 equations for statements. */
1324 /* Allow cloog to build strides with a stride width different to one.
1325 This example has stride = 4:
1327 for (i = 0; i < 20; i += 4)
1329 options
->strides
= 1;
1331 /* Disable optimizations and make cloog generate source code closer to the
1332 input. This is useful for debugging, but later we want the optimized
1335 XXX: We can not disable optimizations, as loop blocking is not working
1340 options
->l
= INT_MAX
;
1346 /* Prints STMT to STDERR. */
1349 print_clast_stmt (FILE *file
, struct clast_stmt
*stmt
)
1351 CloogOptions
*options
= set_cloog_options ();
1353 clast_pprint (file
, stmt
, 0, options
);
1354 cloog_options_free (options
);
1357 /* Prints STMT to STDERR. */
1360 debug_clast_stmt (struct clast_stmt
*stmt
)
1362 print_clast_stmt (stderr
, stmt
);
1365 /* Translate SCOP to a CLooG program and clast. These two
1366 representations should be freed together: a clast cannot be used
1367 without a program. */
1370 scop_to_clast (scop_p scop
)
1372 CloogOptions
*options
= set_cloog_options ();
1373 cloog_prog_clast pc
;
1375 /* Connect new cloog prog generation to graphite. */
1376 pc
.prog
= cloog_program_malloc ();
1377 build_cloog_prog (scop
, pc
.prog
, options
);
1378 pc
.prog
= cloog_program_generate (pc
.prog
, options
);
1379 pc
.stmt
= cloog_clast_create (pc
.prog
, options
);
1381 cloog_options_free (options
);
1385 /* Prints to FILE the code generated by CLooG for SCOP. */
1388 print_generated_program (FILE *file
, scop_p scop
)
1390 CloogOptions
*options
= set_cloog_options ();
1392 cloog_prog_clast pc
= scop_to_clast (scop
);
1394 fprintf (file
, " (prog: \n");
1395 cloog_program_print (file
, pc
.prog
);
1396 fprintf (file
, " )\n");
1398 fprintf (file
, " (clast: \n");
1399 clast_pprint (file
, pc
.stmt
, 0, options
);
1400 fprintf (file
, " )\n");
1402 cloog_options_free (options
);
1403 cloog_clast_free (pc
.stmt
);
1404 cloog_program_free (pc
.prog
);
1407 /* Prints to STDERR the code generated by CLooG for SCOP. */
1410 debug_generated_program (scop_p scop
)
1412 print_generated_program (stderr
, scop
);
1415 /* Add CLooG names to parameter index. The index is used to translate
1416 back from CLooG names to GCC trees. */
1419 create_params_index (htab_t index_table
, CloogProgram
*prog
) {
1420 CloogNames
* names
= cloog_program_names (prog
);
1421 int nb_parameters
= cloog_names_nb_parameters (names
);
1422 char **parameters
= cloog_names_parameters (names
);
1425 for (i
= 0; i
< nb_parameters
; i
++)
1426 save_clast_name_index (index_table
, parameters
[i
], i
);
1429 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1430 the given SCOP. Return true if code generation succeeded.
1431 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1435 gloog (scop_p scop
, htab_t bb_pbb_mapping
)
1437 VEC (tree
, heap
) *newivs
= VEC_alloc (tree
, heap
, 10);
1438 loop_p context_loop
;
1439 sese region
= SCOP_REGION (scop
);
1440 ifsese if_region
= NULL
;
1441 htab_t newivs_index
, params_index
;
1442 cloog_prog_clast pc
;
1444 timevar_push (TV_GRAPHITE_CODE_GEN
);
1445 gloog_error
= false;
1447 pc
= scop_to_clast (scop
);
1449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1451 fprintf (dump_file
, "\nCLAST generated by CLooG: \n");
1452 print_clast_stmt (dump_file
, pc
.stmt
);
1453 fprintf (dump_file
, "\n");
1456 recompute_all_dominators ();
1459 if_region
= move_sese_in_condition (region
);
1460 sese_insert_phis_for_liveouts (region
,
1461 if_region
->region
->exit
->src
,
1462 if_region
->false_region
->exit
,
1463 if_region
->true_region
->exit
);
1464 recompute_all_dominators ();
1467 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1468 newivs_index
= htab_create (10, clast_name_index_elt_info
,
1469 eq_clast_name_indexes
, free
);
1470 params_index
= htab_create (10, clast_name_index_elt_info
,
1471 eq_clast_name_indexes
, free
);
1473 create_params_index (params_index
, pc
.prog
);
1475 translate_clast (region
, context_loop
, pc
.stmt
,
1476 if_region
->true_region
->entry
,
1477 &newivs
, newivs_index
,
1478 bb_pbb_mapping
, 0, params_index
);
1481 recompute_all_dominators ();
1485 set_ifsese_condition (if_region
, integer_zero_node
);
1487 free (if_region
->true_region
);
1488 free (if_region
->region
);
1491 htab_delete (newivs_index
);
1492 htab_delete (params_index
);
1493 VEC_free (tree
, heap
, newivs
);
1494 cloog_clast_free (pc
.stmt
);
1495 cloog_program_free (pc
.prog
);
1496 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1502 int num_no_dependency
= 0;
1504 FOR_EACH_LOOP (li
, loop
, 0)
1505 if (loop
->can_be_parallel
)
1506 num_no_dependency
++;
1508 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1512 return !gloog_error
;