1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 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>
29 /* Since ISL-0.13, the extern is in val_gmp.h. */
30 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
33 #include <isl/val_gmp.h>
34 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
40 #include "coretypes.h"
49 #include "fold-const.h"
52 #include "hard-reg-set.h"
55 #include "dominance.h"
57 #include "basic-block.h"
58 #include "tree-ssa-alias.h"
59 #include "internal-fn.h"
60 #include "gimple-expr.h"
63 #include "gimple-iterator.h"
64 #include "tree-ssa-loop.h"
65 #include "tree-pass.h"
67 #include "tree-data-ref.h"
69 #include "tree-ssa-loop-manip.h"
70 #include "tree-scalar-evolution.h"
71 #include "gimple-ssa.h"
72 #include "tree-into-ssa.h"
76 #include "graphite-poly.h"
77 #include "graphite-isl-ast-to-gimple.h"
79 /* This flag is set when an error occurred during the translation of
82 static bool graphite_regenerate_error
;
84 /* We always try to use signed 128 bit types, but fall back to smaller types
85 in case a platform does not provide types of these sizes. In the future we
86 should use isl to derive the optimal type for each subexpression. */
88 static int max_mode_int_precision
=
89 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
90 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
91 128 : max_mode_int_precision
;
96 : is_parallelizable(false)
98 bool is_parallelizable
;
101 /* Converts a GMP constant VAL to a tree and returns it. */
104 gmp_cst_to_tree (tree type
, mpz_t val
)
106 tree t
= type
? type
: integer_type_node
;
111 wide_int wi
= wi::from_mpz (t
, tmp
, true);
114 return wide_int_to_tree (t
, wi
);
117 /* Verifies properties that GRAPHITE should maintain during translation. */
120 graphite_verify (void)
122 #ifdef ENABLE_CHECKING
123 verify_loop_structure ();
124 verify_loop_closed_ssa (true);
128 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
129 to corresponding trees. */
131 typedef std::map
<isl_id
*, tree
> ivs_params
;
133 /* Free all memory allocated for ISL's identifiers. */
135 void ivs_params_clear (ivs_params
&ip
)
137 std::map
<isl_id
*, tree
>::iterator it
;
138 for (it
= ip
.begin ();
139 it
!= ip
.end (); it
++)
141 isl_id_free (it
->first
);
146 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*,
149 /* Return the tree variable that corresponds to the given isl ast identifier
150 expression (an isl_ast_expr of type isl_ast_expr_id).
152 FIXME: We should replace blind conversation of id's type with derivation
153 of the optimal type when we get the corresponding isl support. Blindly
154 converting type sizes may be problematic when we switch to smaller
158 gcc_expression_from_isl_ast_expr_id (tree type
,
159 __isl_keep isl_ast_expr
*expr_id
,
162 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
163 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
164 std::map
<isl_id
*, tree
>::iterator res
;
165 res
= ip
.find (tmp_isl_id
);
166 isl_id_free (tmp_isl_id
);
167 gcc_assert (res
!= ip
.end () &&
168 "Could not map isl_id to tree expression");
169 isl_ast_expr_free (expr_id
);
170 return fold_convert (type
, res
->second
);
173 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
177 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
179 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
180 isl_val
*val
= isl_ast_expr_get_val (expr
);
182 mpz_init (val_mpz_t
);
184 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
187 res
= gmp_cst_to_tree (type
, val_mpz_t
);
189 isl_ast_expr_free (expr
);
190 mpz_clear (val_mpz_t
);
194 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
198 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
200 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
201 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
202 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
203 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
204 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
205 isl_ast_expr_free (expr
);
209 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
212 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
215 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
218 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
220 case isl_ast_op_pdiv_q
:
221 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
223 case isl_ast_op_pdiv_r
:
224 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
226 case isl_ast_op_fdiv_q
:
227 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
230 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
231 tree_lhs_expr
, tree_rhs_expr
);
234 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
237 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
240 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
243 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
246 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
249 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
256 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
260 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
262 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
263 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
265 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
266 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
267 tree tree_second_expr
268 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
269 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
271 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
272 isl_ast_expr_free (expr
);
273 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
274 tree_second_expr
, tree_third_expr
);
277 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
281 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
283 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
284 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
285 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
286 isl_ast_expr_free (expr
);
287 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
290 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
291 to a GCC expression tree of type TYPE. */
294 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
296 enum tree_code op_code
;
297 switch (isl_ast_expr_get_op_type (expr
))
310 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
311 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
313 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
315 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
316 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
317 res
= fold_build2 (op_code
, type
, res
, t
);
319 isl_ast_expr_free (expr
);
324 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
328 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
331 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
332 switch (isl_ast_expr_get_op_type (expr
))
334 /* These isl ast expressions are not supported yet. */
335 case isl_ast_op_error
:
336 case isl_ast_op_call
:
337 case isl_ast_op_and_then
:
338 case isl_ast_op_or_else
:
339 case isl_ast_op_select
:
344 return nary_op_to_tree (type
, expr
, ip
);
350 case isl_ast_op_pdiv_q
:
351 case isl_ast_op_pdiv_r
:
352 case isl_ast_op_fdiv_q
:
360 return binary_op_to_tree (type
, expr
, ip
);
362 case isl_ast_op_minus
:
363 return unary_op_to_tree (type
, expr
, ip
);
365 case isl_ast_op_cond
:
366 return ternary_op_to_tree (type
, expr
, ip
);
375 /* Converts an ISL AST expression E back to a GCC expression tree of
379 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
382 switch (isl_ast_expr_get_type (expr
))
384 case isl_ast_expr_id
:
385 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
387 case isl_ast_expr_int
:
388 return gcc_expression_from_isl_expr_int (type
, expr
);
390 case isl_ast_expr_op
:
391 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
400 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
401 induction variable for the new LOOP. New LOOP is attached to CFG
402 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
403 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
404 ISL's scattering name to the induction variable created for the
405 loop of STMT. The new induction variable is inserted in the NEWIVS
406 vector and is of type TYPE. */
409 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
410 loop_p outer
, tree type
, tree lb
, tree ub
,
413 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
414 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
415 tree ivvar
= create_tmp_var (type
, "graphite_IV");
416 tree iv
, iv_after_increment
;
417 loop_p loop
= create_empty_loop_on_edge
418 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
419 outer
? outer
: entry_edge
->src
->loop_father
);
421 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
422 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
423 std::map
<isl_id
*, tree
>::iterator res
;
426 isl_id_free (res
->first
);
428 isl_ast_expr_free (for_iterator
);
433 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
434 edge next_e
, ivs_params
&ip
);
436 /* Create the loop for a isl_ast_node_for.
438 - NEXT_E is the edge where new generated code should be attached. */
441 translate_isl_ast_for_loop (loop_p context_loop
,
442 __isl_keep isl_ast_node
*node_for
, edge next_e
,
443 tree type
, tree lb
, tree ub
,
446 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
447 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
449 edge last_e
= single_exit (loop
);
450 edge to_body
= single_succ_edge (loop
->header
);
451 basic_block after
= to_body
->dest
;
453 /* Create a basic block for loop close phi nodes. */
454 last_e
= single_succ_edge (split_edge (last_e
));
456 /* Translate the body of the loop. */
457 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
458 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
459 isl_ast_node_free (for_body
);
460 redirect_edge_succ_nodup (next_e
, after
);
461 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
463 if (flag_loop_parallelize_all
)
465 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
467 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
468 loop
->can_be_parallel
= for_info
->is_parallelizable
;
476 /* We use this function to get the upper bound because of the form,
477 which is used by isl to represent loops:
479 for (iterator = init; cond; iterator += inc)
487 The loop condition is an arbitrary expression, which contains the
488 current loop iterator.
490 (e.g. iterator + 3 < B && C > iterator + A)
492 We have to know the upper bound of the iterator to generate a loop
493 in Gimple form. It can be obtained from the special representation
494 of the loop condition, which is generated by isl,
495 if the ast_build_atomic_upper_bound option is set. In this case,
496 isl generates a loop condition that consists of the current loop
497 iterator, + an operator (< or <=) and an expression not involving
498 the iterator, which is processed and returned by this function.
500 (e.g iterator <= upper-bound-expression-without-iterator) */
502 static __isl_give isl_ast_expr
*
503 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
505 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
506 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
507 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
509 switch (isl_ast_expr_get_op_type (for_cond
))
512 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
517 // (iterator < ub) => (iterator <= ub - 1)
519 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
520 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
521 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
528 isl_ast_expr_free (for_cond
);
532 /* All loops generated by create_empty_loop_on_edge have the form of
539 } while (lower bound < upper bound);
541 We create a new if region protecting the loop to be executed, if
542 the execution count is zero (lower bound > upper bound). */
545 graphite_create_new_loop_guard (edge entry_edge
,
546 __isl_keep isl_ast_node
*node_for
, tree
*type
,
547 tree
*lb
, tree
*ub
, ivs_params
&ip
)
549 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
554 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
555 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
556 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
557 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
558 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
560 /* When ub is simply a constant or a parameter, use lb <= ub. */
561 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
562 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
565 tree one
= (POINTER_TYPE_P (*type
)
566 ? convert_to_ptrofftype (integer_one_node
)
567 : fold_convert (*type
, integer_one_node
));
568 /* Adding +1 and using LT_EXPR helps with loop latches that have a
569 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
570 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
571 is true, even if we do not want this. However lb < ub + 1 is false,
573 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
574 : PLUS_EXPR
, *type
, *ub
, one
);
576 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
579 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
584 /* Translates an isl_ast_node_for to Gimple. */
587 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
588 edge next_e
, ivs_params
&ip
)
590 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
592 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
594 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
596 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
601 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
602 variables of the loops around GBB in SESE.
604 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
605 chrec, we could consider using a map<int, tree> that maps loop ids to the
606 corresponding tree expressions. */
609 build_iv_mapping (vec
<tree
> iv_map
, gimple_bb_p gbb
,
610 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
613 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
614 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
616 isl_ast_expr
*arg_expr
;
617 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
619 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
621 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
622 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
623 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
624 iv_map
[old_loop
->num
] = t
;
629 /* Translates an isl_ast_node_user to Gimple.
631 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
634 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
635 edge next_e
, ivs_params
&ip
)
637 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
638 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
639 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
640 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
641 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
642 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
644 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
646 isl_ast_expr_free (name_expr
);
647 isl_id_free (name_id
);
649 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
650 "The entry block should not even appear within a scop");
652 int nb_loops
= number_of_loops (cfun
);
653 iv_map
.create (nb_loops
);
654 iv_map
.safe_grow_cleared (nb_loops
);
656 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
657 isl_ast_expr_free (user_expr
);
658 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
659 SCOP_REGION (pbb
->scop
), next_e
,
661 &graphite_regenerate_error
);
663 mark_virtual_operands_for_renaming (cfun
);
664 update_ssa (TODO_update_ssa
);
668 /* Translates an isl_ast_node_block to Gimple. */
671 translate_isl_ast_node_block (loop_p context_loop
,
672 __isl_keep isl_ast_node
*node
,
673 edge next_e
, ivs_params
&ip
)
675 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
676 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
678 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
680 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
681 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
682 isl_ast_node_free (tmp_node
);
684 isl_ast_node_list_free (node_list
);
688 /* Creates a new if region corresponding to ISL's cond. */
691 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
695 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
696 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
697 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
701 /* Translates an isl_ast_node_if to Gimple. */
704 translate_isl_ast_node_if (loop_p context_loop
,
705 __isl_keep isl_ast_node
*node
,
706 edge next_e
, ivs_params
&ip
)
708 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
709 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
710 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
712 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
713 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
714 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
715 isl_ast_node_free (then_node
);
717 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
718 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
719 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
720 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
721 isl_ast_node_free (else_node
);
725 /* Translates an ISL AST node NODE to GCC representation in the
726 context of a SESE. */
729 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
730 edge next_e
, ivs_params
&ip
)
732 switch (isl_ast_node_get_type (node
))
734 case isl_ast_node_error
:
737 case isl_ast_node_for
:
738 return translate_isl_ast_node_for (context_loop
, node
,
741 case isl_ast_node_if
:
742 return translate_isl_ast_node_if (context_loop
, node
,
745 case isl_ast_node_user
:
746 return translate_isl_ast_node_user (node
, next_e
, ip
);
748 case isl_ast_node_block
:
749 return translate_isl_ast_node_block (context_loop
, node
,
757 /* Prints NODE to FILE. */
760 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
761 __isl_keep isl_ctx
*ctx
)
763 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
764 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
765 prn
= isl_printer_print_ast_node (prn
, node
);
766 prn
= isl_printer_print_str (prn
, "\n");
767 isl_printer_free (prn
);
770 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
773 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
775 sese region
= SCOP_REGION (scop
);
776 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
777 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
779 for (i
= 0; i
< nb_parameters
; i
++)
781 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
782 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
787 /* Generates a build, which specifies the constraints on the parameters. */
789 static __isl_give isl_ast_build
*
790 generate_isl_context (scop_p scop
)
792 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
793 return isl_ast_build_from_context (context_isl
);
796 /* Get the maximal number of schedule dimensions in the scop SCOP. */
799 int get_max_schedule_dimensions (scop_p scop
)
803 int schedule_dims
= 0;
805 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
807 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
808 if (pbb_schedule_dims
> schedule_dims
)
809 schedule_dims
= pbb_schedule_dims
;
812 return schedule_dims
;
815 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
817 For schedules with different dimensionality, the isl AST generator can not
818 define an order and will just randomly choose an order. The solution to this
819 problem is to extend all schedules to the maximal number of schedule
820 dimensions (using '0's for the remaining values). */
822 static __isl_give isl_map
*
823 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
825 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
827 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
829 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
831 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
834 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
840 /* Set the separation_class option for unroll and jam. */
842 static __isl_give isl_union_map
*
843 generate_luj_sepclass_opt (scop_p scop
, __isl_take isl_union_set
*domain
,
847 isl_space
*space
, *space_sep
;
850 int nsched
= get_max_schedule_dimensions (scop
);
853 space_sep
= isl_space_alloc (ctx
, 0, 1, 1);
854 space_sep
= isl_space_wrap (space_sep
);
855 space_sep
= isl_space_set_tuple_name (space_sep
, isl_dim_set
,
857 space
= isl_set_get_space (scop
->context
);
858 space_sep
= isl_space_align_params (space_sep
, isl_space_copy(space
));
859 space
= isl_space_map_from_domain_and_range (space
, space_sep
);
860 space
= isl_space_add_dims (space
,isl_dim_in
, nsched
);
861 map
= isl_map_universe (space
);
862 isl_map_fix_si (map
,isl_dim_out
,0,dim
);
863 isl_map_fix_si (map
,isl_dim_out
,1,cl
);
865 mapu
= isl_union_map_intersect_domain (isl_union_map_from_map (map
),
870 /* Compute the separation class for loop unroll and jam. */
872 static __isl_give isl_union_set
*
873 generate_luj_sepclass (scop_p scop
)
877 isl_union_set
*domain_isl
;
879 domain_isl
= isl_union_set_empty (isl_set_get_space (scop
->context
));
881 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
884 isl_set
*bb_domain_s
;
886 if (pbb
->map_sepclass
== NULL
)
889 if (isl_set_is_empty (pbb
->domain
))
892 bb_domain
= isl_set_copy (pbb
->domain
);
893 bb_domain_s
= isl_set_apply (bb_domain
, pbb
->map_sepclass
);
894 pbb
->map_sepclass
= NULL
;
897 isl_union_set_union (domain_isl
, isl_union_set_from_set (bb_domain_s
));
903 /* Set the AST built options for loop unroll and jam. */
905 static __isl_give isl_union_map
*
906 generate_luj_options (scop_p scop
)
908 isl_union_set
*domain_isl
;
909 isl_union_map
*options_isl_ss
;
910 isl_union_map
*options_isl
=
911 isl_union_map_empty (isl_set_get_space (scop
->context
));
912 int dim
= get_max_schedule_dimensions (scop
) - 1;
913 int dim1
= dim
- PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH
);
915 if (!flag_loop_unroll_jam
)
918 domain_isl
= generate_luj_sepclass (scop
);
920 options_isl_ss
= generate_luj_sepclass_opt (scop
, domain_isl
, dim1
, 0);
921 options_isl
= isl_union_map_union (options_isl
, options_isl_ss
);
926 /* Generates a schedule, which specifies an order used to
927 visit elements in a domain. */
929 static __isl_give isl_union_map
*
930 generate_isl_schedule (scop_p scop
)
932 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
935 isl_union_map
*schedule_isl
=
936 isl_union_map_empty (isl_set_get_space (scop
->context
));
938 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
940 /* Dead code elimination: when the domain of a PBB is empty,
941 don't generate code for the PBB. */
942 if (isl_set_is_empty (pbb
->domain
))
945 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
946 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
947 isl_set_copy (pbb
->domain
));
948 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
950 isl_union_map_union (schedule_isl
,
951 isl_union_map_from_map (bb_schedule
));
956 /* This method is executed before the construction of a for node. */
957 static __isl_give isl_id
*
958 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
960 isl_union_map
*dependences
= (isl_union_map
*) user
;
961 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
962 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
963 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
964 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
965 for_info
->is_parallelizable
=
966 !carries_deps (schedule
, dependences
, dimension
);
967 isl_union_map_free (schedule
);
968 isl_space_free (schedule_space
);
969 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
973 /* Set the separate option for all dimensions.
974 This helps to reduce control overhead.
975 Set the options for unroll and jam. */
977 static __isl_give isl_ast_build
*
978 set_options (__isl_take isl_ast_build
*control
,
979 __isl_keep isl_union_map
*schedule
,
980 __isl_take isl_union_map
*opt_luj
)
982 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
983 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
985 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
986 isl_union_set
*range
=
987 isl_union_set_from_set (isl_set_universe (range_space
));
988 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
989 domain
= isl_union_set_universe (domain
);
990 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
992 options
= isl_union_map_union (options
, opt_luj
);
994 return isl_ast_build_set_options (control
, options
);
997 static __isl_give isl_ast_node
*
998 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
1000 /* Generate loop upper bounds that consist of the current loop iterator,
1001 an operator (< or <=) and an expression not involving the iterator.
1002 If this option is not set, then the current loop iterator may appear several
1003 times in the upper bound. See the isl manual for more details. */
1004 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
1006 add_parameters_to_ivs_params (scop
, ip
);
1008 isl_union_map
*options_luj
= generate_luj_options (scop
);
1010 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1011 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1013 context_isl
= set_options (context_isl
, schedule_isl
, options_luj
);
1015 isl_union_map
*dependences
= NULL
;
1016 if (flag_loop_parallelize_all
)
1018 dependences
= scop_get_dependences (scop
);
1020 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1023 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1026 isl_union_map_free (dependences
);
1027 isl_ast_build_free (context_isl
);
1031 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1032 the given SCOP. Return true if code generation succeeded.
1034 FIXME: This is not yet a full implementation of the code generator
1035 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1038 graphite_regenerate_ast_isl (scop_p scop
)
1040 loop_p context_loop
;
1041 sese region
= SCOP_REGION (scop
);
1042 ifsese if_region
= NULL
;
1043 isl_ast_node
*root_node
;
1046 timevar_push (TV_GRAPHITE_CODE_GEN
);
1047 graphite_regenerate_error
= false;
1048 root_node
= scop_to_isl_ast (scop
, ip
);
1050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1052 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1053 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
1054 fprintf (dump_file
, "\n");
1057 recompute_all_dominators ();
1060 if_region
= move_sese_in_condition (region
);
1061 sese_insert_phis_for_liveouts (region
,
1062 if_region
->region
->exit
->src
,
1063 if_region
->false_region
->exit
,
1064 if_region
->true_region
->exit
);
1065 recompute_all_dominators ();
1068 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1070 translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
1074 recompute_all_dominators ();
1077 if (graphite_regenerate_error
)
1078 set_ifsese_condition (if_region
, integer_zero_node
);
1080 free (if_region
->true_region
);
1081 free (if_region
->region
);
1084 ivs_params_clear (ip
);
1085 isl_ast_node_free (root_node
);
1086 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1091 int num_no_dependency
= 0;
1093 FOR_EACH_LOOP (loop
, 0)
1094 if (loop
->can_be_parallel
)
1095 num_no_dependency
++;
1097 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1101 return !graphite_regenerate_error
;