1 /* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2018 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/>. */
29 #include "coretypes.h"
36 #include "fold-const.h"
37 #include "gimple-fold.h"
38 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-ssa-operands.h"
44 #include "tree-ssa-propagate.h"
45 #include "tree-pass.h"
47 #include "tree-data-ref.h"
48 #include "tree-ssa-loop-manip.h"
49 #include "tree-scalar-evolution.h"
50 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "tree-into-ssa.h"
53 #include "ssa-iterators.h"
55 #include "gimple-pretty-print.h"
57 #include "value-prof.h"
59 #include "tree-vectorizer.h"
65 : is_parallelizable(false)
67 bool is_parallelizable
;
70 /* IVS_PARAMS maps isl's scattering and parameter identifiers
71 to corresponding trees. */
73 typedef std::map
<isl_id
*, tree
> ivs_params
;
75 /* Free all memory allocated for isl's identifiers. */
77 static void ivs_params_clear (ivs_params
&ip
)
79 std::map
<isl_id
*, tree
>::iterator it
;
80 for (it
= ip
.begin ();
81 it
!= ip
.end (); it
++)
83 isl_id_free (it
->first
);
87 /* Set the "separate" option for the schedule node. */
89 static isl_schedule_node
*
90 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
95 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
98 /* Set the "separate" option unless it is set earlier to another option. */
99 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
100 == isl_ast_loop_default
)
101 return isl_schedule_node_band_member_set_ast_loop_type
102 (node
, 0, isl_ast_loop_separate
);
107 /* Print SCHEDULE under an AST form on file F. */
110 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
112 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
113 isl_ast_build
*context
= isl_ast_build_from_context (set
);
115 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
116 isl_ast_build_free (context
);
117 print_isl_ast (f
, ast
);
118 isl_ast_node_free (ast
);
122 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
124 print_schedule_ast (stderr
, s
, scop
);
135 class translate_isl_ast_to_gimple
138 translate_isl_ast_to_gimple (sese_info_p r
);
139 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
140 edge next_e
, ivs_params
&ip
);
141 edge
translate_isl_ast_node_for (loop_p context_loop
,
142 __isl_keep isl_ast_node
*node
,
143 edge next_e
, ivs_params
&ip
);
144 edge
translate_isl_ast_for_loop (loop_p context_loop
,
145 __isl_keep isl_ast_node
*node_for
,
147 tree type
, tree lb
, tree ub
,
149 edge
translate_isl_ast_node_if (loop_p context_loop
,
150 __isl_keep isl_ast_node
*node
,
151 edge next_e
, ivs_params
&ip
);
152 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
153 edge next_e
, ivs_params
&ip
);
154 edge
translate_isl_ast_node_block (loop_p context_loop
,
155 __isl_keep isl_ast_node
*node
,
156 edge next_e
, ivs_params
&ip
);
157 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
159 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
161 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
163 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
165 tree
gcc_expression_from_isl_expression (tree type
,
166 __isl_take isl_ast_expr
*,
168 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
169 __isl_keep isl_ast_expr
*expr_id
,
171 widest_int
widest_int_from_isl_expr_int (__isl_keep isl_ast_expr
*expr
);
172 tree
gcc_expression_from_isl_expr_int (tree type
,
173 __isl_take isl_ast_expr
*expr
);
174 tree
gcc_expression_from_isl_expr_op (tree type
,
175 __isl_take isl_ast_expr
*expr
,
177 struct loop
*graphite_create_new_loop (edge entry_edge
,
178 __isl_keep isl_ast_node
*node_for
,
179 loop_p outer
, tree type
,
180 tree lb
, tree ub
, ivs_params
&ip
);
181 edge
graphite_create_new_guard (edge entry_edge
,
182 __isl_take isl_ast_expr
*if_cond
,
184 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
185 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
187 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
188 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
190 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
192 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
194 void graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
196 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
198 void set_rename (tree old_name
, tree expr
);
199 void gsi_insert_earliest (gimple_seq seq
);
200 bool codegen_error_p () const { return codegen_error
; }
202 void set_codegen_error ()
204 codegen_error
= true;
205 gcc_assert (! flag_checking
206 || PARAM_VALUE (PARAM_GRAPHITE_ALLOW_CODEGEN_ERRORS
));
209 bool is_constant (tree op
) const
211 return TREE_CODE (op
) == INTEGER_CST
212 || TREE_CODE (op
) == REAL_CST
213 || TREE_CODE (op
) == COMPLEX_CST
214 || TREE_CODE (op
) == VECTOR_CST
;
218 /* The region to be translated. */
221 /* This flag is set when an error occurred during the translation of isl AST
225 /* A vector of all the edges at if_condition merge points. */
226 auto_vec
<edge
, 2> merge_points
;
228 tree graphite_expr_type
;
231 translate_isl_ast_to_gimple::translate_isl_ast_to_gimple (sese_info_p r
)
232 : region (r
), codegen_error (false)
234 /* We always try to use signed 128 bit types, but fall back to smaller types
235 in case a platform does not provide types of these sizes. In the future we
236 should use isl to derive the optimal type for each subexpression. */
237 int max_mode_int_precision
238 = GET_MODE_PRECISION (int_mode_for_size (MAX_FIXED_MODE_SIZE
, 0).require ());
239 int graphite_expr_type_precision
240 = 128 <= max_mode_int_precision
? 128 : max_mode_int_precision
;
242 = build_nonstandard_integer_type (graphite_expr_type_precision
, 0);
245 /* Return the tree variable that corresponds to the given isl ast identifier
246 expression (an isl_ast_expr of type isl_ast_expr_id).
248 FIXME: We should replace blind conversion of id's type with derivation
249 of the optimal type when we get the corresponding isl support. Blindly
250 converting type sizes may be problematic when we switch to smaller
253 tree
translate_isl_ast_to_gimple::
254 gcc_expression_from_isl_ast_expr_id (tree type
,
255 __isl_take isl_ast_expr
*expr_id
,
258 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
259 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
260 std::map
<isl_id
*, tree
>::iterator res
;
261 res
= ip
.find (tmp_isl_id
);
262 isl_id_free (tmp_isl_id
);
263 gcc_assert (res
!= ip
.end () &&
264 "Could not map isl_id to tree expression");
265 isl_ast_expr_free (expr_id
);
266 tree t
= res
->second
;
267 if (useless_type_conversion_p (type
, TREE_TYPE (t
)))
269 return fold_convert (type
, t
);
272 /* Converts an isl_ast_expr_int expression E to a widest_int.
273 Raises a code generation error when the constant doesn't fit. */
275 widest_int
translate_isl_ast_to_gimple::
276 widest_int_from_isl_expr_int (__isl_keep isl_ast_expr
*expr
)
278 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
279 isl_val
*val
= isl_ast_expr_get_val (expr
);
280 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
281 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
282 if (n
> WIDE_INT_MAX_ELTS
283 || isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
286 set_codegen_error ();
289 widest_int wi
= widest_int::from_array (chunks
, n
, true);
290 if (isl_val_is_neg (val
))
296 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
297 type TYPE. Raises a code generation error when the constant doesn't fit. */
299 tree
translate_isl_ast_to_gimple::
300 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
302 widest_int wi
= widest_int_from_isl_expr_int (expr
);
303 isl_ast_expr_free (expr
);
304 if (codegen_error_p ())
306 if (wi::min_precision (wi
, TYPE_SIGN (type
)) > TYPE_PRECISION (type
))
308 set_codegen_error ();
311 return wide_int_to_tree (type
, wi
);
314 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
317 tree
translate_isl_ast_to_gimple::
318 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
320 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
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 isl_ast_expr_free (expr
);
326 /* From our constraint generation we may get modulo operations that
327 we cannot represent explicitely but that are no-ops for TYPE.
329 if ((expr_type
== isl_ast_op_pdiv_r
330 || expr_type
== isl_ast_op_add
)
331 && isl_ast_expr_get_type (arg_expr
) == isl_ast_expr_int
332 && (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr
))
333 >= TYPE_PRECISION (type
)))
335 isl_ast_expr_free (arg_expr
);
336 return tree_lhs_expr
;
339 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
340 if (codegen_error_p ())
346 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
349 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
352 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
355 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
357 case isl_ast_op_pdiv_q
:
358 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
360 case isl_ast_op_zdiv_r
:
361 case isl_ast_op_pdiv_r
:
362 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
364 case isl_ast_op_fdiv_q
:
365 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
368 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
369 tree_lhs_expr
, tree_rhs_expr
);
372 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
375 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
378 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
381 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
384 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
387 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
394 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
397 tree
translate_isl_ast_to_gimple::
398 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
400 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
401 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
402 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
403 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
404 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
405 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
406 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
407 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
408 isl_ast_expr_free (expr
);
410 if (codegen_error_p ())
413 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
416 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
419 tree
translate_isl_ast_to_gimple::
420 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
422 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
423 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
424 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
425 isl_ast_expr_free (expr
);
426 return codegen_error_p () ? NULL_TREE
427 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
430 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
431 to a GCC expression tree of type TYPE. */
433 tree
translate_isl_ast_to_gimple::
434 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
436 enum tree_code op_code
;
437 switch (isl_ast_expr_get_op_type (expr
))
450 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
451 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
453 if (codegen_error_p ())
455 isl_ast_expr_free (expr
);
460 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
462 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
463 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
465 if (codegen_error_p ())
467 isl_ast_expr_free (expr
);
471 res
= fold_build2 (op_code
, type
, res
, t
);
473 isl_ast_expr_free (expr
);
477 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
480 tree
translate_isl_ast_to_gimple::
481 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
484 if (codegen_error_p ())
486 isl_ast_expr_free (expr
);
490 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
491 switch (isl_ast_expr_get_op_type (expr
))
493 /* These isl ast expressions are not supported yet. */
494 case isl_ast_op_error
:
495 case isl_ast_op_call
:
496 case isl_ast_op_and_then
:
497 case isl_ast_op_or_else
:
502 return nary_op_to_tree (type
, expr
, ip
);
508 case isl_ast_op_pdiv_q
:
509 case isl_ast_op_pdiv_r
:
510 case isl_ast_op_fdiv_q
:
511 case isl_ast_op_zdiv_r
:
519 return binary_op_to_tree (type
, expr
, ip
);
521 case isl_ast_op_minus
:
522 return unary_op_to_tree (type
, expr
, ip
);
524 case isl_ast_op_cond
:
525 case isl_ast_op_select
:
526 return ternary_op_to_tree (type
, expr
, ip
);
535 /* Converts an isl AST expression E back to a GCC expression tree of
538 tree
translate_isl_ast_to_gimple::
539 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
542 if (codegen_error_p ())
544 isl_ast_expr_free (expr
);
548 switch (isl_ast_expr_get_type (expr
))
550 case isl_ast_expr_id
:
551 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
553 case isl_ast_expr_int
:
554 return gcc_expression_from_isl_expr_int (type
, expr
);
556 case isl_ast_expr_op
:
557 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
566 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
567 induction variable for the new LOOP. New LOOP is attached to CFG
568 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
569 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
570 isl's scattering name to the induction variable created for the
571 loop of STMT. The new induction variable is inserted in the NEWIVS
572 vector and is of type TYPE. */
574 struct loop
*translate_isl_ast_to_gimple::
575 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
576 loop_p outer
, tree type
, tree lb
, tree ub
,
579 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
580 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
582 /* To fail code generation, we generate wrong code until we discard it. */
583 if (codegen_error_p ())
584 stride
= integer_zero_node
;
586 tree ivvar
= create_tmp_var (type
, "graphite_IV");
587 tree iv
, iv_after_increment
;
588 loop_p loop
= create_empty_loop_on_edge
589 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
590 outer
? outer
: entry_edge
->src
->loop_father
);
592 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
593 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
594 std::map
<isl_id
*, tree
>::iterator res
;
597 isl_id_free (res
->first
);
599 isl_ast_expr_free (for_iterator
);
603 /* Create the loop for a isl_ast_node_for.
605 - NEXT_E is the edge where new generated code should be attached. */
607 edge
translate_isl_ast_to_gimple::
608 translate_isl_ast_for_loop (loop_p context_loop
,
609 __isl_keep isl_ast_node
*node_for
, edge next_e
,
610 tree type
, tree lb
, tree ub
,
613 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
614 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
616 edge last_e
= single_exit (loop
);
617 edge to_body
= single_succ_edge (loop
->header
);
618 basic_block after
= to_body
->dest
;
620 /* Translate the body of the loop. */
621 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
622 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
623 isl_ast_node_free (for_body
);
625 /* Early return if we failed to translate loop body. */
626 if (!next_e
|| codegen_error_p ())
629 if (next_e
->dest
!= after
)
630 redirect_edge_succ_nodup (next_e
, after
);
631 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
633 if (flag_loop_parallelize_all
)
635 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
637 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
638 loop
->can_be_parallel
= for_info
->is_parallelizable
;
646 /* We use this function to get the upper bound because of the form,
647 which is used by isl to represent loops:
649 for (iterator = init; cond; iterator += inc)
657 The loop condition is an arbitrary expression, which contains the
658 current loop iterator.
660 (e.g. iterator + 3 < B && C > iterator + A)
662 We have to know the upper bound of the iterator to generate a loop
663 in Gimple form. It can be obtained from the special representation
664 of the loop condition, which is generated by isl,
665 if the ast_build_atomic_upper_bound option is set. In this case,
666 isl generates a loop condition that consists of the current loop
667 iterator, + an operator (< or <=) and an expression not involving
668 the iterator, which is processed and returned by this function.
670 (e.g iterator <= upper-bound-expression-without-iterator) */
672 static __isl_give isl_ast_expr
*
673 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
675 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
676 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
677 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
679 switch (isl_ast_expr_get_op_type (for_cond
))
682 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
687 /* (iterator < ub) => (iterator <= ub - 1). */
689 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
690 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
691 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
698 isl_ast_expr_free (for_cond
);
702 /* Translates an isl_ast_node_for to Gimple. */
704 edge
translate_isl_ast_to_gimple::
705 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
706 edge next_e
, ivs_params
&ip
)
708 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
709 tree type
= graphite_expr_type
;
711 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
712 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
713 /* To fail code generation, we generate wrong code until we discard it. */
714 if (codegen_error_p ())
715 lb
= integer_zero_node
;
717 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
718 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
719 /* To fail code generation, we generate wrong code until we discard it. */
720 if (codegen_error_p ())
721 ub
= integer_zero_node
;
723 edge last_e
= single_succ_edge (split_edge (next_e
));
725 /* Compensate for the fact that we emit a do { } while loop from
727 ??? We often miss constraints on niter because the SESE region
728 doesn't cover loop header copies. Ideally we'd add constraints
729 for all relevant dominating conditions. */
730 if (TREE_CODE (lb
) == INTEGER_CST
&& TREE_CODE (ub
) == INTEGER_CST
731 && tree_int_cst_compare (lb
, ub
) <= 0)
735 tree one
= build_one_cst (POINTER_TYPE_P (type
) ? sizetype
: type
);
736 /* Adding +1 and using LT_EXPR helps with loop latches that have a
737 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
738 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
739 is true, even if we do not want this. However lb < ub + 1 is false,
741 tree ub_one
= fold_build2 (POINTER_TYPE_P (type
)
742 ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
743 type
, unshare_expr (ub
), one
);
744 create_empty_if_region_on_edge (next_e
,
745 fold_build2 (LT_EXPR
, boolean_type_node
,
746 unshare_expr (lb
), ub_one
));
747 next_e
= get_true_edge_from_guard_bb (next_e
->dest
);
750 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
755 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
756 variables of the loops around GBB in SESE.
758 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
759 chrec, we could consider using a map<int, tree> that maps loop ids to the
760 corresponding tree expressions. */
762 void translate_isl_ast_to_gimple::
763 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
764 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
767 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
768 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
770 isl_ast_expr
*arg_expr
;
771 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
773 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
774 tree type
= graphite_expr_type
;
775 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
777 /* To fail code generation, we generate wrong code until we discard it. */
778 if (codegen_error_p ())
779 t
= integer_zero_node
;
781 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
782 iv_map
[old_loop
->num
] = t
;
786 /* Translates an isl_ast_node_user to Gimple.
788 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
790 edge
translate_isl_ast_to_gimple::
791 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
792 edge next_e
, ivs_params
&ip
)
794 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
796 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
797 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
798 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
800 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
801 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
804 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
806 isl_ast_expr_free (name_expr
);
807 isl_id_free (name_id
);
809 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
810 "The entry block should not even appear within a scop");
812 const int nb_loops
= number_of_loops (cfun
);
814 iv_map
.create (nb_loops
);
815 iv_map
.safe_grow_cleared (nb_loops
);
817 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
818 isl_ast_expr_free (user_expr
);
820 basic_block old_bb
= GBB_BB (gbb
);
821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
824 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
825 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
826 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
829 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
833 if (codegen_error_p ())
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
838 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
839 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
845 /* Translates an isl_ast_node_block to Gimple. */
847 edge
translate_isl_ast_to_gimple::
848 translate_isl_ast_node_block (loop_p context_loop
,
849 __isl_keep isl_ast_node
*node
,
850 edge next_e
, ivs_params
&ip
)
852 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
853 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
855 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
857 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
858 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
859 isl_ast_node_free (tmp_node
);
861 isl_ast_node_list_free (node_list
);
865 /* Creates a new if region corresponding to isl's cond. */
867 edge
translate_isl_ast_to_gimple::
868 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
871 tree type
= graphite_expr_type
;
872 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
874 /* To fail code generation, we generate wrong code until we discard it. */
875 if (codegen_error_p ())
876 cond_expr
= integer_zero_node
;
878 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
882 /* Translates an isl_ast_node_if to Gimple. */
884 edge
translate_isl_ast_to_gimple::
885 translate_isl_ast_node_if (loop_p context_loop
,
886 __isl_keep isl_ast_node
*node
,
887 edge next_e
, ivs_params
&ip
)
889 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
890 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
891 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
892 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
893 merge_points
.safe_push (last_e
);
895 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
896 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
897 isl_ast_node_free (then_node
);
899 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
900 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
901 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
902 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
904 isl_ast_node_free (else_node
);
908 /* Translates an isl AST node NODE to GCC representation in the
909 context of a SESE. */
911 edge
translate_isl_ast_to_gimple::
912 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
913 edge next_e
, ivs_params
&ip
)
915 if (codegen_error_p ())
918 switch (isl_ast_node_get_type (node
))
920 case isl_ast_node_error
:
923 case isl_ast_node_for
:
924 return translate_isl_ast_node_for (context_loop
, node
,
927 case isl_ast_node_if
:
928 return translate_isl_ast_node_if (context_loop
, node
,
931 case isl_ast_node_user
:
932 return translate_isl_ast_node_user (node
, next_e
, ip
);
934 case isl_ast_node_block
:
935 return translate_isl_ast_node_block (context_loop
, node
,
938 case isl_ast_node_mark
:
940 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
941 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
942 isl_ast_node_free (n
);
951 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
952 When OLD_NAME and EXPR are the same we assert. */
954 void translate_isl_ast_to_gimple::
955 set_rename (tree old_name
, tree expr
)
959 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
960 print_generic_expr (dump_file
, old_name
);
961 fprintf (dump_file
, ", new decl = ");
962 print_generic_expr (dump_file
, expr
);
963 fprintf (dump_file
, "\n");
965 bool res
= region
->rename_map
->put (old_name
, expr
);
969 /* Return an iterator to the instructions comes last in the execution order.
970 Either GSI1 and GSI2 should belong to the same basic block or one of their
971 respective basic blocks should dominate the other. */
974 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
976 basic_block bb1
= gsi_bb (gsi1
);
977 basic_block bb2
= gsi_bb (gsi2
);
979 /* Find the iterator which is the latest. */
982 gimple
*stmt1
= gsi_stmt (gsi1
);
983 gimple
*stmt2
= gsi_stmt (gsi2
);
985 if (stmt1
!= NULL
&& stmt2
!= NULL
)
987 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
988 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
990 if (is_phi1
!= is_phi2
)
991 return is_phi1
? gsi2
: gsi1
;
994 /* For empty basic blocks gsis point to the end of the sequence. Since
995 there is no operator== defined for gimple_stmt_iterator and for gsis
996 not pointing to a valid statement gsi_next would assert. */
997 gimple_stmt_iterator gsi
= gsi1
;
999 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1002 } while (!gsi_end_p (gsi
));
1007 /* Find the basic block closest to the basic block which defines stmt. */
1008 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1011 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1015 /* Insert each statement from SEQ at its earliest insertion p. */
1017 void translate_isl_ast_to_gimple::
1018 gsi_insert_earliest (gimple_seq seq
)
1020 update_modified_stmts (seq
);
1021 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1022 basic_block begin_bb
= get_entry_bb (codegen_region
);
1024 /* Inserting the gimple statements in a vector because gimple_seq behave
1025 in strage ways when inserting the stmts from it into different basic
1026 blocks one at a time. */
1027 auto_vec
<gimple
*, 3> stmts
;
1028 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1030 stmts
.safe_push (gsi_stmt (gsi
));
1034 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1036 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1037 gimple_stmt_iterator gsi_def_stmt
= gsi_start_nondebug_bb (begin_bb
);
1039 use_operand_p use_p
;
1040 ssa_op_iter op_iter
;
1041 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1043 /* Iterator to the current def of use_p. For function parameters or
1044 anything where def is not found, insert at the beginning of the
1045 generated region. */
1046 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1048 tree op
= USE_FROM_PTR (use_p
);
1049 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1050 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1051 gsi_stmt
= gsi_for_stmt (stmt
);
1053 /* For region parameters, insert at the beginning of the generated
1055 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1056 gsi_stmt
= gsi_def_stmt
;
1058 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1061 if (!gsi_stmt (gsi_def_stmt
))
1063 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1064 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1066 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1068 gimple_stmt_iterator bsi
1069 = gsi_start_nondebug_bb (gsi_bb (gsi_def_stmt
));
1070 /* Insert right after the PHI statements. */
1071 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1074 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1078 fprintf (dump_file
, "[codegen] inserting statement in BB %d: ",
1079 gimple_bb (use_stmt
)->index
);
1080 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1085 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1086 scalar evolution around LOOP. */
1088 tree
translate_isl_ast_to_gimple::
1089 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1092 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1094 /* At this point we should know the exact scev for each
1095 scalar SSA_NAME used in the scop: all the other scalar
1096 SSA_NAMEs should have been translated out of SSA using
1097 arrays with one element. */
1099 if (chrec_contains_undetermined (scev
))
1101 set_codegen_error ();
1102 return build_zero_cst (TREE_TYPE (old_name
));
1105 new_expr
= chrec_apply_map (scev
, iv_map
);
1107 /* The apply should produce an expression tree containing
1108 the uses of the new induction variables. We should be
1109 able to use new_expr instead of the old_name in the newly
1110 generated loop nest. */
1111 if (chrec_contains_undetermined (new_expr
)
1112 || tree_contains_chrecs (new_expr
, NULL
))
1114 set_codegen_error ();
1115 return build_zero_cst (TREE_TYPE (old_name
));
1118 /* Replace the old_name with the new_expr. */
1119 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1124 /* Return true if STMT should be copied from region to the new code-generated
1125 region. LABELs, CONDITIONS, induction-variables and region parameters need
1129 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
1131 /* Do not copy labels or conditions. */
1132 if (gimple_code (stmt
) == GIMPLE_LABEL
1133 || gimple_code (stmt
) == GIMPLE_COND
)
1137 /* Do not copy induction variables. */
1138 if (is_gimple_assign (stmt
)
1139 && (lhs
= gimple_assign_lhs (stmt
))
1140 && TREE_CODE (lhs
) == SSA_NAME
1141 && scev_analyzable_p (lhs
, region
->region
)
1142 /* But to code-generate liveouts - liveout PHI generation is
1143 in generic sese.c code that cannot do code generation. */
1144 && ! bitmap_bit_p (region
->liveout
, SSA_NAME_VERSION (lhs
)))
1150 /* Duplicates the statements of basic block BB into basic block NEW_BB
1151 and compute the new induction variables according to the IV_MAP. */
1153 void translate_isl_ast_to_gimple::
1154 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
1157 /* Iterator poining to the place where new statement (s) will be inserted. */
1158 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
1160 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1163 gimple
*stmt
= gsi_stmt (gsi
);
1164 if (!should_copy_to_new_region (stmt
, region
))
1167 /* Create a new copy of STMT and duplicate STMT's virtual
1169 gimple
*copy
= gimple_copy (stmt
);
1171 /* Rather than not copying debug stmts we reset them.
1172 ??? Where we can rewrite uses without inserting new
1173 stmts we could simply do that. */
1174 if (is_gimple_debug (copy
))
1176 if (gimple_debug_bind_p (copy
))
1177 gimple_debug_bind_reset_value (copy
);
1178 else if (gimple_debug_source_bind_p (copy
)
1179 || gimple_debug_nonbind_marker_p (copy
))
1185 maybe_duplicate_eh_stmt (copy
, stmt
);
1186 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1188 /* Crete new names for each def in the copied stmt. */
1189 def_operand_p def_p
;
1190 ssa_op_iter op_iter
;
1191 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1193 tree old_name
= DEF_FROM_PTR (def_p
);
1194 create_new_def_for (old_name
, copy
, def_p
);
1197 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1200 fprintf (dump_file
, "[codegen] inserting statement: ");
1201 print_gimple_stmt (dump_file
, copy
, 0);
1204 /* For each SCEV analyzable SSA_NAME, rename their usage. */
1206 use_operand_p use_p
;
1207 if (!is_gimple_debug (copy
))
1209 bool changed
= false;
1210 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
1212 tree old_name
= USE_FROM_PTR (use_p
);
1214 if (TREE_CODE (old_name
) != SSA_NAME
1215 || SSA_NAME_IS_DEFAULT_DEF (old_name
)
1216 || ! scev_analyzable_p (old_name
, region
->region
))
1219 gimple_seq stmts
= NULL
;
1220 tree new_name
= get_rename_from_scev (old_name
, &stmts
,
1221 bb
->loop_father
, iv_map
);
1222 if (! codegen_error_p ())
1223 gsi_insert_earliest (stmts
);
1224 replace_exp (use_p
, new_name
);
1228 fold_stmt_inplace (&gsi_tgt
);
1236 /* Copies BB and includes in the copied BB all the statements that can
1237 be reached following the use-def chains from the memory accesses,
1238 and returns the next edge following this new block. */
1240 edge
translate_isl_ast_to_gimple::
1241 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
1243 basic_block new_bb
= split_edge (next_e
);
1244 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
1245 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1248 gphi
*phi
= psi
.phi ();
1249 tree res
= gimple_phi_result (phi
);
1250 if (virtual_operand_p (res
)
1251 || scev_analyzable_p (res
, region
->region
))
1255 tree
*rename
= region
->rename_map
->get (res
);
1258 new_phi_def
= create_tmp_reg (TREE_TYPE (res
));
1259 set_rename (res
, new_phi_def
);
1262 new_phi_def
= *rename
;
1264 gassign
*ass
= gimple_build_assign (NULL_TREE
, new_phi_def
);
1265 create_new_def_for (res
, ass
, NULL
);
1266 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1269 graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
);
1271 /* Insert out-of SSA copies on the original BB outgoing edges. */
1272 gsi_tgt
= gsi_last_bb (new_bb
);
1273 basic_block bb_for_succs
= bb
;
1274 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1275 && bb_in_sese_p (bb_for_succs
, region
->region
)
1276 && sese_trivially_empty_bb_p (bb_for_succs
))
1277 bb_for_succs
= NULL
;
1278 while (bb_for_succs
)
1280 basic_block latch
= NULL
;
1283 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1285 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1288 gphi
*phi
= psi
.phi ();
1289 tree res
= gimple_phi_result (phi
);
1290 if (virtual_operand_p (res
)
1291 || scev_analyzable_p (res
, region
->region
))
1295 tree
*rename
= region
->rename_map
->get (res
);
1298 new_phi_def
= create_tmp_reg (TREE_TYPE (res
));
1299 set_rename (res
, new_phi_def
);
1302 new_phi_def
= *rename
;
1304 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1305 if (TREE_CODE (arg
) == SSA_NAME
1306 && scev_analyzable_p (arg
, region
->region
))
1308 gimple_seq stmts
= NULL
;
1309 tree new_name
= get_rename_from_scev (arg
, &stmts
,
1312 if (! codegen_error_p ())
1313 gsi_insert_earliest (stmts
);
1316 gassign
*ass
= gimple_build_assign (new_phi_def
, arg
);
1317 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1319 if (e
->dest
== bb_for_succs
->loop_father
->latch
1320 && bb_in_sese_p (e
->dest
, region
->region
)
1321 && sese_trivially_empty_bb_p (e
->dest
))
1324 bb_for_succs
= latch
;
1327 return single_succ_edge (new_bb
);
1330 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
1332 void translate_isl_ast_to_gimple::
1333 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
1335 sese_info_p region
= scop
->scop_info
;
1336 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
1337 gcc_assert (nb_parameters
== sese_nb_params (region
));
1340 FOR_EACH_VEC_ELT (region
->params
, i
, param
)
1342 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
1349 /* Generates a build, which specifies the constraints on the parameters. */
1351 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
1352 generate_isl_context (scop_p scop
)
1354 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
1355 return isl_ast_build_from_context (context_isl
);
1358 /* This method is executed before the construction of a for node. */
1360 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1362 isl_union_map
*dependences
= (isl_union_map
*) user
;
1363 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1364 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1365 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1366 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1367 for_info
->is_parallelizable
=
1368 !carries_deps (schedule
, dependences
, dimension
);
1369 isl_union_map_free (schedule
);
1370 isl_space_free (schedule_space
);
1371 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1375 /* Generate isl AST from schedule of SCOP. */
1377 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
1378 scop_to_isl_ast (scop_p scop
)
1380 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1381 int old_max_operations
= isl_ctx_get_max_operations (scop
->isl_context
);
1382 int max_operations
= PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS
);
1384 isl_ctx_set_max_operations (scop
->isl_context
, max_operations
);
1385 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1387 gcc_assert (scop
->transformed_schedule
);
1389 /* Set the separate option to reduce control flow overhead. */
1390 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
1391 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
1392 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1394 if (flag_loop_parallelize_all
)
1396 scop_get_dependences (scop
);
1398 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1402 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
1403 (context_isl
, schedule
);
1404 isl_ast_build_free (context_isl
);
1406 isl_options_set_on_error (scop
->isl_context
, old_err
);
1407 isl_ctx_reset_operations (scop
->isl_context
);
1408 isl_ctx_set_max_operations (scop
->isl_context
, old_max_operations
);
1409 if (isl_ctx_last_error (scop
->isl_context
) != isl_error_none
)
1411 location_t loc
= find_loop_location
1412 (scop
->scop_info
->region
.entry
->dest
->loop_father
);
1413 if (isl_ctx_last_error (scop
->isl_context
) == isl_error_quota
)
1414 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1415 "loop nest not optimized, AST generation timed out "
1416 "after %d operations [--param max-isl-operations]\n",
1419 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1420 "loop nest not optimized, ISL AST generation "
1421 "signalled an error\n");
1422 isl_ast_node_free (ast_isl
);
1429 /* Generate out-of-SSA copies for the entry edge FALSE_ENTRY/TRUE_ENTRY
1433 generate_entry_out_of_ssa_copies (edge false_entry
,
1437 gimple_stmt_iterator gsi_tgt
= gsi_start_bb (true_entry
->dest
);
1438 for (gphi_iterator psi
= gsi_start_phis (false_entry
->dest
);
1439 !gsi_end_p (psi
); gsi_next (&psi
))
1441 gphi
*phi
= psi
.phi ();
1442 tree res
= gimple_phi_result (phi
);
1443 if (virtual_operand_p (res
))
1445 /* When there's no out-of-SSA var registered do not bother
1447 tree
*rename
= region
->rename_map
->get (res
);
1450 tree new_phi_def
= *rename
;
1451 gassign
*ass
= gimple_build_assign (new_phi_def
,
1452 PHI_ARG_DEF_FROM_EDGE (phi
,
1454 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1458 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
1459 Return true if code generation succeeded. */
1462 graphite_regenerate_ast_isl (scop_p scop
)
1464 sese_info_p region
= scop
->scop_info
;
1465 translate_isl_ast_to_gimple
t (region
);
1467 ifsese if_region
= NULL
;
1468 isl_ast_node
*root_node
;
1471 timevar_push (TV_GRAPHITE_CODE_GEN
);
1472 t
.add_parameters_to_ivs_params (scop
, ip
);
1473 root_node
= t
.scop_to_isl_ast (scop
);
1476 ivs_params_clear (ip
);
1477 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1483 fprintf (dump_file
, "[scheduler] original schedule:\n");
1484 print_isl_schedule (dump_file
, scop
->original_schedule
);
1485 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
1486 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
1488 fprintf (dump_file
, "[scheduler] original ast:\n");
1489 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
1490 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
1491 print_isl_ast (dump_file
, root_node
);
1494 if_region
= move_sese_in_condition (region
);
1495 region
->if_region
= if_region
;
1497 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
1498 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
1499 basic_block bb
= split_edge (e
);
1501 /* Update the true_region exit edge. */
1502 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
1504 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
1505 if (! t
.codegen_error_p ())
1507 generate_entry_out_of_ssa_copies (if_region
->false_region
->region
.entry
,
1508 if_region
->true_region
->region
.entry
,
1510 sese_insert_phis_for_liveouts (region
,
1511 if_region
->region
->region
.exit
->src
,
1512 if_region
->false_region
->region
.exit
,
1513 if_region
->true_region
->region
.exit
);
1515 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
1518 if (t
.codegen_error_p ())
1520 location_t loc
= find_loop_location
1521 (scop
->scop_info
->region
.entry
->dest
->loop_father
);
1522 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1523 "loop nest not optimized, code generation error\n");
1525 /* Remove the unreachable region. */
1526 remove_edge_and_dominated_blocks (if_region
->true_region
->region
.entry
);
1527 basic_block ifb
= if_region
->false_region
->region
.entry
->src
;
1528 gimple_stmt_iterator gsi
= gsi_last_bb (ifb
);
1529 gsi_remove (&gsi
, true);
1530 if_region
->false_region
->region
.entry
->flags
&= ~EDGE_FALSE_VALUE
;
1531 if_region
->false_region
->region
.entry
->flags
|= EDGE_FALLTHRU
;
1532 /* remove_edge_and_dominated_blocks marks loops for removal but
1533 doesn't actually remove them (fix that...). */
1535 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1540 /* We are delaying SSA update to after code-generating all SCOPs.
1541 This is because we analyzed DRs and parameters on the unmodified
1542 IL and thus rely on SSA update to pick up new dominating definitions
1543 from for example SESE liveout PHIs. This is also for efficiency
1544 as SSA update does work depending on the size of the function. */
1546 free (if_region
->true_region
);
1547 free (if_region
->region
);
1550 ivs_params_clear (ip
);
1551 isl_ast_node_free (root_node
);
1552 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1554 return !t
.codegen_error_p ();
1557 #endif /* HAVE_isl */