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/>. */
24 /* Workaround for GMP 5.1.3 bug, see PR56019. */
27 #include <isl/constraint.h>
29 #include <isl/union_set.h>
31 #include <isl/union_map.h>
32 #include <isl/ast_build.h>
34 /* Since ISL-0.13, the extern is in val_gmp.h. */
35 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
38 #include <isl/val_gmp.h>
39 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
44 #include "coretypes.h"
50 #include "fold-const.h"
51 #include "gimple-iterator.h"
52 #include "tree-ssa-loop.h"
53 #include "tree-pass.h"
55 #include "tree-data-ref.h"
56 #include "graphite-poly.h"
57 #include "tree-ssa-loop-manip.h"
58 #include "tree-scalar-evolution.h"
59 #include "gimple-ssa.h"
60 #include "tree-phinodes.h"
61 #include "tree-into-ssa.h"
62 #include "ssa-iterators.h"
64 #include "graphite-isl-ast-to-gimple.h"
66 /* This flag is set when an error occurred during the translation of
69 static bool graphite_regenerate_error
;
71 /* We always try to use signed 128 bit types, but fall back to smaller types
72 in case a platform does not provide types of these sizes. In the future we
73 should use isl to derive the optimal type for each subexpression. */
75 static int max_mode_int_precision
=
76 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
77 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
78 128 : max_mode_int_precision
;
83 : is_parallelizable(false)
85 bool is_parallelizable
;
88 /* Converts a GMP constant VAL to a tree and returns it. */
91 gmp_cst_to_tree (tree type
, mpz_t val
)
93 tree t
= type
? type
: integer_type_node
;
98 wide_int wi
= wi::from_mpz (t
, tmp
, true);
101 return wide_int_to_tree (t
, wi
);
104 /* Verifies properties that GRAPHITE should maintain during translation. */
107 graphite_verify (void)
109 checking_verify_loop_structure ();
110 checking_verify_loop_closed_ssa (true);
113 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
114 to corresponding trees. */
116 typedef std::map
<isl_id
*, tree
> ivs_params
;
118 /* Free all memory allocated for ISL's identifiers. */
120 void ivs_params_clear (ivs_params
&ip
)
122 std::map
<isl_id
*, tree
>::iterator it
;
123 for (it
= ip
.begin ();
124 it
!= ip
.end (); it
++)
126 isl_id_free (it
->first
);
130 class translate_isl_ast_to_gimple
133 translate_isl_ast_to_gimple (sese_info_p r
)
137 /* Translates an ISL AST node NODE to GCC representation in the
138 context of a SESE. */
139 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
140 edge next_e
, ivs_params
&ip
);
142 /* Translates an isl_ast_node_for to Gimple. */
143 edge
translate_isl_ast_node_for (loop_p context_loop
,
144 __isl_keep isl_ast_node
*node
,
145 edge next_e
, ivs_params
&ip
);
147 /* Create the loop for a isl_ast_node_for.
149 - NEXT_E is the edge where new generated code should be attached. */
150 edge
translate_isl_ast_for_loop (loop_p context_loop
,
151 __isl_keep isl_ast_node
*node_for
,
153 tree type
, tree lb
, tree ub
,
156 /* Translates an isl_ast_node_if to Gimple. */
157 edge
translate_isl_ast_node_if (loop_p context_loop
,
158 __isl_keep isl_ast_node
*node
,
159 edge next_e
, ivs_params
&ip
);
161 /* Translates an isl_ast_node_user to Gimple.
163 FIXME: We should remove iv_map.create (loop->num + 1), if it is
165 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
166 edge next_e
, ivs_params
&ip
);
168 /* Translates an isl_ast_node_block to Gimple. */
169 edge
translate_isl_ast_node_block (loop_p context_loop
,
170 __isl_keep isl_ast_node
*node
,
171 edge next_e
, ivs_params
&ip
);
173 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
175 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
178 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
180 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
183 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
185 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
188 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
189 to a GCC expression tree of type TYPE. */
190 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
193 /* Converts an ISL AST expression E back to a GCC expression tree of
195 tree
gcc_expression_from_isl_expression (tree type
,
196 __isl_take isl_ast_expr
*,
199 /* Return the tree variable that corresponds to the given isl ast identifier
200 expression (an isl_ast_expr of type isl_ast_expr_id).
202 FIXME: We should replace blind conversation of id's type with derivation
203 of the optimal type when we get the corresponding isl support. Blindly
204 converting type sizes may be problematic when we switch to smaller
206 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
207 __isl_keep isl_ast_expr
*expr_id
,
210 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
212 tree
gcc_expression_from_isl_expr_int (tree type
,
213 __isl_take isl_ast_expr
*expr
);
215 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
217 tree
gcc_expression_from_isl_expr_op (tree type
,
218 __isl_take isl_ast_expr
*expr
,
221 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
222 induction variable for the new LOOP. New LOOP is attached to CFG
223 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
224 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
225 ISL's scattering name to the induction variable created for the
226 loop of STMT. The new induction variable is inserted in the NEWIVS
227 vector and is of type TYPE. */
228 struct loop
*graphite_create_new_loop (edge entry_edge
,
229 __isl_keep isl_ast_node
*node_for
,
230 loop_p outer
, tree type
,
231 tree lb
, tree ub
, ivs_params
&ip
);
233 /* All loops generated by create_empty_loop_on_edge have the form of
240 } while (lower bound < upper bound);
242 We create a new if region protecting the loop to be executed, if
243 the execution count is zero (lower bound > upper bound). */
244 edge
graphite_create_new_loop_guard (edge entry_edge
,
245 __isl_keep isl_ast_node
*node_for
,
247 tree
*lb
, tree
*ub
, ivs_params
&ip
);
249 /* Creates a new if region corresponding to ISL's cond. */
250 edge
graphite_create_new_guard (edge entry_edge
,
251 __isl_take isl_ast_expr
*if_cond
,
254 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
255 variables of the loops around GBB in SESE.
257 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
258 chrec, we could consider using a map<int, tree> that maps loop ids to the
259 corresponding tree expressions. */
260 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
261 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
267 /* Return the tree variable that corresponds to the given isl ast identifier
268 expression (an isl_ast_expr of type isl_ast_expr_id).
270 FIXME: We should replace blind conversation of id's type with derivation
271 of the optimal type when we get the corresponding isl support. Blindly
272 converting type sizes may be problematic when we switch to smaller
276 translate_isl_ast_to_gimple::
277 gcc_expression_from_isl_ast_expr_id (tree type
,
278 __isl_keep isl_ast_expr
*expr_id
,
281 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
282 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
283 std::map
<isl_id
*, tree
>::iterator res
;
284 res
= ip
.find (tmp_isl_id
);
285 isl_id_free (tmp_isl_id
);
286 gcc_assert (res
!= ip
.end () &&
287 "Could not map isl_id to tree expression");
288 isl_ast_expr_free (expr_id
);
289 tree t
= res
->second
;
290 tree
*val
= region
->parameter_rename_map
->get(t
);
294 return fold_convert (type
, *val
);
297 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
301 translate_isl_ast_to_gimple::
302 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
304 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
305 isl_val
*val
= isl_ast_expr_get_val (expr
);
307 mpz_init (val_mpz_t
);
309 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
312 res
= gmp_cst_to_tree (type
, val_mpz_t
);
314 isl_ast_expr_free (expr
);
315 mpz_clear (val_mpz_t
);
319 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
323 translate_isl_ast_to_gimple::
324 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
326 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
327 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
328 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
329 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
330 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
331 isl_ast_expr_free (expr
);
335 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
338 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
341 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
344 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
346 case isl_ast_op_pdiv_q
:
347 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
349 case isl_ast_op_pdiv_r
:
350 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
352 case isl_ast_op_fdiv_q
:
353 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
356 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
357 tree_lhs_expr
, tree_rhs_expr
);
360 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
363 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
366 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
369 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
372 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
375 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
382 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
386 translate_isl_ast_to_gimple::
387 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
389 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
390 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
392 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
393 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
394 tree tree_second_expr
395 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
396 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
398 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
399 isl_ast_expr_free (expr
);
400 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
401 tree_second_expr
, tree_third_expr
);
404 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
408 translate_isl_ast_to_gimple::
409 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
411 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
412 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
413 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
414 isl_ast_expr_free (expr
);
415 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
418 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
419 to a GCC expression tree of type TYPE. */
422 translate_isl_ast_to_gimple::
423 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
425 enum tree_code op_code
;
426 switch (isl_ast_expr_get_op_type (expr
))
439 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
440 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
442 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
444 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
445 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
446 res
= fold_build2 (op_code
, type
, res
, t
);
448 isl_ast_expr_free (expr
);
452 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
456 translate_isl_ast_to_gimple::
457 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
460 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
461 switch (isl_ast_expr_get_op_type (expr
))
463 /* These isl ast expressions are not supported yet. */
464 case isl_ast_op_error
:
465 case isl_ast_op_call
:
466 case isl_ast_op_and_then
:
467 case isl_ast_op_or_else
:
468 case isl_ast_op_select
:
473 return nary_op_to_tree (type
, expr
, ip
);
479 case isl_ast_op_pdiv_q
:
480 case isl_ast_op_pdiv_r
:
481 case isl_ast_op_fdiv_q
:
489 return binary_op_to_tree (type
, expr
, ip
);
491 case isl_ast_op_minus
:
492 return unary_op_to_tree (type
, expr
, ip
);
494 case isl_ast_op_cond
:
495 return ternary_op_to_tree (type
, expr
, ip
);
504 /* Converts an ISL AST expression E back to a GCC expression tree of
508 translate_isl_ast_to_gimple::
509 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
512 switch (isl_ast_expr_get_type (expr
))
514 case isl_ast_expr_id
:
515 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
517 case isl_ast_expr_int
:
518 return gcc_expression_from_isl_expr_int (type
, expr
);
520 case isl_ast_expr_op
:
521 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
530 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
531 induction variable for the new LOOP. New LOOP is attached to CFG
532 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
533 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
534 ISL's scattering name to the induction variable created for the
535 loop of STMT. The new induction variable is inserted in the NEWIVS
536 vector and is of type TYPE. */
539 translate_isl_ast_to_gimple::
540 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
541 loop_p outer
, tree type
, tree lb
, tree ub
,
544 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
545 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
546 tree ivvar
= create_tmp_var (type
, "graphite_IV");
547 tree iv
, iv_after_increment
;
548 loop_p loop
= create_empty_loop_on_edge
549 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
550 outer
? outer
: entry_edge
->src
->loop_father
);
552 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
553 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
554 std::map
<isl_id
*, tree
>::iterator res
;
557 isl_id_free (res
->first
);
559 isl_ast_expr_free (for_iterator
);
563 /* Create the loop for a isl_ast_node_for.
565 - NEXT_E is the edge where new generated code should be attached. */
568 translate_isl_ast_to_gimple::
569 translate_isl_ast_for_loop (loop_p context_loop
,
570 __isl_keep isl_ast_node
*node_for
, edge next_e
,
571 tree type
, tree lb
, tree ub
,
574 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
575 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
577 edge last_e
= single_exit (loop
);
578 edge to_body
= single_succ_edge (loop
->header
);
579 basic_block after
= to_body
->dest
;
581 /* Create a basic block for loop close phi nodes. */
582 last_e
= single_succ_edge (split_edge (last_e
));
584 /* Translate the body of the loop. */
585 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
586 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
587 isl_ast_node_free (for_body
);
588 redirect_edge_succ_nodup (next_e
, after
);
589 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
591 if (flag_loop_parallelize_all
)
593 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
595 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
596 loop
->can_be_parallel
= for_info
->is_parallelizable
;
604 /* We use this function to get the upper bound because of the form,
605 which is used by isl to represent loops:
607 for (iterator = init; cond; iterator += inc)
615 The loop condition is an arbitrary expression, which contains the
616 current loop iterator.
618 (e.g. iterator + 3 < B && C > iterator + A)
620 We have to know the upper bound of the iterator to generate a loop
621 in Gimple form. It can be obtained from the special representation
622 of the loop condition, which is generated by isl,
623 if the ast_build_atomic_upper_bound option is set. In this case,
624 isl generates a loop condition that consists of the current loop
625 iterator, + an operator (< or <=) and an expression not involving
626 the iterator, which is processed and returned by this function.
628 (e.g iterator <= upper-bound-expression-without-iterator) */
630 static __isl_give isl_ast_expr
*
631 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
633 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
634 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
635 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
637 switch (isl_ast_expr_get_op_type (for_cond
))
640 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
645 // (iterator < ub) => (iterator <= ub - 1)
647 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
648 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
649 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
656 isl_ast_expr_free (for_cond
);
660 /* All loops generated by create_empty_loop_on_edge have the form of
667 } while (lower bound < upper bound);
669 We create a new if region protecting the loop to be executed, if
670 the execution count is zero (lower bound > upper bound). */
673 translate_isl_ast_to_gimple::
674 graphite_create_new_loop_guard (edge entry_edge
,
675 __isl_keep isl_ast_node
*node_for
, tree
*type
,
676 tree
*lb
, tree
*ub
, ivs_params
&ip
)
678 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
683 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
684 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
685 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
686 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
687 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
689 /* When ub is simply a constant or a parameter, use lb <= ub. */
690 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
691 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
694 tree one
= (POINTER_TYPE_P (*type
)
695 ? convert_to_ptrofftype (integer_one_node
)
696 : fold_convert (*type
, integer_one_node
));
697 /* Adding +1 and using LT_EXPR helps with loop latches that have a
698 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
699 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
700 is true, even if we do not want this. However lb < ub + 1 is false,
702 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
703 : PLUS_EXPR
, *type
, *ub
, one
);
705 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
708 if (integer_onep (cond_expr
))
709 exit_edge
= entry_edge
;
711 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
716 /* Translates an isl_ast_node_for to Gimple. */
719 translate_isl_ast_to_gimple::
720 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
721 edge next_e
, ivs_params
&ip
)
723 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
725 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
728 if (last_e
== next_e
)
729 /* There was no guard generated. */
730 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
733 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
734 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
738 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
739 variables of the loops around GBB in SESE.
741 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
742 chrec, we could consider using a map<int, tree> that maps loop ids to the
743 corresponding tree expressions. */
746 translate_isl_ast_to_gimple::
747 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
748 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
751 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
752 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
754 isl_ast_expr
*arg_expr
;
755 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
757 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
759 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
760 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
761 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
762 iv_map
[old_loop
->num
] = t
;
766 /* Translates an isl_ast_node_user to Gimple.
768 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
771 translate_isl_ast_to_gimple::
772 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
773 edge next_e
, ivs_params
&ip
)
775 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
776 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
777 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
778 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
779 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
780 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
782 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
784 isl_ast_expr_free (name_expr
);
785 isl_id_free (name_id
);
787 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
788 "The entry block should not even appear within a scop");
790 int nb_loops
= number_of_loops (cfun
);
791 iv_map
.create (nb_loops
);
792 iv_map
.safe_grow_cleared (nb_loops
);
794 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
795 isl_ast_expr_free (user_expr
);
796 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
797 pbb
->scop
->scop_info
, next_e
,
799 &graphite_regenerate_error
);
801 mark_virtual_operands_for_renaming (cfun
);
802 update_ssa (TODO_update_ssa
);
806 /* Translates an isl_ast_node_block to Gimple. */
809 translate_isl_ast_to_gimple::
810 translate_isl_ast_node_block (loop_p context_loop
,
811 __isl_keep isl_ast_node
*node
,
812 edge next_e
, ivs_params
&ip
)
814 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
815 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
817 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
819 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
820 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
821 isl_ast_node_free (tmp_node
);
823 isl_ast_node_list_free (node_list
);
827 /* Creates a new if region corresponding to ISL's cond. */
830 translate_isl_ast_to_gimple::
831 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
835 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
836 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
837 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
841 /* Translates an isl_ast_node_if to Gimple. */
844 translate_isl_ast_to_gimple::
845 translate_isl_ast_node_if (loop_p context_loop
,
846 __isl_keep isl_ast_node
*node
,
847 edge next_e
, ivs_params
&ip
)
849 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
850 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
851 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
853 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
854 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
855 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
856 isl_ast_node_free (then_node
);
858 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
859 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
860 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
861 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
862 isl_ast_node_free (else_node
);
866 /* Translates an ISL AST node NODE to GCC representation in the
867 context of a SESE. */
870 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
871 __isl_keep isl_ast_node
*node
,
872 edge next_e
, ivs_params
&ip
)
874 switch (isl_ast_node_get_type (node
))
876 case isl_ast_node_error
:
879 case isl_ast_node_for
:
880 return translate_isl_ast_node_for (context_loop
, node
,
883 case isl_ast_node_if
:
884 return translate_isl_ast_node_if (context_loop
, node
,
887 case isl_ast_node_user
:
888 return translate_isl_ast_node_user (node
, next_e
, ip
);
890 case isl_ast_node_block
:
891 return translate_isl_ast_node_block (context_loop
, node
,
899 /* Prints NODE to FILE. */
902 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
903 __isl_keep isl_ctx
*ctx
)
905 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
906 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
907 prn
= isl_printer_print_ast_node (prn
, node
);
908 prn
= isl_printer_print_str (prn
, "\n");
909 isl_printer_free (prn
);
912 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
915 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
917 sese_info_p region
= scop
->scop_info
;
918 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
919 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
921 for (i
= 0; i
< nb_parameters
; i
++)
923 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
925 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
930 /* Generates a build, which specifies the constraints on the parameters. */
932 static __isl_give isl_ast_build
*
933 generate_isl_context (scop_p scop
)
935 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
936 return isl_ast_build_from_context (context_isl
);
939 /* Get the maximal number of schedule dimensions in the scop SCOP. */
942 int get_max_schedule_dimensions (scop_p scop
)
946 int schedule_dims
= 0;
948 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
950 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
951 if (pbb_schedule_dims
> schedule_dims
)
952 schedule_dims
= pbb_schedule_dims
;
955 return schedule_dims
;
958 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
960 For schedules with different dimensionality, the isl AST generator can not
961 define an order and will just randomly choose an order. The solution to this
962 problem is to extend all schedules to the maximal number of schedule
963 dimensions (using '0's for the remaining values). */
965 static __isl_give isl_map
*
966 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
968 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
970 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
972 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
974 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
977 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
983 /* Generates a schedule, which specifies an order used to
984 visit elements in a domain. */
986 static __isl_give isl_union_map
*
987 generate_isl_schedule (scop_p scop
)
989 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
992 isl_union_map
*schedule_isl
=
993 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
995 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
997 /* Dead code elimination: when the domain of a PBB is empty,
998 don't generate code for the PBB. */
999 if (isl_set_is_empty (pbb
->domain
))
1002 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
1003 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
1004 isl_set_copy (pbb
->domain
));
1005 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
1007 isl_union_map_union (schedule_isl
,
1008 isl_union_map_from_map (bb_schedule
));
1010 return schedule_isl
;
1013 /* This method is executed before the construction of a for node. */
1014 static __isl_give isl_id
*
1015 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1017 isl_union_map
*dependences
= (isl_union_map
*) user
;
1018 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1019 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1020 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1021 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1022 for_info
->is_parallelizable
=
1023 !carries_deps (schedule
, dependences
, dimension
);
1024 isl_union_map_free (schedule
);
1025 isl_space_free (schedule_space
);
1026 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1030 /* Set the separate option for all dimensions.
1031 This helps to reduce control overhead. */
1033 static __isl_give isl_ast_build
*
1034 set_options (__isl_take isl_ast_build
*control
,
1035 __isl_keep isl_union_map
*schedule
)
1037 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
1038 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
1040 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
1041 isl_union_set
*range
=
1042 isl_union_set_from_set (isl_set_universe (range_space
));
1043 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
1044 domain
= isl_union_set_universe (domain
);
1045 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
1046 return isl_ast_build_set_options (control
, options
);
1049 static __isl_give isl_ast_node
*
1050 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
1052 /* Generate loop upper bounds that consist of the current loop iterator,
1053 an operator (< or <=) and an expression not involving the iterator.
1054 If this option is not set, then the current loop iterator may appear several
1055 times in the upper bound. See the isl manual for more details. */
1056 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
1058 add_parameters_to_ivs_params (scop
, ip
);
1059 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1060 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1061 context_isl
= set_options (context_isl
, schedule_isl
);
1062 isl_union_map
*dependences
= NULL
;
1063 if (flag_loop_parallelize_all
)
1065 dependences
= scop_get_dependences (scop
);
1067 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1070 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1073 isl_union_map_free (dependences
);
1074 isl_ast_build_free (context_isl
);
1078 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
1079 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
1082 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
1083 gimple_stmt_iterator
*gsi
)
1085 if (!defined_in_sese_p (tr
, region
->region
))
1089 use_operand_p use_p
;
1090 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
1092 tree use_tr
= USE_FROM_PTR (use_p
);
1094 /* Do not copy parameters that have been generated in the header of the
1096 if (region
->parameter_rename_map
->get(use_tr
))
1099 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
1103 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
1106 gimple
*copy
= gimple_copy (def_stmt
);
1107 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
1109 /* Create new names for all the definitions created by COPY and
1110 add replacement mappings for each new name. */
1111 def_operand_p def_p
;
1112 ssa_op_iter op_iter
;
1113 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1115 tree old_name
= DEF_FROM_PTR (def_p
);
1116 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1117 region
->parameter_rename_map
->put(old_name
, new_name
);
1124 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
1126 /* For all the parameters which definitino is in the if_region->false_region,
1127 insert code on true_region (if_region->true_region->entry). */
1131 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
1133 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
1135 // If def is not in region.
1136 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
1138 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
1142 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1143 the given SCOP. Return true if code generation succeeded.
1145 FIXME: This is not yet a full implementation of the code generator
1146 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1149 graphite_regenerate_ast_isl (scop_p scop
)
1151 loop_p context_loop
;
1152 sese_info_p region
= scop
->scop_info
;
1153 ifsese if_region
= NULL
;
1154 isl_ast_node
*root_node
;
1157 timevar_push (TV_GRAPHITE_CODE_GEN
);
1158 graphite_regenerate_error
= false;
1159 root_node
= scop_to_isl_ast (scop
, ip
);
1161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1163 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1164 print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
1165 fprintf (dump_file
, "\n");
1168 recompute_all_dominators ();
1171 if_region
= move_sese_in_condition (region
);
1172 sese_insert_phis_for_liveouts (region
,
1173 if_region
->region
->region
.exit
->src
,
1174 if_region
->false_region
->region
.exit
,
1175 if_region
->true_region
->region
.exit
);
1176 recompute_all_dominators ();
1179 context_loop
= region
->region
.entry
->src
->loop_father
;
1181 /* Copy all the parameters which are defined in the region. */
1182 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
1184 translate_isl_ast_to_gimple
t(region
);
1185 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
1187 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
1189 mark_virtual_operands_for_renaming (cfun
);
1190 update_ssa (TODO_update_ssa
);
1194 recompute_all_dominators ();
1197 if (graphite_regenerate_error
)
1198 set_ifsese_condition (if_region
, integer_zero_node
);
1200 free (if_region
->true_region
);
1201 free (if_region
->region
);
1204 ivs_params_clear (ip
);
1205 isl_ast_node_free (root_node
);
1206 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1211 int num_no_dependency
= 0;
1213 FOR_EACH_LOOP (loop
, 0)
1214 if (loop
->can_be_parallel
)
1215 num_no_dependency
++;
1217 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1221 return !graphite_regenerate_error
;
1223 #endif /* HAVE_isl */