1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.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/>. */
26 #include <isl/union_map.h>
27 #include <isl/ast_build.h>
28 #if defined(__cplusplus)
31 #include <isl/val_gmp.h>
32 #if defined(__cplusplus)
38 #include "coretypes.h"
46 #include "hard-reg-set.h"
49 #include "dominance.h"
51 #include "basic-block.h"
52 #include "tree-ssa-alias.h"
53 #include "internal-fn.h"
54 #include "gimple-expr.h"
57 #include "gimple-iterator.h"
58 #include "tree-ssa-loop.h"
59 #include "tree-pass.h"
61 #include "tree-data-ref.h"
63 #include "tree-ssa-loop-manip.h"
64 #include "tree-scalar-evolution.h"
65 #include "gimple-ssa.h"
66 #include "tree-into-ssa.h"
70 #include "graphite-poly.h"
71 #include "graphite-isl-ast-to-gimple.h"
73 /* This flag is set when an error occurred during the translation of
76 static bool graphite_regenerate_error
;
78 /* We always try to use signed 128 bit types, but fall back to smaller types
79 in case a platform does not provide types of these sizes. In the future we
80 should use isl to derive the optimal type for each subexpression. */
82 static int max_mode_int_precision
=
83 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
84 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
85 128 : max_mode_int_precision
;
90 : is_parallelizable(false)
92 bool is_parallelizable
;
95 /* Converts a GMP constant VAL to a tree and returns it. */
98 gmp_cst_to_tree (tree type
, mpz_t val
)
100 tree t
= type
? type
: integer_type_node
;
105 wide_int wi
= wi::from_mpz (t
, tmp
, true);
108 return wide_int_to_tree (t
, wi
);
111 /* Verifies properties that GRAPHITE should maintain during translation. */
114 graphite_verify (void)
116 #ifdef ENABLE_CHECKING
117 verify_loop_structure ();
118 verify_loop_closed_ssa (true);
122 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
123 to corresponding trees. */
125 typedef std::map
<isl_id
*, tree
> ivs_params
;
127 /* Free all memory allocated for ISL's identifiers. */
129 void ivs_params_clear (ivs_params
&ip
)
131 std::map
<isl_id
*, tree
>::iterator it
;
132 for (it
= ip
.begin ();
133 it
!= ip
.end (); it
++)
135 isl_id_free (it
->first
);
140 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*,
143 /* Return the tree variable that corresponds to the given isl ast identifier
144 expression (an isl_ast_expr of type isl_ast_expr_id).
146 FIXME: We should replace blind conversation of id's type with derivation
147 of the optimal type when we get the corresponding isl support. Blindly
148 converting type sizes may be problematic when we switch to smaller
152 gcc_expression_from_isl_ast_expr_id (tree type
,
153 __isl_keep isl_ast_expr
*expr_id
,
156 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
157 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
158 std::map
<isl_id
*, tree
>::iterator res
;
159 res
= ip
.find (tmp_isl_id
);
160 isl_id_free (tmp_isl_id
);
161 gcc_assert (res
!= ip
.end () &&
162 "Could not map isl_id to tree expression");
163 isl_ast_expr_free (expr_id
);
164 return fold_convert (type
, res
->second
);
167 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
171 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
173 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
174 isl_val
*val
= isl_ast_expr_get_val (expr
);
176 mpz_init (val_mpz_t
);
178 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
181 res
= gmp_cst_to_tree (type
, val_mpz_t
);
183 isl_ast_expr_free (expr
);
184 mpz_clear (val_mpz_t
);
188 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
192 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
194 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
195 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
196 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
197 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
198 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
199 isl_ast_expr_free (expr
);
203 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
206 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
209 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
212 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
214 case isl_ast_op_pdiv_q
:
215 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
217 case isl_ast_op_pdiv_r
:
218 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
220 case isl_ast_op_fdiv_q
:
221 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
224 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
225 tree_lhs_expr
, tree_rhs_expr
);
228 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
231 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
234 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
237 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
240 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
243 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
250 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
254 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
256 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
257 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
259 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
260 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
261 tree tree_second_expr
262 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
263 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
265 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
266 isl_ast_expr_free (expr
);
267 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
268 tree_second_expr
, tree_third_expr
);
271 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
275 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
277 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
278 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
279 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
280 isl_ast_expr_free (expr
);
281 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
284 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
285 to a GCC expression tree of type TYPE. */
288 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
290 enum tree_code op_code
;
291 switch (isl_ast_expr_get_op_type (expr
))
304 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
305 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
307 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
309 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
310 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
311 res
= fold_build2 (op_code
, type
, res
, t
);
313 isl_ast_expr_free (expr
);
318 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
322 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
325 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
326 switch (isl_ast_expr_get_op_type (expr
))
328 /* These isl ast expressions are not supported yet. */
329 case isl_ast_op_error
:
330 case isl_ast_op_call
:
331 case isl_ast_op_and_then
:
332 case isl_ast_op_or_else
:
333 case isl_ast_op_select
:
338 return nary_op_to_tree (type
, expr
, ip
);
344 case isl_ast_op_pdiv_q
:
345 case isl_ast_op_pdiv_r
:
346 case isl_ast_op_fdiv_q
:
354 return binary_op_to_tree (type
, expr
, ip
);
356 case isl_ast_op_minus
:
357 return unary_op_to_tree (type
, expr
, ip
);
359 case isl_ast_op_cond
:
360 return ternary_op_to_tree (type
, expr
, ip
);
369 /* Converts an ISL AST expression E back to a GCC expression tree of
373 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
376 switch (isl_ast_expr_get_type (expr
))
378 case isl_ast_expr_id
:
379 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
381 case isl_ast_expr_int
:
382 return gcc_expression_from_isl_expr_int (type
, expr
);
384 case isl_ast_expr_op
:
385 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
394 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
395 induction variable for the new LOOP. New LOOP is attached to CFG
396 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
397 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
398 ISL's scattering name to the induction variable created for the
399 loop of STMT. The new induction variable is inserted in the NEWIVS
400 vector and is of type TYPE. */
403 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
404 loop_p outer
, tree type
, tree lb
, tree ub
,
407 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
408 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
409 tree ivvar
= create_tmp_var (type
, "graphite_IV");
410 tree iv
, iv_after_increment
;
411 loop_p loop
= create_empty_loop_on_edge
412 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
413 outer
? outer
: entry_edge
->src
->loop_father
);
415 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
416 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
417 std::map
<isl_id
*, tree
>::iterator res
;
420 isl_id_free (res
->first
);
422 isl_ast_expr_free (for_iterator
);
427 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
428 edge next_e
, ivs_params
&ip
);
430 /* Create the loop for a isl_ast_node_for.
432 - NEXT_E is the edge where new generated code should be attached. */
435 translate_isl_ast_for_loop (loop_p context_loop
,
436 __isl_keep isl_ast_node
*node_for
, edge next_e
,
437 tree type
, tree lb
, tree ub
,
440 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
441 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
443 edge last_e
= single_exit (loop
);
444 edge to_body
= single_succ_edge (loop
->header
);
445 basic_block after
= to_body
->dest
;
447 /* Create a basic block for loop close phi nodes. */
448 last_e
= single_succ_edge (split_edge (last_e
));
450 /* Translate the body of the loop. */
451 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
452 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
453 isl_ast_node_free (for_body
);
454 redirect_edge_succ_nodup (next_e
, after
);
455 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
457 if (flag_loop_parallelize_all
)
459 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
461 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
462 loop
->can_be_parallel
= for_info
->is_parallelizable
;
470 /* We use this function to get the upper bound because of the form,
471 which is used by isl to represent loops:
473 for (iterator = init; cond; iterator += inc)
481 The loop condition is an arbitrary expression, which contains the
482 current loop iterator.
484 (e.g. iterator + 3 < B && C > iterator + A)
486 We have to know the upper bound of the iterator to generate a loop
487 in Gimple form. It can be obtained from the special representation
488 of the loop condition, which is generated by isl,
489 if the ast_build_atomic_upper_bound option is set. In this case,
490 isl generates a loop condition that consists of the current loop
491 iterator, + an operator (< or <=) and an expression not involving
492 the iterator, which is processed and returned by this function.
494 (e.g iterator <= upper-bound-expression-without-iterator) */
496 static __isl_give isl_ast_expr
*
497 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
499 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
500 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
501 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
503 switch (isl_ast_expr_get_op_type (for_cond
))
506 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
511 // (iterator < ub) => (iterator <= ub - 1)
513 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
514 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
515 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
522 isl_ast_expr_free (for_cond
);
526 /* All loops generated by create_empty_loop_on_edge have the form of
533 } while (lower bound < upper bound);
535 We create a new if region protecting the loop to be executed, if
536 the execution count is zero (lower bound > upper bound). */
539 graphite_create_new_loop_guard (edge entry_edge
,
540 __isl_keep isl_ast_node
*node_for
, tree
*type
,
541 tree
*lb
, tree
*ub
, ivs_params
&ip
)
543 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
548 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
549 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
550 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
551 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
552 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
554 /* When ub is simply a constant or a parameter, use lb <= ub. */
555 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
556 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
559 tree one
= (POINTER_TYPE_P (*type
)
560 ? convert_to_ptrofftype (integer_one_node
)
561 : fold_convert (*type
, integer_one_node
));
562 /* Adding +1 and using LT_EXPR helps with loop latches that have a
563 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
564 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
565 is true, even if we do not want this. However lb < ub + 1 is false,
567 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
568 : PLUS_EXPR
, *type
, *ub
, one
);
570 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
573 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
578 /* Translates an isl_ast_node_for to Gimple. */
581 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
582 edge next_e
, ivs_params
&ip
)
584 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
586 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
588 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
590 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
595 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
596 variables of the loops around GBB in SESE.
598 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
599 chrec, we could consider using a map<int, tree> that maps loop ids to the
600 corresponding tree expressions. */
603 build_iv_mapping (vec
<tree
> iv_map
, gimple_bb_p gbb
,
604 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
607 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
608 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
610 isl_ast_expr
*arg_expr
;
611 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
613 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
615 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
616 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
617 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
618 iv_map
[old_loop
->num
] = t
;
623 /* Translates an isl_ast_node_user to Gimple.
625 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
628 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
629 edge next_e
, ivs_params
&ip
)
631 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
632 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
633 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
634 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
635 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
636 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
638 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
640 isl_ast_expr_free (name_expr
);
641 isl_id_free (name_id
);
643 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
644 "The entry block should not even appear within a scop");
646 int nb_loops
= number_of_loops (cfun
);
647 iv_map
.create (nb_loops
);
648 iv_map
.safe_grow_cleared (nb_loops
);
650 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
651 isl_ast_expr_free (user_expr
);
652 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
653 SCOP_REGION (pbb
->scop
), next_e
,
655 &graphite_regenerate_error
);
657 mark_virtual_operands_for_renaming (cfun
);
658 update_ssa (TODO_update_ssa
);
662 /* Translates an isl_ast_node_block to Gimple. */
665 translate_isl_ast_node_block (loop_p context_loop
,
666 __isl_keep isl_ast_node
*node
,
667 edge next_e
, ivs_params
&ip
)
669 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
670 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
672 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
674 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
675 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
676 isl_ast_node_free (tmp_node
);
678 isl_ast_node_list_free (node_list
);
682 /* Creates a new if region corresponding to ISL's cond. */
685 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
689 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
690 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
691 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
695 /* Translates an isl_ast_node_if to Gimple. */
698 translate_isl_ast_node_if (loop_p context_loop
,
699 __isl_keep isl_ast_node
*node
,
700 edge next_e
, ivs_params
&ip
)
702 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
703 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
704 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
706 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
707 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
708 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
709 isl_ast_node_free (then_node
);
711 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
712 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
713 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
714 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
715 isl_ast_node_free (else_node
);
719 /* Translates an ISL AST node NODE to GCC representation in the
720 context of a SESE. */
723 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
724 edge next_e
, ivs_params
&ip
)
726 switch (isl_ast_node_get_type (node
))
728 case isl_ast_node_error
:
731 case isl_ast_node_for
:
732 return translate_isl_ast_node_for (context_loop
, node
,
735 case isl_ast_node_if
:
736 return translate_isl_ast_node_if (context_loop
, node
,
739 case isl_ast_node_user
:
740 return translate_isl_ast_node_user (node
, next_e
, ip
);
742 case isl_ast_node_block
:
743 return translate_isl_ast_node_block (context_loop
, node
,
751 /* Prints NODE to FILE. */
754 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
755 __isl_keep isl_ctx
*ctx
)
757 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
758 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
759 prn
= isl_printer_print_ast_node (prn
, node
);
760 prn
= isl_printer_print_str (prn
, "\n");
761 isl_printer_free (prn
);
764 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
767 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
769 sese region
= SCOP_REGION (scop
);
770 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
771 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
773 for (i
= 0; i
< nb_parameters
; i
++)
775 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
776 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
781 /* Generates a build, which specifies the constraints on the parameters. */
783 static __isl_give isl_ast_build
*
784 generate_isl_context (scop_p scop
)
786 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
787 return isl_ast_build_from_context (context_isl
);
790 /* Get the maximal number of schedule dimensions in the scop SCOP. */
793 int get_max_schedule_dimensions (scop_p scop
)
797 int schedule_dims
= 0;
799 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
801 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
802 if (pbb_schedule_dims
> schedule_dims
)
803 schedule_dims
= pbb_schedule_dims
;
806 return schedule_dims
;
809 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
811 For schedules with different dimensionality, the isl AST generator can not
812 define an order and will just randomly choose an order. The solution to this
813 problem is to extend all schedules to the maximal number of schedule
814 dimensions (using '0's for the remaining values). */
816 static __isl_give isl_map
*
817 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
819 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
821 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
823 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
825 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
828 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
834 /* Generates a schedule, which specifies an order used to
835 visit elements in a domain. */
837 static __isl_give isl_union_map
*
838 generate_isl_schedule (scop_p scop
)
840 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
843 isl_union_map
*schedule_isl
=
844 isl_union_map_empty (isl_set_get_space (scop
->context
));
846 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
848 /* Dead code elimination: when the domain of a PBB is empty,
849 don't generate code for the PBB. */
850 if (isl_set_is_empty (pbb
->domain
))
853 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
854 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
855 isl_set_copy (pbb
->domain
));
856 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
858 isl_union_map_union (schedule_isl
,
859 isl_union_map_from_map (bb_schedule
));
864 /* This method is executed before the construction of a for node. */
865 static __isl_give isl_id
*
866 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
868 isl_union_map
*dependences
= (isl_union_map
*) user
;
869 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
870 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
871 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
872 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
873 for_info
->is_parallelizable
=
874 !carries_deps (schedule
, dependences
, dimension
);
875 isl_union_map_free (schedule
);
876 isl_space_free (schedule_space
);
877 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
881 /* Set the separate option for all dimensions.
882 This helps to reduce control overhead. */
884 static __isl_give isl_ast_build
*
885 set_options (__isl_take isl_ast_build
*control
,
886 __isl_keep isl_union_map
*schedule
)
888 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
889 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
891 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
892 isl_union_set
*range
=
893 isl_union_set_from_set (isl_set_universe (range_space
));
894 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
895 domain
= isl_union_set_universe (domain
);
896 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
897 return isl_ast_build_set_options (control
, options
);
900 static __isl_give isl_ast_node
*
901 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
903 /* Generate loop upper bounds that consist of the current loop iterator,
904 an operator (< or <=) and an expression not involving the iterator.
905 If this option is not set, then the current loop iterator may appear several
906 times in the upper bound. See the isl manual for more details. */
907 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
909 add_parameters_to_ivs_params (scop
, ip
);
910 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
911 isl_ast_build
*context_isl
= generate_isl_context (scop
);
912 context_isl
= set_options (context_isl
, schedule_isl
);
913 isl_union_map
*dependences
= NULL
;
914 if (flag_loop_parallelize_all
)
916 dependences
= scop_get_dependences (scop
);
918 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
921 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
924 isl_union_map_free (dependences
);
925 isl_ast_build_free (context_isl
);
929 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
930 the given SCOP. Return true if code generation succeeded.
932 FIXME: This is not yet a full implementation of the code generator
933 with ISL ASTs. Generation of GIMPLE code has to be completed. */
936 graphite_regenerate_ast_isl (scop_p scop
)
939 sese region
= SCOP_REGION (scop
);
940 ifsese if_region
= NULL
;
941 isl_ast_node
*root_node
;
944 timevar_push (TV_GRAPHITE_CODE_GEN
);
945 graphite_regenerate_error
= false;
946 root_node
= scop_to_isl_ast (scop
, ip
);
948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
950 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
951 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
952 fprintf (dump_file
, "\n");
955 recompute_all_dominators ();
958 if_region
= move_sese_in_condition (region
);
959 sese_insert_phis_for_liveouts (region
,
960 if_region
->region
->exit
->src
,
961 if_region
->false_region
->exit
,
962 if_region
->true_region
->exit
);
963 recompute_all_dominators ();
966 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
968 translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
972 recompute_all_dominators ();
975 if (graphite_regenerate_error
)
976 set_ifsese_condition (if_region
, integer_zero_node
);
978 free (if_region
->true_region
);
979 free (if_region
->region
);
982 ivs_params_clear (ip
);
983 isl_ast_node_free (root_node
);
984 timevar_pop (TV_GRAPHITE_CODE_GEN
);
986 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
989 int num_no_dependency
= 0;
991 FOR_EACH_LOOP (loop
, 0)
992 if (loop
->can_be_parallel
)
995 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
999 return !graphite_regenerate_error
;