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"
54 #include "gimple-ssa.h"
55 #include "tree-into-ssa.h"
59 #include "graphite-poly.h"
60 #include "graphite-isl-ast-to-gimple.h"
62 /* This flag is set when an error occurred during the translation of
65 static bool graphite_regenerate_error
;
67 /* We always try to use signed 128 bit types, but fall back to smaller types
68 in case a platform does not provide types of these sizes. In the future we
69 should use isl to derive the optimal type for each subexpression. */
71 static int max_mode_int_precision
=
72 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
73 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
74 128 : max_mode_int_precision
;
76 /* Converts a GMP constant VAL to a tree and returns it. */
79 gmp_cst_to_tree (tree type
, mpz_t val
)
81 tree t
= type
? type
: integer_type_node
;
86 wide_int wi
= wi::from_mpz (t
, tmp
, true);
89 return wide_int_to_tree (t
, wi
);
92 /* Verifies properties that GRAPHITE should maintain during translation. */
95 graphite_verify (void)
97 #ifdef ENABLE_CHECKING
98 verify_loop_structure ();
99 verify_loop_closed_ssa (true);
103 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
104 to corresponding trees. */
106 typedef std::map
<isl_id
*, tree
> ivs_params
;
108 /* Free all memory allocated for ISL's identifiers. */
110 void ivs_params_clear (ivs_params
&ip
)
112 std::map
<isl_id
*, tree
>::iterator it
;
113 for (it
= ip
.begin ();
114 it
!= ip
.end (); it
++)
116 isl_id_free (it
->first
);
121 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*,
124 /* Return the tree variable that corresponds to the given isl ast identifier
125 expression (an isl_ast_expr of type isl_ast_expr_id). */
128 gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr
*expr_id
,
131 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
132 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
133 std::map
<isl_id
*, tree
>::iterator res
;
134 res
= ip
.find (tmp_isl_id
);
135 isl_id_free (tmp_isl_id
);
136 gcc_assert (res
!= ip
.end () &&
137 "Could not map isl_id to tree expression");
138 isl_ast_expr_free (expr_id
);
142 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
146 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
148 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
149 isl_val
*val
= isl_ast_expr_get_val (expr
);
151 mpz_init (val_mpz_t
);
153 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
156 res
= gmp_cst_to_tree (type
, val_mpz_t
);
158 isl_ast_expr_free (expr
);
159 mpz_clear (val_mpz_t
);
163 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
167 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
169 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
170 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
171 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
172 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
173 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
174 isl_ast_expr_free (expr
);
178 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
181 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
184 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
187 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
189 case isl_ast_op_pdiv_q
:
190 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
192 case isl_ast_op_pdiv_r
:
193 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
195 case isl_ast_op_fdiv_q
:
196 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
199 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
200 tree_lhs_expr
, tree_rhs_expr
);
203 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
206 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
209 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
212 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
215 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
218 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
225 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
229 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
231 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
232 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
234 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
235 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
236 tree tree_second_expr
237 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
238 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
240 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
241 isl_ast_expr_free (expr
);
242 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
243 tree_second_expr
, tree_third_expr
);
246 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
250 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
252 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
253 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
254 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
255 isl_ast_expr_free (expr
);
256 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
259 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
260 to a GCC expression tree of type TYPE. */
263 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
265 enum tree_code op_code
;
266 switch (isl_ast_expr_get_op_type (expr
))
279 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
280 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
282 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
284 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
285 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
286 res
= fold_build2 (op_code
, type
, res
, t
);
288 isl_ast_expr_free (expr
);
293 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
297 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
300 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
301 switch (isl_ast_expr_get_op_type (expr
))
303 /* These isl ast expressions are not supported yet. */
304 case isl_ast_op_error
:
305 case isl_ast_op_call
:
306 case isl_ast_op_and_then
:
307 case isl_ast_op_or_else
:
308 case isl_ast_op_select
:
313 return nary_op_to_tree (type
, expr
, ip
);
319 case isl_ast_op_pdiv_q
:
320 case isl_ast_op_pdiv_r
:
321 case isl_ast_op_fdiv_q
:
329 return binary_op_to_tree (type
, expr
, ip
);
331 case isl_ast_op_minus
:
332 return unary_op_to_tree (type
, expr
, ip
);
334 case isl_ast_op_cond
:
335 return ternary_op_to_tree (type
, expr
, ip
);
344 /* Converts an ISL AST expression E back to a GCC expression tree of
348 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
351 switch (isl_ast_expr_get_type (expr
))
353 case isl_ast_expr_id
:
354 return gcc_expression_from_isl_ast_expr_id (expr
, ip
);
356 case isl_ast_expr_int
:
357 return gcc_expression_from_isl_expr_int (type
, expr
);
359 case isl_ast_expr_op
:
360 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
369 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
370 induction variable for the new LOOP. New LOOP is attached to CFG
371 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
372 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
373 ISL's scattering name to the induction variable created for the
374 loop of STMT. The new induction variable is inserted in the NEWIVS
375 vector and is of type TYPE. */
378 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
379 loop_p outer
, tree type
, tree lb
, tree ub
,
382 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
383 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
384 tree ivvar
= create_tmp_var (type
, "graphite_IV");
385 tree iv
, iv_after_increment
;
386 loop_p loop
= create_empty_loop_on_edge
387 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
388 outer
? outer
: entry_edge
->src
->loop_father
);
390 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
391 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
393 isl_ast_expr_free (for_iterator
);
398 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
399 edge next_e
, ivs_params
&ip
);
401 /* Create the loop for a isl_ast_node_for.
403 - NEXT_E is the edge where new generated code should be attached. */
406 translate_isl_ast_for_loop (loop_p context_loop
,
407 __isl_keep isl_ast_node
*node_for
, edge next_e
,
408 tree type
, tree lb
, tree ub
,
411 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
412 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
414 edge last_e
= single_exit (loop
);
415 edge to_body
= single_succ_edge (loop
->header
);
416 basic_block after
= to_body
->dest
;
418 /* Create a basic block for loop close phi nodes. */
419 last_e
= single_succ_edge (split_edge (last_e
));
421 /* Translate the body of the loop. */
422 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
423 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
424 isl_ast_node_free (for_body
);
425 redirect_edge_succ_nodup (next_e
, after
);
426 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
428 /* TODO: Add checking for the loop parallelism. */
433 /* We use this function to get the upper bound because of the form,
434 which is used by isl to represent loops:
436 for (iterator = init; cond; iterator += inc)
444 The loop condition is an arbitrary expression, which contains the
445 current loop iterator.
447 (e.g. iterator + 3 < B && C > iterator + A)
449 We have to know the upper bound of the iterator to generate a loop
450 in Gimple form. It can be obtained from the special representation
451 of the loop condition, which is generated by isl,
452 if the ast_build_atomic_upper_bound option is set. In this case,
453 isl generates a loop condition that consists of the current loop
454 iterator, + an operator (< or <=) and an expression not involving
455 the iterator, which is processed and returned by this function.
457 (e.g iterator <= upper-bound-expression-without-iterator) */
459 static __isl_give isl_ast_expr
*
460 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
462 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
463 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
464 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
466 switch (isl_ast_expr_get_op_type (for_cond
))
469 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
474 // (iterator < ub) => (iterator <= ub - 1)
476 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
477 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
478 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
485 isl_ast_expr_free (for_cond
);
489 /* All loops generated by create_empty_loop_on_edge have the form of
496 } while (lower bound < upper bound);
498 We create a new if region protecting the loop to be executed, if
499 the execution count is zero (lower bound > upper bound). */
502 graphite_create_new_loop_guard (edge entry_edge
,
503 __isl_keep isl_ast_node
*node_for
, tree
*type
,
504 tree
*lb
, tree
*ub
, ivs_params
&ip
)
506 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
511 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
512 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
513 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
514 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
515 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
517 /* When ub is simply a constant or a parameter, use lb <= ub. */
518 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
519 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
522 tree one
= (POINTER_TYPE_P (*type
)
523 ? convert_to_ptrofftype (integer_one_node
)
524 : fold_convert (*type
, integer_one_node
));
525 /* Adding +1 and using LT_EXPR helps with loop latches that have a
526 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
527 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
528 is true, even if we do not want this. However lb < ub + 1 is false,
530 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
531 : PLUS_EXPR
, *type
, *ub
, one
);
533 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
536 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
541 /* Translates an isl_ast_node_for to Gimple. */
544 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
545 edge next_e
, ivs_params
&ip
)
547 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
549 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
551 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
553 translate_isl_ast_for_loop (context_loop
, node
, true_e
,
558 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
559 variables of the loops around GBB in SESE.
561 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
562 chrec, we could consider using a map<int, tree> that maps loop ids to the
563 corresponding tree expressions. */
566 build_iv_mapping (vec
<tree
> iv_map
, gimple_bb_p gbb
,
567 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
570 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
571 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
573 isl_ast_expr
*arg_expr
;
574 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
576 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
578 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
579 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
580 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
581 iv_map
[old_loop
->num
] = t
;
586 /* Translates an isl_ast_node_user to Gimple.
588 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
591 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
592 edge next_e
, ivs_params
&ip
)
594 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
595 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
596 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
597 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
598 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
599 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
601 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
603 isl_ast_expr_free (name_expr
);
604 isl_id_free (name_id
);
606 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
607 "The entry block should not even appear within a scop");
609 loop_p loop
= gbb_loop (gbb
);
610 iv_map
.create (loop
->num
+ 1);
611 iv_map
.safe_grow_cleared (loop
->num
+ 1);
613 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, SCOP_REGION (pbb
->scop
));
614 isl_ast_expr_free (user_expr
);
615 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
),
616 SCOP_REGION (pbb
->scop
), next_e
,
618 &graphite_regenerate_error
);
620 mark_virtual_operands_for_renaming (cfun
);
621 update_ssa (TODO_update_ssa
);
625 /* Translates an isl_ast_node_block to Gimple. */
628 translate_isl_ast_node_block (loop_p context_loop
,
629 __isl_keep isl_ast_node
*node
,
630 edge next_e
, ivs_params
&ip
)
632 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
633 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
635 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
637 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
638 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
639 isl_ast_node_free (tmp_node
);
641 isl_ast_node_list_free (node_list
);
645 /* Translates an ISL AST node NODE to GCC representation in the
646 context of a SESE. */
649 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
650 edge next_e
, ivs_params
&ip
)
652 switch (isl_ast_node_get_type (node
))
654 case isl_ast_node_error
:
657 case isl_ast_node_for
:
658 return translate_isl_ast_node_for (context_loop
, node
,
661 case isl_ast_node_if
:
664 case isl_ast_node_user
:
665 return translate_isl_ast_node_user (node
, next_e
, ip
);
667 case isl_ast_node_block
:
668 return translate_isl_ast_node_block (context_loop
, node
,
676 /* Prints NODE to FILE. */
679 print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
680 __isl_keep isl_ctx
*ctx
)
682 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
683 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
684 prn
= isl_printer_print_ast_node (prn
, node
);
685 prn
= isl_printer_print_str (prn
, "\n");
686 isl_printer_free (prn
);
689 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
692 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
694 sese region
= SCOP_REGION (scop
);
695 unsigned nb_parameters
= isl_set_dim (scop
->context
, isl_dim_param
);
696 gcc_assert (nb_parameters
== SESE_PARAMS (region
).length ());
698 for (i
= 0; i
< nb_parameters
; i
++)
700 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->context
, isl_dim_param
, i
);
701 ip
[tmp_id
] = SESE_PARAMS (region
)[i
];
706 /* Generates a build, which specifies the constraints on the parameters. */
708 static __isl_give isl_ast_build
*
709 generate_isl_context (scop_p scop
)
711 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->context
));
712 return isl_ast_build_from_context (context_isl
);
715 /* Get the maximal number of schedule dimensions in the scop SCOP. */
718 int get_max_schedule_dimensions (scop_p scop
)
722 int schedule_dims
= 0;
724 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
726 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
727 if (pbb_schedule_dims
> schedule_dims
)
728 schedule_dims
= pbb_schedule_dims
;
731 return schedule_dims
;
734 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
736 For schedules with different dimensionality, the isl AST generator can not
737 define an order and will just randomly choose an order. The solution to this
738 problem is to extend all schedules to the maximal number of schedule
739 dimensions (using '0's for the remaining values). */
741 static __isl_give isl_map
*
742 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
744 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
746 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
748 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
750 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
753 isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
759 /* Generates a schedule, which specifies an order used to
760 visit elements in a domain. */
762 static __isl_give isl_union_map
*
763 generate_isl_schedule (scop_p scop
)
765 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
768 isl_union_map
*schedule_isl
=
769 isl_union_map_empty (isl_set_get_space (scop
->context
));
771 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
773 /* Dead code elimination: when the domain of a PBB is empty,
774 don't generate code for the PBB. */
775 if (isl_set_is_empty (pbb
->domain
))
778 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
779 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
780 isl_set_copy (pbb
->domain
));
781 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
783 isl_union_map_union (schedule_isl
,
784 isl_union_map_from_map (bb_schedule
));
789 static __isl_give isl_ast_node
*
790 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
792 /* Generate loop upper bounds that consist of the current loop iterator,
793 an operator (< or <=) and an expression not involving the iterator.
794 If this option is not set, then the current loop iterator may appear several
795 times in the upper bound. See the isl manual for more details. */
796 isl_options_set_ast_build_atomic_upper_bound (scop
->ctx
, true);
798 add_parameters_to_ivs_params (scop
, ip
);
799 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
800 isl_ast_build
*context_isl
= generate_isl_context (scop
);
801 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
803 isl_ast_build_free (context_isl
);
807 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
808 the given SCOP. Return true if code generation succeeded.
810 FIXME: This is not yet a full implementation of the code generator
811 with ISL ASTs. Generation of GIMPLE code has to be completed. */
814 graphite_regenerate_ast_isl (scop_p scop
)
817 sese region
= SCOP_REGION (scop
);
818 ifsese if_region
= NULL
;
819 isl_ast_node
*root_node
;
822 timevar_push (TV_GRAPHITE_CODE_GEN
);
823 graphite_regenerate_error
= false;
824 root_node
= scop_to_isl_ast (scop
, ip
);
826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
828 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
829 print_isl_ast_node (dump_file
, root_node
, scop
->ctx
);
830 fprintf (dump_file
, "\n");
833 recompute_all_dominators ();
836 if_region
= move_sese_in_condition (region
);
837 sese_insert_phis_for_liveouts (region
,
838 if_region
->region
->exit
->src
,
839 if_region
->false_region
->exit
,
840 if_region
->true_region
->exit
);
841 recompute_all_dominators ();
844 context_loop
= SESE_ENTRY (region
)->src
->loop_father
;
846 translate_isl_ast (context_loop
, root_node
, if_region
->true_region
->entry
,
850 recompute_all_dominators ();
853 if (graphite_regenerate_error
)
854 set_ifsese_condition (if_region
, integer_zero_node
);
856 free (if_region
->true_region
);
857 free (if_region
->region
);
860 ivs_params_clear (ip
);
861 isl_ast_node_free (root_node
);
862 timevar_pop (TV_GRAPHITE_CODE_GEN
);
864 return !graphite_regenerate_error
;