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-into-ssa.h"
62 #include "graphite-isl-ast-to-gimple.h"
64 /* This flag is set when an error occurred during the translation of
67 static bool graphite_regenerate_error
;
69 /* We always try to use signed 128 bit types, but fall back to smaller types
70 in case a platform does not provide types of these sizes. In the future we
71 should use isl to derive the optimal type for each subexpression. */
73 static int max_mode_int_precision
=
74 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
75 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
76 128 : max_mode_int_precision
;
81 : is_parallelizable(false)
83 bool is_parallelizable
;
86 /* Converts a GMP constant VAL to a tree and returns it. */
89 gmp_cst_to_tree (tree type
, mpz_t val
)
91 tree t
= type
? type
: integer_type_node
;
96 wide_int wi
= wi::from_mpz (t
, tmp
, true);
99 return wide_int_to_tree (t
, wi
);
102 /* Verifies properties that GRAPHITE should maintain during translation. */
105 graphite_verify (void)
107 #ifdef ENABLE_CHECKING
108 verify_loop_structure ();
109 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 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_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 return fold_convert (type
, res
->second
);
292 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
296 translate_isl_ast_to_gimple::
297 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
299 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
300 isl_val
*val
= isl_ast_expr_get_val (expr
);
302 mpz_init (val_mpz_t
);
304 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
307 res
= gmp_cst_to_tree (type
, val_mpz_t
);
309 isl_ast_expr_free (expr
);
310 mpz_clear (val_mpz_t
);
314 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
318 translate_isl_ast_to_gimple::
319 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
321 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
322 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
323 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
324 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
325 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
326 isl_ast_expr_free (expr
);
330 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
333 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
336 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
339 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
341 case isl_ast_op_pdiv_q
:
342 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
344 case isl_ast_op_pdiv_r
:
345 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
347 case isl_ast_op_fdiv_q
:
348 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
351 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
352 tree_lhs_expr
, tree_rhs_expr
);
355 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
358 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
361 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
364 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
367 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
370 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
377 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
381 translate_isl_ast_to_gimple::
382 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
384 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
385 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
387 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
388 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
389 tree tree_second_expr
390 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
391 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
393 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
394 isl_ast_expr_free (expr
);
395 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
396 tree_second_expr
, tree_third_expr
);
399 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
403 translate_isl_ast_to_gimple::
404 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
406 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
407 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
408 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
409 isl_ast_expr_free (expr
);
410 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
413 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
414 to a GCC expression tree of type TYPE. */
417 translate_isl_ast_to_gimple::
418 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
420 enum tree_code op_code
;
421 switch (isl_ast_expr_get_op_type (expr
))
434 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
435 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
437 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
439 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
440 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
441 res
= fold_build2 (op_code
, type
, res
, t
);
443 isl_ast_expr_free (expr
);
447 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
451 translate_isl_ast_to_gimple::
452 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
455 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
456 switch (isl_ast_expr_get_op_type (expr
))
458 /* These isl ast expressions are not supported yet. */
459 case isl_ast_op_error
:
460 case isl_ast_op_call
:
461 case isl_ast_op_and_then
:
462 case isl_ast_op_or_else
:
463 case isl_ast_op_select
:
468 return nary_op_to_tree (type
, expr
, ip
);
474 case isl_ast_op_pdiv_q
:
475 case isl_ast_op_pdiv_r
:
476 case isl_ast_op_fdiv_q
:
484 return binary_op_to_tree (type
, expr
, ip
);
486 case isl_ast_op_minus
:
487 return unary_op_to_tree (type
, expr
, ip
);
489 case isl_ast_op_cond
:
490 return ternary_op_to_tree (type
, expr
, ip
);
499 /* Converts an ISL AST expression E back to a GCC expression tree of
503 translate_isl_ast_to_gimple::
504 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
507 switch (isl_ast_expr_get_type (expr
))
509 case isl_ast_expr_id
:
510 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
512 case isl_ast_expr_int
:
513 return gcc_expression_from_isl_expr_int (type
, expr
);
515 case isl_ast_expr_op
:
516 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
525 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
526 induction variable for the new LOOP. New LOOP is attached to CFG
527 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
528 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
529 ISL's scattering name to the induction variable created for the
530 loop of STMT. The new induction variable is inserted in the NEWIVS
531 vector and is of type TYPE. */
534 translate_isl_ast_to_gimple::
535 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
536 loop_p outer
, tree type
, tree lb
, tree ub
,
539 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
540 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
541 tree ivvar
= create_tmp_var (type
, "graphite_IV");
542 tree iv
, iv_after_increment
;
543 loop_p loop
= create_empty_loop_on_edge
544 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
545 outer
? outer
: entry_edge
->src
->loop_father
);
547 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
548 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
549 std::map
<isl_id
*, tree
>::iterator res
;
552 isl_id_free (res
->first
);
554 isl_ast_expr_free (for_iterator
);
558 /* Create the loop for a isl_ast_node_for.
560 - NEXT_E is the edge where new generated code should be attached. */
563 translate_isl_ast_to_gimple::
564 translate_isl_ast_for_loop (loop_p context_loop
,
565 __isl_keep isl_ast_node
*node_for
, edge next_e
,
566 tree type
, tree lb
, tree ub
,
569 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
570 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
572 edge last_e
= single_exit (loop
);
573 edge to_body
= single_succ_edge (loop
->header
);
574 basic_block after
= to_body
->dest
;
576 /* Create a basic block for loop close phi nodes. */
577 last_e
= single_succ_edge (split_edge (last_e
));
579 /* Translate the body of the loop. */
580 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
581 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
582 isl_ast_node_free (for_body
);
583 redirect_edge_succ_nodup (next_e
, after
);
584 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
586 if (flag_loop_parallelize_all
)
588 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
590 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
591 loop
->can_be_parallel
= for_info
->is_parallelizable
;
599 /* We use this function to get the upper bound because of the form,
600 which is used by isl to represent loops:
602 for (iterator = init; cond; iterator += inc)
610 The loop condition is an arbitrary expression, which contains the
611 current loop iterator.
613 (e.g. iterator + 3 < B && C > iterator + A)
615 We have to know the upper bound of the iterator to generate a loop
616 in Gimple form. It can be obtained from the special representation
617 of the loop condition, which is generated by isl,
618 if the ast_build_atomic_upper_bound option is set. In this case,
619 isl generates a loop condition that consists of the current loop
620 iterator, + an operator (< or <=) and an expression not involving
621 the iterator, which is processed and returned by this function.
623 (e.g iterator <= upper-bound-expression-without-iterator) */
625 static __isl_give isl_ast_expr
*
626 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
628 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
629 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
630 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
632 switch (isl_ast_expr_get_op_type (for_cond
))
635 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
640 // (iterator < ub) => (iterator <= ub - 1)
642 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
643 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
644 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
651 isl_ast_expr_free (for_cond
);
655 /* All loops generated by create_empty_loop_on_edge have the form of
662 } while (lower bound < upper bound);
664 We create a new if region protecting the loop to be executed, if
665 the execution count is zero (lower bound > upper bound). */
668 translate_isl_ast_to_gimple::
669 graphite_create_new_loop_guard (edge entry_edge
,
670 __isl_keep isl_ast_node
*node_for
, tree
*type
,
671 tree
*lb
, tree
*ub
, ivs_params
&ip
)
673 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
678 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
679 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
680 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
681 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
682 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
684 /* When ub is simply a constant or a parameter, use lb <= ub. */
685 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
686 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
689 tree one
= (POINTER_TYPE_P (*type
)
690 ? convert_to_ptrofftype (integer_one_node
)
691 : fold_convert (*type
, integer_one_node
));
692 /* Adding +1 and using LT_EXPR helps with loop latches that have a
693 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
694 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
695 is true, even if we do not want this. However lb < ub + 1 is false,
697 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
698 : PLUS_EXPR
, *type
, *ub
, one
);
700 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
703 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
708 /* Translates an isl_ast_node_for to Gimple. */
711 translate_isl_ast_to_gimple::
712 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
713 edge next_e
, ivs_params
&ip
)
715 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
717 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
719 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
721 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
726 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
727 variables of the loops around GBB in SESE.
729 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
730 chrec, we could consider using a map<int, tree> that maps loop ids to the
731 corresponding tree expressions. */
734 translate_isl_ast_to_gimple::
735 build_iv_mapping (vec
<tree
> iv_map
, gimple_bb_p gbb
,
736 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
739 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
740 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
742 isl_ast_expr
*arg_expr
;
743 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
745 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
747 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
748 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
749 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
750 iv_map
[old_loop
->num
] = t
;
755 /* Translates an isl_ast_node_user to Gimple.
757 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
760 translate_isl_ast_to_gimple::
761 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
762 edge next_e
, ivs_params
&ip
)
764 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
765 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
766 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
767 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
768 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
769 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
771 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
773 isl_ast_expr_free (name_expr
);
774 isl_id_free (name_id
);
776 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
777 "The entry block should not even appear within a scop");
779 int nb_loops
= number_of_loops (cfun
);
780 iv_map
.create (nb_loops
);
781 iv_map
.safe_grow_cleared (nb_loops
);
783 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
784 isl_ast_expr_free (user_expr
);
785 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
786 SCOP_REGION (pbb
->scop
), next_e
,
788 &graphite_regenerate_error
);
790 mark_virtual_operands_for_renaming (cfun
);
791 update_ssa (TODO_update_ssa
);
795 /* Translates an isl_ast_node_block to Gimple. */
798 translate_isl_ast_to_gimple::
799 translate_isl_ast_node_block (loop_p context_loop
,
800 __isl_keep isl_ast_node
*node
,
801 edge next_e
, ivs_params
&ip
)
803 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
804 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
806 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
808 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
809 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
810 isl_ast_node_free (tmp_node
);
812 isl_ast_node_list_free (node_list
);
816 /* Creates a new if region corresponding to ISL's cond. */
819 translate_isl_ast_to_gimple::
820 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
824 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
825 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
826 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
830 /* Translates an isl_ast_node_if to Gimple. */
833 translate_isl_ast_to_gimple::
834 translate_isl_ast_node_if (loop_p context_loop
,
835 __isl_keep isl_ast_node
*node
,
836 edge next_e
, ivs_params
&ip
)
838 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
839 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
840 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
842 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
843 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
844 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
845 isl_ast_node_free (then_node
);
847 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
848 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
849 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
850 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
851 isl_ast_node_free (else_node
);
855 /* Translates an ISL AST node NODE to GCC representation in the
856 context of a SESE. */
859 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
860 __isl_keep isl_ast_node
*node
,
861 edge next_e
, ivs_params
&ip
)
863 switch (isl_ast_node_get_type (node
))
865 case isl_ast_node_error
:
868 case isl_ast_node_for
:
869 return translate_isl_ast_node_for (context_loop
, node
,
872 case isl_ast_node_if
:
873 return translate_isl_ast_node_if (context_loop
, node
,
876 case isl_ast_node_user
:
877 return translate_isl_ast_node_user (node
, next_e
, ip
);
879 case isl_ast_node_block
:
880 return translate_isl_ast_node_block (context_loop
, node
,
888 /* Prints NODE to FILE. */
891 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
892 __isl_keep isl_ctx
*ctx
)
894 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
895 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
896 prn
= isl_printer_print_ast_node (prn
, node
);
897 prn
= isl_printer_print_str (prn
, "\n");
898 isl_printer_free (prn
);
901 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
904 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
906 sese region
= SCOP_REGION (scop
);
907 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
908 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
910 for (i
= 0; i
< nb_parameters
; i
++)
912 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
913 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
918 /* Generates a build, which specifies the constraints on the parameters. */
920 static __isl_give isl_ast_build
*
921 generate_isl_context (scop_p scop
)
923 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
924 return isl_ast_build_from_context (context_isl
);
927 /* Get the maximal number of schedule dimensions in the scop SCOP. */
930 int get_max_schedule_dimensions (scop_p scop
)
934 int schedule_dims
= 0;
936 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
938 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
939 if (pbb_schedule_dims
> schedule_dims
)
940 schedule_dims
= pbb_schedule_dims
;
943 return schedule_dims
;
946 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
948 For schedules with different dimensionality, the isl AST generator can not
949 define an order and will just randomly choose an order. The solution to this
950 problem is to extend all schedules to the maximal number of schedule
951 dimensions (using '0's for the remaining values). */
953 static __isl_give isl_map
*
954 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
956 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
958 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
960 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
962 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
965 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
971 /* Generates a schedule, which specifies an order used to
972 visit elements in a domain. */
974 static __isl_give isl_union_map
*
975 generate_isl_schedule (scop_p scop
)
977 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
980 isl_union_map
*schedule_isl
=
981 isl_union_map_empty (isl_set_get_space (scop
->context
));
983 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
985 /* Dead code elimination: when the domain of a PBB is empty,
986 don't generate code for the PBB. */
987 if (isl_set_is_empty (pbb
->domain
))
990 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
991 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
992 isl_set_copy (pbb
->domain
));
993 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
995 isl_union_map_union (schedule_isl
,
996 isl_union_map_from_map (bb_schedule
));
1001 /* This method is executed before the construction of a for node. */
1002 static __isl_give isl_id
*
1003 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1005 isl_union_map
*dependences
= (isl_union_map
*) user
;
1006 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1007 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1008 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1009 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1010 for_info
->is_parallelizable
=
1011 !carries_deps (schedule
, dependences
, dimension
);
1012 isl_union_map_free (schedule
);
1013 isl_space_free (schedule_space
);
1014 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1018 /* Set the separate option for all dimensions.
1019 This helps to reduce control overhead. */
1021 static __isl_give isl_ast_build
*
1022 set_options (__isl_take isl_ast_build
*control
,
1023 __isl_keep isl_union_map
*schedule
)
1025 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
1026 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
1028 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
1029 isl_union_set
*range
=
1030 isl_union_set_from_set (isl_set_universe (range_space
));
1031 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
1032 domain
= isl_union_set_universe (domain
);
1033 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
1034 return isl_ast_build_set_options (control
, options
);
1037 static __isl_give isl_ast_node
*
1038 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
1040 /* Generate loop upper bounds that consist of the current loop iterator,
1041 an operator (< or <=) and an expression not involving the iterator.
1042 If this option is not set, then the current loop iterator may appear several
1043 times in the upper bound. See the isl manual for more details. */
1044 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
1046 add_parameters_to_ivs_params (scop
, ip
);
1047 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
1048 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1049 context_isl
= set_options (context_isl
, schedule_isl
);
1050 isl_union_map
*dependences
= NULL
;
1051 if (flag_loop_parallelize_all
)
1053 dependences
= scop_get_dependences (scop
);
1055 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1058 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
1061 isl_union_map_free (dependences
);
1062 isl_ast_build_free (context_isl
);
1066 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1067 the given SCOP. Return true if code generation succeeded.
1069 FIXME: This is not yet a full implementation of the code generator
1070 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1073 graphite_regenerate_ast_isl (scop_p scop
)
1075 loop_p context_loop
;
1076 sese region
= SCOP_REGION (scop
);
1077 ifsese if_region
= NULL
;
1078 isl_ast_node
*root_node
;
1081 timevar_push (TV_GRAPHITE_CODE_GEN
);
1082 graphite_regenerate_error
= false;
1083 root_node
= scop_to_isl_ast (scop
, ip
);
1085 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1087 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
1088 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
1089 fprintf (dump_file
, "\n");
1092 recompute_all_dominators ();
1095 if_region
= move_sese_in_condition (region
);
1096 sese_insert_phis_for_liveouts (region
,
1097 if_region
->region
->exit
->src
,
1098 if_region
->false_region
->exit
,
1099 if_region
->true_region
->exit
);
1100 recompute_all_dominators ();
1103 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
1105 translate_isl_ast_to_gimple
t (region
);
1107 t
.translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
1110 mark_virtual_operands_for_renaming (cfun
);
1111 update_ssa (TODO_update_ssa
);
1115 recompute_all_dominators ();
1118 if (graphite_regenerate_error
)
1119 set_ifsese_condition (if_region
, integer_zero_node
);
1121 free (if_region
->true_region
);
1122 free (if_region
->region
);
1125 ivs_params_clear (ip
);
1126 isl_ast_node_free (root_node
);
1127 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1129 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1132 int num_no_dependency
= 0;
1134 FOR_EACH_LOOP (loop
, 0)
1135 if (loop
->can_be_parallel
)
1136 num_no_dependency
++;
1138 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
1142 return !graphite_regenerate_error
;
1144 #endif /* HAVE_isl */