1 /* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2017 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 && isl_ast_expr_get_type (arg_expr
) == isl_ast_expr_int
331 && (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr
))
332 >= TYPE_PRECISION (type
)))
334 isl_ast_expr_free (arg_expr
);
335 return tree_lhs_expr
;
338 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
339 if (codegen_error_p ())
345 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
348 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
351 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
354 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
356 case isl_ast_op_pdiv_q
:
357 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
359 case isl_ast_op_zdiv_r
:
360 case isl_ast_op_pdiv_r
:
361 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
363 case isl_ast_op_fdiv_q
:
364 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
367 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
368 tree_lhs_expr
, tree_rhs_expr
);
371 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
374 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
377 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
380 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
383 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
386 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
393 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
396 tree
translate_isl_ast_to_gimple::
397 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
399 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
400 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
401 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
402 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
403 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
404 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
405 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
406 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
407 isl_ast_expr_free (expr
);
409 if (codegen_error_p ())
412 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
415 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
418 tree
translate_isl_ast_to_gimple::
419 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
421 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
422 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
423 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
424 isl_ast_expr_free (expr
);
425 return codegen_error_p () ? NULL_TREE
426 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
429 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
430 to a GCC expression tree of type TYPE. */
432 tree
translate_isl_ast_to_gimple::
433 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
435 enum tree_code op_code
;
436 switch (isl_ast_expr_get_op_type (expr
))
449 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
450 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
452 if (codegen_error_p ())
454 isl_ast_expr_free (expr
);
459 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
461 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
462 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
464 if (codegen_error_p ())
466 isl_ast_expr_free (expr
);
470 res
= fold_build2 (op_code
, type
, res
, t
);
472 isl_ast_expr_free (expr
);
476 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
479 tree
translate_isl_ast_to_gimple::
480 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
483 if (codegen_error_p ())
485 isl_ast_expr_free (expr
);
489 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
490 switch (isl_ast_expr_get_op_type (expr
))
492 /* These isl ast expressions are not supported yet. */
493 case isl_ast_op_error
:
494 case isl_ast_op_call
:
495 case isl_ast_op_and_then
:
496 case isl_ast_op_or_else
:
501 return nary_op_to_tree (type
, expr
, ip
);
507 case isl_ast_op_pdiv_q
:
508 case isl_ast_op_pdiv_r
:
509 case isl_ast_op_fdiv_q
:
510 case isl_ast_op_zdiv_r
:
518 return binary_op_to_tree (type
, expr
, ip
);
520 case isl_ast_op_minus
:
521 return unary_op_to_tree (type
, expr
, ip
);
523 case isl_ast_op_cond
:
524 case isl_ast_op_select
:
525 return ternary_op_to_tree (type
, expr
, ip
);
534 /* Converts an isl AST expression E back to a GCC expression tree of
537 tree
translate_isl_ast_to_gimple::
538 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
541 if (codegen_error_p ())
543 isl_ast_expr_free (expr
);
547 switch (isl_ast_expr_get_type (expr
))
549 case isl_ast_expr_id
:
550 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
552 case isl_ast_expr_int
:
553 return gcc_expression_from_isl_expr_int (type
, expr
);
555 case isl_ast_expr_op
:
556 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
565 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
566 induction variable for the new LOOP. New LOOP is attached to CFG
567 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
568 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
569 isl's scattering name to the induction variable created for the
570 loop of STMT. The new induction variable is inserted in the NEWIVS
571 vector and is of type TYPE. */
573 struct loop
*translate_isl_ast_to_gimple::
574 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
575 loop_p outer
, tree type
, tree lb
, tree ub
,
578 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
579 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
581 /* To fail code generation, we generate wrong code until we discard it. */
582 if (codegen_error_p ())
583 stride
= integer_zero_node
;
585 tree ivvar
= create_tmp_var (type
, "graphite_IV");
586 tree iv
, iv_after_increment
;
587 loop_p loop
= create_empty_loop_on_edge
588 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
589 outer
? outer
: entry_edge
->src
->loop_father
);
591 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
592 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
593 std::map
<isl_id
*, tree
>::iterator res
;
596 isl_id_free (res
->first
);
598 isl_ast_expr_free (for_iterator
);
602 /* Create the loop for a isl_ast_node_for.
604 - NEXT_E is the edge where new generated code should be attached. */
606 edge
translate_isl_ast_to_gimple::
607 translate_isl_ast_for_loop (loop_p context_loop
,
608 __isl_keep isl_ast_node
*node_for
, edge next_e
,
609 tree type
, tree lb
, tree ub
,
612 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
613 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
615 edge last_e
= single_exit (loop
);
616 edge to_body
= single_succ_edge (loop
->header
);
617 basic_block after
= to_body
->dest
;
619 /* Translate the body of the loop. */
620 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
621 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
622 isl_ast_node_free (for_body
);
624 /* Early return if we failed to translate loop body. */
625 if (!next_e
|| codegen_error_p ())
628 if (next_e
->dest
!= after
)
629 redirect_edge_succ_nodup (next_e
, after
);
630 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
632 if (flag_loop_parallelize_all
)
634 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
636 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
637 loop
->can_be_parallel
= for_info
->is_parallelizable
;
645 /* We use this function to get the upper bound because of the form,
646 which is used by isl to represent loops:
648 for (iterator = init; cond; iterator += inc)
656 The loop condition is an arbitrary expression, which contains the
657 current loop iterator.
659 (e.g. iterator + 3 < B && C > iterator + A)
661 We have to know the upper bound of the iterator to generate a loop
662 in Gimple form. It can be obtained from the special representation
663 of the loop condition, which is generated by isl,
664 if the ast_build_atomic_upper_bound option is set. In this case,
665 isl generates a loop condition that consists of the current loop
666 iterator, + an operator (< or <=) and an expression not involving
667 the iterator, which is processed and returned by this function.
669 (e.g iterator <= upper-bound-expression-without-iterator) */
671 static __isl_give isl_ast_expr
*
672 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
674 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
675 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
676 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
678 switch (isl_ast_expr_get_op_type (for_cond
))
681 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
686 /* (iterator < ub) => (iterator <= ub - 1). */
688 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
689 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
690 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
697 isl_ast_expr_free (for_cond
);
701 /* Translates an isl_ast_node_for to Gimple. */
703 edge
translate_isl_ast_to_gimple::
704 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
705 edge next_e
, ivs_params
&ip
)
707 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
708 tree type
= graphite_expr_type
;
710 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
711 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
712 /* To fail code generation, we generate wrong code until we discard it. */
713 if (codegen_error_p ())
714 lb
= integer_zero_node
;
716 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
717 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
718 /* To fail code generation, we generate wrong code until we discard it. */
719 if (codegen_error_p ())
720 ub
= integer_zero_node
;
722 edge last_e
= single_succ_edge (split_edge (next_e
));
724 /* Compensate for the fact that we emit a do { } while loop from
726 ??? We often miss constraints on niter because the SESE region
727 doesn't cover loop header copies. Ideally we'd add constraints
728 for all relevant dominating conditions. */
729 if (TREE_CODE (lb
) == INTEGER_CST
&& TREE_CODE (ub
) == INTEGER_CST
730 && tree_int_cst_compare (lb
, ub
) <= 0)
734 tree one
= build_one_cst (POINTER_TYPE_P (type
) ? sizetype
: type
);
735 /* Adding +1 and using LT_EXPR helps with loop latches that have a
736 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
737 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
738 is true, even if we do not want this. However lb < ub + 1 is false,
740 tree ub_one
= fold_build2 (POINTER_TYPE_P (type
)
741 ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
743 create_empty_if_region_on_edge (next_e
,
744 fold_build2 (LT_EXPR
, boolean_type_node
,
746 next_e
= get_true_edge_from_guard_bb (next_e
->dest
);
749 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
754 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
755 variables of the loops around GBB in SESE.
757 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
758 chrec, we could consider using a map<int, tree> that maps loop ids to the
759 corresponding tree expressions. */
761 void translate_isl_ast_to_gimple::
762 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
763 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
766 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
767 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
769 isl_ast_expr
*arg_expr
;
770 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
772 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
773 tree type
= graphite_expr_type
;
774 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
776 /* To fail code generation, we generate wrong code until we discard it. */
777 if (codegen_error_p ())
778 t
= integer_zero_node
;
780 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
781 iv_map
[old_loop
->num
] = t
;
785 /* Translates an isl_ast_node_user to Gimple.
787 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
789 edge
translate_isl_ast_to_gimple::
790 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
791 edge next_e
, ivs_params
&ip
)
793 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
795 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
796 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
797 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
799 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
800 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
803 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
805 isl_ast_expr_free (name_expr
);
806 isl_id_free (name_id
);
808 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
809 "The entry block should not even appear within a scop");
811 const int nb_loops
= number_of_loops (cfun
);
813 iv_map
.create (nb_loops
);
814 iv_map
.safe_grow_cleared (nb_loops
);
816 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
817 isl_ast_expr_free (user_expr
);
819 basic_block old_bb
= GBB_BB (gbb
);
820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
823 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
824 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
825 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
828 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
832 if (codegen_error_p ())
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
838 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
844 /* Translates an isl_ast_node_block to Gimple. */
846 edge
translate_isl_ast_to_gimple::
847 translate_isl_ast_node_block (loop_p context_loop
,
848 __isl_keep isl_ast_node
*node
,
849 edge next_e
, ivs_params
&ip
)
851 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
852 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
854 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
856 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
857 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
858 isl_ast_node_free (tmp_node
);
860 isl_ast_node_list_free (node_list
);
864 /* Creates a new if region corresponding to isl's cond. */
866 edge
translate_isl_ast_to_gimple::
867 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
870 tree type
= graphite_expr_type
;
871 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
873 /* To fail code generation, we generate wrong code until we discard it. */
874 if (codegen_error_p ())
875 cond_expr
= integer_zero_node
;
877 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
881 /* Translates an isl_ast_node_if to Gimple. */
883 edge
translate_isl_ast_to_gimple::
884 translate_isl_ast_node_if (loop_p context_loop
,
885 __isl_keep isl_ast_node
*node
,
886 edge next_e
, ivs_params
&ip
)
888 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
889 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
890 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
891 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
892 merge_points
.safe_push (last_e
);
894 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
895 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
896 isl_ast_node_free (then_node
);
898 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
899 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
900 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
901 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
903 isl_ast_node_free (else_node
);
907 /* Translates an isl AST node NODE to GCC representation in the
908 context of a SESE. */
910 edge
translate_isl_ast_to_gimple::
911 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
912 edge next_e
, ivs_params
&ip
)
914 if (codegen_error_p ())
917 switch (isl_ast_node_get_type (node
))
919 case isl_ast_node_error
:
922 case isl_ast_node_for
:
923 return translate_isl_ast_node_for (context_loop
, node
,
926 case isl_ast_node_if
:
927 return translate_isl_ast_node_if (context_loop
, node
,
930 case isl_ast_node_user
:
931 return translate_isl_ast_node_user (node
, next_e
, ip
);
933 case isl_ast_node_block
:
934 return translate_isl_ast_node_block (context_loop
, node
,
937 case isl_ast_node_mark
:
939 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
940 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
941 isl_ast_node_free (n
);
950 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
951 When OLD_NAME and EXPR are the same we assert. */
953 void translate_isl_ast_to_gimple::
954 set_rename (tree old_name
, tree expr
)
958 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
959 print_generic_expr (dump_file
, old_name
);
960 fprintf (dump_file
, ", new decl = ");
961 print_generic_expr (dump_file
, expr
);
962 fprintf (dump_file
, "\n");
964 bool res
= region
->rename_map
->put (old_name
, expr
);
968 /* Return an iterator to the instructions comes last in the execution order.
969 Either GSI1 and GSI2 should belong to the same basic block or one of their
970 respective basic blocks should dominate the other. */
973 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
975 basic_block bb1
= gsi_bb (gsi1
);
976 basic_block bb2
= gsi_bb (gsi2
);
978 /* Find the iterator which is the latest. */
981 gimple
*stmt1
= gsi_stmt (gsi1
);
982 gimple
*stmt2
= gsi_stmt (gsi2
);
984 if (stmt1
!= NULL
&& stmt2
!= NULL
)
986 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
987 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
989 if (is_phi1
!= is_phi2
)
990 return is_phi1
? gsi2
: gsi1
;
993 /* For empty basic blocks gsis point to the end of the sequence. Since
994 there is no operator== defined for gimple_stmt_iterator and for gsis
995 not pointing to a valid statement gsi_next would assert. */
996 gimple_stmt_iterator gsi
= gsi1
;
998 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1001 } while (!gsi_end_p (gsi
));
1006 /* Find the basic block closest to the basic block which defines stmt. */
1007 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1010 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1014 /* Insert each statement from SEQ at its earliest insertion p. */
1016 void translate_isl_ast_to_gimple::
1017 gsi_insert_earliest (gimple_seq seq
)
1019 update_modified_stmts (seq
);
1020 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1021 basic_block begin_bb
= get_entry_bb (codegen_region
);
1023 /* Inserting the gimple statements in a vector because gimple_seq behave
1024 in strage ways when inserting the stmts from it into different basic
1025 blocks one at a time. */
1026 auto_vec
<gimple
*, 3> stmts
;
1027 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1029 stmts
.safe_push (gsi_stmt (gsi
));
1033 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1035 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1036 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1038 use_operand_p use_p
;
1039 ssa_op_iter op_iter
;
1040 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1042 /* Iterator to the current def of use_p. For function parameters or
1043 anything where def is not found, insert at the beginning of the
1044 generated region. */
1045 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1047 tree op
= USE_FROM_PTR (use_p
);
1048 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1049 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1050 gsi_stmt
= gsi_for_stmt (stmt
);
1052 /* For region parameters, insert at the beginning of the generated
1054 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1055 gsi_stmt
= gsi_def_stmt
;
1057 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1060 if (!gsi_stmt (gsi_def_stmt
))
1062 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1063 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1065 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1067 gimple_stmt_iterator bsi
1068 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1069 /* Insert right after the PHI statements. */
1070 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1073 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1077 fprintf (dump_file
, "[codegen] inserting statement in BB %d: ",
1078 gimple_bb (use_stmt
)->index
);
1079 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1084 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1085 scalar evolution around LOOP. */
1087 tree
translate_isl_ast_to_gimple::
1088 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1091 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1093 /* At this point we should know the exact scev for each
1094 scalar SSA_NAME used in the scop: all the other scalar
1095 SSA_NAMEs should have been translated out of SSA using
1096 arrays with one element. */
1098 if (chrec_contains_undetermined (scev
))
1100 set_codegen_error ();
1101 return build_zero_cst (TREE_TYPE (old_name
));
1104 new_expr
= chrec_apply_map (scev
, iv_map
);
1106 /* The apply should produce an expression tree containing
1107 the uses of the new induction variables. We should be
1108 able to use new_expr instead of the old_name in the newly
1109 generated loop nest. */
1110 if (chrec_contains_undetermined (new_expr
)
1111 || tree_contains_chrecs (new_expr
, NULL
))
1113 set_codegen_error ();
1114 return build_zero_cst (TREE_TYPE (old_name
));
1117 /* Replace the old_name with the new_expr. */
1118 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1123 /* Return true if STMT should be copied from region to the new code-generated
1124 region. LABELs, CONDITIONS, induction-variables and region parameters need
1128 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
1130 /* Do not copy labels or conditions. */
1131 if (gimple_code (stmt
) == GIMPLE_LABEL
1132 || gimple_code (stmt
) == GIMPLE_COND
)
1136 /* Do not copy induction variables. */
1137 if (is_gimple_assign (stmt
)
1138 && (lhs
= gimple_assign_lhs (stmt
))
1139 && TREE_CODE (lhs
) == SSA_NAME
1140 && is_gimple_reg (lhs
)
1141 && scev_analyzable_p (lhs
, region
->region
))
1147 /* Duplicates the statements of basic block BB into basic block NEW_BB
1148 and compute the new induction variables according to the IV_MAP. */
1150 void translate_isl_ast_to_gimple::
1151 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
1154 /* Iterator poining to the place where new statement (s) will be inserted. */
1155 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
1157 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1160 gimple
*stmt
= gsi_stmt (gsi
);
1161 if (!should_copy_to_new_region (stmt
, region
))
1164 /* Create a new copy of STMT and duplicate STMT's virtual
1166 gimple
*copy
= gimple_copy (stmt
);
1168 /* Rather than not copying debug stmts we reset them.
1169 ??? Where we can rewrite uses without inserting new
1170 stmts we could simply do that. */
1171 if (is_gimple_debug (copy
))
1173 if (gimple_debug_bind_p (copy
))
1174 gimple_debug_bind_reset_value (copy
);
1175 else if (gimple_debug_source_bind_p (copy
))
1181 maybe_duplicate_eh_stmt (copy
, stmt
);
1182 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
1184 /* Crete new names for each def in the copied stmt. */
1185 def_operand_p def_p
;
1186 ssa_op_iter op_iter
;
1187 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
1189 tree old_name
= DEF_FROM_PTR (def_p
);
1190 create_new_def_for (old_name
, copy
, def_p
);
1193 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
1196 fprintf (dump_file
, "[codegen] inserting statement: ");
1197 print_gimple_stmt (dump_file
, copy
, 0);
1200 /* For each SCEV analyzable SSA_NAME, rename their usage. */
1202 use_operand_p use_p
;
1203 if (!is_gimple_debug (copy
))
1205 bool changed
= false;
1206 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
1208 tree old_name
= USE_FROM_PTR (use_p
);
1210 if (TREE_CODE (old_name
) != SSA_NAME
1211 || SSA_NAME_IS_DEFAULT_DEF (old_name
)
1212 || ! scev_analyzable_p (old_name
, region
->region
))
1215 gimple_seq stmts
= NULL
;
1216 tree new_name
= get_rename_from_scev (old_name
, &stmts
,
1217 bb
->loop_father
, iv_map
);
1218 if (! codegen_error_p ())
1219 gsi_insert_earliest (stmts
);
1220 replace_exp (use_p
, new_name
);
1224 fold_stmt_inplace (&gsi_tgt
);
1232 /* Copies BB and includes in the copied BB all the statements that can
1233 be reached following the use-def chains from the memory accesses,
1234 and returns the next edge following this new block. */
1236 edge
translate_isl_ast_to_gimple::
1237 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
1239 basic_block new_bb
= split_edge (next_e
);
1240 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
1241 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1244 gphi
*phi
= psi
.phi ();
1245 tree res
= gimple_phi_result (phi
);
1246 if (virtual_operand_p (res
)
1247 || scev_analyzable_p (res
, region
->region
))
1251 tree
*rename
= region
->rename_map
->get (res
);
1254 new_phi_def
= create_tmp_reg (TREE_TYPE (res
));
1255 set_rename (res
, new_phi_def
);
1258 new_phi_def
= *rename
;
1260 gassign
*ass
= gimple_build_assign (NULL_TREE
, new_phi_def
);
1261 create_new_def_for (res
, ass
, NULL
);
1262 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1265 graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
);
1267 /* Insert out-of SSA copies on the original BB outgoing edges. */
1268 gsi_tgt
= gsi_last_bb (new_bb
);
1269 basic_block bb_for_succs
= bb
;
1270 if (bb_for_succs
== bb_for_succs
->loop_father
->latch
1271 && bb_in_sese_p (bb_for_succs
, region
->region
)
1272 && sese_trivially_empty_bb_p (bb_for_succs
))
1273 bb_for_succs
= NULL
;
1274 while (bb_for_succs
)
1276 basic_block latch
= NULL
;
1279 FOR_EACH_EDGE (e
, ei
, bb_for_succs
->succs
)
1281 for (gphi_iterator psi
= gsi_start_phis (e
->dest
); !gsi_end_p (psi
);
1284 gphi
*phi
= psi
.phi ();
1285 tree res
= gimple_phi_result (phi
);
1286 if (virtual_operand_p (res
)
1287 || scev_analyzable_p (res
, region
->region
))
1291 tree
*rename
= region
->rename_map
->get (res
);
1294 new_phi_def
= create_tmp_reg (TREE_TYPE (res
));
1295 set_rename (res
, new_phi_def
);
1298 new_phi_def
= *rename
;
1300 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1301 if (TREE_CODE (arg
) == SSA_NAME
1302 && scev_analyzable_p (arg
, region
->region
))
1304 gimple_seq stmts
= NULL
;
1305 tree new_name
= get_rename_from_scev (arg
, &stmts
,
1308 if (! codegen_error_p ())
1309 gsi_insert_earliest (stmts
);
1312 gassign
*ass
= gimple_build_assign (new_phi_def
, arg
);
1313 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1315 if (e
->dest
== bb_for_succs
->loop_father
->latch
1316 && bb_in_sese_p (e
->dest
, region
->region
)
1317 && sese_trivially_empty_bb_p (e
->dest
))
1320 bb_for_succs
= latch
;
1323 return single_succ_edge (new_bb
);
1326 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
1328 void translate_isl_ast_to_gimple::
1329 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
1331 sese_info_p region
= scop
->scop_info
;
1332 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
1333 gcc_assert (nb_parameters
== sese_nb_params (region
));
1336 FOR_EACH_VEC_ELT (region
->params
, i
, param
)
1338 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
1345 /* Generates a build, which specifies the constraints on the parameters. */
1347 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
1348 generate_isl_context (scop_p scop
)
1350 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
1351 return isl_ast_build_from_context (context_isl
);
1354 /* This method is executed before the construction of a for node. */
1356 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
1358 isl_union_map
*dependences
= (isl_union_map
*) user
;
1359 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
1360 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
1361 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
1362 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
1363 for_info
->is_parallelizable
=
1364 !carries_deps (schedule
, dependences
, dimension
);
1365 isl_union_map_free (schedule
);
1366 isl_space_free (schedule_space
);
1367 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
1371 /* Generate isl AST from schedule of SCOP. */
1373 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
1374 scop_to_isl_ast (scop_p scop
)
1376 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1377 int old_max_operations
= isl_ctx_get_max_operations (scop
->isl_context
);
1378 int max_operations
= PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS
);
1380 isl_ctx_set_max_operations (scop
->isl_context
, max_operations
);
1381 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1383 gcc_assert (scop
->transformed_schedule
);
1385 /* Set the separate option to reduce control flow overhead. */
1386 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
1387 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
1388 isl_ast_build
*context_isl
= generate_isl_context (scop
);
1390 if (flag_loop_parallelize_all
)
1392 scop_get_dependences (scop
);
1394 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
1398 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
1399 (context_isl
, schedule
);
1400 isl_ast_build_free (context_isl
);
1402 isl_options_set_on_error (scop
->isl_context
, old_err
);
1403 isl_ctx_reset_operations (scop
->isl_context
);
1404 isl_ctx_set_max_operations (scop
->isl_context
, old_max_operations
);
1405 if (isl_ctx_last_error (scop
->isl_context
) != isl_error_none
)
1407 location_t loc
= find_loop_location
1408 (scop
->scop_info
->region
.entry
->dest
->loop_father
);
1409 if (isl_ctx_last_error (scop
->isl_context
) == isl_error_quota
)
1410 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1411 "loop nest not optimized, AST generation timed out "
1412 "after %d operations [--param max-isl-operations]\n",
1415 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1416 "loop nest not optimized, ISL AST generation "
1417 "signalled an error\n");
1418 isl_ast_node_free (ast_isl
);
1425 /* Generate out-of-SSA copies for the entry edge FALSE_ENTRY/TRUE_ENTRY
1429 generate_entry_out_of_ssa_copies (edge false_entry
,
1433 gimple_stmt_iterator gsi_tgt
= gsi_start_bb (true_entry
->dest
);
1434 for (gphi_iterator psi
= gsi_start_phis (false_entry
->dest
);
1435 !gsi_end_p (psi
); gsi_next (&psi
))
1437 gphi
*phi
= psi
.phi ();
1438 tree res
= gimple_phi_result (phi
);
1439 if (virtual_operand_p (res
))
1441 /* When there's no out-of-SSA var registered do not bother
1443 tree
*rename
= region
->rename_map
->get (res
);
1446 tree new_phi_def
= *rename
;
1447 gassign
*ass
= gimple_build_assign (new_phi_def
,
1448 PHI_ARG_DEF_FROM_EDGE (phi
,
1450 gsi_insert_after (&gsi_tgt
, ass
, GSI_NEW_STMT
);
1454 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
1455 Return true if code generation succeeded. */
1458 graphite_regenerate_ast_isl (scop_p scop
)
1460 sese_info_p region
= scop
->scop_info
;
1461 translate_isl_ast_to_gimple
t (region
);
1463 ifsese if_region
= NULL
;
1464 isl_ast_node
*root_node
;
1467 timevar_push (TV_GRAPHITE_CODE_GEN
);
1468 t
.add_parameters_to_ivs_params (scop
, ip
);
1469 root_node
= t
.scop_to_isl_ast (scop
);
1472 ivs_params_clear (ip
);
1473 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1479 fprintf (dump_file
, "[scheduler] original schedule:\n");
1480 print_isl_schedule (dump_file
, scop
->original_schedule
);
1481 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
1482 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
1484 fprintf (dump_file
, "[scheduler] original ast:\n");
1485 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
1486 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
1487 print_isl_ast (dump_file
, root_node
);
1490 if_region
= move_sese_in_condition (region
);
1491 region
->if_region
= if_region
;
1493 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
1494 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
1495 basic_block bb
= split_edge (e
);
1497 /* Update the true_region exit edge. */
1498 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
1500 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
1501 if (! t
.codegen_error_p ())
1503 generate_entry_out_of_ssa_copies (if_region
->false_region
->region
.entry
,
1504 if_region
->true_region
->region
.entry
,
1506 sese_insert_phis_for_liveouts (region
,
1507 if_region
->region
->region
.exit
->src
,
1508 if_region
->false_region
->region
.exit
,
1509 if_region
->true_region
->region
.exit
);
1511 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
1514 if (t
.codegen_error_p ())
1516 location_t loc
= find_loop_location
1517 (scop
->scop_info
->region
.entry
->dest
->loop_father
);
1518 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1519 "loop nest not optimized, code generation error\n");
1521 /* Remove the unreachable region. */
1522 remove_edge_and_dominated_blocks (if_region
->true_region
->region
.entry
);
1523 basic_block ifb
= if_region
->false_region
->region
.entry
->src
;
1524 gimple_stmt_iterator gsi
= gsi_last_bb (ifb
);
1525 gsi_remove (&gsi
, true);
1526 if_region
->false_region
->region
.entry
->flags
&= ~EDGE_FALSE_VALUE
;
1527 if_region
->false_region
->region
.entry
->flags
|= EDGE_FALLTHRU
;
1528 /* remove_edge_and_dominated_blocks marks loops for removal but
1529 doesn't actually remove them (fix that...). */
1531 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1536 /* We are delaying SSA update to after code-generating all SCOPs.
1537 This is because we analyzed DRs and parameters on the unmodified
1538 IL and thus rely on SSA update to pick up new dominating definitions
1539 from for example SESE liveout PHIs. This is also for efficiency
1540 as SSA update does work depending on the size of the function. */
1542 free (if_region
->true_region
);
1543 free (if_region
->region
);
1546 ivs_params_clear (ip
);
1547 isl_ast_node_free (root_node
);
1548 timevar_pop (TV_GRAPHITE_CODE_GEN
);
1550 return !t
.codegen_error_p ();
1553 #endif /* HAVE_isl */