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"
48 #include "hard-reg-set.h"
51 #include "dominance.h"
53 #include "basic-block.h"
54 #include "tree-ssa-alias.h"
55 #include "internal-fn.h"
56 #include "gimple-expr.h"
59 #include "gimple-iterator.h"
60 #include "tree-ssa-loop.h"
61 #include "tree-pass.h"
63 #include "tree-data-ref.h"
65 #include "tree-ssa-loop-manip.h"
66 #include "tree-scalar-evolution.h"
67 #include "gimple-ssa.h"
68 #include "tree-into-ssa.h"
72 #include "graphite-poly.h"
73 #include "graphite-isl-ast-to-gimple.h"
75 /* This flag is set when an error occurred during the translation of
78 static bool graphite_regenerate_error
;
80 /* We always try to use signed 128 bit types, but fall back to smaller types
81 in case a platform does not provide types of these sizes. In the future we
82 should use isl to derive the optimal type for each subexpression. */
84 static int max_mode_int_precision
=
85 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
86 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
87 128 : max_mode_int_precision
;
92 : is_parallelizable(false)
94 bool is_parallelizable
;
97 /* Converts a GMP constant VAL to a tree and returns it. */
100 gmp_cst_to_tree (tree type
, mpz_t val
)
102 tree t
= type
? type
: integer_type_node
;
107 wide_int wi
= wi::from_mpz (t
, tmp
, true);
110 return wide_int_to_tree (t
, wi
);
113 /* Verifies properties that GRAPHITE should maintain during translation. */
116 graphite_verify (void)
118 #ifdef ENABLE_CHECKING
119 verify_loop_structure ();
120 verify_loop_closed_ssa (true);
124 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
125 to corresponding trees. */
127 typedef std::map
<isl_id
*, tree
> ivs_params
;
129 /* Free all memory allocated for ISL's identifiers. */
131 void ivs_params_clear (ivs_params
&ip
)
133 std::map
<isl_id
*, tree
>::iterator it
;
134 for (it
= ip
.begin ();
135 it
!= ip
.end (); it
++)
137 isl_id_free (it
->first
);
142 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*,
145 /* Return the tree variable that corresponds to the given isl ast identifier
146 expression (an isl_ast_expr of type isl_ast_expr_id).
148 FIXME: We should replace blind conversation of id's type with derivation
149 of the optimal type when we get the corresponding isl support. Blindly
150 converting type sizes may be problematic when we switch to smaller
154 gcc_expression_from_isl_ast_expr_id (tree type
,
155 __isl_keep isl_ast_expr
*expr_id
,
158 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
159 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
160 std::map
<isl_id
*, tree
>::iterator res
;
161 res
= ip
.find (tmp_isl_id
);
162 isl_id_free (tmp_isl_id
);
163 gcc_assert (res
!= ip
.end () &&
164 "Could not map isl_id to tree expression");
165 isl_ast_expr_free (expr_id
);
166 return fold_convert (type
, res
->second
);
169 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
173 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
175 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
176 isl_val
*val
= isl_ast_expr_get_val (expr
);
178 mpz_init (val_mpz_t
);
180 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
183 res
= gmp_cst_to_tree (type
, val_mpz_t
);
185 isl_ast_expr_free (expr
);
186 mpz_clear (val_mpz_t
);
190 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
194 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
196 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
197 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
198 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
199 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
200 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
201 isl_ast_expr_free (expr
);
205 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
208 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
211 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
214 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
216 case isl_ast_op_pdiv_q
:
217 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
219 case isl_ast_op_pdiv_r
:
220 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
222 case isl_ast_op_fdiv_q
:
223 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
226 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
227 tree_lhs_expr
, tree_rhs_expr
);
230 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
233 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
236 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
239 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
242 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
245 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
252 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
256 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
258 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
259 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
261 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
262 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
263 tree tree_second_expr
264 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
265 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
267 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
268 isl_ast_expr_free (expr
);
269 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
270 tree_second_expr
, tree_third_expr
);
273 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
277 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
279 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
280 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
281 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
282 isl_ast_expr_free (expr
);
283 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
286 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
287 to a GCC expression tree of type TYPE. */
290 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
292 enum tree_code op_code
;
293 switch (isl_ast_expr_get_op_type (expr
))
306 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
307 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
309 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
311 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
312 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
313 res
= fold_build2 (op_code
, type
, res
, t
);
315 isl_ast_expr_free (expr
);
320 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
324 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
327 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
328 switch (isl_ast_expr_get_op_type (expr
))
330 /* These isl ast expressions are not supported yet. */
331 case isl_ast_op_error
:
332 case isl_ast_op_call
:
333 case isl_ast_op_and_then
:
334 case isl_ast_op_or_else
:
335 case isl_ast_op_select
:
340 return nary_op_to_tree (type
, expr
, ip
);
346 case isl_ast_op_pdiv_q
:
347 case isl_ast_op_pdiv_r
:
348 case isl_ast_op_fdiv_q
:
356 return binary_op_to_tree (type
, expr
, ip
);
358 case isl_ast_op_minus
:
359 return unary_op_to_tree (type
, expr
, ip
);
361 case isl_ast_op_cond
:
362 return ternary_op_to_tree (type
, expr
, ip
);
371 /* Converts an ISL AST expression E back to a GCC expression tree of
375 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
378 switch (isl_ast_expr_get_type (expr
))
380 case isl_ast_expr_id
:
381 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
383 case isl_ast_expr_int
:
384 return gcc_expression_from_isl_expr_int (type
, expr
);
386 case isl_ast_expr_op
:
387 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
396 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
397 induction variable for the new LOOP. New LOOP is attached to CFG
398 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
399 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
400 ISL's scattering name to the induction variable created for the
401 loop of STMT. The new induction variable is inserted in the NEWIVS
402 vector and is of type TYPE. */
405 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
406 loop_p outer
, tree type
, tree lb
, tree ub
,
409 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
410 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
411 tree ivvar
= create_tmp_var (type
, "graphite_IV");
412 tree iv
, iv_after_increment
;
413 loop_p loop
= create_empty_loop_on_edge
414 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
415 outer
? outer
: entry_edge
->src
->loop_father
);
417 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
418 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
419 std::map
<isl_id
*, tree
>::iterator res
;
422 isl_id_free (res
->first
);
424 isl_ast_expr_free (for_iterator
);
429 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
430 edge next_e
, ivs_params
&ip
);
432 /* Create the loop for a isl_ast_node_for.
434 - NEXT_E is the edge where new generated code should be attached. */
437 translate_isl_ast_for_loop (loop_p context_loop
,
438 __isl_keep isl_ast_node
*node_for
, edge next_e
,
439 tree type
, tree lb
, tree ub
,
442 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
443 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
445 edge last_e
= single_exit (loop
);
446 edge to_body
= single_succ_edge (loop
->header
);
447 basic_block after
= to_body
->dest
;
449 /* Create a basic block for loop close phi nodes. */
450 last_e
= single_succ_edge (split_edge (last_e
));
452 /* Translate the body of the loop. */
453 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
454 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
455 isl_ast_node_free (for_body
);
456 redirect_edge_succ_nodup (next_e
, after
);
457 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
459 if (flag_loop_parallelize_all
)
461 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
463 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
464 loop
->can_be_parallel
= for_info
->is_parallelizable
;
472 /* We use this function to get the upper bound because of the form,
473 which is used by isl to represent loops:
475 for (iterator = init; cond; iterator += inc)
483 The loop condition is an arbitrary expression, which contains the
484 current loop iterator.
486 (e.g. iterator + 3 < B && C > iterator + A)
488 We have to know the upper bound of the iterator to generate a loop
489 in Gimple form. It can be obtained from the special representation
490 of the loop condition, which is generated by isl,
491 if the ast_build_atomic_upper_bound option is set. In this case,
492 isl generates a loop condition that consists of the current loop
493 iterator, + an operator (< or <=) and an expression not involving
494 the iterator, which is processed and returned by this function.
496 (e.g iterator <= upper-bound-expression-without-iterator) */
498 static __isl_give isl_ast_expr
*
499 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
501 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
502 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
503 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
505 switch (isl_ast_expr_get_op_type (for_cond
))
508 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
513 // (iterator < ub) => (iterator <= ub - 1)
515 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
516 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
517 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
524 isl_ast_expr_free (for_cond
);
528 /* All loops generated by create_empty_loop_on_edge have the form of
535 } while (lower bound < upper bound);
537 We create a new if region protecting the loop to be executed, if
538 the execution count is zero (lower bound > upper bound). */
541 graphite_create_new_loop_guard (edge entry_edge
,
542 __isl_keep isl_ast_node
*node_for
, tree
*type
,
543 tree
*lb
, tree
*ub
, ivs_params
&ip
)
545 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
550 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
551 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
552 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
553 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
554 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
556 /* When ub is simply a constant or a parameter, use lb <= ub. */
557 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
558 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
561 tree one
= (POINTER_TYPE_P (*type
)
562 ? convert_to_ptrofftype (integer_one_node
)
563 : fold_convert (*type
, integer_one_node
));
564 /* Adding +1 and using LT_EXPR helps with loop latches that have a
565 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
566 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
567 is true, even if we do not want this. However lb < ub + 1 is false,
569 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
570 : PLUS_EXPR
, *type
, *ub
, one
);
572 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
575 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
580 /* Translates an isl_ast_node_for to Gimple. */
583 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
584 edge next_e
, ivs_params
&ip
)
586 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
588 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
590 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
592 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
597 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
598 variables of the loops around GBB in SESE.
600 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
601 chrec, we could consider using a map<int, tree> that maps loop ids to the
602 corresponding tree expressions. */
605 build_iv_mapping (vec
<tree
> iv_map
, gimple_bb_p gbb
,
606 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
609 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
610 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
612 isl_ast_expr
*arg_expr
;
613 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
615 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
617 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
618 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
619 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
620 iv_map
[old_loop
->num
] = t
;
625 /* Translates an isl_ast_node_user to Gimple.
627 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
630 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
631 edge next_e
, ivs_params
&ip
)
633 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
634 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
635 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
636 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
637 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
638 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
640 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
642 isl_ast_expr_free (name_expr
);
643 isl_id_free (name_id
);
645 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
646 "The entry block should not even appear within a scop");
648 int nb_loops
= number_of_loops (cfun
);
649 iv_map
.create (nb_loops
);
650 iv_map
.safe_grow_cleared (nb_loops
);
652 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
653 isl_ast_expr_free (user_expr
);
654 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
655 SCOP_REGION (pbb
->scop
), next_e
,
657 &graphite_regenerate_error
);
659 mark_virtual_operands_for_renaming (cfun
);
660 update_ssa (TODO_update_ssa
);
664 /* Translates an isl_ast_node_block to Gimple. */
667 translate_isl_ast_node_block (loop_p context_loop
,
668 __isl_keep isl_ast_node
*node
,
669 edge next_e
, ivs_params
&ip
)
671 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
672 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
674 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
676 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
677 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
678 isl_ast_node_free (tmp_node
);
680 isl_ast_node_list_free (node_list
);
684 /* Creates a new if region corresponding to ISL's cond. */
687 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
691 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
692 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
693 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
697 /* Translates an isl_ast_node_if to Gimple. */
700 translate_isl_ast_node_if (loop_p context_loop
,
701 __isl_keep isl_ast_node
*node
,
702 edge next_e
, ivs_params
&ip
)
704 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
705 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
706 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
708 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
709 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
710 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
711 isl_ast_node_free (then_node
);
713 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
714 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
715 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
716 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
717 isl_ast_node_free (else_node
);
721 /* Translates an ISL AST node NODE to GCC representation in the
722 context of a SESE. */
725 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
726 edge next_e
, ivs_params
&ip
)
728 switch (isl_ast_node_get_type (node
))
730 case isl_ast_node_error
:
733 case isl_ast_node_for
:
734 return translate_isl_ast_node_for (context_loop
, node
,
737 case isl_ast_node_if
:
738 return translate_isl_ast_node_if (context_loop
, node
,
741 case isl_ast_node_user
:
742 return translate_isl_ast_node_user (node
, next_e
, ip
);
744 case isl_ast_node_block
:
745 return translate_isl_ast_node_block (context_loop
, node
,
753 /* Prints NODE to FILE. */
756 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
757 __isl_keep isl_ctx
*ctx
)
759 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
760 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
761 prn
= isl_printer_print_ast_node (prn
, node
);
762 prn
= isl_printer_print_str (prn
, "\n");
763 isl_printer_free (prn
);
766 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
769 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
771 sese region
= SCOP_REGION (scop
);
772 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
773 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
775 for (i
= 0; i
< nb_parameters
; i
++)
777 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
778 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
783 /* Generates a build, which specifies the constraints on the parameters. */
785 static __isl_give isl_ast_build
*
786 generate_isl_context (scop_p scop
)
788 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
789 return isl_ast_build_from_context (context_isl
);
792 /* Get the maximal number of schedule dimensions in the scop SCOP. */
795 int get_max_schedule_dimensions (scop_p scop
)
799 int schedule_dims
= 0;
801 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
803 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
804 if (pbb_schedule_dims
> schedule_dims
)
805 schedule_dims
= pbb_schedule_dims
;
808 return schedule_dims
;
811 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
813 For schedules with different dimensionality, the isl AST generator can not
814 define an order and will just randomly choose an order. The solution to this
815 problem is to extend all schedules to the maximal number of schedule
816 dimensions (using '0's for the remaining values). */
818 static __isl_give isl_map
*
819 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
821 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
823 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
825 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
827 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
830 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
836 /* Set the separation_class option for unroll and jam. */
838 static __isl_give isl_union_map
*
839 generate_luj_sepclass_opt (scop_p scop
, __isl_take isl_union_set
*domain
,
843 isl_space
*space
, *space_sep
;
846 int nsched
= get_max_schedule_dimensions (scop
);
849 space_sep
= isl_space_alloc (ctx
, 0, 1, 1);
850 space_sep
= isl_space_wrap (space_sep
);
851 space_sep
= isl_space_set_tuple_name (space_sep
, isl_dim_set
,
853 space
= isl_set_get_space (scop
->context
);
854 space_sep
= isl_space_align_params (space_sep
, isl_space_copy(space
));
855 space
= isl_space_map_from_domain_and_range (space
, space_sep
);
856 space
= isl_space_add_dims (space
,isl_dim_in
, nsched
);
857 map
= isl_map_universe (space
);
858 isl_map_fix_si (map
,isl_dim_out
,0,dim
);
859 isl_map_fix_si (map
,isl_dim_out
,1,cl
);
861 mapu
= isl_union_map_intersect_domain (isl_union_map_from_map (map
),
866 /* Compute the separation class for loop unroll and jam. */
868 static __isl_give isl_union_set
*
869 generate_luj_sepclass (scop_p scop
)
873 isl_union_set
*domain_isl
;
875 domain_isl
= isl_union_set_empty (isl_set_get_space (scop
->context
));
877 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
880 isl_set
*bb_domain_s
;
882 if (pbb
->map_sepclass
== NULL
)
885 if (isl_set_is_empty (pbb
->domain
))
888 bb_domain
= isl_set_copy (pbb
->domain
);
889 bb_domain_s
= isl_set_apply (bb_domain
, pbb
->map_sepclass
);
890 pbb
->map_sepclass
= NULL
;
893 isl_union_set_union (domain_isl
, isl_union_set_from_set (bb_domain_s
));
899 /* Set the AST built options for loop unroll and jam. */
901 static __isl_give isl_union_map
*
902 generate_luj_options (scop_p scop
)
904 isl_union_set
*domain_isl
;
905 isl_union_map
*options_isl_ss
;
906 isl_union_map
*options_isl
=
907 isl_union_map_empty (isl_set_get_space (scop
->context
));
908 int dim
= get_max_schedule_dimensions (scop
) - 1;
909 int dim1
= dim
- PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH
);
911 if (!flag_loop_unroll_jam
)
914 domain_isl
= generate_luj_sepclass (scop
);
916 options_isl_ss
= generate_luj_sepclass_opt (scop
, domain_isl
, dim1
, 0);
917 options_isl
= isl_union_map_union (options_isl
, options_isl_ss
);
922 /* Generates a schedule, which specifies an order used to
923 visit elements in a domain. */
925 static __isl_give isl_union_map
*
926 generate_isl_schedule (scop_p scop
)
928 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
931 isl_union_map
*schedule_isl
=
932 isl_union_map_empty (isl_set_get_space (scop
->context
));
934 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
936 /* Dead code elimination: when the domain of a PBB is empty,
937 don't generate code for the PBB. */
938 if (isl_set_is_empty (pbb
->domain
))
941 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
942 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
943 isl_set_copy (pbb
->domain
));
944 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
946 isl_union_map_union (schedule_isl
,
947 isl_union_map_from_map (bb_schedule
));
952 /* This method is executed before the construction of a for node. */
953 static __isl_give isl_id
*
954 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
956 isl_union_map
*dependences
= (isl_union_map
*) user
;
957 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
958 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
959 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
960 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
961 for_info
->is_parallelizable
=
962 !carries_deps (schedule
, dependences
, dimension
);
963 isl_union_map_free (schedule
);
964 isl_space_free (schedule_space
);
965 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
969 /* Set the separate option for all dimensions.
970 This helps to reduce control overhead.
971 Set the options for unroll and jam. */
973 static __isl_give isl_ast_build
*
974 set_options (__isl_take isl_ast_build
*control
,
975 __isl_keep isl_union_map
*schedule
,
976 __isl_take isl_union_map
*opt_luj
)
978 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
979 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
981 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
982 isl_union_set
*range
=
983 isl_union_set_from_set (isl_set_universe (range_space
));
984 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
985 domain
= isl_union_set_universe (domain
);
986 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
988 options
= isl_union_map_union (options
, opt_luj
);
990 return isl_ast_build_set_options (control
, options
);
993 static __isl_give isl_ast_node
*
994 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
996 /* Generate loop upper bounds that consist of the current loop iterator,
997 an operator (< or <=) and an expression not involving the iterator.
998 If this option is not set, then the current loop iterator may appear several
999 times in the upper bound. See the isl manual for more details. */
1000 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
1002 add_parameters_to_ivs_params (scop
, ip
);
1004 isl_union_map
*options_luj
= generate_luj_options (scop
);
1006 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1007 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1009 context_isl
= set_options (context_isl
, schedule_isl
, options_luj
);
1011 isl_union_map
*dependences
= NULL
;
1012 if (flag_loop_parallelize_all
)
1014 dependences
= scop_get_dependences (scop
);
1016 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1019 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1022 isl_union_map_free (dependences
);
1023 isl_ast_build_free (context_isl
);
1027 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1028 the given SCOP. Return true if code generation succeeded.
1030 FIXME: This is not yet a full implementation of the code generator
1031 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1034 graphite_regenerate_ast_isl (scop_p scop
)
1036 loop_p context_loop
;
1037 sese region
= SCOP_REGION (scop
);
1038 ifsese if_region
= NULL
;
1039 isl_ast_node
*root_node
;
1042 timevar_push (TV_GRAPHITE_CODE_GEN
);
1043 graphite_regenerate_error
= false;
1044 root_node
= scop_to_isl_ast (scop
, ip
);
1046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1048 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1049 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
1050 fprintf (dump_file
, "\n");
1053 recompute_all_dominators ();
1056 if_region
= move_sese_in_condition (region
);
1057 sese_insert_phis_for_liveouts (region
,
1058 if_region
->region
->exit
->src
,
1059 if_region
->false_region
->exit
,
1060 if_region
->true_region
->exit
);
1061 recompute_all_dominators ();
1064 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1066 translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
1070 recompute_all_dominators ();
1073 if (graphite_regenerate_error
)
1074 set_ifsese_condition (if_region
, integer_zero_node
);
1076 free (if_region
->true_region
);
1077 free (if_region
->region
);
1080 ivs_params_clear (ip
);
1081 isl_ast_node_free (root_node
);
1082 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1087 int num_no_dependency
= 0;
1089 FOR_EACH_LOOP (loop
, 0)
1090 if (loop
->can_be_parallel
)
1091 num_no_dependency
++;
1093 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1097 return !graphite_regenerate_error
;