1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-dependences.h"
55 /* Verifies properties that GRAPHITE should maintain during translation. */
58 graphite_verify (void)
60 #ifdef ENABLE_CHECKING
61 verify_loop_structure ();
62 verify_dominators (CDI_DOMINATORS
);
63 verify_dominators (CDI_POST_DOMINATORS
);
65 verify_loop_closed_ssa ();
69 /* For a given loop DEPTH in the loop nest of the original black box
70 PBB, return the old induction variable associated to that loop. */
73 pbb_to_depth_to_oldiv (poly_bb_p pbb
, int depth
)
75 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
76 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
77 loop_p loop
= gbb_loop_at_index (gbb
, region
, depth
);
79 return (tree
) loop
->aux
;
82 /* For a given scattering dimension, return the new induction variable
86 newivs_to_depth_to_newiv (VEC (tree
, heap
) *newivs
, int depth
)
88 return VEC_index (tree
, newivs
, depth
);
93 /* Returns the tree variable from the name NAME that was given in
94 Cloog representation. */
97 clast_name_to_gcc (const char *name
, sese region
, VEC (tree
, heap
) *newivs
,
101 VEC (tree
, heap
) *params
= SESE_PARAMS (region
);
102 htab_t params_index
= SESE_PARAMS_INDEX (region
);
104 if (params
&& params_index
)
106 index
= clast_name_to_index (name
, params_index
);
109 return VEC_index (tree
, params
, index
);
112 gcc_assert (newivs
&& newivs_index
);
113 index
= clast_name_to_index (name
, newivs_index
);
114 gcc_assert (index
>= 0);
116 return newivs_to_depth_to_newiv (newivs
, index
);
119 /* Returns the maximal precision type for expressions E1 and E2. */
122 max_precision_type (tree e1
, tree e2
)
124 tree type1
= TREE_TYPE (e1
);
125 tree type2
= TREE_TYPE (e2
);
126 return TYPE_PRECISION (type1
) > TYPE_PRECISION (type2
) ? type1
: type2
;
130 clast_to_gcc_expression (tree
, struct clast_expr
*, sese
, VEC (tree
, heap
) *,
133 /* Converts a Cloog reduction expression R with reduction operation OP
134 to a GCC expression tree of type TYPE. */
137 clast_to_gcc_expression_red (tree type
, enum tree_code op
,
138 struct clast_reduction
*r
,
139 sese region
, VEC (tree
, heap
) *newivs
,
143 tree res
= clast_to_gcc_expression (type
, r
->elts
[0], region
, newivs
,
145 tree operand_type
= (op
== POINTER_PLUS_EXPR
) ? sizetype
: type
;
147 for (i
= 1; i
< r
->n
; i
++)
149 tree t
= clast_to_gcc_expression (operand_type
, r
->elts
[i
], region
,
150 newivs
, newivs_index
);
151 res
= fold_build2 (op
, type
, res
, t
);
157 /* Converts a Cloog AST expression E back to a GCC expression tree of
161 clast_to_gcc_expression (tree type
, struct clast_expr
*e
,
162 sese region
, VEC (tree
, heap
) *newivs
,
169 struct clast_term
*t
= (struct clast_term
*) e
;
173 if (value_one_p (t
->val
))
175 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
177 return fold_convert (type
, name
);
180 else if (value_mone_p (t
->val
))
182 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
184 name
= fold_convert (type
, name
);
185 return fold_build1 (NEGATE_EXPR
, type
, name
);
189 tree name
= clast_name_to_gcc (t
->var
, region
, newivs
,
191 tree cst
= gmp_cst_to_tree (type
, t
->val
);
192 name
= fold_convert (type
, name
);
193 return fold_build2 (MULT_EXPR
, type
, cst
, name
);
197 return gmp_cst_to_tree (type
, t
->val
);
202 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
207 return clast_to_gcc_expression_red
208 (type
, POINTER_TYPE_P (type
) ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
209 r
, region
, newivs
, newivs_index
);
212 return clast_to_gcc_expression_red (type
, MIN_EXPR
, r
, region
,
213 newivs
, newivs_index
);
216 return clast_to_gcc_expression_red (type
, MAX_EXPR
, r
, region
,
217 newivs
, newivs_index
);
227 struct clast_binary
*b
= (struct clast_binary
*) e
;
228 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
229 tree tl
= clast_to_gcc_expression (type
, lhs
, region
, newivs
,
231 tree tr
= gmp_cst_to_tree (type
, b
->RHS
);
236 return fold_build2 (FLOOR_DIV_EXPR
, type
, tl
, tr
);
239 return fold_build2 (CEIL_DIV_EXPR
, type
, tl
, tr
);
242 return fold_build2 (EXACT_DIV_EXPR
, type
, tl
, tr
);
245 return fold_build2 (TRUNC_MOD_EXPR
, type
, tl
, tr
);
259 /* Returns the type for the expression E. */
262 gcc_type_for_clast_expr (struct clast_expr
*e
,
263 sese region
, VEC (tree
, heap
) *newivs
,
270 struct clast_term
*t
= (struct clast_term
*) e
;
273 return TREE_TYPE (clast_name_to_gcc (t
->var
, region
, newivs
,
281 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
284 return gcc_type_for_clast_expr (r
->elts
[0], region
, newivs
,
289 for (i
= 0; i
< r
->n
; i
++)
291 tree type
= gcc_type_for_clast_expr (r
->elts
[i
], region
,
292 newivs
, newivs_index
);
302 struct clast_binary
*b
= (struct clast_binary
*) e
;
303 struct clast_expr
*lhs
= (struct clast_expr
*) b
->LHS
;
304 return gcc_type_for_clast_expr (lhs
, region
, newivs
,
315 /* Returns the type for the equation CLEQ. */
318 gcc_type_for_clast_eq (struct clast_equation
*cleq
,
319 sese region
, VEC (tree
, heap
) *newivs
,
322 tree type
= gcc_type_for_clast_expr (cleq
->LHS
, region
, newivs
,
327 return gcc_type_for_clast_expr (cleq
->RHS
, region
, newivs
, newivs_index
);
330 /* Translates a clast equation CLEQ to a tree. */
333 graphite_translate_clast_equation (sese region
,
334 struct clast_equation
*cleq
,
335 VEC (tree
, heap
) *newivs
,
339 tree type
= gcc_type_for_clast_eq (cleq
, region
, newivs
, newivs_index
);
340 tree lhs
= clast_to_gcc_expression (type
, cleq
->LHS
, region
, newivs
,
342 tree rhs
= clast_to_gcc_expression (type
, cleq
->RHS
, region
, newivs
,
348 else if (cleq
->sign
> 0)
354 return fold_build2 (comp
, boolean_type_node
, lhs
, rhs
);
357 /* Creates the test for the condition in STMT. */
360 graphite_create_guard_cond_expr (sese region
, struct clast_guard
*stmt
,
361 VEC (tree
, heap
) *newivs
,
367 for (i
= 0; i
< stmt
->n
; i
++)
369 tree eq
= graphite_translate_clast_equation (region
, &stmt
->eq
[i
],
370 newivs
, newivs_index
);
373 cond
= fold_build2 (TRUTH_AND_EXPR
, TREE_TYPE (eq
), cond
, eq
);
381 /* Creates a new if region corresponding to Cloog's guard. */
384 graphite_create_new_guard (sese region
, edge entry_edge
,
385 struct clast_guard
*stmt
,
386 VEC (tree
, heap
) *newivs
,
389 tree cond_expr
= graphite_create_guard_cond_expr (region
, stmt
, newivs
,
391 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
395 /* Walks a CLAST and returns the first statement in the body of a
398 static struct clast_user_stmt
*
399 clast_get_body_of_loop (struct clast_stmt
*stmt
)
402 || CLAST_STMT_IS_A (stmt
, stmt_user
))
403 return (struct clast_user_stmt
*) stmt
;
405 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
406 return clast_get_body_of_loop (((struct clast_for
*) stmt
)->body
);
408 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
409 return clast_get_body_of_loop (((struct clast_guard
*) stmt
)->then
);
411 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
412 return clast_get_body_of_loop (((struct clast_block
*) stmt
)->body
);
417 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
418 If the information is not available, i.e. in the case one of the
419 transforms created the loop, just return integer_type_node. */
422 gcc_type_for_cloog_iv (const char *cloog_iv
, gimple_bb_p gbb
)
424 struct ivtype_map_elt_s tmp
;
427 tmp
.cloog_iv
= cloog_iv
;
428 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, NO_INSERT
);
431 return ((ivtype_map_elt
) *slot
)->type
;
433 return integer_type_node
;
436 /* Returns the induction variable for the loop that gets translated to
440 gcc_type_for_iv_of_clast_loop (struct clast_for
*stmt_for
)
442 struct clast_stmt
*stmt
= (struct clast_stmt
*) stmt_for
;
443 struct clast_user_stmt
*body
= clast_get_body_of_loop (stmt
);
444 const char *cloog_iv
= stmt_for
->iterator
;
445 CloogStatement
*cs
= body
->statement
;
446 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
448 return gcc_type_for_cloog_iv (cloog_iv
, PBB_BLACK_BOX (pbb
));
451 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
452 induction variable for the new LOOP. New LOOP is attached to CFG
453 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
454 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
455 CLooG's scattering name to the induction variable created for the
456 loop of STMT. The new induction variable is inserted in the NEWIVS
460 graphite_create_new_loop (sese region
, edge entry_edge
,
461 struct clast_for
*stmt
,
462 loop_p outer
, VEC (tree
, heap
) **newivs
,
465 tree type
= gcc_type_for_iv_of_clast_loop (stmt
);
466 tree lb
= clast_to_gcc_expression (type
, stmt
->LB
, region
, *newivs
,
468 tree ub
= clast_to_gcc_expression (type
, stmt
->UB
, region
, *newivs
,
470 tree stride
= gmp_cst_to_tree (type
, stmt
->stride
);
471 tree ivvar
= create_tmp_var (type
, "graphite_IV");
472 tree iv
, iv_after_increment
;
473 loop_p loop
= create_empty_loop_on_edge
474 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
475 outer
? outer
: entry_edge
->src
->loop_father
);
477 add_referenced_var (ivvar
);
479 save_clast_name_index (newivs_index
, stmt
->iterator
,
480 VEC_length (tree
, *newivs
));
481 VEC_safe_push (tree
, heap
, *newivs
, iv
);
485 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
486 variables of the loops around GBB in SESE. */
489 build_iv_mapping (htab_t map
, sese region
,
490 VEC (tree
, heap
) *newivs
, htab_t newivs_index
,
491 struct clast_user_stmt
*user_stmt
)
493 struct clast_stmt
*t
;
495 CloogStatement
*cs
= user_stmt
->statement
;
496 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
498 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
500 struct clast_expr
*expr
= (struct clast_expr
*)
501 ((struct clast_assignment
*)t
)->RHS
;
502 tree type
= gcc_type_for_clast_expr (expr
, region
, newivs
,
504 tree old_name
= pbb_to_depth_to_oldiv (pbb
, index
);
505 tree e
= clast_to_gcc_expression (type
, expr
, region
, newivs
,
507 set_rename (map
, old_name
, e
);
511 /* Helper function for htab_traverse. */
514 copy_renames (void **slot
, void *s
)
516 struct rename_map_elt_s
*entry
= (struct rename_map_elt_s
*) *slot
;
517 htab_t res
= (htab_t
) s
;
518 tree old_name
= entry
->old_name
;
519 tree expr
= entry
->expr
;
520 struct rename_map_elt_s tmp
;
523 tmp
.old_name
= old_name
;
524 x
= htab_find_slot (res
, &tmp
, INSERT
);
527 *x
= new_rename_map_elt (old_name
, expr
);
532 /* Construct bb_pbb_def with BB and PBB. */
535 new_bb_pbb_def (basic_block bb
, poly_bb_p pbb
)
537 bb_pbb_def
*bb_pbb_p
;
539 bb_pbb_p
= XNEW (bb_pbb_def
);
546 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
549 mark_bb_with_pbb (poly_bb_p pbb
, basic_block bb
, htab_t bb_pbb_mapping
)
555 x
= htab_find_slot (bb_pbb_mapping
, &tmp
, INSERT
);
558 *x
= new_bb_pbb_def (bb
, pbb
);
561 /* Returns the scattering dimension for STMTFOR.
563 FIXME: This is a hackish solution to locate the scattering
564 dimension in newly created loops. Here the hackish solush
565 assume that the stmt_for->iterator is always something like:
566 scat_1 , scat_3 etc., where after "scat_" is loop level in
567 scattering dimension.
570 static int get_stmtfor_depth (struct clast_for
*stmtfor
)
572 const char * iterator
= stmtfor
->iterator
;
575 depth
= strchr (iterator
, '_');
576 if (!strncmp (iterator
, "scat_", 5))
577 return atoi (depth
+1);
582 /* Translates a CLAST statement STMT to GCC representation in the
585 - NEXT_E is the edge where new generated code should be attached.
586 - CONTEXT_LOOP is the loop in which the generated code will be placed
587 - RENAME_MAP contains a set of tuples of new names associated to
588 the original variables names.
589 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.
593 translate_clast (sese region
, struct loop
*context_loop
,
594 struct clast_stmt
*stmt
, edge next_e
,
595 htab_t rename_map
, VEC (tree
, heap
) **newivs
,
596 htab_t newivs_index
, htab_t bb_pbb_mapping
)
601 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
602 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
603 rename_map
, newivs
, newivs_index
, bb_pbb_mapping
);
605 if (CLAST_STMT_IS_A (stmt
, stmt_user
))
609 CloogStatement
*cs
= ((struct clast_user_stmt
*) stmt
)->statement
;
610 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
611 gbb
= PBB_BLACK_BOX (pbb
);
613 if (GBB_BB (gbb
) == ENTRY_BLOCK_PTR
)
616 build_iv_mapping (rename_map
, region
, *newivs
, newivs_index
,
617 (struct clast_user_stmt
*) stmt
);
618 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), region
,
620 new_bb
= next_e
->src
;
621 mark_bb_with_pbb (pbb
, new_bb
, bb_pbb_mapping
);
622 recompute_all_dominators ();
623 update_ssa (TODO_update_ssa
);
625 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
626 rename_map
, newivs
, newivs_index
,
630 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
632 struct clast_for
*stmtfor
= (struct clast_for
*)stmt
;
634 = graphite_create_new_loop (region
, next_e
, stmtfor
,
635 context_loop
, newivs
, newivs_index
);
636 edge last_e
= single_exit (loop
);
637 edge to_body
= single_succ_edge (loop
->header
);
638 basic_block after
= to_body
->dest
;
640 loop
->aux
= XNEW (int);
641 /* Pass scattering level information of the new loop by LOOP->AUX. */
642 *((int *)(loop
->aux
)) = get_stmtfor_depth (stmtfor
);
644 /* Create a basic block for loop close phi nodes. */
645 last_e
= single_succ_edge (split_edge (last_e
));
647 /* Translate the body of the loop. */
648 next_e
= translate_clast
649 (region
, loop
, ((struct clast_for
*) stmt
)->body
,
650 single_succ_edge (loop
->header
), rename_map
, newivs
,
651 newivs_index
, bb_pbb_mapping
);
652 redirect_edge_succ_nodup (next_e
, after
);
653 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
655 /* Remove from rename_map all the tuples containing variables
656 defined in loop's body. */
657 insert_loop_close_phis (rename_map
, loop
);
659 recompute_all_dominators ();
661 return translate_clast (region
, context_loop
, stmt
->next
, last_e
,
662 rename_map
, newivs
, newivs_index
,
666 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
668 edge last_e
= graphite_create_new_guard (region
, next_e
,
669 ((struct clast_guard
*) stmt
),
670 *newivs
, newivs_index
);
671 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
672 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
673 edge exit_true_e
= single_succ_edge (true_e
->dest
);
674 edge exit_false_e
= single_succ_edge (false_e
->dest
);
675 htab_t before_guard
= htab_create (10, rename_map_elt_info
,
676 eq_rename_map_elts
, free
);
678 htab_traverse (rename_map
, copy_renames
, before_guard
);
679 next_e
= translate_clast (region
, context_loop
,
680 ((struct clast_guard
*) stmt
)->then
,
681 true_e
, rename_map
, newivs
, newivs_index
,
683 insert_guard_phis (last_e
->src
, exit_true_e
, exit_false_e
,
684 before_guard
, rename_map
);
686 htab_delete (before_guard
);
687 recompute_all_dominators ();
690 return translate_clast (region
, context_loop
, stmt
->next
, last_e
,
691 rename_map
, newivs
, newivs_index
,
695 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
697 next_e
= translate_clast (region
, context_loop
,
698 ((struct clast_block
*) stmt
)->body
,
699 next_e
, rename_map
, newivs
, newivs_index
,
701 recompute_all_dominators ();
703 return translate_clast (region
, context_loop
, stmt
->next
, next_e
,
704 rename_map
, newivs
, newivs_index
,
711 /* Returns the first cloog name used in EXPR. */
714 find_cloog_iv_in_expr (struct clast_expr
*expr
)
716 struct clast_term
*term
= (struct clast_term
*) expr
;
718 if (expr
->type
== expr_term
722 if (expr
->type
== expr_term
)
725 if (expr
->type
== expr_red
)
728 struct clast_reduction
*red
= (struct clast_reduction
*) expr
;
730 for (i
= 0; i
< red
->n
; i
++)
732 const char *res
= find_cloog_iv_in_expr ((red
)->elts
[i
]);
742 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
743 induction variables and the corresponding GCC old induction
744 variables. This information is stored on each GRAPHITE_BB. */
747 compute_cloog_iv_types_1 (poly_bb_p pbb
, struct clast_user_stmt
*user_stmt
)
749 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
750 struct clast_stmt
*t
;
753 for (t
= user_stmt
->substitutions
; t
; t
= t
->next
, index
++)
756 struct ivtype_map_elt_s tmp
;
757 struct clast_expr
*expr
= (struct clast_expr
*)
758 ((struct clast_assignment
*)t
)->RHS
;
760 /* Create an entry (clast_var, type). */
761 tmp
.cloog_iv
= find_cloog_iv_in_expr (expr
);
765 slot
= htab_find_slot (GBB_CLOOG_IV_TYPES (gbb
), &tmp
, INSERT
);
769 tree oldiv
= pbb_to_depth_to_oldiv (pbb
, index
);
770 tree type
= oldiv
? TREE_TYPE (oldiv
) : integer_type_node
;
771 *slot
= new_ivtype_map_elt (tmp
.cloog_iv
, type
);
776 /* Walk the CLAST tree starting from STMT and build for each
777 clast_user_stmt a map between the CLAST induction variables and the
778 corresponding GCC old induction variables. This information is
779 stored on each GRAPHITE_BB. */
782 compute_cloog_iv_types (struct clast_stmt
*stmt
)
787 if (CLAST_STMT_IS_A (stmt
, stmt_root
))
790 if (CLAST_STMT_IS_A (stmt
, stmt_user
))
792 CloogStatement
*cs
= ((struct clast_user_stmt
*) stmt
)->statement
;
793 poly_bb_p pbb
= (poly_bb_p
) cloog_statement_usr (cs
);
794 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
796 if (!GBB_CLOOG_IV_TYPES (gbb
))
797 GBB_CLOOG_IV_TYPES (gbb
) = htab_create (10, ivtype_map_elt_info
,
798 eq_ivtype_map_elts
, free
);
800 compute_cloog_iv_types_1 (pbb
, (struct clast_user_stmt
*) stmt
);
804 if (CLAST_STMT_IS_A (stmt
, stmt_for
))
806 struct clast_stmt
*s
= ((struct clast_for
*) stmt
)->body
;
807 compute_cloog_iv_types (s
);
811 if (CLAST_STMT_IS_A (stmt
, stmt_guard
))
813 struct clast_stmt
*s
= ((struct clast_guard
*) stmt
)->then
;
814 compute_cloog_iv_types (s
);
818 if (CLAST_STMT_IS_A (stmt
, stmt_block
))
820 struct clast_stmt
*s
= ((struct clast_block
*) stmt
)->body
;
821 compute_cloog_iv_types (s
);
828 compute_cloog_iv_types (stmt
->next
);
831 /* Free the SCATTERING domain list. */
834 free_scattering (CloogDomainList
*scattering
)
838 CloogDomain
*dom
= cloog_domain (scattering
);
839 CloogDomainList
*next
= cloog_next_domain (scattering
);
841 cloog_domain_free (dom
);
847 /* Initialize Cloog's parameter names from the names used in GIMPLE.
848 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
849 from 0 to scop_nb_loops (scop). */
852 initialize_cloog_names (scop_p scop
, CloogProgram
*prog
)
854 sese region
= SCOP_REGION (scop
);
856 int nb_iterators
= scop_max_loop_depth (scop
);
857 int nb_scattering
= cloog_program_nb_scattdims (prog
);
858 char **iterators
= XNEWVEC (char *, nb_iterators
* 2);
859 char **scattering
= XNEWVEC (char *, nb_scattering
);
861 cloog_program_set_names (prog
, cloog_names_malloc ());
862 cloog_names_set_nb_parameters (cloog_program_names (prog
),
863 VEC_length (tree
, SESE_PARAMS (region
)));
864 cloog_names_set_parameters (cloog_program_names (prog
),
865 SESE_PARAMS_NAMES (region
));
867 for (i
= 0; i
< nb_iterators
; i
++)
870 iterators
[i
] = XNEWVEC (char, len
);
871 snprintf (iterators
[i
], len
, "git_%d", i
);
874 cloog_names_set_nb_iterators (cloog_program_names (prog
),
876 cloog_names_set_iterators (cloog_program_names (prog
),
879 for (i
= 0; i
< nb_scattering
; i
++)
882 scattering
[i
] = XNEWVEC (char, len
);
883 snprintf (scattering
[i
], len
, "scat_%d", i
);
886 cloog_names_set_nb_scattering (cloog_program_names (prog
),
888 cloog_names_set_scattering (cloog_program_names (prog
),
892 /* Build cloog program for SCoP. */
895 build_cloog_prog (scop_p scop
, CloogProgram
*prog
)
898 int max_nb_loops
= scop_max_loop_depth (scop
);
900 CloogLoop
*loop_list
= NULL
;
901 CloogBlockList
*block_list
= NULL
;
902 CloogDomainList
*scattering
= NULL
;
903 int nbs
= 2 * max_nb_loops
+ 1;
906 cloog_program_set_context
907 (prog
, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop
)));
908 nbs
= unify_scattering_dimensions (scop
);
909 scaldims
= (int *) xmalloc (nbs
* (sizeof (int)));
910 cloog_program_set_nb_scattdims (prog
, nbs
);
911 initialize_cloog_names (scop
, prog
);
913 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
915 CloogStatement
*stmt
;
918 /* Dead code elimination: when the domain of a PBB is empty,
919 don't generate code for the PBB. */
920 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb
)))
923 /* Build the new statement and its block. */
924 stmt
= cloog_statement_alloc (GBB_BB (PBB_BLACK_BOX (pbb
))->index
);
925 block
= cloog_block_alloc (stmt
, 0, NULL
, pbb_dim_iter_domain (pbb
));
926 cloog_statement_set_usr (stmt
, pbb
);
928 /* Build loop list. */
930 CloogLoop
*new_loop_list
= cloog_loop_malloc ();
931 cloog_loop_set_next (new_loop_list
, loop_list
);
932 cloog_loop_set_domain
934 new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb
)));
935 cloog_loop_set_block (new_loop_list
, block
);
936 loop_list
= new_loop_list
;
939 /* Build block list. */
941 CloogBlockList
*new_block_list
= cloog_block_list_malloc ();
943 cloog_block_list_set_next (new_block_list
, block_list
);
944 cloog_block_list_set_block (new_block_list
, block
);
945 block_list
= new_block_list
;
948 /* Build scattering list. */
950 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
951 CloogDomainList
*new_scattering
952 = (CloogDomainList
*) xmalloc (sizeof (CloogDomainList
));
953 ppl_Polyhedron_t scat
;
956 scat
= PBB_TRANSFORMED_SCATTERING (pbb
);
957 dom
= new_Cloog_Domain_from_ppl_Polyhedron (scat
);
959 cloog_set_next_domain (new_scattering
, scattering
);
960 cloog_set_domain (new_scattering
, dom
);
961 scattering
= new_scattering
;
965 cloog_program_set_loop (prog
, loop_list
);
966 cloog_program_set_blocklist (prog
, block_list
);
968 for (i
= 0; i
< nbs
; i
++)
971 cloog_program_set_scaldims (prog
, scaldims
);
973 /* Extract scalar dimensions to simplify the code generation problem. */
974 cloog_program_extract_scalars (prog
, scattering
);
976 /* Apply scattering. */
977 cloog_program_scatter (prog
, scattering
);
978 free_scattering (scattering
);
980 /* Iterators corresponding to scalar dimensions have to be extracted. */
981 cloog_names_scalarize (cloog_program_names (prog
), nbs
,
982 cloog_program_scaldims (prog
));
984 /* Free blocklist. */
986 CloogBlockList
*next
= cloog_program_blocklist (prog
);
990 CloogBlockList
*toDelete
= next
;
991 next
= cloog_block_list_next (next
);
992 cloog_block_list_set_next (toDelete
, NULL
);
993 cloog_block_list_set_block (toDelete
, NULL
);
994 cloog_block_list_free (toDelete
);
996 cloog_program_set_blocklist (prog
, NULL
);
1000 /* Return the options that will be used in GLOOG. */
1002 static CloogOptions
*
1003 set_cloog_options (void)
1005 CloogOptions
*options
= cloog_options_malloc ();
1007 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1008 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1009 we pass an incomplete program to cloog. */
1010 options
->language
= LANGUAGE_C
;
1012 /* Enable complex equality spreading: removes dummy statements
1013 (assignments) in the generated code which repeats the
1014 substitution equations for statements. This is useless for
1018 /* Enable C pretty-printing mode: normalizes the substitution
1019 equations for statements. */
1022 /* Allow cloog to build strides with a stride width different to one.
1023 This example has stride = 4:
1025 for (i = 0; i < 20; i += 4)
1027 options
->strides
= 1;
1029 /* Disable optimizations and make cloog generate source code closer to the
1030 input. This is useful for debugging, but later we want the optimized
1033 XXX: We can not disable optimizations, as loop blocking is not working
1038 options
->l
= INT_MAX
;
1044 /* Prints STMT to STDERR. */
1047 print_clast_stmt (FILE *file
, struct clast_stmt
*stmt
)
1049 CloogOptions
*options
= set_cloog_options ();
1051 pprint (file
, stmt
, 0, options
);
1052 cloog_options_free (options
);
1055 /* Prints STMT to STDERR. */
1058 debug_clast_stmt (struct clast_stmt
*stmt
)
1060 print_clast_stmt (stderr
, stmt
);
1063 /* Translate SCOP to a CLooG program and clast. These two
1064 representations should be freed together: a clast cannot be used
1065 without a program. */
1068 scop_to_clast (scop_p scop
)
1070 CloogOptions
*options
= set_cloog_options ();
1071 cloog_prog_clast pc
;
1073 /* Connect new cloog prog generation to graphite. */
1074 pc
.prog
= cloog_program_malloc ();
1075 build_cloog_prog (scop
, pc
.prog
);
1076 pc
.prog
= cloog_program_generate (pc
.prog
, options
);
1077 pc
.stmt
= cloog_clast_create (pc
.prog
, options
);
1079 cloog_options_free (options
);
1083 /* Prints to FILE the code generated by CLooG for SCOP. */
1086 print_generated_program (FILE *file
, scop_p scop
)
1088 CloogOptions
*options
= set_cloog_options ();
1089 cloog_prog_clast pc
= scop_to_clast (scop
);
1091 fprintf (file
, " (prog: \n");
1092 cloog_program_print (file
, pc
.prog
);
1093 fprintf (file
, " )\n");
1095 fprintf (file
, " (clast: \n");
1096 pprint (file
, pc
.stmt
, 0, options
);
1097 fprintf (file
, " )\n");
1099 cloog_options_free (options
);
1100 cloog_clast_free (pc
.stmt
);
1101 cloog_program_free (pc
.prog
);
1104 /* Prints to STDERR the code generated by CLooG for SCOP. */
1107 debug_generated_program (scop_p scop
)
1109 print_generated_program (stderr
, scop
);
1112 /* A LOOP is in normal form for Graphite when it contains only one
1113 scalar phi node that defines the main induction variable of the
1114 loop, only one increment of the IV, and only one exit condition. */
1117 graphite_loop_normal_form (loop_p loop
)
1119 struct tree_niter_desc niter
;
1122 edge exit
= single_dom_exit (loop
);
1124 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
1126 /* At this point we should know the number of iterations, */
1127 gcc_assert (known_niter
);
1129 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
1132 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1134 loop
->aux
= canonicalize_loop_ivs (loop
, &nit
);
1137 /* Converts REGION to loop normal form: one induction variable per loop. */
1140 build_graphite_loop_normal_form (sese region
)
1145 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1146 graphite_loop_normal_form (loop
);
1149 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1150 the given SCOP. Return true if code generation succeeded.
1151 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1155 gloog (scop_p scop
, htab_t bb_pbb_mapping
)
1157 edge new_scop_exit_edge
= NULL
;
1158 VEC (tree
, heap
) *newivs
= VEC_alloc (tree
, heap
, 10);
1159 loop_p context_loop
;
1160 sese region
= SCOP_REGION (scop
);
1161 ifsese if_region
= NULL
;
1162 htab_t rename_map
, newivs_index
;
1163 cloog_prog_clast pc
= scop_to_clast (scop
);
1165 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1167 fprintf (dump_file
, "\nCLAST generated by CLooG: \n");
1168 print_clast_stmt (dump_file
, pc
.stmt
);
1169 fprintf (dump_file
, "\n");
1172 build_graphite_loop_normal_form (region
);
1173 recompute_all_dominators ();
1176 if_region
= move_sese_in_condition (region
);
1177 sese_insert_phis_for_liveouts (region
,
1178 if_region
->region
->exit
->src
,
1179 if_region
->false_region
->exit
,
1180 if_region
->true_region
->exit
);
1182 recompute_all_dominators ();
1184 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1185 compute_cloog_iv_types (pc
.stmt
);
1187 rename_map
= htab_create (10, rename_map_elt_info
, eq_rename_map_elts
, free
);
1188 newivs_index
= htab_create (10, clast_name_index_elt_info
,
1189 eq_clast_name_indexes
, free
);
1191 new_scop_exit_edge
= translate_clast (region
, context_loop
, pc
.stmt
,
1192 if_region
->true_region
->entry
,
1193 rename_map
, &newivs
, newivs_index
,
1195 sese_reset_aux_in_loops (region
);
1197 sese_adjust_liveout_phis (region
, rename_map
,
1198 if_region
->region
->exit
->src
,
1199 if_region
->false_region
->exit
,
1200 if_region
->true_region
->exit
);
1201 recompute_all_dominators ();
1204 htab_delete (rename_map
);
1205 htab_delete (newivs_index
);
1206 VEC_free (tree
, heap
, newivs
);
1207 cloog_clast_free (pc
.stmt
);
1208 cloog_program_free (pc
.prog
);
1214 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
1217 find_pbb_via_hash (htab_t bb_pbb_mapping
, basic_block bb
)
1223 slot
= htab_find_slot (bb_pbb_mapping
, &tmp
, NO_INSERT
);
1226 return ((bb_pbb_def
*) *slot
)->pbb
;
1231 /* Free loop->aux in newly created loops by translate_clast. */
1234 free_aux_in_new_loops (void)
1239 FOR_EACH_LOOP (li
, loop
, 0)
1248 /* Check data dependency in LOOP. BB_PBB_MAPPING is a basic_block and
1249 it's related poly_bb_p mapping.
1253 dependency_in_loop_p (loop_p loop
, htab_t bb_pbb_mapping
)
1257 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1259 level
= *((int *)(loop
->aux
));
1261 for (i
= 0; i
< loop
->num_nodes
; i
++)
1263 poly_bb_p pbb1
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[i
]);
1268 for (j
= 0; j
< loop
->num_nodes
; j
++)
1270 poly_bb_p pbb2
= find_pbb_via_hash (bb_pbb_mapping
, bbs
[j
]);
1275 if (dependency_between_pbbs_p (pbb1
, pbb2
, level
))
1288 /* Mark loop as parallel if data dependency does not exist.
1289 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1292 void mark_loops_parallel (htab_t bb_pbb_mapping
)
1296 int num_no_dependency
= 0;
1298 FOR_EACH_LOOP (li
, loop
, 0)
1303 if (!dependency_in_loop_p (loop
, bb_pbb_mapping
))
1305 loop
->can_be_parallel
= true;
1306 num_no_dependency
++;
1310 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1312 fprintf (dump_file
, "\n%d loops carried no dependency.\n",