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"
67 /* This flag is set when an error occurred during the translation of
70 static bool graphite_regenerate_error
;
72 /* We always try to use signed 128 bit types, but fall back to smaller types
73 in case a platform does not provide types of these sizes. In the future we
74 should use isl to derive the optimal type for each subexpression. */
76 static int max_mode_int_precision
=
77 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
78 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
79 128 : max_mode_int_precision
;
84 : is_parallelizable(false)
86 bool is_parallelizable
;
89 /* Converts a GMP constant VAL to a tree and returns it. */
92 gmp_cst_to_tree (tree type
, mpz_t val
)
94 tree t
= type
? type
: integer_type_node
;
99 wide_int wi
= wi::from_mpz (t
, tmp
, true);
102 return wide_int_to_tree (t
, wi
);
105 /* Verifies properties that GRAPHITE should maintain during translation. */
108 graphite_verify (void)
110 checking_verify_loop_structure ();
111 checking_verify_loop_closed_ssa (true);
114 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
115 to corresponding trees. */
117 typedef std::map
<isl_id
*, tree
> ivs_params
;
119 /* Free all memory allocated for ISL's identifiers. */
121 void ivs_params_clear (ivs_params
&ip
)
123 std::map
<isl_id
*, tree
>::iterator it
;
124 for (it
= ip
.begin ();
125 it
!= ip
.end (); it
++)
127 isl_id_free (it
->first
);
131 class translate_isl_ast_to_gimple
134 translate_isl_ast_to_gimple (sese_info_p r
)
138 /* Translates an ISL AST node NODE to GCC representation in the
139 context of a SESE. */
140 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
141 edge next_e
, ivs_params
&ip
);
143 /* Translates an isl_ast_node_for to Gimple. */
144 edge
translate_isl_ast_node_for (loop_p context_loop
,
145 __isl_keep isl_ast_node
*node
,
146 edge next_e
, ivs_params
&ip
);
148 /* Create the loop for a isl_ast_node_for.
150 - NEXT_E is the edge where new generated code should be attached. */
151 edge
translate_isl_ast_for_loop (loop_p context_loop
,
152 __isl_keep isl_ast_node
*node_for
,
154 tree type
, tree lb
, tree ub
,
157 /* Translates an isl_ast_node_if to Gimple. */
158 edge
translate_isl_ast_node_if (loop_p context_loop
,
159 __isl_keep isl_ast_node
*node
,
160 edge next_e
, ivs_params
&ip
);
162 /* Translates an isl_ast_node_user to Gimple.
164 FIXME: We should remove iv_map.create (loop->num + 1), if it is
166 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
167 edge next_e
, ivs_params
&ip
);
169 /* Translates an isl_ast_node_block to Gimple. */
170 edge
translate_isl_ast_node_block (loop_p context_loop
,
171 __isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
174 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
176 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
179 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
181 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
184 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
186 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
189 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
190 to a GCC expression tree of type TYPE. */
191 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
194 /* Converts an ISL AST expression E back to a GCC expression tree of
196 tree
gcc_expression_from_isl_expression (tree type
,
197 __isl_take isl_ast_expr
*,
200 /* Return the tree variable that corresponds to the given isl ast identifier
201 expression (an isl_ast_expr of type isl_ast_expr_id).
203 FIXME: We should replace blind conversation of id's type with derivation
204 of the optimal type when we get the corresponding isl support. Blindly
205 converting type sizes may be problematic when we switch to smaller
207 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
208 __isl_keep isl_ast_expr
*expr_id
,
211 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
213 tree
gcc_expression_from_isl_expr_int (tree type
,
214 __isl_take isl_ast_expr
*expr
);
216 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
218 tree
gcc_expression_from_isl_expr_op (tree type
,
219 __isl_take isl_ast_expr
*expr
,
222 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
223 induction variable for the new LOOP. New LOOP is attached to CFG
224 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
225 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
226 ISL's scattering name to the induction variable created for the
227 loop of STMT. The new induction variable is inserted in the NEWIVS
228 vector and is of type TYPE. */
229 struct loop
*graphite_create_new_loop (edge entry_edge
,
230 __isl_keep isl_ast_node
*node_for
,
231 loop_p outer
, tree type
,
232 tree lb
, tree ub
, ivs_params
&ip
);
234 /* All loops generated by create_empty_loop_on_edge have the form of
241 } while (lower bound < upper bound);
243 We create a new if region protecting the loop to be executed, if
244 the execution count is zero (lower bound > upper bound). */
245 edge
graphite_create_new_loop_guard (edge entry_edge
,
246 __isl_keep isl_ast_node
*node_for
,
248 tree
*lb
, tree
*ub
, ivs_params
&ip
);
250 /* Creates a new if region corresponding to ISL's cond. */
251 edge
graphite_create_new_guard (edge entry_edge
,
252 __isl_take isl_ast_expr
*if_cond
,
255 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
256 variables of the loops around GBB in SESE.
258 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
259 chrec, we could consider using a map<int, tree> that maps loop ids to the
260 corresponding tree expressions. */
261 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
262 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
268 /* Return the tree variable that corresponds to the given isl ast identifier
269 expression (an isl_ast_expr of type isl_ast_expr_id).
271 FIXME: We should replace blind conversation of id's type with derivation
272 of the optimal type when we get the corresponding isl support. Blindly
273 converting type sizes may be problematic when we switch to smaller
277 translate_isl_ast_to_gimple::
278 gcc_expression_from_isl_ast_expr_id (tree type
,
279 __isl_keep isl_ast_expr
*expr_id
,
282 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
283 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
284 std::map
<isl_id
*, tree
>::iterator res
;
285 res
= ip
.find (tmp_isl_id
);
286 isl_id_free (tmp_isl_id
);
287 gcc_assert (res
!= ip
.end () &&
288 "Could not map isl_id to tree expression");
289 isl_ast_expr_free (expr_id
);
290 tree t
= res
->second
;
291 tree
*val
= region
->parameter_rename_map
->get(t
);
295 return fold_convert (type
, *val
);
298 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
302 translate_isl_ast_to_gimple::
303 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
305 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
306 isl_val
*val
= isl_ast_expr_get_val (expr
);
308 mpz_init (val_mpz_t
);
310 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
313 res
= gmp_cst_to_tree (type
, val_mpz_t
);
315 isl_ast_expr_free (expr
);
316 mpz_clear (val_mpz_t
);
320 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
324 translate_isl_ast_to_gimple::
325 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
327 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
328 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
329 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
330 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
331 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
332 isl_ast_expr_free (expr
);
336 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
339 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
342 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
345 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
347 case isl_ast_op_pdiv_q
:
348 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
350 case isl_ast_op_pdiv_r
:
351 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
353 case isl_ast_op_fdiv_q
:
354 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
357 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
358 tree_lhs_expr
, tree_rhs_expr
);
361 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
364 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
367 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
370 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
373 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
376 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
383 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
387 translate_isl_ast_to_gimple::
388 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
390 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
391 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
393 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
394 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
395 tree tree_second_expr
396 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
397 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
399 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
400 isl_ast_expr_free (expr
);
401 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
402 tree_second_expr
, tree_third_expr
);
405 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
409 translate_isl_ast_to_gimple::
410 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
412 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
413 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
414 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
415 isl_ast_expr_free (expr
);
416 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
419 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
420 to a GCC expression tree of type TYPE. */
423 translate_isl_ast_to_gimple::
424 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
426 enum tree_code op_code
;
427 switch (isl_ast_expr_get_op_type (expr
))
440 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
441 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
443 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
445 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
446 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
447 res
= fold_build2 (op_code
, type
, res
, t
);
449 isl_ast_expr_free (expr
);
453 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
457 translate_isl_ast_to_gimple::
458 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
461 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
462 switch (isl_ast_expr_get_op_type (expr
))
464 /* These isl ast expressions are not supported yet. */
465 case isl_ast_op_error
:
466 case isl_ast_op_call
:
467 case isl_ast_op_and_then
:
468 case isl_ast_op_or_else
:
469 case isl_ast_op_select
:
474 return nary_op_to_tree (type
, expr
, ip
);
480 case isl_ast_op_pdiv_q
:
481 case isl_ast_op_pdiv_r
:
482 case isl_ast_op_fdiv_q
:
490 return binary_op_to_tree (type
, expr
, ip
);
492 case isl_ast_op_minus
:
493 return unary_op_to_tree (type
, expr
, ip
);
495 case isl_ast_op_cond
:
496 return ternary_op_to_tree (type
, expr
, ip
);
505 /* Converts an ISL AST expression E back to a GCC expression tree of
509 translate_isl_ast_to_gimple::
510 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
513 switch (isl_ast_expr_get_type (expr
))
515 case isl_ast_expr_id
:
516 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
518 case isl_ast_expr_int
:
519 return gcc_expression_from_isl_expr_int (type
, expr
);
521 case isl_ast_expr_op
:
522 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
531 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
532 induction variable for the new LOOP. New LOOP is attached to CFG
533 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
534 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
535 ISL's scattering name to the induction variable created for the
536 loop of STMT. The new induction variable is inserted in the NEWIVS
537 vector and is of type TYPE. */
540 translate_isl_ast_to_gimple::
541 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
542 loop_p outer
, tree type
, tree lb
, tree ub
,
545 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
546 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
547 tree ivvar
= create_tmp_var (type
, "graphite_IV");
548 tree iv
, iv_after_increment
;
549 loop_p loop
= create_empty_loop_on_edge
550 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
551 outer
? outer
: entry_edge
->src
->loop_father
);
553 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
554 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
555 std::map
<isl_id
*, tree
>::iterator res
;
558 isl_id_free (res
->first
);
560 isl_ast_expr_free (for_iterator
);
564 /* Create the loop for a isl_ast_node_for.
566 - NEXT_E is the edge where new generated code should be attached. */
569 translate_isl_ast_to_gimple::
570 translate_isl_ast_for_loop (loop_p context_loop
,
571 __isl_keep isl_ast_node
*node_for
, edge next_e
,
572 tree type
, tree lb
, tree ub
,
575 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
576 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
578 edge last_e
= single_exit (loop
);
579 edge to_body
= single_succ_edge (loop
->header
);
580 basic_block after
= to_body
->dest
;
582 /* Create a basic block for loop close phi nodes. */
583 last_e
= single_succ_edge (split_edge (last_e
));
585 /* Translate the body of the loop. */
586 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
587 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
588 isl_ast_node_free (for_body
);
589 redirect_edge_succ_nodup (next_e
, after
);
590 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
592 if (flag_loop_parallelize_all
)
594 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
596 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
597 loop
->can_be_parallel
= for_info
->is_parallelizable
;
605 /* We use this function to get the upper bound because of the form,
606 which is used by isl to represent loops:
608 for (iterator = init; cond; iterator += inc)
616 The loop condition is an arbitrary expression, which contains the
617 current loop iterator.
619 (e.g. iterator + 3 < B && C > iterator + A)
621 We have to know the upper bound of the iterator to generate a loop
622 in Gimple form. It can be obtained from the special representation
623 of the loop condition, which is generated by isl,
624 if the ast_build_atomic_upper_bound option is set. In this case,
625 isl generates a loop condition that consists of the current loop
626 iterator, + an operator (< or <=) and an expression not involving
627 the iterator, which is processed and returned by this function.
629 (e.g iterator <= upper-bound-expression-without-iterator) */
631 static __isl_give isl_ast_expr
*
632 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
634 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
635 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
636 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
638 switch (isl_ast_expr_get_op_type (for_cond
))
641 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
646 // (iterator < ub) => (iterator <= ub - 1)
648 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
649 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
650 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
657 isl_ast_expr_free (for_cond
);
661 /* All loops generated by create_empty_loop_on_edge have the form of
668 } while (lower bound < upper bound);
670 We create a new if region protecting the loop to be executed, if
671 the execution count is zero (lower bound > upper bound). */
674 translate_isl_ast_to_gimple::
675 graphite_create_new_loop_guard (edge entry_edge
,
676 __isl_keep isl_ast_node
*node_for
, tree
*type
,
677 tree
*lb
, tree
*ub
, ivs_params
&ip
)
679 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
684 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
685 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
686 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
687 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
688 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
690 /* When ub is simply a constant or a parameter, use lb <= ub. */
691 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
692 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
695 tree one
= (POINTER_TYPE_P (*type
)
696 ? convert_to_ptrofftype (integer_one_node
)
697 : fold_convert (*type
, integer_one_node
));
698 /* Adding +1 and using LT_EXPR helps with loop latches that have a
699 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
700 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
701 is true, even if we do not want this. However lb < ub + 1 is false,
703 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
704 : PLUS_EXPR
, *type
, *ub
, one
);
706 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
709 if (integer_onep (cond_expr
))
710 exit_edge
= entry_edge
;
712 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
717 /* Translates an isl_ast_node_for to Gimple. */
720 translate_isl_ast_to_gimple::
721 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
722 edge next_e
, ivs_params
&ip
)
724 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
726 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
729 if (last_e
== next_e
)
730 /* There was no guard generated. */
731 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
734 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
735 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
739 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
740 variables of the loops around GBB in SESE.
742 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
743 chrec, we could consider using a map<int, tree> that maps loop ids to the
744 corresponding tree expressions. */
747 translate_isl_ast_to_gimple::
748 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
749 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
752 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
753 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
755 isl_ast_expr
*arg_expr
;
756 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
758 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
760 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
761 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
762 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
763 iv_map
[old_loop
->num
] = t
;
767 /* Translates an isl_ast_node_user to Gimple.
769 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
772 translate_isl_ast_to_gimple::
773 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
774 edge next_e
, ivs_params
&ip
)
776 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
777 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
778 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
779 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
780 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
781 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
783 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
785 isl_ast_expr_free (name_expr
);
786 isl_id_free (name_id
);
788 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
789 "The entry block should not even appear within a scop");
791 int nb_loops
= number_of_loops (cfun
);
792 iv_map
.create (nb_loops
);
793 iv_map
.safe_grow_cleared (nb_loops
);
795 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
796 isl_ast_expr_free (user_expr
);
800 fprintf (dump_file
, "[codegen] copying");
801 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
804 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
805 pbb
->scop
->scop_info
, next_e
,
807 &graphite_regenerate_error
);
810 fprintf (dump_file
, "[codegen] to");
811 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
815 mark_virtual_operands_for_renaming (cfun
);
816 update_ssa (TODO_update_ssa
);
820 /* Translates an isl_ast_node_block to Gimple. */
823 translate_isl_ast_to_gimple::
824 translate_isl_ast_node_block (loop_p context_loop
,
825 __isl_keep isl_ast_node
*node
,
826 edge next_e
, ivs_params
&ip
)
828 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
829 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
831 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
833 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
834 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
835 isl_ast_node_free (tmp_node
);
837 isl_ast_node_list_free (node_list
);
841 /* Creates a new if region corresponding to ISL's cond. */
844 translate_isl_ast_to_gimple::
845 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
849 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
850 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
851 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
855 /* Translates an isl_ast_node_if to Gimple. */
858 translate_isl_ast_to_gimple::
859 translate_isl_ast_node_if (loop_p context_loop
,
860 __isl_keep isl_ast_node
*node
,
861 edge next_e
, ivs_params
&ip
)
863 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
864 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
865 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
867 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
868 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
869 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
870 isl_ast_node_free (then_node
);
872 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
873 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
874 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
875 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
876 isl_ast_node_free (else_node
);
880 /* Translates an ISL AST node NODE to GCC representation in the
881 context of a SESE. */
884 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
885 __isl_keep isl_ast_node
*node
,
886 edge next_e
, ivs_params
&ip
)
888 switch (isl_ast_node_get_type (node
))
890 case isl_ast_node_error
:
893 case isl_ast_node_for
:
894 return translate_isl_ast_node_for (context_loop
, node
,
897 case isl_ast_node_if
:
898 return translate_isl_ast_node_if (context_loop
, node
,
901 case isl_ast_node_user
:
902 return translate_isl_ast_node_user (node
, next_e
, ip
);
904 case isl_ast_node_block
:
905 return translate_isl_ast_node_block (context_loop
, node
,
913 /* Prints NODE to FILE. */
916 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
917 __isl_keep isl_ctx
*ctx
)
919 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
920 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
921 prn
= isl_printer_print_ast_node (prn
, node
);
922 prn
= isl_printer_print_str (prn
, "\n");
923 isl_printer_free (prn
);
926 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
929 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
931 sese_info_p region
= scop
->scop_info
;
932 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
933 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
935 for (i
= 0; i
< nb_parameters
; i
++)
937 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
939 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
944 /* Generates a build, which specifies the constraints on the parameters. */
946 static __isl_give isl_ast_build
*
947 generate_isl_context (scop_p scop
)
949 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
950 return isl_ast_build_from_context (context_isl
);
953 /* Get the maximal number of schedule dimensions in the scop SCOP. */
956 int get_max_schedule_dimensions (scop_p scop
)
960 int schedule_dims
= 0;
962 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
964 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
965 if (pbb_schedule_dims
> schedule_dims
)
966 schedule_dims
= pbb_schedule_dims
;
969 return schedule_dims
;
972 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
974 For schedules with different dimensionality, the isl AST generator can not
975 define an order and will just randomly choose an order. The solution to this
976 problem is to extend all schedules to the maximal number of schedule
977 dimensions (using '0's for the remaining values). */
979 static __isl_give isl_map
*
980 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
982 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
984 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
986 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
988 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
991 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
997 /* Generates a schedule, which specifies an order used to
998 visit elements in a domain. */
1000 static __isl_give isl_union_map
*
1001 generate_isl_schedule (scop_p scop
)
1003 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
1006 isl_union_map
*schedule_isl
=
1007 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
1009 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1011 /* Dead code elimination: when the domain of a PBB is empty,
1012 don't generate code for the PBB. */
1013 if (isl_set_is_empty (pbb
->domain
))
1016 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
1017 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
1018 isl_set_copy (pbb
->domain
));
1019 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
1021 isl_union_map_union (schedule_isl
,
1022 isl_union_map_from_map (bb_schedule
));
1024 return schedule_isl
;
1027 /* This method is executed before the construction of a for node. */
1028 static __isl_give isl_id
*
1029 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1031 isl_union_map
*dependences
= (isl_union_map
*) user
;
1032 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1033 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1034 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1035 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1036 for_info
->is_parallelizable
=
1037 !carries_deps (schedule
, dependences
, dimension
);
1038 isl_union_map_free (schedule
);
1039 isl_space_free (schedule_space
);
1040 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1044 /* Set the separate option for all dimensions.
1045 This helps to reduce control overhead. */
1047 static __isl_give isl_ast_build
*
1048 set_options (__isl_take isl_ast_build
*control
,
1049 __isl_keep isl_union_map
*schedule
)
1051 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
1052 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
1054 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
1055 isl_union_set
*range
=
1056 isl_union_set_from_set (isl_set_universe (range_space
));
1057 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
1058 domain
= isl_union_set_universe (domain
);
1059 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
1060 return isl_ast_build_set_options (control
, options
);
1063 static __isl_give isl_ast_node
*
1064 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
1066 /* Generate loop upper bounds that consist of the current loop iterator,
1067 an operator (< or <=) and an expression not involving the iterator.
1068 If this option is not set, then the current loop iterator may appear several
1069 times in the upper bound. See the isl manual for more details. */
1070 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
1072 add_parameters_to_ivs_params (scop
, ip
);
1073 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1074 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1075 context_isl
= set_options (context_isl
, schedule_isl
);
1076 isl_union_map
*dependences
= NULL
;
1077 if (flag_loop_parallelize_all
)
1079 dependences
= scop_get_dependences (scop
);
1081 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1084 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1087 isl_union_map_free (dependences
);
1088 isl_ast_build_free (context_isl
);
1092 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
1093 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
1096 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
1097 gimple_stmt_iterator
*gsi
)
1099 if (!defined_in_sese_p (tr
, region
->region
))
1103 use_operand_p use_p
;
1104 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
1106 tree use_tr
= USE_FROM_PTR (use_p
);
1108 /* Do not copy parameters that have been generated in the header of the
1110 if (region
->parameter_rename_map
->get(use_tr
))
1113 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
1117 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
1120 gimple
*copy
= gimple_copy (def_stmt
);
1121 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
1123 /* Create new names for all the definitions created by COPY and
1124 add replacement mappings for each new name. */
1125 def_operand_p def_p
;
1126 ssa_op_iter op_iter
;
1127 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1129 tree old_name
= DEF_FROM_PTR (def_p
);
1130 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
1131 region
->parameter_rename_map
->put(old_name
, new_name
);
1138 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
1140 /* For all the parameters which definitino is in the if_region->false_region,
1141 insert code on true_region (if_region->true_region->entry). */
1145 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
1147 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
1149 // If def is not in region.
1150 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
1152 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
1156 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1157 the given SCOP. Return true if code generation succeeded.
1159 FIXME: This is not yet a full implementation of the code generator
1160 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1163 graphite_regenerate_ast_isl (scop_p scop
)
1165 loop_p context_loop
;
1166 sese_info_p region
= scop
->scop_info
;
1167 ifsese if_region
= NULL
;
1168 isl_ast_node
*root_node
;
1171 timevar_push (TV_GRAPHITE_CODE_GEN
);
1172 graphite_regenerate_error
= false;
1173 root_node
= scop_to_isl_ast (scop
, ip
);
1175 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1177 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1178 print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
1179 fprintf (dump_file
, "\n");
1182 recompute_all_dominators ();
1185 if_region
= move_sese_in_condition (region
);
1186 sese_insert_phis_for_liveouts (region
,
1187 if_region
->region
->region
.exit
->src
,
1188 if_region
->false_region
->region
.exit
,
1189 if_region
->true_region
->region
.exit
);
1190 recompute_all_dominators ();
1193 context_loop
= region
->region
.entry
->src
->loop_father
;
1195 /* Copy all the parameters which are defined in the region. */
1196 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
1198 translate_isl_ast_to_gimple
t(region
);
1199 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
1201 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
1203 mark_virtual_operands_for_renaming (cfun
);
1204 update_ssa (TODO_update_ssa
);
1208 recompute_all_dominators ();
1211 if (graphite_regenerate_error
)
1212 set_ifsese_condition (if_region
, integer_zero_node
);
1214 free (if_region
->true_region
);
1215 free (if_region
->region
);
1218 ivs_params_clear (ip
);
1219 isl_ast_node_free (root_node
);
1220 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1225 int num_no_dependency
= 0;
1227 FOR_EACH_LOOP (loop
, 0)
1228 if (loop
->can_be_parallel
)
1229 num_no_dependency
++;
1231 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1235 return !graphite_regenerate_error
;
1237 #endif /* HAVE_isl */