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 #ifdef ENABLE_CHECKING
110 verify_loop_structure ();
111 verify_loop_closed_ssa (true);
115 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
116 to corresponding trees. */
118 typedef std::map
<isl_id
*, tree
> ivs_params
;
120 /* Free all memory allocated for ISL's identifiers. */
122 void ivs_params_clear (ivs_params
&ip
)
124 std::map
<isl_id
*, tree
>::iterator it
;
125 for (it
= ip
.begin ();
126 it
!= ip
.end (); it
++)
128 isl_id_free (it
->first
);
132 class translate_isl_ast_to_gimple
135 translate_isl_ast_to_gimple (sese r
)
139 /* Translates an ISL AST node NODE to GCC representation in the
140 context of a SESE. */
141 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
142 edge next_e
, ivs_params
&ip
);
144 /* Translates an isl_ast_node_for to Gimple. */
145 edge
translate_isl_ast_node_for (loop_p context_loop
,
146 __isl_keep isl_ast_node
*node
,
147 edge next_e
, ivs_params
&ip
);
149 /* Create the loop for a isl_ast_node_for.
151 - NEXT_E is the edge where new generated code should be attached. */
152 edge
translate_isl_ast_for_loop (loop_p context_loop
,
153 __isl_keep isl_ast_node
*node_for
,
155 tree type
, tree lb
, tree ub
,
158 /* Translates an isl_ast_node_if to Gimple. */
159 edge
translate_isl_ast_node_if (loop_p context_loop
,
160 __isl_keep isl_ast_node
*node
,
161 edge next_e
, ivs_params
&ip
);
163 /* Translates an isl_ast_node_user to Gimple.
165 FIXME: We should remove iv_map.create (loop->num + 1), if it is
167 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
168 edge next_e
, ivs_params
&ip
);
170 /* Translates an isl_ast_node_block to Gimple. */
171 edge
translate_isl_ast_node_block (loop_p context_loop
,
172 __isl_keep isl_ast_node
*node
,
173 edge next_e
, ivs_params
&ip
);
175 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
177 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
180 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
182 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
185 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
187 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
190 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
191 to a GCC expression tree of type TYPE. */
192 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
195 /* Converts an ISL AST expression E back to a GCC expression tree of
197 tree
gcc_expression_from_isl_expression (tree type
,
198 __isl_take isl_ast_expr
*,
201 /* Return the tree variable that corresponds to the given isl ast identifier
202 expression (an isl_ast_expr of type isl_ast_expr_id).
204 FIXME: We should replace blind conversation of id's type with derivation
205 of the optimal type when we get the corresponding isl support. Blindly
206 converting type sizes may be problematic when we switch to smaller
208 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
209 __isl_keep isl_ast_expr
*expr_id
,
212 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
214 tree
gcc_expression_from_isl_expr_int (tree type
,
215 __isl_take isl_ast_expr
*expr
);
217 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
219 tree
gcc_expression_from_isl_expr_op (tree type
,
220 __isl_take isl_ast_expr
*expr
,
223 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
224 induction variable for the new LOOP. New LOOP is attached to CFG
225 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
226 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
227 ISL's scattering name to the induction variable created for the
228 loop of STMT. The new induction variable is inserted in the NEWIVS
229 vector and is of type TYPE. */
230 struct loop
*graphite_create_new_loop (edge entry_edge
,
231 __isl_keep isl_ast_node
*node_for
,
232 loop_p outer
, tree type
,
233 tree lb
, tree ub
, ivs_params
&ip
);
235 /* All loops generated by create_empty_loop_on_edge have the form of
242 } while (lower bound < upper bound);
244 We create a new if region protecting the loop to be executed, if
245 the execution count is zero (lower bound > upper bound). */
246 edge
graphite_create_new_loop_guard (edge entry_edge
,
247 __isl_keep isl_ast_node
*node_for
,
249 tree
*lb
, tree
*ub
, ivs_params
&ip
);
251 /* Creates a new if region corresponding to ISL's cond. */
252 edge
graphite_create_new_guard (edge entry_edge
,
253 __isl_take isl_ast_expr
*if_cond
,
256 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
257 variables of the loops around GBB in SESE.
259 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
260 chrec, we could consider using a map<int, tree> that maps loop ids to the
261 corresponding tree expressions. */
262 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
263 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
269 /* Return the tree variable that corresponds to the given isl ast identifier
270 expression (an isl_ast_expr of type isl_ast_expr_id).
272 FIXME: We should replace blind conversation of id's type with derivation
273 of the optimal type when we get the corresponding isl support. Blindly
274 converting type sizes may be problematic when we switch to smaller
278 translate_isl_ast_to_gimple::
279 gcc_expression_from_isl_ast_expr_id (tree type
,
280 __isl_keep isl_ast_expr
*expr_id
,
283 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
284 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
285 std::map
<isl_id
*, tree
>::iterator res
;
286 res
= ip
.find (tmp_isl_id
);
287 isl_id_free (tmp_isl_id
);
288 gcc_assert (res
!= ip
.end () &&
289 "Could not map isl_id to tree expression");
290 isl_ast_expr_free (expr_id
);
291 tree t
= res
->second
;
292 tree
*val
= region
->parameter_rename_map
->get(t
);
296 return fold_convert (type
, *val
);
299 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
303 translate_isl_ast_to_gimple::
304 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
306 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
307 isl_val
*val
= isl_ast_expr_get_val (expr
);
309 mpz_init (val_mpz_t
);
311 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
314 res
= gmp_cst_to_tree (type
, val_mpz_t
);
316 isl_ast_expr_free (expr
);
317 mpz_clear (val_mpz_t
);
321 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
325 translate_isl_ast_to_gimple::
326 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
328 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
329 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
330 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
331 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
332 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
333 isl_ast_expr_free (expr
);
337 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
340 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
343 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
346 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
348 case isl_ast_op_pdiv_q
:
349 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
351 case isl_ast_op_pdiv_r
:
352 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
354 case isl_ast_op_fdiv_q
:
355 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
358 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
359 tree_lhs_expr
, tree_rhs_expr
);
362 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
365 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
368 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
371 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
374 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
377 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
384 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
388 translate_isl_ast_to_gimple::
389 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
391 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
392 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
394 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
395 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
396 tree tree_second_expr
397 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
398 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
400 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
401 isl_ast_expr_free (expr
);
402 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
403 tree_second_expr
, tree_third_expr
);
406 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
410 translate_isl_ast_to_gimple::
411 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
413 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
414 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
415 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
416 isl_ast_expr_free (expr
);
417 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
420 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
421 to a GCC expression tree of type TYPE. */
424 translate_isl_ast_to_gimple::
425 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
427 enum tree_code op_code
;
428 switch (isl_ast_expr_get_op_type (expr
))
441 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
442 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
444 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
446 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
447 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
448 res
= fold_build2 (op_code
, type
, res
, t
);
450 isl_ast_expr_free (expr
);
454 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
458 translate_isl_ast_to_gimple::
459 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
462 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
463 switch (isl_ast_expr_get_op_type (expr
))
465 /* These isl ast expressions are not supported yet. */
466 case isl_ast_op_error
:
467 case isl_ast_op_call
:
468 case isl_ast_op_and_then
:
469 case isl_ast_op_or_else
:
470 case isl_ast_op_select
:
475 return nary_op_to_tree (type
, expr
, ip
);
481 case isl_ast_op_pdiv_q
:
482 case isl_ast_op_pdiv_r
:
483 case isl_ast_op_fdiv_q
:
491 return binary_op_to_tree (type
, expr
, ip
);
493 case isl_ast_op_minus
:
494 return unary_op_to_tree (type
, expr
, ip
);
496 case isl_ast_op_cond
:
497 return ternary_op_to_tree (type
, expr
, ip
);
506 /* Converts an ISL AST expression E back to a GCC expression tree of
510 translate_isl_ast_to_gimple::
511 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
514 switch (isl_ast_expr_get_type (expr
))
516 case isl_ast_expr_id
:
517 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
519 case isl_ast_expr_int
:
520 return gcc_expression_from_isl_expr_int (type
, expr
);
522 case isl_ast_expr_op
:
523 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
532 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
533 induction variable for the new LOOP. New LOOP is attached to CFG
534 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
535 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
536 ISL's scattering name to the induction variable created for the
537 loop of STMT. The new induction variable is inserted in the NEWIVS
538 vector and is of type TYPE. */
541 translate_isl_ast_to_gimple::
542 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
543 loop_p outer
, tree type
, tree lb
, tree ub
,
546 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
547 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
548 tree ivvar
= create_tmp_var (type
, "graphite_IV");
549 tree iv
, iv_after_increment
;
550 loop_p loop
= create_empty_loop_on_edge
551 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
552 outer
? outer
: entry_edge
->src
->loop_father
);
554 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
555 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
556 std::map
<isl_id
*, tree
>::iterator res
;
559 isl_id_free (res
->first
);
561 isl_ast_expr_free (for_iterator
);
565 /* Create the loop for a isl_ast_node_for.
567 - NEXT_E is the edge where new generated code should be attached. */
570 translate_isl_ast_to_gimple::
571 translate_isl_ast_for_loop (loop_p context_loop
,
572 __isl_keep isl_ast_node
*node_for
, edge next_e
,
573 tree type
, tree lb
, tree ub
,
576 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
577 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
579 edge last_e
= single_exit (loop
);
580 edge to_body
= single_succ_edge (loop
->header
);
581 basic_block after
= to_body
->dest
;
583 /* Create a basic block for loop close phi nodes. */
584 last_e
= single_succ_edge (split_edge (last_e
));
586 /* Translate the body of the loop. */
587 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
588 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
589 isl_ast_node_free (for_body
);
590 redirect_edge_succ_nodup (next_e
, after
);
591 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
593 if (flag_loop_parallelize_all
)
595 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
597 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
598 loop
->can_be_parallel
= for_info
->is_parallelizable
;
606 /* We use this function to get the upper bound because of the form,
607 which is used by isl to represent loops:
609 for (iterator = init; cond; iterator += inc)
617 The loop condition is an arbitrary expression, which contains the
618 current loop iterator.
620 (e.g. iterator + 3 < B && C > iterator + A)
622 We have to know the upper bound of the iterator to generate a loop
623 in Gimple form. It can be obtained from the special representation
624 of the loop condition, which is generated by isl,
625 if the ast_build_atomic_upper_bound option is set. In this case,
626 isl generates a loop condition that consists of the current loop
627 iterator, + an operator (< or <=) and an expression not involving
628 the iterator, which is processed and returned by this function.
630 (e.g iterator <= upper-bound-expression-without-iterator) */
632 static __isl_give isl_ast_expr
*
633 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
635 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
636 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
637 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
639 switch (isl_ast_expr_get_op_type (for_cond
))
642 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
647 // (iterator < ub) => (iterator <= ub - 1)
649 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
650 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
651 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
658 isl_ast_expr_free (for_cond
);
662 /* All loops generated by create_empty_loop_on_edge have the form of
669 } while (lower bound < upper bound);
671 We create a new if region protecting the loop to be executed, if
672 the execution count is zero (lower bound > upper bound). */
675 translate_isl_ast_to_gimple::
676 graphite_create_new_loop_guard (edge entry_edge
,
677 __isl_keep isl_ast_node
*node_for
, tree
*type
,
678 tree
*lb
, tree
*ub
, ivs_params
&ip
)
680 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
685 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
686 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
687 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
688 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
689 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
691 /* When ub is simply a constant or a parameter, use lb <= ub. */
692 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
693 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
696 tree one
= (POINTER_TYPE_P (*type
)
697 ? convert_to_ptrofftype (integer_one_node
)
698 : fold_convert (*type
, integer_one_node
));
699 /* Adding +1 and using LT_EXPR helps with loop latches that have a
700 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
701 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
702 is true, even if we do not want this. However lb < ub + 1 is false,
704 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
705 : PLUS_EXPR
, *type
, *ub
, one
);
707 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
710 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
715 /* Translates an isl_ast_node_for to Gimple. */
718 translate_isl_ast_to_gimple::
719 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
720 edge next_e
, ivs_params
&ip
)
722 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
724 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
726 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
728 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
733 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
734 variables of the loops around GBB in SESE.
736 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
737 chrec, we could consider using a map<int, tree> that maps loop ids to the
738 corresponding tree expressions. */
741 translate_isl_ast_to_gimple::
742 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
743 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
746 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
747 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
749 isl_ast_expr
*arg_expr
;
750 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
752 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
754 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
755 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
756 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
757 iv_map
[old_loop
->num
] = t
;
762 /* Translates an isl_ast_node_user to Gimple.
764 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
767 translate_isl_ast_to_gimple::
768 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
769 edge next_e
, ivs_params
&ip
)
771 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
772 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
773 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
774 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
775 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
776 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
778 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
780 isl_ast_expr_free (name_expr
);
781 isl_id_free (name_id
);
783 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
784 "The entry block should not even appear within a scop");
786 int nb_loops
= number_of_loops (cfun
);
787 iv_map
.create (nb_loops
);
788 iv_map
.safe_grow_cleared (nb_loops
);
790 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
791 isl_ast_expr_free (user_expr
);
792 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
793 SCOP_REGION (pbb
->scop
), next_e
,
795 &graphite_regenerate_error
);
797 mark_virtual_operands_for_renaming (cfun
);
798 update_ssa (TODO_update_ssa
);
802 /* Translates an isl_ast_node_block to Gimple. */
805 translate_isl_ast_to_gimple::
806 translate_isl_ast_node_block (loop_p context_loop
,
807 __isl_keep isl_ast_node
*node
,
808 edge next_e
, ivs_params
&ip
)
810 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
811 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
813 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
815 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
816 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
817 isl_ast_node_free (tmp_node
);
819 isl_ast_node_list_free (node_list
);
823 /* Creates a new if region corresponding to ISL's cond. */
826 translate_isl_ast_to_gimple::
827 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
831 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
832 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
833 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
837 /* Translates an isl_ast_node_if to Gimple. */
840 translate_isl_ast_to_gimple::
841 translate_isl_ast_node_if (loop_p context_loop
,
842 __isl_keep isl_ast_node
*node
,
843 edge next_e
, ivs_params
&ip
)
845 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
846 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
847 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
849 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
850 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
851 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
852 isl_ast_node_free (then_node
);
854 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
855 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
856 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
857 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
858 isl_ast_node_free (else_node
);
862 /* Translates an ISL AST node NODE to GCC representation in the
863 context of a SESE. */
866 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
867 __isl_keep isl_ast_node
*node
,
868 edge next_e
, ivs_params
&ip
)
870 switch (isl_ast_node_get_type (node
))
872 case isl_ast_node_error
:
875 case isl_ast_node_for
:
876 return translate_isl_ast_node_for (context_loop
, node
,
879 case isl_ast_node_if
:
880 return translate_isl_ast_node_if (context_loop
, node
,
883 case isl_ast_node_user
:
884 return translate_isl_ast_node_user (node
, next_e
, ip
);
886 case isl_ast_node_block
:
887 return translate_isl_ast_node_block (context_loop
, node
,
895 /* Prints NODE to FILE. */
898 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
899 __isl_keep isl_ctx
*ctx
)
901 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
902 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
903 prn
= isl_printer_print_ast_node (prn
, node
);
904 prn
= isl_printer_print_str (prn
, "\n");
905 isl_printer_free (prn
);
908 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
911 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
913 sese region
= SCOP_REGION (scop
);
914 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
915 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
917 for (i
= 0; i
< nb_parameters
; i
++)
919 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
920 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
925 /* Generates a build, which specifies the constraints on the parameters. */
927 static __isl_give isl_ast_build
*
928 generate_isl_context (scop_p scop
)
930 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
931 return isl_ast_build_from_context (context_isl
);
934 /* Get the maximal number of schedule dimensions in the scop SCOP. */
937 int get_max_schedule_dimensions (scop_p scop
)
941 int schedule_dims
= 0;
943 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
945 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
946 if (pbb_schedule_dims
> schedule_dims
)
947 schedule_dims
= pbb_schedule_dims
;
950 return schedule_dims
;
953 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
955 For schedules with different dimensionality, the isl AST generator can not
956 define an order and will just randomly choose an order. The solution to this
957 problem is to extend all schedules to the maximal number of schedule
958 dimensions (using '0's for the remaining values). */
960 static __isl_give isl_map
*
961 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
963 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
965 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
967 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
969 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
972 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
978 /* Generates a schedule, which specifies an order used to
979 visit elements in a domain. */
981 static __isl_give isl_union_map
*
982 generate_isl_schedule (scop_p scop
)
984 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
987 isl_union_map
*schedule_isl
=
988 isl_union_map_empty (isl_set_get_space (scop
->context
));
990 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
992 /* Dead code elimination: when the domain of a PBB is empty,
993 don't generate code for the PBB. */
994 if (isl_set_is_empty (pbb
->domain
))
997 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
998 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
999 isl_set_copy (pbb
->domain
));
1000 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
1002 isl_union_map_union (schedule_isl
,
1003 isl_union_map_from_map (bb_schedule
));
1005 return schedule_isl
;
1008 /* This method is executed before the construction of a for node. */
1009 static __isl_give isl_id
*
1010 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1012 isl_union_map
*dependences
= (isl_union_map
*) user
;
1013 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1014 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1015 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1016 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1017 for_info
->is_parallelizable
=
1018 !carries_deps (schedule
, dependences
, dimension
);
1019 isl_union_map_free (schedule
);
1020 isl_space_free (schedule_space
);
1021 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1025 /* Set the separate option for all dimensions.
1026 This helps to reduce control overhead. */
1028 static __isl_give isl_ast_build
*
1029 set_options (__isl_take isl_ast_build
*control
,
1030 __isl_keep isl_union_map
*schedule
)
1032 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
1033 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
1035 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
1036 isl_union_set
*range
=
1037 isl_union_set_from_set (isl_set_universe (range_space
));
1038 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
1039 domain
= isl_union_set_universe (domain
);
1040 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
1041 return isl_ast_build_set_options (control
, options
);
1044 static __isl_give isl_ast_node
*
1045 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
1047 /* Generate loop upper bounds that consist of the current loop iterator,
1048 an operator (< or <=) and an expression not involving the iterator.
1049 If this option is not set, then the current loop iterator may appear several
1050 times in the upper bound. See the isl manual for more details. */
1051 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
1053 add_parameters_to_ivs_params (scop
, ip
);
1054 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1055 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1056 context_isl
= set_options (context_isl
, schedule_isl
);
1057 isl_union_map
*dependences
= NULL
;
1058 if (flag_loop_parallelize_all
)
1060 dependences
= scop_get_dependences (scop
);
1062 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1065 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1068 isl_union_map_free (dependences
);
1069 isl_ast_build_free (context_isl
);
1073 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
1074 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
1077 copy_def(tree tr
, gimple
*def_stmt
, sese region
, sese to_region
, gimple_stmt_iterator
*gsi
)
1079 if (!defined_in_sese_p (tr
, region
))
1082 use_operand_p use_p
;
1084 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
1086 tree use_tr
= USE_FROM_PTR (use_p
);
1088 /* Do not copy parameters that have been generated in the header of the
1090 if (region
->parameter_rename_map
->get(use_tr
))
1093 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
1097 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
1100 gimple
*copy
= gimple_copy (def_stmt
);
1101 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
1103 /* Create new names for all the definitions created by COPY and
1104 add replacement mappings for each new name. */
1105 def_operand_p def_p
;
1106 ssa_op_iter op_iter
;
1107 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1109 tree old_name
= DEF_FROM_PTR (def_p
);
1110 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1111 region
->parameter_rename_map
->put(old_name
, new_name
);
1118 copy_internal_parameters(sese region
, sese to_region
)
1120 /* For all the parameters which definitino is in the if_region->false_region,
1121 insert code on true_region (if_region->true_region->entry). */
1125 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->entry
->dest
);
1127 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
1129 // If def is not in region.
1130 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
1132 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
1136 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1137 the given SCOP. Return true if code generation succeeded.
1139 FIXME: This is not yet a full implementation of the code generator
1140 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1143 graphite_regenerate_ast_isl (scop_p scop
)
1145 loop_p context_loop
;
1146 sese region
= SCOP_REGION (scop
);
1147 ifsese if_region
= NULL
;
1148 isl_ast_node
*root_node
;
1151 timevar_push (TV_GRAPHITE_CODE_GEN
);
1152 graphite_regenerate_error
= false;
1153 root_node
= scop_to_isl_ast (scop
, ip
);
1155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1157 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1158 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
1159 fprintf (dump_file
, "\n");
1162 recompute_all_dominators ();
1165 if_region
= move_sese_in_condition (region
);
1166 sese_insert_phis_for_liveouts (region
,
1167 if_region
->region
->exit
->src
,
1168 if_region
->false_region
->exit
,
1169 if_region
->true_region
->exit
);
1170 recompute_all_dominators ();
1173 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1175 /* Copy all the parameters which are defined in the region. */
1176 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
1178 translate_isl_ast_to_gimple
t(region
);
1179 edge e
= single_succ_edge (if_region
->true_region
->entry
->dest
);
1181 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
1183 mark_virtual_operands_for_renaming (cfun
);
1184 update_ssa (TODO_update_ssa
);
1188 recompute_all_dominators ();
1191 if (graphite_regenerate_error
)
1192 set_ifsese_condition (if_region
, integer_zero_node
);
1194 free (if_region
->true_region
);
1195 free (if_region
->region
);
1198 ivs_params_clear (ip
);
1199 isl_ast_node_free (root_node
);
1200 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1205 int num_no_dependency
= 0;
1207 FOR_EACH_LOOP (loop
, 0)
1208 if (loop
->can_be_parallel
)
1209 num_no_dependency
++;
1211 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1215 return !graphite_regenerate_error
;
1217 #endif /* HAVE_isl */