1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
26 #include <isl/union_map.h>
27 #include <isl/ast_build.h>
28 #if defined(__cplusplus)
31 #include <isl/val_gmp.h>
32 #if defined(__cplusplus)
38 #include "coretypes.h"
40 #include "basic-block.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
46 #include "gimple-iterator.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-pass.h"
50 #include "tree-data-ref.h"
52 #include "tree-ssa-loop-manip.h"
53 #include "tree-scalar-evolution.h"
57 #include "graphite-poly.h"
58 #include "graphite-isl-ast-to-gimple.h"
60 /* This flag is set when an error occurred during the translation of
63 static bool graphite_regenerate_error
;
65 /* We always try to use signed 128 bit types, but fall back to smaller types
66 in case a platform does not provide types of these sizes. In the future we
67 should use isl to derive the optimal type for each subexpression. */
69 static int max_mode_int_precision
=
70 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
71 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
72 128 : max_mode_int_precision
;
74 /* Converts a GMP constant VAL to a tree and returns it. */
77 gmp_cst_to_tree (tree type
, mpz_t val
)
79 tree t
= type
? type
: integer_type_node
;
84 wide_int wi
= wi::from_mpz (t
, tmp
, true);
87 return wide_int_to_tree (t
, wi
);
90 /* Verifies properties that GRAPHITE should maintain during translation. */
93 graphite_verify (void)
95 #ifdef ENABLE_CHECKING
96 verify_loop_structure ();
97 verify_loop_closed_ssa (true);
101 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
102 to corresponding trees. */
104 typedef std::map
<isl_id
*, tree
> ivs_params
;
106 /* Free all memory allocated for ISL's identifiers. */
108 void ivs_params_clear (ivs_params
&ip
)
110 std::map
<isl_id
*, tree
>::iterator it
;
111 for (it
= ip
.begin ();
112 it
!= ip
.end (); it
++)
114 isl_id_free (it
->first
);
119 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*,
122 /* Return the tree variable that corresponds to the given isl ast identifier
123 expression (an isl_ast_expr of type isl_ast_expr_id). */
126 gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr
*expr_id
,
129 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
130 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
131 std::map
<isl_id
*, tree
>::iterator res
;
132 res
= ip
.find (tmp_isl_id
);
133 isl_id_free (tmp_isl_id
);
134 gcc_assert (res
!= ip
.end () &&
135 "Could not map isl_id to tree expression");
136 isl_ast_expr_free (expr_id
);
140 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
144 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
146 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
147 isl_val
*val
= isl_ast_expr_get_val (expr
);
149 mpz_init (val_mpz_t
);
151 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
154 res
= gmp_cst_to_tree (type
, val_mpz_t
);
156 isl_ast_expr_free (expr
);
157 mpz_clear (val_mpz_t
);
161 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
165 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
167 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
168 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
169 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
170 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
171 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
172 isl_ast_expr_free (expr
);
176 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
179 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
182 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
185 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
187 case isl_ast_op_fdiv_q
:
188 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
191 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
192 tree_lhs_expr
, tree_rhs_expr
);
195 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
198 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
201 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
204 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
207 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
210 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
217 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
221 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
223 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
224 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
226 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
227 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
228 tree tree_second_expr
229 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
230 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
232 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
233 isl_ast_expr_free (expr
);
234 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
235 tree_second_expr
, tree_third_expr
);
238 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
242 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
244 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
245 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
246 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
247 isl_ast_expr_free (expr
);
248 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
251 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
252 to a GCC expression tree of type TYPE. */
255 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
257 enum tree_code op_code
;
258 switch (isl_ast_expr_get_op_type (expr
))
271 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
272 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
274 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
276 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
277 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
278 res
= fold_build2 (op_code
, type
, res
, t
);
280 isl_ast_expr_free (expr
);
285 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
289 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
292 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
293 switch (isl_ast_expr_get_op_type (expr
))
295 /* These isl ast expressions are not supported yet. */
296 case isl_ast_op_error
:
297 case isl_ast_op_call
:
298 case isl_ast_op_and_then
:
299 case isl_ast_op_or_else
:
300 case isl_ast_op_pdiv_q
:
301 case isl_ast_op_pdiv_r
:
302 case isl_ast_op_select
:
307 return nary_op_to_tree (type
, expr
, ip
);
313 case isl_ast_op_fdiv_q
:
321 return binary_op_to_tree (type
, expr
, ip
);
323 case isl_ast_op_minus
:
324 return unary_op_to_tree (type
, expr
, ip
);
326 case isl_ast_op_cond
:
327 return ternary_op_to_tree (type
, expr
, ip
);
336 /* Converts an ISL AST expression E back to a GCC expression tree of
340 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
343 switch (isl_ast_expr_get_type (expr
))
345 case isl_ast_expr_id
:
346 return gcc_expression_from_isl_ast_expr_id (expr
, ip
);
348 case isl_ast_expr_int
:
349 return gcc_expression_from_isl_expr_int (type
, expr
);
351 case isl_ast_expr_op
:
352 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
361 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
362 induction variable for the new LOOP. New LOOP is attached to CFG
363 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
364 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
365 ISL's scattering name to the induction variable created for the
366 loop of STMT. The new induction variable is inserted in the NEWIVS
367 vector and is of type TYPE. */
370 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
371 loop_p outer
, tree type
, tree lb
, tree ub
,
374 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
375 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
376 tree ivvar
= create_tmp_var (type
, "graphite_IV");
377 tree iv
, iv_after_increment
;
378 loop_p loop
= create_empty_loop_on_edge
379 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
380 outer
? outer
: entry_edge
->src
->loop_father
);
382 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
383 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
385 isl_ast_expr_free (for_iterator
);
390 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
391 edge next_e
, ivs_params
&ip
);
393 /* Create the loop for a isl_ast_node_for.
395 - NEXT_E is the edge where new generated code should be attached. */
398 translate_isl_ast_for_loop (loop_p context_loop
,
399 __isl_keep isl_ast_node
*node_for
, edge next_e
,
400 tree type
, tree lb
, tree ub
,
403 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
404 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
406 edge last_e
= single_exit (loop
);
407 edge to_body
= single_succ_edge (loop
->header
);
408 basic_block after
= to_body
->dest
;
410 /* Create a basic block for loop close phi nodes. */
411 last_e
= single_succ_edge (split_edge (last_e
));
413 /* Translate the body of the loop. */
414 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
415 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
416 isl_ast_node_free (for_body
);
417 redirect_edge_succ_nodup (next_e
, after
);
418 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
420 /* TODO: Add checking for the loop parallelism. */
425 /* We use this function to get the upper bound because of the form,
426 which is used by isl to represent loops:
428 for (iterator = init; cond; iterator += inc)
436 The loop condition is an arbitrary expression, which contains the
437 current loop iterator.
439 (e.g. iterator + 3 < B && C > iterator + A)
441 We have to know the upper bound of the iterator to generate a loop
442 in Gimple form. It can be obtained from the special representation
443 of the loop condition, which is generated by isl,
444 if the ast_build_atomic_upper_bound option is set. In this case,
445 isl generates a loop condition that consists of the current loop
446 iterator, + an operator (< or <=) and an expression not involving
447 the iterator, which is processed and returned by this function.
449 (e.g iterator <= upper-bound-expression-without-iterator) */
451 static __isl_give isl_ast_expr
*
452 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
454 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
455 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
456 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
458 switch (isl_ast_expr_get_op_type (for_cond
))
461 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
466 // (iterator < ub) => (iterator <= ub - 1)
467 isl_val
*one
= isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
468 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
469 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
476 isl_ast_expr_free (for_cond
);
480 /* All loops generated by create_empty_loop_on_edge have the form of
487 } while (lower bound < upper bound);
489 We create a new if region protecting the loop to be executed, if
490 the execution count is zero (lower bound > upper bound). */
493 graphite_create_new_loop_guard (edge entry_edge
,
494 __isl_keep isl_ast_node
*node_for
, tree
*type
,
495 tree
*lb
, tree
*ub
, ivs_params
&ip
)
497 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
502 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
503 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
504 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
505 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
506 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
508 /* When ub is simply a constant or a parameter, use lb <= ub. */
509 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
510 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
513 tree one
= (POINTER_TYPE_P (*type
)
514 ? convert_to_ptrofftype (integer_one_node
)
515 : fold_convert (*type
, integer_one_node
));
516 /* Adding +1 and using LT_EXPR helps with loop latches that have a
517 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
518 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
519 is true, even if we do not want this. However lb < ub + 1 is false,
521 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
522 : PLUS_EXPR
, *type
, *ub
, one
);
524 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
527 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
532 /* Translates an isl_ast_node_for to Gimple. */
535 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
536 edge next_e
, ivs_params
&ip
)
538 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
540 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
542 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
544 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
549 /* Translates an ISL AST node NODE to GCC representation in the
550 context of a SESE. */
553 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
554 edge next_e
, ivs_params
&ip
)
556 switch (isl_ast_node_get_type (node
))
558 case isl_ast_node_error
:
561 case isl_ast_node_for
:
562 return translate_isl_ast_node_for (context_loop
, node
,
565 case isl_ast_node_if
:
568 case isl_ast_node_user
:
571 case isl_ast_node_block
:
579 /* Prints NODE to FILE. */
582 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
583 __isl_keep isl_ctx
*ctx
)
585 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
586 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
587 prn
= isl_printer_print_ast_node (prn
, node
);
588 prn
= isl_printer_print_str (prn
, "\n");
589 isl_printer_free (prn
);
592 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
595 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
597 sese region
= SCOP_REGION (scop
);
598 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
599 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
601 for (i
= 0; i
< nb_parameters
; i
++)
603 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
604 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
609 /* Generates a build, which specifies the constraints on the parameters. */
611 static __isl_give isl_ast_build
*
612 generate_isl_context (scop_p scop
)
614 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
615 return isl_ast_build_from_context (context_isl
);
618 /* Generates a schedule, which specifies an order used to
619 visit elements in a domain. */
621 static __isl_give isl_union_map
*
622 generate_isl_schedule (scop_p scop
)
626 isl_union_map
*schedule_isl
=
627 isl_union_map_empty (isl_set_get_space (scop
->context
));
629 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
631 /* Dead code elimination: when the domain of a PBB is empty,
632 don't generate code for the PBB. */
633 if (isl_set_is_empty (pbb
->domain
))
636 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
637 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
638 isl_set_copy (pbb
->domain
));
640 isl_union_map_union (schedule_isl
,
641 isl_union_map_from_map (bb_schedule
));
646 static __isl_give isl_ast_node
*
647 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
649 /* Generate loop upper bounds that consist of the current loop iterator,
650 an operator (< or <=) and an expression not involving the iterator.
651 If this option is not set, then the current loop iterator may appear several
652 times in the upper bound. See the isl manual for more details. */
653 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
655 add_parameters_to_ivs_params (scop
, ip
);
656 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
657 isl_ast_build
*context_isl
= generate_isl_context (scop
);
658 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
660 isl_ast_build_free (context_isl
);
664 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
665 the given SCOP. Return true if code generation succeeded.
667 FIXME: This is not yet a full implementation of the code generator
668 with ISL ASTs. Generation of GIMPLE code has to be completed. */
671 graphite_regenerate_ast_isl (scop_p scop
)
674 sese region
= SCOP_REGION (scop
);
675 ifsese if_region
= NULL
;
676 isl_ast_node
*root_node
;
679 timevar_push (TV_GRAPHITE_CODE_GEN
);
680 graphite_regenerate_error
= false;
681 root_node
= scop_to_isl_ast (scop
, ip
);
683 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
685 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
686 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
687 fprintf (dump_file
, "\n");
690 recompute_all_dominators ();
693 if_region
= move_sese_in_condition (region
);
694 sese_insert_phis_for_liveouts (region
,
695 if_region
->region
->exit
->src
,
696 if_region
->false_region
->exit
,
697 if_region
->true_region
->exit
);
698 recompute_all_dominators ();
701 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
703 translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
707 recompute_all_dominators ();
710 if (graphite_regenerate_error
)
711 set_ifsese_condition (if_region
, integer_zero_node
);
713 free (if_region
->true_region
);
714 free (if_region
->region
);
717 ivs_params_clear (ip
);
718 isl_ast_node_free (root_node
);
719 timevar_pop (TV_GRAPHITE_CODE_GEN
);
721 return !graphite_regenerate_error
;