1 /* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2016 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"
35 #include "fold-const.h"
36 #include "gimple-fold.h"
37 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-ssa-operands.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-pass.h"
46 #include "tree-data-ref.h"
47 #include "tree-ssa-loop-manip.h"
48 #include "tree-scalar-evolution.h"
49 #include "gimple-ssa.h"
50 #include "tree-phinodes.h"
51 #include "tree-into-ssa.h"
52 #include "ssa-iterators.h"
54 #include "gimple-pretty-print.h"
56 #include "value-prof.h"
59 /* We always try to use signed 128 bit types, but fall back to smaller types
60 in case a platform does not provide types of these sizes. In the future we
61 should use isl to derive the optimal type for each subexpression. */
63 static int max_mode_int_precision
=
64 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
65 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
66 128 : max_mode_int_precision
;
71 : is_parallelizable(false)
73 bool is_parallelizable
;
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 checking_verify_loop_structure ();
98 checking_verify_loop_closed_ssa (true);
101 /* IVS_PARAMS maps isl's scattering and parameter identifiers
102 to corresponding trees. */
104 typedef std::map
<isl_id
*, tree
> ivs_params
;
106 /* Free all memory allocated for isl's identifiers. */
108 static void ivs_params_clear (ivs_params
&ip
)
110 std::map
<isl_id
*, tree
>::iterator it
;
111 for (it
= ip
.begin ();
112 it
!= ip
.end (); it
++)
114 isl_id_free (it
->first
);
118 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
120 /* Set the "separate" option for the schedule node. */
122 static isl_schedule_node
*
123 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
128 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
131 /* Set the "separate" option unless it is set earlier to another option. */
132 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
133 == isl_ast_loop_default
)
134 return isl_schedule_node_band_member_set_ast_loop_type
135 (node
, 0, isl_ast_loop_separate
);
140 /* Print SCHEDULE under an AST form on file F. */
143 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
145 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
146 isl_ast_build
*context
= isl_ast_build_from_context (set
);
148 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
149 isl_ast_build_free (context
);
150 print_isl_ast (f
, ast
);
151 isl_ast_node_free (ast
);
155 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
157 print_schedule_ast (stderr
, s
, scop
);
170 class translate_isl_ast_to_gimple
173 translate_isl_ast_to_gimple (sese_info_p r
)
174 : region (r
), codegen_error (false) { }
175 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
176 edge next_e
, ivs_params
&ip
);
177 edge
translate_isl_ast_node_for (loop_p context_loop
,
178 __isl_keep isl_ast_node
*node
,
179 edge next_e
, ivs_params
&ip
);
180 edge
translate_isl_ast_for_loop (loop_p context_loop
,
181 __isl_keep isl_ast_node
*node_for
,
183 tree type
, tree lb
, tree ub
,
185 edge
translate_isl_ast_node_if (loop_p context_loop
,
186 __isl_keep isl_ast_node
*node
,
187 edge next_e
, ivs_params
&ip
);
188 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
189 edge next_e
, ivs_params
&ip
);
190 edge
translate_isl_ast_node_block (loop_p context_loop
,
191 __isl_keep isl_ast_node
*node
,
192 edge next_e
, ivs_params
&ip
);
193 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
195 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
197 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
199 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
201 tree
gcc_expression_from_isl_expression (tree type
,
202 __isl_take isl_ast_expr
*,
204 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
205 __isl_keep isl_ast_expr
*expr_id
,
207 tree
gcc_expression_from_isl_expr_int (tree type
,
208 __isl_take isl_ast_expr
*expr
);
209 tree
gcc_expression_from_isl_expr_op (tree type
,
210 __isl_take isl_ast_expr
*expr
,
212 struct loop
*graphite_create_new_loop (edge entry_edge
,
213 __isl_keep isl_ast_node
*node_for
,
214 loop_p outer
, tree type
,
215 tree lb
, tree ub
, ivs_params
&ip
);
216 edge
graphite_create_new_loop_guard (edge entry_edge
,
217 __isl_keep isl_ast_node
*node_for
,
219 tree
*lb
, tree
*ub
, ivs_params
&ip
);
220 edge
graphite_create_new_guard (edge entry_edge
,
221 __isl_take isl_ast_expr
*if_cond
,
223 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
224 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
226 void translate_pending_phi_nodes (void);
227 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
228 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
230 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
231 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
233 int get_max_schedule_dimensions (scop_p scop
);
234 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
235 int nb_schedule_dims
);
236 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
237 __isl_give isl_ast_build
*set_options (__isl_take isl_ast_build
*control
,
238 __isl_keep isl_union_map
*schedule
);
239 __isl_give isl_ast_node
*scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
242 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
243 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
244 tree
get_rename (basic_block new_bb
, tree old_name
,
245 basic_block old_bb
, phi_node_kind
) const;
246 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
247 basic_block new_bb
, basic_block old_bb
,
249 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
250 tree
get_new_name (basic_block new_bb
, tree op
,
251 basic_block old_bb
, phi_node_kind
) const;
252 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
253 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
254 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
256 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
257 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
259 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
260 gimple
*old_close_phi
);
261 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
263 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
264 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
266 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
268 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
270 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
272 edge
edge_for_new_close_phis (basic_block bb
);
273 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
274 edge old_bb_dominating_edge
,
275 edge old_bb_non_dominating_edge
,
276 gphi
*phi
, gphi
*new_phi
,
278 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
279 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
280 void set_rename (tree old_name
, tree expr
);
281 void set_rename_for_each_def (gimple
*stmt
);
282 void gsi_insert_earliest (gimple_seq seq
);
283 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
284 bool codegen_error_p () const { return codegen_error
; }
285 bool is_constant (tree op
) const
287 return TREE_CODE (op
) == INTEGER_CST
288 || TREE_CODE (op
) == REAL_CST
289 || TREE_CODE (op
) == COMPLEX_CST
290 || TREE_CODE (op
) == VECTOR_CST
;
294 /* The region to be translated. */
297 /* This flag is set when an error occurred during the translation of isl AST
301 /* A vector of all the edges at if_condition merge points. */
302 auto_vec
<edge
, 2> merge_points
;
305 /* Return the tree variable that corresponds to the given isl ast identifier
306 expression (an isl_ast_expr of type isl_ast_expr_id).
308 FIXME: We should replace blind conversion of id's type with derivation
309 of the optimal type when we get the corresponding isl support. Blindly
310 converting type sizes may be problematic when we switch to smaller
313 tree
translate_isl_ast_to_gimple::
314 gcc_expression_from_isl_ast_expr_id (tree type
,
315 __isl_take isl_ast_expr
*expr_id
,
318 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
319 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
320 std::map
<isl_id
*, tree
>::iterator res
;
321 res
= ip
.find (tmp_isl_id
);
322 isl_id_free (tmp_isl_id
);
323 gcc_assert (res
!= ip
.end () &&
324 "Could not map isl_id to tree expression");
325 isl_ast_expr_free (expr_id
);
326 tree t
= res
->second
;
327 tree
*val
= region
->parameter_rename_map
->get(t
);
331 return fold_convert (type
, *val
);
334 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
337 tree
translate_isl_ast_to_gimple::
338 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
340 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
341 isl_val
*val
= isl_ast_expr_get_val (expr
);
343 mpz_init (val_mpz_t
);
345 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
348 res
= gmp_cst_to_tree (type
, val_mpz_t
);
350 isl_ast_expr_free (expr
);
351 mpz_clear (val_mpz_t
);
355 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
358 tree
translate_isl_ast_to_gimple::
359 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
361 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
362 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
363 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
364 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
366 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
367 isl_ast_expr_free (expr
);
369 if (codegen_error_p ())
375 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
378 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
381 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
384 /* As isl operates on arbitrary precision numbers, we may end up with
385 division by 2^64 that is folded to 0. */
386 if (integer_zerop (tree_rhs_expr
))
388 codegen_error
= true;
391 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
393 case isl_ast_op_pdiv_q
:
394 /* As isl operates on arbitrary precision numbers, we may end up with
395 division by 2^64 that is folded to 0. */
396 if (integer_zerop (tree_rhs_expr
))
398 codegen_error
= true;
401 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
403 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
404 /* isl 0.15 or later. */
405 case isl_ast_op_zdiv_r
:
407 case isl_ast_op_pdiv_r
:
408 /* As isl operates on arbitrary precision numbers, we may end up with
409 division by 2^64 that is folded to 0. */
410 if (integer_zerop (tree_rhs_expr
))
412 codegen_error
= true;
415 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
417 case isl_ast_op_fdiv_q
:
418 /* As isl operates on arbitrary precision numbers, we may end up with
419 division by 2^64 that is folded to 0. */
420 if (integer_zerop (tree_rhs_expr
))
422 codegen_error
= true;
425 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
428 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
429 tree_lhs_expr
, tree_rhs_expr
);
432 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
435 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
438 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
441 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
444 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
447 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
454 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
457 tree
translate_isl_ast_to_gimple::
458 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
460 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
461 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
462 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
463 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
464 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
465 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
466 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
467 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
468 isl_ast_expr_free (expr
);
470 if (codegen_error_p ())
473 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
476 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
479 tree
translate_isl_ast_to_gimple::
480 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
482 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
483 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
484 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
485 isl_ast_expr_free (expr
);
486 return codegen_error_p () ? NULL_TREE
487 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
490 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
491 to a GCC expression tree of type TYPE. */
493 tree
translate_isl_ast_to_gimple::
494 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
496 enum tree_code op_code
;
497 switch (isl_ast_expr_get_op_type (expr
))
510 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
511 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
513 if (codegen_error_p ())
515 isl_ast_expr_free (expr
);
520 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
522 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
523 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
525 if (codegen_error_p ())
527 isl_ast_expr_free (expr
);
531 res
= fold_build2 (op_code
, type
, res
, t
);
533 isl_ast_expr_free (expr
);
537 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
540 tree
translate_isl_ast_to_gimple::
541 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
544 if (codegen_error_p ())
546 isl_ast_expr_free (expr
);
550 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
551 switch (isl_ast_expr_get_op_type (expr
))
553 /* These isl ast expressions are not supported yet. */
554 case isl_ast_op_error
:
555 case isl_ast_op_call
:
556 case isl_ast_op_and_then
:
557 case isl_ast_op_or_else
:
562 return nary_op_to_tree (type
, expr
, ip
);
568 case isl_ast_op_pdiv_q
:
569 case isl_ast_op_pdiv_r
:
570 case isl_ast_op_fdiv_q
:
571 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
572 /* isl 0.15 or later. */
573 case isl_ast_op_zdiv_r
:
582 return binary_op_to_tree (type
, expr
, ip
);
584 case isl_ast_op_minus
:
585 return unary_op_to_tree (type
, expr
, ip
);
587 case isl_ast_op_cond
:
588 case isl_ast_op_select
:
589 return ternary_op_to_tree (type
, expr
, ip
);
598 /* Converts an isl AST expression E back to a GCC expression tree of
601 tree
translate_isl_ast_to_gimple::
602 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
605 if (codegen_error_p ())
607 isl_ast_expr_free (expr
);
611 switch (isl_ast_expr_get_type (expr
))
613 case isl_ast_expr_id
:
614 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
616 case isl_ast_expr_int
:
617 return gcc_expression_from_isl_expr_int (type
, expr
);
619 case isl_ast_expr_op
:
620 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
629 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
630 induction variable for the new LOOP. New LOOP is attached to CFG
631 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
632 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
633 isl's scattering name to the induction variable created for the
634 loop of STMT. The new induction variable is inserted in the NEWIVS
635 vector and is of type TYPE. */
637 struct loop
*translate_isl_ast_to_gimple::
638 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
639 loop_p outer
, tree type
, tree lb
, tree ub
,
642 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
643 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
645 /* To fail code generation, we generate wrong code until we discard it. */
646 if (codegen_error_p ())
647 stride
= integer_zero_node
;
649 tree ivvar
= create_tmp_var (type
, "graphite_IV");
650 tree iv
, iv_after_increment
;
651 loop_p loop
= create_empty_loop_on_edge
652 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
653 outer
? outer
: entry_edge
->src
->loop_father
);
655 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
656 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
657 std::map
<isl_id
*, tree
>::iterator res
;
660 isl_id_free (res
->first
);
662 isl_ast_expr_free (for_iterator
);
666 /* Create the loop for a isl_ast_node_for.
668 - NEXT_E is the edge where new generated code should be attached. */
670 edge
translate_isl_ast_to_gimple::
671 translate_isl_ast_for_loop (loop_p context_loop
,
672 __isl_keep isl_ast_node
*node_for
, edge next_e
,
673 tree type
, tree lb
, tree ub
,
676 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
677 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
679 edge last_e
= single_exit (loop
);
680 edge to_body
= single_succ_edge (loop
->header
);
681 basic_block after
= to_body
->dest
;
683 /* Translate the body of the loop. */
684 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
685 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
686 isl_ast_node_free (for_body
);
688 /* Early return if we failed to translate loop body. */
689 if (!next_e
|| codegen_error_p ())
692 if (next_e
->dest
!= after
)
693 redirect_edge_succ_nodup (next_e
, after
);
694 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
696 if (flag_loop_parallelize_all
)
698 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
700 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
701 loop
->can_be_parallel
= for_info
->is_parallelizable
;
709 /* We use this function to get the upper bound because of the form,
710 which is used by isl to represent loops:
712 for (iterator = init; cond; iterator += inc)
720 The loop condition is an arbitrary expression, which contains the
721 current loop iterator.
723 (e.g. iterator + 3 < B && C > iterator + A)
725 We have to know the upper bound of the iterator to generate a loop
726 in Gimple form. It can be obtained from the special representation
727 of the loop condition, which is generated by isl,
728 if the ast_build_atomic_upper_bound option is set. In this case,
729 isl generates a loop condition that consists of the current loop
730 iterator, + an operator (< or <=) and an expression not involving
731 the iterator, which is processed and returned by this function.
733 (e.g iterator <= upper-bound-expression-without-iterator) */
735 static __isl_give isl_ast_expr
*
736 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
738 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
739 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
740 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
742 switch (isl_ast_expr_get_op_type (for_cond
))
745 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
750 /* (iterator < ub) => (iterator <= ub - 1). */
752 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
753 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
754 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
761 isl_ast_expr_free (for_cond
);
765 /* All loops generated by create_empty_loop_on_edge have the form of
772 } while (lower bound < upper bound);
774 We create a new if region protecting the loop to be executed, if
775 the execution count is zero (lower bound > upper bound). */
777 edge
translate_isl_ast_to_gimple::
778 graphite_create_new_loop_guard (edge entry_edge
,
779 __isl_keep isl_ast_node
*node_for
, tree
*type
,
780 tree
*lb
, tree
*ub
, ivs_params
&ip
)
782 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
787 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
788 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
789 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
791 /* To fail code generation, we generate wrong code until we discard it. */
792 if (codegen_error_p ())
793 *lb
= integer_zero_node
;
795 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
796 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
798 /* To fail code generation, we generate wrong code until we discard it. */
799 if (codegen_error_p ())
800 *ub
= integer_zero_node
;
802 /* When ub is simply a constant or a parameter, use lb <= ub. */
803 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
804 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
807 tree one
= (POINTER_TYPE_P (*type
)
808 ? convert_to_ptrofftype (integer_one_node
)
809 : fold_convert (*type
, integer_one_node
));
810 /* Adding +1 and using LT_EXPR helps with loop latches that have a
811 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
812 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
813 is true, even if we do not want this. However lb < ub + 1 is false,
815 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
816 : PLUS_EXPR
, *type
, *ub
, one
);
818 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
821 if (integer_onep (cond_expr
))
822 exit_edge
= entry_edge
;
824 exit_edge
= create_empty_if_region_on_edge (entry_edge
,
825 unshare_expr (cond_expr
));
830 /* Translates an isl_ast_node_for to Gimple. */
832 edge
translate_isl_ast_to_gimple::
833 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
834 edge next_e
, ivs_params
&ip
)
836 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
838 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
841 if (last_e
== next_e
)
843 /* There was no guard generated. */
844 last_e
= single_succ_edge (split_edge (last_e
));
846 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
851 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
852 merge_points
.safe_push (last_e
);
854 last_e
= single_succ_edge (split_edge (last_e
));
855 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
860 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
861 variables of the loops around GBB in SESE.
863 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
864 chrec, we could consider using a map<int, tree> that maps loop ids to the
865 corresponding tree expressions. */
867 void translate_isl_ast_to_gimple::
868 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
869 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
872 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
873 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
875 isl_ast_expr
*arg_expr
;
876 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
878 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
880 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
881 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
883 /* To fail code generation, we generate wrong code until we discard it. */
884 if (codegen_error_p ())
885 t
= integer_zero_node
;
887 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
888 iv_map
[old_loop
->num
] = t
;
892 /* Translates an isl_ast_node_user to Gimple.
894 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
896 edge
translate_isl_ast_to_gimple::
897 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
898 edge next_e
, ivs_params
&ip
)
900 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
902 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
903 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
904 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
906 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
907 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
910 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
912 isl_ast_expr_free (name_expr
);
913 isl_id_free (name_id
);
915 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
916 "The entry block should not even appear within a scop");
918 const int nb_loops
= number_of_loops (cfun
);
920 iv_map
.create (nb_loops
);
921 iv_map
.safe_grow_cleared (nb_loops
);
923 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
924 isl_ast_expr_free (user_expr
);
926 basic_block old_bb
= GBB_BB (gbb
);
930 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
931 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
932 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
936 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
940 if (codegen_error_p ())
945 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
946 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
952 /* Translates an isl_ast_node_block to Gimple. */
954 edge
translate_isl_ast_to_gimple::
955 translate_isl_ast_node_block (loop_p context_loop
,
956 __isl_keep isl_ast_node
*node
,
957 edge next_e
, ivs_params
&ip
)
959 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
960 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
962 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
964 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
965 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
966 isl_ast_node_free (tmp_node
);
968 isl_ast_node_list_free (node_list
);
972 /* Creates a new if region corresponding to isl's cond. */
974 edge
translate_isl_ast_to_gimple::
975 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
979 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
980 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
982 /* To fail code generation, we generate wrong code until we discard it. */
983 if (codegen_error_p ())
984 cond_expr
= integer_zero_node
;
986 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
990 /* Translates an isl_ast_node_if to Gimple. */
992 edge
translate_isl_ast_to_gimple::
993 translate_isl_ast_node_if (loop_p context_loop
,
994 __isl_keep isl_ast_node
*node
,
995 edge next_e
, ivs_params
&ip
)
997 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
998 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
999 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1000 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1001 merge_points
.safe_push (last_e
);
1003 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1004 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1005 isl_ast_node_free (then_node
);
1007 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1008 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1009 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1010 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1012 isl_ast_node_free (else_node
);
1016 /* Translates an isl AST node NODE to GCC representation in the
1017 context of a SESE. */
1019 edge
translate_isl_ast_to_gimple::
1020 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1021 edge next_e
, ivs_params
&ip
)
1023 if (codegen_error_p ())
1026 switch (isl_ast_node_get_type (node
))
1028 case isl_ast_node_error
:
1031 case isl_ast_node_for
:
1032 return translate_isl_ast_node_for (context_loop
, node
,
1035 case isl_ast_node_if
:
1036 return translate_isl_ast_node_if (context_loop
, node
,
1039 case isl_ast_node_user
:
1040 return translate_isl_ast_node_user (node
, next_e
, ip
);
1042 case isl_ast_node_block
:
1043 return translate_isl_ast_node_block (context_loop
, node
,
1046 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1047 case isl_ast_node_mark
:
1049 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1050 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1051 isl_ast_node_free (n
);
1061 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1062 at the exit of loop which takes one argument that is the last value of the
1063 variable being used out of the loop. */
1066 bb_contains_loop_close_phi_nodes (basic_block bb
)
1068 return single_pred_p (bb
)
1069 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1072 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1073 header containing phi nodes which has one init-edge and one back-edge. */
1076 bb_contains_loop_phi_nodes (basic_block bb
)
1078 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1080 if (bb
->preds
->length () == 1)
1083 unsigned depth
= loop_depth (bb
->loop_father
);
1085 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1087 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1088 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1091 /* When one of the edges correspond to the same loop father and other
1093 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1094 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1097 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1098 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1104 /* Check if USE is defined in a basic block from where the definition of USE can
1105 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1108 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1110 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1113 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1114 if (bb_contains_loop_close_phi_nodes (bb
))
1117 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1118 basic_block def_bb
= gimple_bb (def
);
1120 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1123 /* Return the number of phi nodes in BB. */
1126 number_of_phi_nodes (basic_block bb
)
1129 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1135 /* Returns true if BB uses name in one of its PHIs. */
1138 phi_uses_name (basic_block bb
, tree name
)
1140 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1143 gphi
*phi
= psi
.phi ();
1144 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1146 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1147 if (use_arg
== name
)
1154 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1155 definition should flow into use, and the use should respect the loop-closed
1158 bool translate_isl_ast_to_gimple::
1159 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1160 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1162 /* The def of the rename must either dominate the uses or come from a
1163 back-edge. Also the def must respect the loop closed ssa form. */
1164 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1168 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1169 print_generic_expr (dump_file
, rename
, 0);
1170 fprintf (dump_file
, "\n");
1175 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1178 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1180 /* The loop-header dominates the loop-body. */
1181 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1184 /* RENAME would be used in loop-phi. */
1185 gcc_assert (number_of_phi_nodes (use_bb
));
1187 /* For definitions coming from back edges, we should check that
1188 old_name is used in a loop PHI node.
1189 FIXME: Verify if this is true. */
1190 if (phi_uses_name (old_bb
, old_name
))
1196 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1197 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1199 tree
translate_isl_ast_to_gimple::
1200 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1201 phi_node_kind phi_kind
) const
1203 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1204 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1206 if (!renames
|| renames
->is_empty ())
1209 if (1 == renames
->length ())
1211 tree rename
= (*renames
)[0];
1212 if (TREE_CODE (rename
) == SSA_NAME
)
1214 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1215 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1216 && (phi_kind
== close_phi
1217 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1222 if (is_constant (rename
))
1228 /* More than one renames corresponding to the old_name. Find the rename for
1229 which the definition flows into usage at new_bb. */
1231 tree t1
= NULL_TREE
, t2
;
1232 basic_block t1_bb
= NULL
;
1233 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1235 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1237 /* Defined in the same basic block as used. */
1238 if (t2_bb
== new_bb
)
1241 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1242 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1245 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1248 /* Compute the nearest dominator. */
1249 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1259 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1260 When OLD_NAME and EXPR are the same we assert. */
1262 void translate_isl_ast_to_gimple::
1263 set_rename (tree old_name
, tree expr
)
1267 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1268 print_generic_expr (dump_file
, old_name
, 0);
1269 fprintf (dump_file
, ", new_name = ");
1270 print_generic_expr (dump_file
, expr
, 0);
1271 fprintf (dump_file
, "\n");
1274 if (old_name
== expr
)
1277 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1280 renames
->safe_push (expr
);
1286 region
->rename_map
->put (old_name
, r
);
1291 /* For a parameter of a scop we don't want to rename it. */
1292 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1294 region
->parameter_rename_map
->put(old_name
, expr
);
1297 /* Return an iterator to the instructions comes last in the execution order.
1298 Either GSI1 and GSI2 should belong to the same basic block or one of their
1299 respective basic blocks should dominate the other. */
1301 gimple_stmt_iterator
1302 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1304 basic_block bb1
= gsi_bb (gsi1
);
1305 basic_block bb2
= gsi_bb (gsi2
);
1307 /* Find the iterator which is the latest. */
1310 /* For empty basic blocks gsis point to the end of the sequence. Since
1311 there is no operator== defined for gimple_stmt_iterator and for gsis
1312 not pointing to a valid statement gsi_next would assert. */
1313 gimple_stmt_iterator gsi
= gsi1
;
1315 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1318 } while (!gsi_end_p (gsi
));
1323 /* Find the basic block closest to the basic block which defines stmt. */
1324 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1327 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1331 /* Insert each statement from SEQ at its earliest insertion p. */
1333 void translate_isl_ast_to_gimple::
1334 gsi_insert_earliest (gimple_seq seq
)
1336 update_modified_stmts (seq
);
1337 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1338 basic_block begin_bb
= get_entry_bb (codegen_region
);
1340 /* Inserting the gimple statements in a vector because gimple_seq behave
1341 in strage ways when inserting the stmts from it into different basic
1342 blocks one at a time. */
1343 auto_vec
<gimple
*, 3> stmts
;
1344 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1346 stmts
.safe_push (gsi_stmt (gsi
));
1350 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1352 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1353 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1355 use_operand_p use_p
;
1356 ssa_op_iter op_iter
;
1357 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1359 /* Iterator to the current def of use_p. For function parameters or
1360 anything where def is not found, insert at the beginning of the
1361 generated region. */
1362 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1364 tree op
= USE_FROM_PTR (use_p
);
1365 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1366 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1367 gsi_stmt
= gsi_for_stmt (stmt
);
1369 /* For region parameters, insert at the beginning of the generated
1371 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1372 gsi_stmt
= gsi_def_stmt
;
1374 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1377 if (!gsi_stmt (gsi_def_stmt
))
1379 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1380 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1382 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1384 gimple_stmt_iterator bsi
1385 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1386 /* Insert right after the PHI statements. */
1387 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1390 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1394 fprintf (dump_file
, "[codegen] inserting statement: ");
1395 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1396 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1401 /* Collect all the operands of NEW_EXPR by recursively visiting each
1404 void translate_isl_ast_to_gimple::
1405 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1407 if (new_expr
== NULL_TREE
)
1410 /* Rename all uses in new_expr. */
1411 if (TREE_CODE (new_expr
) == SSA_NAME
)
1413 vec_ssa
->safe_push (new_expr
);
1417 /* Iterate over SSA_NAMES in NEW_EXPR. */
1418 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1420 tree op
= TREE_OPERAND (new_expr
, i
);
1421 collect_all_ssa_names (op
, vec_ssa
);
1425 /* This is abridged version of the function copied from:
1426 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1429 substitute_ssa_name (tree exp
, tree f
, tree r
)
1431 enum tree_code code
= TREE_CODE (exp
);
1432 tree op0
, op1
, op2
, op3
;
1435 /* We handle TREE_LIST and COMPONENT_REF separately. */
1436 if (code
== TREE_LIST
)
1438 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1439 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1440 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1443 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1445 else if (code
== COMPONENT_REF
)
1449 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1450 and it is the right field, replace it with R. */
1451 for (inner
= TREE_OPERAND (exp
, 0);
1452 REFERENCE_CLASS_P (inner
);
1453 inner
= TREE_OPERAND (inner
, 0))
1457 op1
= TREE_OPERAND (exp
, 1);
1459 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1462 /* If this expression hasn't been completed let, leave it alone. */
1463 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1466 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1467 if (op0
== TREE_OPERAND (exp
, 0))
1471 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1474 switch (TREE_CODE_CLASS (code
))
1479 case tcc_declaration
:
1485 case tcc_expression
:
1489 /* Fall through... */
1491 case tcc_exceptional
:
1494 case tcc_comparison
:
1496 switch (TREE_CODE_LENGTH (code
))
1504 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1505 if (op0
== TREE_OPERAND (exp
, 0))
1508 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1512 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1513 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1515 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1518 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1522 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1523 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1524 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1526 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1527 && op2
== TREE_OPERAND (exp
, 2))
1530 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1534 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1535 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1536 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1537 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1539 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1540 && op2
== TREE_OPERAND (exp
, 2)
1541 && op3
== TREE_OPERAND (exp
, 3))
1545 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1558 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1560 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1561 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1566 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1568 tree
translate_isl_ast_to_gimple::
1569 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1571 auto_vec
<tree
, 2> ssa_names
;
1572 collect_all_ssa_names (new_expr
, &ssa_names
);
1575 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1576 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1577 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1582 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1583 scalar evolution around LOOP. */
1585 tree
translate_isl_ast_to_gimple::
1586 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1587 basic_block new_bb
, basic_block old_bb
,
1590 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1592 /* At this point we should know the exact scev for each
1593 scalar SSA_NAME used in the scop: all the other scalar
1594 SSA_NAMEs should have been translated out of SSA using
1595 arrays with one element. */
1597 if (chrec_contains_undetermined (scev
))
1599 codegen_error
= true;
1600 return build_zero_cst (TREE_TYPE (old_name
));
1603 new_expr
= chrec_apply_map (scev
, iv_map
);
1605 /* The apply should produce an expression tree containing
1606 the uses of the new induction variables. We should be
1607 able to use new_expr instead of the old_name in the newly
1608 generated loop nest. */
1609 if (chrec_contains_undetermined (new_expr
)
1610 || tree_contains_chrecs (new_expr
, NULL
))
1612 codegen_error
= true;
1613 return build_zero_cst (TREE_TYPE (old_name
));
1616 if (TREE_CODE (new_expr
) == SSA_NAME
)
1618 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1619 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1621 codegen_error
= true;
1622 return build_zero_cst (TREE_TYPE (old_name
));
1626 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1628 /* We check all the operands and all of them should dominate the use at
1630 auto_vec
<tree
, 2> new_ssa_names
;
1631 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1634 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1636 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1638 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1639 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1641 codegen_error
= true;
1642 return build_zero_cst (TREE_TYPE (old_name
));
1647 /* Replace the old_name with the new_expr. */
1648 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1652 /* Renames the scalar uses of the statement COPY, using the
1653 substitution map RENAME_MAP, inserting the gimplification code at
1654 GSI_TGT, for the translation REGION, with the original copied
1655 statement in LOOP, and using the induction variable renaming map
1656 IV_MAP. Returns true when something has been renamed. */
1658 bool translate_isl_ast_to_gimple::
1659 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1660 loop_p loop
, vec
<tree
> iv_map
)
1662 bool changed
= false;
1664 if (is_gimple_debug (copy
))
1666 if (gimple_debug_bind_p (copy
))
1667 gimple_debug_bind_reset_value (copy
);
1668 else if (gimple_debug_source_bind_p (copy
))
1678 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1679 print_gimple_stmt (dump_file
, copy
, 0, 0);
1682 use_operand_p use_p
;
1683 ssa_op_iter op_iter
;
1684 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1686 tree old_name
= USE_FROM_PTR (use_p
);
1690 fprintf (dump_file
, "[codegen] renaming old_name = ");
1691 print_generic_expr (dump_file
, old_name
, 0);
1692 fprintf (dump_file
, "\n");
1695 if (TREE_CODE (old_name
) != SSA_NAME
1696 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1700 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1701 old_bb
, unknown_phi
);
1705 tree type_old_name
= TREE_TYPE (old_name
);
1706 tree type_new_expr
= TREE_TYPE (new_expr
);
1710 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1711 print_generic_expr (dump_file
, new_expr
, 0);
1712 fprintf (dump_file
, "\n");
1715 if (type_old_name
!= type_new_expr
1716 || TREE_CODE (new_expr
) != SSA_NAME
)
1718 tree var
= create_tmp_var (type_old_name
, "var");
1720 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1721 new_expr
= fold_convert (type_old_name
, new_expr
);
1724 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1725 gsi_insert_earliest (stmts
);
1728 replace_exp (use_p
, new_expr
);
1733 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1735 if (!new_expr
|| codegen_error_p ())
1740 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1741 print_generic_expr (dump_file
, new_expr
, 0);
1742 fprintf (dump_file
, "\n");
1745 gsi_insert_earliest (stmts
);
1746 replace_exp (use_p
, new_expr
);
1748 if (TREE_CODE (new_expr
) == INTEGER_CST
1749 && is_gimple_assign (copy
))
1751 tree rhs
= gimple_assign_rhs1 (copy
);
1753 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1754 recompute_tree_invariant_for_addr_expr (rhs
);
1757 set_rename (old_name
, new_expr
);
1763 /* Returns a basic block that could correspond to where a constant was defined
1764 in the original code. In the original code OLD_BB had the definition, we
1765 need to find which basic block out of the copies of old_bb, in the new
1766 region, should a definition correspond to if it has to reach BB. */
1768 basic_block
translate_isl_ast_to_gimple::
1769 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1771 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1773 if (!bbs
|| bbs
->is_empty ())
1776 if (1 == bbs
->length ())
1780 basic_block b1
= NULL
, b2
;
1781 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1786 /* BB and B2 are in two unrelated if-clauses. */
1787 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1790 /* Compute the nearest dominator. */
1791 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1798 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1799 determines the kind of phi node. */
1801 tree
translate_isl_ast_to_gimple::
1802 get_new_name (basic_block new_bb
, tree op
,
1803 basic_block old_bb
, phi_node_kind phi_kind
) const
1805 /* For constants the names are the same. */
1806 if (TREE_CODE (op
) != SSA_NAME
)
1809 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1812 /* Return a debug location for OP. */
1817 location_t loc
= UNKNOWN_LOCATION
;
1819 if (TREE_CODE (op
) == SSA_NAME
)
1820 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1824 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1825 the init edge (from outside the loop) and the second one is the back edge
1826 from the same loop. */
1828 std::pair
<edge
, edge
>
1829 get_edges (basic_block bb
)
1831 std::pair
<edge
, edge
> edges
;
1834 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1835 if (bb
->loop_father
!= e
->src
->loop_father
)
1842 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1843 must be found unless they can be POSTPONEd for later. */
1845 bool translate_isl_ast_to_gimple::
1846 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1847 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1850 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1852 basic_block new_bb
= gimple_bb (new_phi
);
1853 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1856 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1857 e
= ibp_new_bb
.first
;
1859 e
= ibp_new_bb
.second
;
1861 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1862 tree new_name
= get_new_name (new_bb
, old_name
,
1863 gimple_bb (old_phi
), loop_phi
);
1866 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1870 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1871 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1872 /* If the phi arg was a function arg, or wasn't defined, just use the
1874 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1877 /* Postpone code gen for later for those back-edges we don't have the
1879 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1881 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1884 /* Either we should add the arg to phi or, we should postpone. */
1890 /* Copy loop phi nodes from BB to NEW_BB. */
1892 bool translate_isl_ast_to_gimple::
1893 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1896 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1899 /* Loop phi nodes should have only two arguments. */
1900 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1902 /* First edge is the init edge and second is the back edge. */
1903 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1905 /* First edge is the init edge and second is the back edge. */
1906 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1908 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1911 gphi
*phi
= psi
.phi ();
1912 tree res
= gimple_phi_result (phi
);
1913 if (virtual_operand_p (res
))
1915 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1918 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1919 tree new_res
= create_new_def_for (res
, new_phi
,
1920 gimple_phi_result_ptr (new_phi
));
1921 set_rename (res
, new_res
);
1922 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1924 update_stmt (new_phi
);
1928 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1929 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
1936 /* Return the init value of PHI, the value coming from outside the loop. */
1939 get_loop_init_value (gphi
*phi
)
1942 loop_p loop
= gimple_bb (phi
)->loop_father
;
1946 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1947 if (e
->src
->loop_father
!= loop
)
1948 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1953 /* Find the init value (the value which comes from outside the loop), of one of
1954 the operands of DEF which is defined by a loop phi. */
1957 find_init_value (gimple
*def
)
1959 if (gimple_code (def
) == GIMPLE_PHI
)
1960 return get_loop_init_value (as_a
<gphi
*> (def
));
1962 if (gimple_vuse (def
))
1966 use_operand_p use_p
;
1967 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1969 tree use
= USE_FROM_PTR (use_p
);
1970 if (TREE_CODE (use
) == SSA_NAME
)
1972 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1980 /* Return the init value, the value coming from outside the loop. */
1983 find_init_value_close_phi (gphi
*phi
)
1985 gcc_assert (gimple_phi_num_args (phi
) == 1);
1986 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1987 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1988 return find_init_value (def
);
1992 tree
translate_isl_ast_to_gimple::
1993 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1994 gimple
*old_close_phi
)
1996 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1997 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1998 basic_block bb
= gimple_bb (stmt
);
1999 if (!bb_in_sese_p (bb
, codegen_region
))
2000 return last_merge_name
;
2002 loop_p loop
= bb
->loop_father
;
2003 if (!loop_in_sese_p (loop
, codegen_region
))
2004 return last_merge_name
;
2006 edge e
= single_exit (loop
);
2008 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2009 return last_merge_name
;
2011 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2012 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2015 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2016 bb
= split_edge (e
);
2018 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2019 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2020 gimple_phi_result_ptr (close_phi
));
2021 set_rename (old_close_phi_name
, res
);
2022 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2023 last_merge_name
= res
;
2025 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2028 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2029 the close phi node PHI. */
2031 bool translate_isl_ast_to_gimple::
2032 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2035 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2036 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2037 if (SSA_NAME
== TREE_CODE (default_value
))
2039 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2040 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2042 default_value_bb
= gimple_bb (stmt
);
2045 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2047 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2048 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2049 tree last_merge_name
= new_close_phi_name
;
2050 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2054 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2056 basic_block new_merge_bb
= merge_e
->src
;
2057 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2060 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2063 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2064 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2065 gimple_phi_result_ptr (merge_phi
));
2066 set_rename (old_close_phi_name
, merge_res
);
2068 edge from_loop
= NULL
, from_default_value
= NULL
;
2071 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2072 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2075 from_default_value
= e
;
2077 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2078 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2079 is contained in another condition. */
2080 if (!from_default_value
|| !from_loop
)
2083 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2084 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2088 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2089 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2092 update_stmt (merge_phi
);
2093 last_merge_name
= merge_res
;
2099 /* Copy all the loop-close phi args from BB to NEW_BB. */
2101 bool translate_isl_ast_to_gimple::
2102 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
, bool postpone
)
2104 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2107 gphi
*old_close_phi
= psi
.phi ();
2108 tree res
= gimple_phi_result (old_close_phi
);
2109 if (virtual_operand_p (res
))
2112 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2113 /* Loop close phi nodes should not be scev_analyzable_p. */
2116 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2117 tree new_res
= create_new_def_for (res
, new_close_phi
,
2118 gimple_phi_result_ptr (new_close_phi
));
2119 set_rename (res
, new_res
);
2121 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2122 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2124 /* Predecessor basic blocks of a loop close phi should have been code
2125 generated before. FIXME: This is fixable by merging PHIs from inner
2126 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2130 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2131 get_loc (old_name
));
2134 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2135 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2138 update_stmt (new_close_phi
);
2140 /* When there is no loop guard around this codegenerated loop, there is no
2141 need to collect the close-phi arg. */
2142 if (merge_points
.is_empty ())
2145 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2146 tree default_value
= find_init_value_close_phi (new_close_phi
);
2148 /* A close phi must come from a loop-phi having a default value. */
2154 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2158 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2159 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2164 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2172 /* Copy loop close phi nodes from BB to NEW_BB. */
2174 bool translate_isl_ast_to_gimple::
2175 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
)
2178 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2180 /* Loop close phi nodes should have only one argument. */
2181 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2183 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2187 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2188 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2189 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2190 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2193 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2194 In this case DOMINATING_PRED = NULL.
2196 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2198 Returns true on successful copy of the args, false otherwise. */
2200 bool translate_isl_ast_to_gimple::
2201 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2202 edge old_bb_dominating_edge
,
2203 edge old_bb_non_dominating_edge
,
2204 gphi
*phi
, gphi
*new_phi
,
2207 basic_block def_pred
[2] = { NULL
, NULL
};
2208 int not_found_bb_index
= -1;
2209 for (int i
= 0; i
< 2; i
++)
2211 /* If the corresponding def_bb could not be found the entry will be
2213 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2214 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2215 gimple_phi_arg_edge (phi
, i
)->src
);
2216 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2217 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2221 /* When non are available bail out. */
2222 if (not_found_bb_index
!= -1)
2224 not_found_bb_index
= i
;
2228 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2229 if (old_bb_dominating_edge
)
2231 if (not_found_bb_index
!= -1)
2234 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2235 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2236 vec
<basic_block
> *bbs
2237 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2239 /* Could not find a mapping. */
2243 basic_block new_pred
= NULL
;
2246 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2248 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2250 /* FIXME: If we have already found new_pred then we have to
2251 disambiguate, bail out for now. */
2254 new_pred
= new_pred1
;
2256 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2258 /* FIXME: If we have already found new_pred then we have to either
2259 it dominates both or we have to disambiguate, bail out. */
2262 new_pred
= new_pred2
;
2269 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2270 gcc_assert (new_non_dominating_edge
);
2271 /* FIXME: Validate each args just like in loop-phis. */
2272 /* By the process of elimination we first insert insert phi-edge for
2273 non-dominating pred which is computed above and then we insert the
2275 int inserted_edge
= 0;
2276 for (; inserted_edge
< 2; inserted_edge
++)
2278 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2279 if (new_non_dominating_edge
== new_bb_pred_edge
)
2281 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2282 new_non_dominating_edge
,
2283 get_loc (old_phi_args
[inserted_edge
]));
2287 if (inserted_edge
== 2)
2290 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2292 edge new_dominating_edge
= NULL
;
2293 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2295 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2296 if (e
!= new_non_dominating_edge
)
2298 new_dominating_edge
= e
;
2299 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2300 new_dominating_edge
,
2301 get_loc (old_phi_args
[inserted_edge
]));
2305 gcc_assert (new_dominating_edge
);
2309 /* Classic diamond structure: both edges are non-dominating. We need to
2310 find one unique edge then the other can be found be elimination. If
2311 any definition (def_pred) dominates both the preds of new_bb then we
2312 bail out. Entries of def_pred maybe NULL, in that case we must
2313 uniquely find pred with help of only one entry. */
2314 edge new_e
[2] = { NULL
, NULL
};
2315 for (int i
= 0; i
< 2; i
++)
2319 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2321 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2324 /* We do not know how to handle the case when def_pred
2325 dominates more than a predecessor. */
2331 gcc_assert (new_e
[0] || new_e
[1]);
2333 /* Find the other edge by process of elimination. */
2334 if (not_found_bb_index
!= -1)
2336 gcc_assert (!new_e
[not_found_bb_index
]);
2337 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2340 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2342 if (new_e
[found_bb_index
] == e
)
2344 new_e
[not_found_bb_index
] = e
;
2348 /* Add edges to phi args. */
2349 for (int i
= 0; i
< 2; i
++)
2350 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2351 get_loc (old_phi_args
[i
]));
2357 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2358 region. If postpone is true and it isn't possible to copy any arg of PHI,
2359 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2360 Returns false if the copying was unsuccessful. */
2362 bool translate_isl_ast_to_gimple::
2363 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2366 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2367 gcc_assert (2 == gimple_phi_num_args (phi
));
2369 basic_block new_bb
= gimple_bb (new_phi
);
2370 loop_p loop
= gimple_bb (phi
)->loop_father
;
2372 basic_block old_bb
= gimple_bb (phi
);
2373 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2377 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2378 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2379 old_bb_non_dominating_edge
= e
;
2381 old_bb_dominating_edge
= e
;
2383 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2384 old_bb_non_dominating_edge
->src
));
2386 tree new_phi_args
[2];
2387 tree old_phi_args
[2];
2389 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2391 tree old_name
= gimple_phi_arg_def (phi
, i
);
2392 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2393 old_phi_args
[i
] = old_name
;
2396 new_phi_args
[i
] = new_name
;
2400 /* If the phi-arg was a parameter. */
2401 if (vec_find (region
->params
, old_name
) != -1)
2403 new_phi_args
[i
] = old_name
;
2407 "[codegen] parameter argument to phi, new_expr: ");
2408 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2409 fprintf (dump_file
, "\n");
2414 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2415 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2416 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2422 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2423 if (is_gimple_reg (old_name
)
2424 && scev_analyzable_p (old_name
, region
->region
))
2427 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2428 new_bb
, old_bb
, iv_map
);
2429 if (codegen_error_p ())
2432 gcc_assert (new_expr
);
2436 "[codegen] scev analyzeable, new_expr: ");
2437 print_generic_expr (dump_file
, new_expr
, 0);
2438 fprintf (dump_file
, "\n");
2440 gsi_insert_earliest (stmts
);
2441 new_phi_args
[i
] = new_expr
;
2445 /* Postpone code gen for later for back-edges. */
2446 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2450 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2451 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2454 new_phi_args
[i
] = NULL_TREE
;
2458 /* Either we should add the arg to phi or, we should postpone. */
2462 /* If none of the args have been determined in the first stage then wait until
2464 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2467 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2468 old_bb_dominating_edge
,
2469 old_bb_non_dominating_edge
,
2470 phi
, new_phi
, new_bb
);
2473 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2474 containing phi nodes coming from two predecessors, and none of them are back
2477 bool translate_isl_ast_to_gimple::
2478 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2481 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2484 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2487 /* Cond phi nodes should have exactly two arguments. */
2488 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2490 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2493 gphi
*phi
= psi
.phi ();
2494 tree res
= gimple_phi_result (phi
);
2495 if (virtual_operand_p (res
))
2497 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2498 /* Cond phi nodes should not be scev_analyzable_p. */
2501 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2502 tree new_res
= create_new_def_for (res
, new_phi
,
2503 gimple_phi_result_ptr (new_phi
));
2504 set_rename (res
, new_res
);
2506 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2509 update_stmt (new_phi
);
2515 /* Return true if STMT should be copied from region to the new code-generated
2516 region. LABELs, CONDITIONS, induction-variables and region parameters need
2520 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2522 /* Do not copy labels or conditions. */
2523 if (gimple_code (stmt
) == GIMPLE_LABEL
2524 || gimple_code (stmt
) == GIMPLE_COND
)
2528 /* Do not copy induction variables. */
2529 if (is_gimple_assign (stmt
)
2530 && (lhs
= gimple_assign_lhs (stmt
))
2531 && TREE_CODE (lhs
) == SSA_NAME
2532 && is_gimple_reg (lhs
)
2533 && scev_analyzable_p (lhs
, region
->region
))
2536 /* Do not copy parameters that have been generated in the header of the
2538 if (is_gimple_assign (stmt
)
2539 && (lhs
= gimple_assign_lhs (stmt
))
2540 && TREE_CODE (lhs
) == SSA_NAME
2541 && region
->parameter_rename_map
->get(lhs
))
2547 /* Create new names for all the definitions created by COPY and add replacement
2548 mappings for each new name. */
2550 void translate_isl_ast_to_gimple::
2551 set_rename_for_each_def (gimple
*stmt
)
2553 def_operand_p def_p
;
2554 ssa_op_iter op_iter
;
2555 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2557 tree old_name
= DEF_FROM_PTR (def_p
);
2558 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2559 set_rename (old_name
, new_name
);
2563 /* Duplicates the statements of basic block BB into basic block NEW_BB
2564 and compute the new induction variables according to the IV_MAP. */
2566 bool translate_isl_ast_to_gimple::
2567 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2570 /* Iterator poining to the place where new statement (s) will be inserted. */
2571 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2573 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2576 gimple
*stmt
= gsi_stmt (gsi
);
2577 if (!should_copy_to_new_region (stmt
, region
))
2580 /* Create a new copy of STMT and duplicate STMT's virtual
2582 gimple
*copy
= gimple_copy (stmt
);
2583 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2587 fprintf (dump_file
, "[codegen] inserting statement: ");
2588 print_gimple_stmt (dump_file
, copy
, 0, 0);
2591 maybe_duplicate_eh_stmt (copy
, stmt
);
2592 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2594 /* Crete new names for each def in the copied stmt. */
2595 set_rename_for_each_def (copy
);
2597 loop_p loop
= bb
->loop_father
;
2598 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2600 fold_stmt_inplace (&gsi_tgt
);
2601 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2604 if (codegen_error_p ())
2607 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2609 use_operand_p use_p
;
2610 if (!is_gimple_debug (copy
))
2611 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2613 tree old_name
= USE_FROM_PTR (use_p
);
2615 if (TREE_CODE (old_name
) != SSA_NAME
2616 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2619 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2623 replace_exp (use_p
, *new_expr
);
2633 /* Given a basic block containing close-phi it returns the new basic block where
2634 to insert a copy of the close-phi nodes. All the uses in close phis should
2635 come from a single loop otherwise it returns NULL. */
2637 edge
translate_isl_ast_to_gimple::
2638 edge_for_new_close_phis (basic_block bb
)
2640 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2641 of close phi in the original code and then find the mapping of basic block
2642 defining that variable. If there are multiple close-phis and they are
2643 defined in different loops (in the original or in the new code) because of
2644 loop splitting, then we bail out. */
2645 loop_p new_loop
= NULL
;
2646 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2649 gphi
*phi
= psi
.phi ();
2650 tree name
= gimple_phi_arg_def (phi
, 0);
2651 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2653 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2654 if (!bbs
|| bbs
->length () != 1)
2655 /* This is one of the places which shows preserving original structure
2656 is not always possible, as we may need to insert close PHI for a loop
2657 where the latch does not have any mapping, or the mapping is
2662 new_loop
= (*bbs
)[0]->loop_father
;
2663 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2670 return single_exit (new_loop
);
2673 /* Copies BB and includes in the copied BB all the statements that can
2674 be reached following the use-def chains from the memory accesses,
2675 and returns the next edge following this new block. */
2677 edge
translate_isl_ast_to_gimple::
2678 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2680 int num_phis
= number_of_phi_nodes (bb
);
2682 if (region
->copied_bb_map
->get (bb
))
2684 /* FIXME: we should be able to handle phi nodes with args coming from
2685 outside the region. */
2688 codegen_error
= true;
2693 basic_block new_bb
= NULL
;
2694 if (bb_contains_loop_close_phi_nodes (bb
))
2697 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2700 edge e
= edge_for_new_close_phis (bb
);
2703 codegen_error
= true;
2707 basic_block phi_bb
= e
->dest
;
2709 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2710 phi_bb
= split_edge (e
);
2712 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2713 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2715 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2717 codegen_error
= true;
2724 new_bb
= split_edge (next_e
);
2728 new_bb
= split_edge (next_e
);
2729 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2731 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2733 /* At this point we are unable to codegenerate by still preserving the SSA
2734 structure because maybe the loop is completely unrolled and the PHIs
2735 and cross-bb scalar dependencies are untrackable w.r.t. the original
2736 code. See gfortran.dg/graphite/pr29832.f90. */
2737 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2739 codegen_error
= true;
2743 /* In case isl did some loop peeling, like this:
2746 for (int c1 = 1; c1 <= 5; c1 += 1) {
2751 there should be no loop-phi nodes in S_8(0).
2753 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2754 values of all scalar variables: for the moment we instantiate only
2755 SCEV analyzable expressions on the iteration domain, and we need to
2756 extend that to reductions that cannot be analyzed by SCEV. */
2757 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2759 codegen_error
= true;
2764 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2766 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2768 codegen_error
= true;
2772 else if (num_phis
> 0)
2775 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2778 basic_block phi_bb
= single_pred (new_bb
);
2779 loop_p loop_father
= new_bb
->loop_father
;
2781 /* Move back until we find the block with two predecessors. */
2782 while (single_pred_p (phi_bb
))
2783 phi_bb
= single_pred_edge (phi_bb
)->src
;
2785 /* If a corresponding merge-point was not found, then abort codegen. */
2786 if (phi_bb
->loop_father
!= loop_father
2787 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2788 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2790 codegen_error
= true;
2797 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2798 bb
->index
, new_bb
->index
);
2800 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2802 copied_bbs
->safe_push (new_bb
);
2805 vec
<basic_block
> bbs
;
2807 bbs
.safe_push (new_bb
);
2808 region
->copied_bb_map
->put (bb
, bbs
);
2811 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2813 codegen_error
= true;
2817 return single_succ_edge (new_bb
);
2820 /* Patch the missing arguments of the phi nodes. */
2822 void translate_isl_ast_to_gimple::
2823 translate_pending_phi_nodes ()
2827 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2829 gphi
*old_phi
= rename
->first
;
2830 gphi
*new_phi
= rename
->second
;
2831 basic_block old_bb
= gimple_bb (old_phi
);
2832 basic_block new_bb
= gimple_bb (new_phi
);
2834 /* First edge is the init edge and second is the back edge. */
2835 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2836 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2840 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2841 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2844 auto_vec
<tree
, 1> iv_map
;
2845 if (bb_contains_loop_phi_nodes (new_bb
))
2846 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2848 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2849 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2851 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2855 fprintf (dump_file
, "[codegen] to new-phi: ");
2856 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2858 if (codegen_error_p ())
2863 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2865 void translate_isl_ast_to_gimple::
2866 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2868 sese_info_p region
= scop
->scop_info
;
2869 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2870 gcc_assert (nb_parameters
== region
->params
.length ());
2872 for (i
= 0; i
< nb_parameters
; i
++)
2874 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2876 ip
[tmp_id
] = region
->params
[i
];
2881 /* Generates a build, which specifies the constraints on the parameters. */
2883 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2884 generate_isl_context (scop_p scop
)
2886 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2887 return isl_ast_build_from_context (context_isl
);
2890 /* This method is executed before the construction of a for node. */
2892 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2894 isl_union_map
*dependences
= (isl_union_map
*) user
;
2895 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2896 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2897 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2898 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2899 for_info
->is_parallelizable
=
2900 !carries_deps (schedule
, dependences
, dimension
);
2901 isl_union_map_free (schedule
);
2902 isl_space_free (schedule_space
);
2903 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2907 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
2909 /* Generate isl AST from schedule of SCOP. */
2911 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2912 scop_to_isl_ast (scop_p scop
)
2914 gcc_assert (scop
->transformed_schedule
);
2916 /* Set the separate option to reduce control flow overhead. */
2917 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2918 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2919 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2921 if (flag_loop_parallelize_all
)
2923 scop_get_dependences (scop
);
2925 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2929 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2930 (context_isl
, schedule
);
2931 isl_ast_build_free (context_isl
);
2936 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2938 int translate_isl_ast_to_gimple::
2939 get_max_schedule_dimensions (scop_p scop
)
2943 int schedule_dims
= 0;
2945 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2947 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
2948 if (pbb_schedule_dims
> schedule_dims
)
2949 schedule_dims
= pbb_schedule_dims
;
2952 return schedule_dims
;
2955 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2957 For schedules with different dimensionality, the isl AST generator can not
2958 define an order and will just randomly choose an order. The solution to this
2959 problem is to extend all schedules to the maximal number of schedule
2960 dimensions (using '0's for the remaining values). */
2962 __isl_give isl_map
*translate_isl_ast_to_gimple::
2963 extend_schedule (__isl_take isl_map
*schedule
, int nb_schedule_dims
)
2965 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
2967 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
2969 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
2971 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
2974 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
2976 isl_val_free (zero
);
2980 /* Generates a schedule, which specifies an order used to
2981 visit elements in a domain. */
2983 __isl_give isl_union_map
*translate_isl_ast_to_gimple::
2984 generate_isl_schedule (scop_p scop
)
2986 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
2989 isl_union_map
*schedule_isl
=
2990 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
2992 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2994 /* Dead code elimination: when the domain of a PBB is empty,
2995 don't generate code for the PBB. */
2996 if (isl_set_is_empty (pbb
->domain
))
2999 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3000 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3001 isl_set_copy (pbb
->domain
));
3002 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3003 bb_schedule
= isl_map_coalesce (bb_schedule
);
3005 = isl_union_map_union (schedule_isl
,
3006 isl_union_map_from_map (bb_schedule
));
3007 schedule_isl
= isl_union_map_coalesce (schedule_isl
);
3009 return schedule_isl
;
3012 /* Set the separate option for all dimensions.
3013 This helps to reduce control overhead. */
3015 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
3016 set_options (__isl_take isl_ast_build
*control
,
3017 __isl_keep isl_union_map
*schedule
)
3019 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3020 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3022 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3023 isl_union_set
*range
=
3024 isl_union_set_from_set (isl_set_universe (range_space
));
3025 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3026 domain
= isl_union_set_universe (domain
);
3027 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3028 return isl_ast_build_set_options (control
, options
);
3031 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3033 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
3034 scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3036 /* Generate loop upper bounds that consist of the current loop iterator, an
3037 operator (< or <=) and an expression not involving the iterator. If this
3038 option is not set, then the current loop iterator may appear several times
3039 in the upper bound. See the isl manual for more details. */
3040 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3042 add_parameters_to_ivs_params (scop
, ip
);
3043 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3044 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3045 context_isl
= set_options (context_isl
, schedule_isl
);
3046 if (flag_loop_parallelize_all
)
3048 isl_union_map
*dependence
= scop_get_dependences (scop
);
3050 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3054 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3058 isl_schedule_free (scop
->schedule
);
3059 scop
->schedule
= NULL
;
3062 isl_ast_build_free (context_isl
);
3067 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
3068 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
3071 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
3072 gimple_stmt_iterator
*gsi
)
3074 if (!defined_in_sese_p (tr
, region
->region
))
3078 use_operand_p use_p
;
3079 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
3081 tree use_tr
= USE_FROM_PTR (use_p
);
3083 /* Do not copy parameters that have been generated in the header of the
3085 if (region
->parameter_rename_map
->get(use_tr
))
3088 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
3092 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
3095 gimple
*copy
= gimple_copy (def_stmt
);
3096 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
3098 /* Create new names for all the definitions created by COPY and
3099 add replacement mappings for each new name. */
3100 def_operand_p def_p
;
3101 ssa_op_iter op_iter
;
3102 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
3104 tree old_name
= DEF_FROM_PTR (def_p
);
3105 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
3106 region
->parameter_rename_map
->put(old_name
, new_name
);
3113 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
3115 /* For all the parameters which definitino is in the if_region->false_region,
3116 insert code on true_region (if_region->true_region->entry). */
3120 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
3122 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
3124 // If def is not in region.
3125 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
3127 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
3131 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
3132 Return true if code generation succeeded. */
3135 graphite_regenerate_ast_isl (scop_p scop
)
3137 sese_info_p region
= scop
->scop_info
;
3138 translate_isl_ast_to_gimple
t (region
);
3140 ifsese if_region
= NULL
;
3141 isl_ast_node
*root_node
;
3144 timevar_push (TV_GRAPHITE_CODE_GEN
);
3145 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3146 t
.add_parameters_to_ivs_params (scop
, ip
);
3147 root_node
= t
.scop_to_isl_ast (scop
);
3149 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3154 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3155 fprintf (dump_file
, "[scheduler] original schedule:\n");
3156 print_isl_schedule (dump_file
, scop
->original_schedule
);
3157 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
3158 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
3160 fprintf (dump_file
, "[scheduler] original ast:\n");
3161 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
3163 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
3164 print_isl_ast (dump_file
, root_node
);
3167 recompute_all_dominators ();
3170 if_region
= move_sese_in_condition (region
);
3171 region
->if_region
= if_region
;
3172 recompute_all_dominators ();
3174 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3176 /* Copy all the parameters which are defined in the region. */
3177 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3179 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3180 basic_block bb
= split_edge (e
);
3182 /* Update the true_region exit edge. */
3183 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3185 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3186 if (t
.codegen_error_p ())
3189 fprintf (dump_file
, "codegen error: "
3190 "reverting back to the original code.\n");
3191 set_ifsese_condition (if_region
, integer_zero_node
);
3195 t
.translate_pending_phi_nodes ();
3196 if (!t
.codegen_error_p ())
3198 sese_insert_phis_for_liveouts (region
,
3199 if_region
->region
->region
.exit
->src
,
3200 if_region
->false_region
->region
.exit
,
3201 if_region
->true_region
->region
.exit
);
3202 mark_virtual_operands_for_renaming (cfun
);
3203 update_ssa (TODO_update_ssa
);
3208 recompute_all_dominators ();
3212 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
3217 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3218 " pending phis, reverting back to the original code.\n");
3219 set_ifsese_condition (if_region
, integer_zero_node
);
3223 free (if_region
->true_region
);
3224 free (if_region
->region
);
3227 ivs_params_clear (ip
);
3228 isl_ast_node_free (root_node
);
3229 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3234 int num_no_dependency
= 0;
3236 FOR_EACH_LOOP (loop
, 0)
3237 if (loop
->can_be_parallel
)
3238 num_no_dependency
++;
3240 fprintf (dump_file
, "%d loops carried no dependency.\n",
3244 return !t
.codegen_error_p ();
3247 #endif /* HAVE_isl */