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"
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 /* Set the "separate" option for the schedule node. */
120 static isl_schedule_node
*
121 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
126 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
129 /* Set the "separate" option unless it is set earlier to another option. */
130 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
131 == isl_ast_loop_default
)
132 return isl_schedule_node_band_member_set_ast_loop_type
133 (node
, 0, isl_ast_loop_separate
);
138 /* Print SCHEDULE under an AST form on file F. */
141 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
143 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
144 isl_ast_build
*context
= isl_ast_build_from_context (set
);
146 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
147 isl_ast_build_free (context
);
148 print_isl_ast (f
, ast
);
149 isl_ast_node_free (ast
);
153 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
155 print_schedule_ast (stderr
, s
, scop
);
166 class translate_isl_ast_to_gimple
169 translate_isl_ast_to_gimple (sese_info_p r
)
170 : region (r
), codegen_error (false) { }
171 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
173 edge
translate_isl_ast_node_for (loop_p context_loop
,
174 __isl_keep isl_ast_node
*node
,
175 edge next_e
, ivs_params
&ip
);
176 edge
translate_isl_ast_for_loop (loop_p context_loop
,
177 __isl_keep isl_ast_node
*node_for
,
179 tree type
, tree lb
, tree ub
,
181 edge
translate_isl_ast_node_if (loop_p context_loop
,
182 __isl_keep isl_ast_node
*node
,
183 edge next_e
, ivs_params
&ip
);
184 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
185 edge next_e
, ivs_params
&ip
);
186 edge
translate_isl_ast_node_block (loop_p context_loop
,
187 __isl_keep isl_ast_node
*node
,
188 edge next_e
, ivs_params
&ip
);
189 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
191 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
193 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
195 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
197 tree
gcc_expression_from_isl_expression (tree type
,
198 __isl_take isl_ast_expr
*,
200 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
201 __isl_keep isl_ast_expr
*expr_id
,
203 tree
gcc_expression_from_isl_expr_int (tree type
,
204 __isl_take isl_ast_expr
*expr
);
205 tree
gcc_expression_from_isl_expr_op (tree type
,
206 __isl_take isl_ast_expr
*expr
,
208 struct loop
*graphite_create_new_loop (edge entry_edge
,
209 __isl_keep isl_ast_node
*node_for
,
210 loop_p outer
, tree type
,
211 tree lb
, tree ub
, ivs_params
&ip
);
212 edge
graphite_create_new_loop_guard (edge entry_edge
,
213 __isl_keep isl_ast_node
*node_for
,
215 tree
*lb
, tree
*ub
, ivs_params
&ip
);
216 edge
graphite_create_new_guard (edge entry_edge
,
217 __isl_take isl_ast_expr
*if_cond
,
219 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
220 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
222 void translate_pending_phi_nodes (void);
223 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
224 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
226 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
228 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
229 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
230 tree
get_rename (basic_block new_bb
, tree old_name
,
231 basic_block old_bb
, phi_node_kind
) const;
232 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
233 basic_block new_bb
, basic_block old_bb
,
235 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
236 tree
get_new_name (basic_block new_bb
, tree op
,
237 basic_block old_bb
, phi_node_kind
) const;
238 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
239 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
240 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
242 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
243 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
245 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
246 gimple
*old_close_phi
);
247 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
249 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
250 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
252 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
254 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
256 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
258 edge
edge_for_new_close_phis (basic_block bb
);
259 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
260 edge old_bb_dominating_edge
,
261 edge old_bb_non_dominating_edge
,
262 gphi
*phi
, gphi
*new_phi
,
264 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
265 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
266 void set_rename (tree old_name
, tree expr
);
267 void set_rename_for_each_def (gimple
*stmt
);
268 void gsi_insert_earliest (gimple_seq seq
);
269 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
270 bool codegen_error_p () const { return codegen_error
; }
271 bool is_constant (tree op
) const
273 return TREE_CODE (op
) == INTEGER_CST
274 || TREE_CODE (op
) == REAL_CST
275 || TREE_CODE (op
) == COMPLEX_CST
276 || TREE_CODE (op
) == VECTOR_CST
;
280 /* The region to be translated. */
283 /* This flag is set when an error occurred during the translation of isl AST
287 /* A vector of all the edges at if_condition merge points. */
288 auto_vec
<edge
, 2> merge_points
;
291 /* Return the tree variable that corresponds to the given isl ast identifier
292 expression (an isl_ast_expr of type isl_ast_expr_id).
294 FIXME: We should replace blind conversion of id's type with derivation
295 of the optimal type when we get the corresponding isl support. Blindly
296 converting type sizes may be problematic when we switch to smaller
299 tree
translate_isl_ast_to_gimple::
300 gcc_expression_from_isl_ast_expr_id (tree type
,
301 __isl_take isl_ast_expr
*expr_id
,
304 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
305 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
306 std::map
<isl_id
*, tree
>::iterator res
;
307 res
= ip
.find (tmp_isl_id
);
308 isl_id_free (tmp_isl_id
);
309 gcc_assert (res
!= ip
.end () &&
310 "Could not map isl_id to tree expression");
311 isl_ast_expr_free (expr_id
);
312 tree t
= res
->second
;
313 tree
*val
= region
->parameter_rename_map
->get(t
);
317 return fold_convert (type
, *val
);
320 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
323 tree
translate_isl_ast_to_gimple::
324 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
326 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
327 isl_val
*val
= isl_ast_expr_get_val (expr
);
329 mpz_init (val_mpz_t
);
331 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
334 res
= gmp_cst_to_tree (type
, val_mpz_t
);
336 isl_ast_expr_free (expr
);
337 mpz_clear (val_mpz_t
);
341 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
344 tree
translate_isl_ast_to_gimple::
345 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
347 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
348 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
349 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
350 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
352 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
353 isl_ast_expr_free (expr
);
355 if (codegen_error_p ())
361 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
364 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
367 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
370 /* As isl operates on arbitrary precision numbers, we may end up with
371 division by 2^64 that is folded to 0. */
372 if (integer_zerop (tree_rhs_expr
))
374 codegen_error
= true;
377 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
379 case isl_ast_op_pdiv_q
:
380 /* As isl operates on arbitrary precision numbers, we may end up with
381 division by 2^64 that is folded to 0. */
382 if (integer_zerop (tree_rhs_expr
))
384 codegen_error
= true;
387 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
389 case isl_ast_op_zdiv_r
:
390 case isl_ast_op_pdiv_r
:
391 /* As isl operates on arbitrary precision numbers, we may end up with
392 division by 2^64 that is folded to 0. */
393 if (integer_zerop (tree_rhs_expr
))
395 codegen_error
= true;
398 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
400 case isl_ast_op_fdiv_q
:
401 /* As isl operates on arbitrary precision numbers, we may end up with
402 division by 2^64 that is folded to 0. */
403 if (integer_zerop (tree_rhs_expr
))
405 codegen_error
= true;
408 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
411 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
412 tree_lhs_expr
, tree_rhs_expr
);
415 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
418 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
421 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
424 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
427 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
430 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
437 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
440 tree
translate_isl_ast_to_gimple::
441 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
443 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
444 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
445 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
446 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
447 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
448 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
449 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
450 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
451 isl_ast_expr_free (expr
);
453 if (codegen_error_p ())
456 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
459 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
462 tree
translate_isl_ast_to_gimple::
463 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
465 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
466 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
467 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
468 isl_ast_expr_free (expr
);
469 return codegen_error_p () ? NULL_TREE
470 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
473 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
474 to a GCC expression tree of type TYPE. */
476 tree
translate_isl_ast_to_gimple::
477 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
479 enum tree_code op_code
;
480 switch (isl_ast_expr_get_op_type (expr
))
493 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
494 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
496 if (codegen_error_p ())
498 isl_ast_expr_free (expr
);
503 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
505 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
506 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
508 if (codegen_error_p ())
510 isl_ast_expr_free (expr
);
514 res
= fold_build2 (op_code
, type
, res
, t
);
516 isl_ast_expr_free (expr
);
520 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
523 tree
translate_isl_ast_to_gimple::
524 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
527 if (codegen_error_p ())
529 isl_ast_expr_free (expr
);
533 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
534 switch (isl_ast_expr_get_op_type (expr
))
536 /* These isl ast expressions are not supported yet. */
537 case isl_ast_op_error
:
538 case isl_ast_op_call
:
539 case isl_ast_op_and_then
:
540 case isl_ast_op_or_else
:
545 return nary_op_to_tree (type
, expr
, ip
);
551 case isl_ast_op_pdiv_q
:
552 case isl_ast_op_pdiv_r
:
553 case isl_ast_op_fdiv_q
:
554 case isl_ast_op_zdiv_r
:
562 return binary_op_to_tree (type
, expr
, ip
);
564 case isl_ast_op_minus
:
565 return unary_op_to_tree (type
, expr
, ip
);
567 case isl_ast_op_cond
:
568 case isl_ast_op_select
:
569 return ternary_op_to_tree (type
, expr
, ip
);
578 /* Converts an isl AST expression E back to a GCC expression tree of
581 tree
translate_isl_ast_to_gimple::
582 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
585 if (codegen_error_p ())
587 isl_ast_expr_free (expr
);
591 switch (isl_ast_expr_get_type (expr
))
593 case isl_ast_expr_id
:
594 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
596 case isl_ast_expr_int
:
597 return gcc_expression_from_isl_expr_int (type
, expr
);
599 case isl_ast_expr_op
:
600 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
609 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
610 induction variable for the new LOOP. New LOOP is attached to CFG
611 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
612 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
613 isl's scattering name to the induction variable created for the
614 loop of STMT. The new induction variable is inserted in the NEWIVS
615 vector and is of type TYPE. */
617 struct loop
*translate_isl_ast_to_gimple::
618 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
619 loop_p outer
, tree type
, tree lb
, tree ub
,
622 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
623 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
625 /* To fail code generation, we generate wrong code until we discard it. */
626 if (codegen_error_p ())
627 stride
= integer_zero_node
;
629 tree ivvar
= create_tmp_var (type
, "graphite_IV");
630 tree iv
, iv_after_increment
;
631 loop_p loop
= create_empty_loop_on_edge
632 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
633 outer
? outer
: entry_edge
->src
->loop_father
);
635 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
636 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
637 std::map
<isl_id
*, tree
>::iterator res
;
640 isl_id_free (res
->first
);
642 isl_ast_expr_free (for_iterator
);
646 /* Create the loop for a isl_ast_node_for.
648 - NEXT_E is the edge where new generated code should be attached. */
650 edge
translate_isl_ast_to_gimple::
651 translate_isl_ast_for_loop (loop_p context_loop
,
652 __isl_keep isl_ast_node
*node_for
, edge next_e
,
653 tree type
, tree lb
, tree ub
,
656 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
657 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
659 edge last_e
= single_exit (loop
);
660 edge to_body
= single_succ_edge (loop
->header
);
661 basic_block after
= to_body
->dest
;
663 /* Translate the body of the loop. */
664 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
665 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
666 isl_ast_node_free (for_body
);
668 /* Early return if we failed to translate loop body. */
669 if (!next_e
|| codegen_error_p ())
672 if (next_e
->dest
!= after
)
673 redirect_edge_succ_nodup (next_e
, after
);
674 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
676 if (flag_loop_parallelize_all
)
678 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
680 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
681 loop
->can_be_parallel
= for_info
->is_parallelizable
;
689 /* We use this function to get the upper bound because of the form,
690 which is used by isl to represent loops:
692 for (iterator = init; cond; iterator += inc)
700 The loop condition is an arbitrary expression, which contains the
701 current loop iterator.
703 (e.g. iterator + 3 < B && C > iterator + A)
705 We have to know the upper bound of the iterator to generate a loop
706 in Gimple form. It can be obtained from the special representation
707 of the loop condition, which is generated by isl,
708 if the ast_build_atomic_upper_bound option is set. In this case,
709 isl generates a loop condition that consists of the current loop
710 iterator, + an operator (< or <=) and an expression not involving
711 the iterator, which is processed and returned by this function.
713 (e.g iterator <= upper-bound-expression-without-iterator) */
715 static __isl_give isl_ast_expr
*
716 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
718 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
719 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
720 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
722 switch (isl_ast_expr_get_op_type (for_cond
))
725 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
730 /* (iterator < ub) => (iterator <= ub - 1). */
732 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
733 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
734 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
741 isl_ast_expr_free (for_cond
);
745 /* All loops generated by create_empty_loop_on_edge have the form of
752 } while (lower bound < upper bound);
754 We create a new if region protecting the loop to be executed, if
755 the execution count is zero (lower bound > upper bound). */
757 edge
translate_isl_ast_to_gimple::
758 graphite_create_new_loop_guard (edge entry_edge
,
759 __isl_keep isl_ast_node
*node_for
, tree
*type
,
760 tree
*lb
, tree
*ub
, ivs_params
&ip
)
762 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
767 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
768 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
769 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
771 /* To fail code generation, we generate wrong code until we discard it. */
772 if (codegen_error_p ())
773 *lb
= integer_zero_node
;
775 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
776 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
778 /* To fail code generation, we generate wrong code until we discard it. */
779 if (codegen_error_p ())
780 *ub
= integer_zero_node
;
782 /* When ub is simply a constant or a parameter, use lb <= ub. */
783 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
784 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
787 tree one
= (POINTER_TYPE_P (*type
)
788 ? convert_to_ptrofftype (integer_one_node
)
789 : fold_convert (*type
, integer_one_node
));
790 /* Adding +1 and using LT_EXPR helps with loop latches that have a
791 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
792 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
793 is true, even if we do not want this. However lb < ub + 1 is false,
795 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
796 : PLUS_EXPR
, *type
, *ub
, one
);
798 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
801 if (integer_onep (cond_expr
))
802 exit_edge
= entry_edge
;
804 exit_edge
= create_empty_if_region_on_edge (entry_edge
,
805 unshare_expr (cond_expr
));
810 /* Translates an isl_ast_node_for to Gimple. */
812 edge
translate_isl_ast_to_gimple::
813 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
814 edge next_e
, ivs_params
&ip
)
816 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
818 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
821 if (last_e
== next_e
)
823 /* There was no guard generated. */
824 last_e
= single_succ_edge (split_edge (last_e
));
826 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
831 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
832 merge_points
.safe_push (last_e
);
834 last_e
= single_succ_edge (split_edge (last_e
));
835 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
840 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
841 variables of the loops around GBB in SESE.
843 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
844 chrec, we could consider using a map<int, tree> that maps loop ids to the
845 corresponding tree expressions. */
847 void translate_isl_ast_to_gimple::
848 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
849 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
852 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
853 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
855 isl_ast_expr
*arg_expr
;
856 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
858 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
860 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
861 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
863 /* To fail code generation, we generate wrong code until we discard it. */
864 if (codegen_error_p ())
865 t
= integer_zero_node
;
867 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
868 iv_map
[old_loop
->num
] = t
;
872 /* Translates an isl_ast_node_user to Gimple.
874 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
876 edge
translate_isl_ast_to_gimple::
877 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
878 edge next_e
, ivs_params
&ip
)
880 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
882 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
883 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
884 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
886 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
887 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
890 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
892 isl_ast_expr_free (name_expr
);
893 isl_id_free (name_id
);
895 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
896 "The entry block should not even appear within a scop");
898 const int nb_loops
= number_of_loops (cfun
);
900 iv_map
.create (nb_loops
);
901 iv_map
.safe_grow_cleared (nb_loops
);
903 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
904 isl_ast_expr_free (user_expr
);
906 basic_block old_bb
= GBB_BB (gbb
);
910 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
911 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
912 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
916 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
920 if (codegen_error_p ())
925 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
926 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
932 /* Translates an isl_ast_node_block to Gimple. */
934 edge
translate_isl_ast_to_gimple::
935 translate_isl_ast_node_block (loop_p context_loop
,
936 __isl_keep isl_ast_node
*node
,
937 edge next_e
, ivs_params
&ip
)
939 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
940 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
942 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
944 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
945 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
946 isl_ast_node_free (tmp_node
);
948 isl_ast_node_list_free (node_list
);
952 /* Creates a new if region corresponding to isl's cond. */
954 edge
translate_isl_ast_to_gimple::
955 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
959 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
960 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
962 /* To fail code generation, we generate wrong code until we discard it. */
963 if (codegen_error_p ())
964 cond_expr
= integer_zero_node
;
966 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
970 /* Translates an isl_ast_node_if to Gimple. */
972 edge
translate_isl_ast_to_gimple::
973 translate_isl_ast_node_if (loop_p context_loop
,
974 __isl_keep isl_ast_node
*node
,
975 edge next_e
, ivs_params
&ip
)
977 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
978 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
979 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
980 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
981 merge_points
.safe_push (last_e
);
983 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
984 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
985 isl_ast_node_free (then_node
);
987 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
988 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
989 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
990 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
992 isl_ast_node_free (else_node
);
996 /* Translates an isl AST node NODE to GCC representation in the
997 context of a SESE. */
999 edge
translate_isl_ast_to_gimple::
1000 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1001 edge next_e
, ivs_params
&ip
)
1003 if (codegen_error_p ())
1006 switch (isl_ast_node_get_type (node
))
1008 case isl_ast_node_error
:
1011 case isl_ast_node_for
:
1012 return translate_isl_ast_node_for (context_loop
, node
,
1015 case isl_ast_node_if
:
1016 return translate_isl_ast_node_if (context_loop
, node
,
1019 case isl_ast_node_user
:
1020 return translate_isl_ast_node_user (node
, next_e
, ip
);
1022 case isl_ast_node_block
:
1023 return translate_isl_ast_node_block (context_loop
, node
,
1026 case isl_ast_node_mark
:
1028 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1029 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1030 isl_ast_node_free (n
);
1039 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1040 at the exit of loop which takes one argument that is the last value of the
1041 variable being used out of the loop. */
1044 bb_contains_loop_close_phi_nodes (basic_block bb
)
1046 return single_pred_p (bb
)
1047 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1050 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1051 header containing phi nodes which has one init-edge and one back-edge. */
1054 bb_contains_loop_phi_nodes (basic_block bb
)
1056 if (EDGE_COUNT (bb
->preds
) != 2)
1059 unsigned depth
= loop_depth (bb
->loop_father
);
1061 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1063 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1064 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1067 /* When one of the edges correspond to the same loop father and other
1069 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1070 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1073 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1074 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1080 /* Check if USE is defined in a basic block from where the definition of USE can
1081 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1084 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1086 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1089 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1090 if (bb_contains_loop_close_phi_nodes (bb
))
1093 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1094 basic_block def_bb
= gimple_bb (def
);
1096 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1099 /* Return the number of phi nodes in BB. */
1102 number_of_phi_nodes (basic_block bb
)
1105 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1111 /* Returns true if BB uses name in one of its PHIs. */
1114 phi_uses_name (basic_block bb
, tree name
)
1116 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1119 gphi
*phi
= psi
.phi ();
1120 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1122 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1123 if (use_arg
== name
)
1130 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1131 definition should flow into use, and the use should respect the loop-closed
1134 bool translate_isl_ast_to_gimple::
1135 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1136 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1138 /* The def of the rename must either dominate the uses or come from a
1139 back-edge. Also the def must respect the loop closed ssa form. */
1140 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1144 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1145 print_generic_expr (dump_file
, rename
, 0);
1146 fprintf (dump_file
, "\n");
1151 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1154 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1156 /* The loop-header dominates the loop-body. */
1157 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1160 /* RENAME would be used in loop-phi. */
1161 gcc_assert (number_of_phi_nodes (use_bb
));
1163 /* For definitions coming from back edges, we should check that
1164 old_name is used in a loop PHI node.
1165 FIXME: Verify if this is true. */
1166 if (phi_uses_name (old_bb
, old_name
))
1172 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1173 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1175 tree
translate_isl_ast_to_gimple::
1176 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1177 phi_node_kind phi_kind
) const
1179 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1180 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1182 if (!renames
|| renames
->is_empty ())
1185 if (1 == renames
->length ())
1187 tree rename
= (*renames
)[0];
1188 if (TREE_CODE (rename
) == SSA_NAME
)
1190 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1191 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1192 && (phi_kind
== close_phi
1193 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1198 if (is_constant (rename
))
1204 /* More than one renames corresponding to the old_name. Find the rename for
1205 which the definition flows into usage at new_bb. */
1207 tree t1
= NULL_TREE
, t2
;
1208 basic_block t1_bb
= NULL
;
1209 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1211 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1213 /* Defined in the same basic block as used. */
1214 if (t2_bb
== new_bb
)
1217 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1218 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1221 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1224 /* Compute the nearest dominator. */
1225 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1235 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1236 When OLD_NAME and EXPR are the same we assert. */
1238 void translate_isl_ast_to_gimple::
1239 set_rename (tree old_name
, tree expr
)
1243 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1244 print_generic_expr (dump_file
, old_name
, 0);
1245 fprintf (dump_file
, ", new_name = ");
1246 print_generic_expr (dump_file
, expr
, 0);
1247 fprintf (dump_file
, "\n");
1250 if (old_name
== expr
)
1253 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1256 renames
->safe_push (expr
);
1262 region
->rename_map
->put (old_name
, r
);
1267 /* For a parameter of a scop we don't want to rename it. */
1268 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1270 region
->parameter_rename_map
->put(old_name
, expr
);
1273 /* Return an iterator to the instructions comes last in the execution order.
1274 Either GSI1 and GSI2 should belong to the same basic block or one of their
1275 respective basic blocks should dominate the other. */
1277 gimple_stmt_iterator
1278 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1280 basic_block bb1
= gsi_bb (gsi1
);
1281 basic_block bb2
= gsi_bb (gsi2
);
1283 /* Find the iterator which is the latest. */
1286 gimple
*stmt1
= gsi_stmt (gsi1
);
1287 gimple
*stmt2
= gsi_stmt (gsi2
);
1289 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1291 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1292 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1294 if (is_phi1
!= is_phi2
)
1295 return is_phi1
? gsi2
: gsi1
;
1298 /* For empty basic blocks gsis point to the end of the sequence. Since
1299 there is no operator== defined for gimple_stmt_iterator and for gsis
1300 not pointing to a valid statement gsi_next would assert. */
1301 gimple_stmt_iterator gsi
= gsi1
;
1303 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1306 } while (!gsi_end_p (gsi
));
1311 /* Find the basic block closest to the basic block which defines stmt. */
1312 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1315 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1319 /* Insert each statement from SEQ at its earliest insertion p. */
1321 void translate_isl_ast_to_gimple::
1322 gsi_insert_earliest (gimple_seq seq
)
1324 update_modified_stmts (seq
);
1325 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1326 basic_block begin_bb
= get_entry_bb (codegen_region
);
1328 /* Inserting the gimple statements in a vector because gimple_seq behave
1329 in strage ways when inserting the stmts from it into different basic
1330 blocks one at a time. */
1331 auto_vec
<gimple
*, 3> stmts
;
1332 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1334 stmts
.safe_push (gsi_stmt (gsi
));
1338 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1340 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1341 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1343 use_operand_p use_p
;
1344 ssa_op_iter op_iter
;
1345 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1347 /* Iterator to the current def of use_p. For function parameters or
1348 anything where def is not found, insert at the beginning of the
1349 generated region. */
1350 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1352 tree op
= USE_FROM_PTR (use_p
);
1353 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1354 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1355 gsi_stmt
= gsi_for_stmt (stmt
);
1357 /* For region parameters, insert at the beginning of the generated
1359 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1360 gsi_stmt
= gsi_def_stmt
;
1362 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1365 if (!gsi_stmt (gsi_def_stmt
))
1367 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1368 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1370 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1372 gimple_stmt_iterator bsi
1373 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1374 /* Insert right after the PHI statements. */
1375 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1378 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1382 fprintf (dump_file
, "[codegen] inserting statement: ");
1383 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1384 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1389 /* Collect all the operands of NEW_EXPR by recursively visiting each
1392 void translate_isl_ast_to_gimple::
1393 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1395 if (new_expr
== NULL_TREE
)
1398 /* Rename all uses in new_expr. */
1399 if (TREE_CODE (new_expr
) == SSA_NAME
)
1401 vec_ssa
->safe_push (new_expr
);
1405 /* Iterate over SSA_NAMES in NEW_EXPR. */
1406 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1408 tree op
= TREE_OPERAND (new_expr
, i
);
1409 collect_all_ssa_names (op
, vec_ssa
);
1413 /* This is abridged version of the function copied from:
1414 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1417 substitute_ssa_name (tree exp
, tree f
, tree r
)
1419 enum tree_code code
= TREE_CODE (exp
);
1420 tree op0
, op1
, op2
, op3
;
1423 /* We handle TREE_LIST and COMPONENT_REF separately. */
1424 if (code
== TREE_LIST
)
1426 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1427 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1428 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1431 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1433 else if (code
== COMPONENT_REF
)
1437 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1438 and it is the right field, replace it with R. */
1439 for (inner
= TREE_OPERAND (exp
, 0);
1440 REFERENCE_CLASS_P (inner
);
1441 inner
= TREE_OPERAND (inner
, 0))
1445 op1
= TREE_OPERAND (exp
, 1);
1447 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1450 /* If this expression hasn't been completed let, leave it alone. */
1451 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1454 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1455 if (op0
== TREE_OPERAND (exp
, 0))
1459 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1462 switch (TREE_CODE_CLASS (code
))
1467 case tcc_declaration
:
1473 case tcc_expression
:
1479 case tcc_exceptional
:
1482 case tcc_comparison
:
1484 switch (TREE_CODE_LENGTH (code
))
1492 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1493 if (op0
== TREE_OPERAND (exp
, 0))
1496 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1500 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1501 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1503 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1506 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1510 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1511 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1512 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1514 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1515 && op2
== TREE_OPERAND (exp
, 2))
1518 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
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
);
1525 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1527 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1528 && op2
== TREE_OPERAND (exp
, 2)
1529 && op3
== TREE_OPERAND (exp
, 3))
1533 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1546 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1548 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1549 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1554 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1556 tree
translate_isl_ast_to_gimple::
1557 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1559 auto_vec
<tree
, 2> ssa_names
;
1560 collect_all_ssa_names (new_expr
, &ssa_names
);
1563 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1564 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1565 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1570 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1571 scalar evolution around LOOP. */
1573 tree
translate_isl_ast_to_gimple::
1574 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1575 basic_block new_bb
, basic_block old_bb
,
1578 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1580 /* At this point we should know the exact scev for each
1581 scalar SSA_NAME used in the scop: all the other scalar
1582 SSA_NAMEs should have been translated out of SSA using
1583 arrays with one element. */
1585 if (chrec_contains_undetermined (scev
))
1587 codegen_error
= true;
1588 return build_zero_cst (TREE_TYPE (old_name
));
1591 new_expr
= chrec_apply_map (scev
, iv_map
);
1593 /* The apply should produce an expression tree containing
1594 the uses of the new induction variables. We should be
1595 able to use new_expr instead of the old_name in the newly
1596 generated loop nest. */
1597 if (chrec_contains_undetermined (new_expr
)
1598 || tree_contains_chrecs (new_expr
, NULL
))
1600 codegen_error
= true;
1601 return build_zero_cst (TREE_TYPE (old_name
));
1604 if (TREE_CODE (new_expr
) == SSA_NAME
)
1606 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1607 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1609 codegen_error
= true;
1610 return build_zero_cst (TREE_TYPE (old_name
));
1614 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1616 /* We check all the operands and all of them should dominate the use at
1618 auto_vec
<tree
, 2> new_ssa_names
;
1619 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1622 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1624 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1626 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1627 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1629 codegen_error
= true;
1630 return build_zero_cst (TREE_TYPE (old_name
));
1635 /* Replace the old_name with the new_expr. */
1636 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1640 /* Renames the scalar uses of the statement COPY, using the
1641 substitution map RENAME_MAP, inserting the gimplification code at
1642 GSI_TGT, for the translation REGION, with the original copied
1643 statement in LOOP, and using the induction variable renaming map
1644 IV_MAP. Returns true when something has been renamed. */
1646 bool translate_isl_ast_to_gimple::
1647 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1648 loop_p loop
, vec
<tree
> iv_map
)
1650 bool changed
= false;
1652 if (is_gimple_debug (copy
))
1654 if (gimple_debug_bind_p (copy
))
1655 gimple_debug_bind_reset_value (copy
);
1656 else if (gimple_debug_source_bind_p (copy
))
1666 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1667 print_gimple_stmt (dump_file
, copy
, 0, 0);
1670 use_operand_p use_p
;
1671 ssa_op_iter op_iter
;
1672 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1674 tree old_name
= USE_FROM_PTR (use_p
);
1678 fprintf (dump_file
, "[codegen] renaming old_name = ");
1679 print_generic_expr (dump_file
, old_name
, 0);
1680 fprintf (dump_file
, "\n");
1683 if (TREE_CODE (old_name
) != SSA_NAME
1684 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1688 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1689 old_bb
, unknown_phi
);
1693 tree type_old_name
= TREE_TYPE (old_name
);
1694 tree type_new_expr
= TREE_TYPE (new_expr
);
1698 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1699 print_generic_expr (dump_file
, new_expr
, 0);
1700 fprintf (dump_file
, "\n");
1703 if (type_old_name
!= type_new_expr
1704 || TREE_CODE (new_expr
) != SSA_NAME
)
1706 tree var
= create_tmp_var (type_old_name
, "var");
1708 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1709 new_expr
= fold_convert (type_old_name
, new_expr
);
1712 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1713 gsi_insert_earliest (stmts
);
1716 replace_exp (use_p
, new_expr
);
1721 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1723 if (!new_expr
|| codegen_error_p ())
1728 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1729 print_generic_expr (dump_file
, new_expr
, 0);
1730 fprintf (dump_file
, "\n");
1733 gsi_insert_earliest (stmts
);
1734 replace_exp (use_p
, new_expr
);
1736 if (TREE_CODE (new_expr
) == INTEGER_CST
1737 && is_gimple_assign (copy
))
1739 tree rhs
= gimple_assign_rhs1 (copy
);
1741 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1742 recompute_tree_invariant_for_addr_expr (rhs
);
1745 set_rename (old_name
, new_expr
);
1751 /* Returns a basic block that could correspond to where a constant was defined
1752 in the original code. In the original code OLD_BB had the definition, we
1753 need to find which basic block out of the copies of old_bb, in the new
1754 region, should a definition correspond to if it has to reach BB. */
1756 basic_block
translate_isl_ast_to_gimple::
1757 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1759 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1761 if (!bbs
|| bbs
->is_empty ())
1764 if (1 == bbs
->length ())
1768 basic_block b1
= NULL
, b2
;
1769 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1774 /* BB and B2 are in two unrelated if-clauses. */
1775 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1778 /* Compute the nearest dominator. */
1779 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1786 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1787 determines the kind of phi node. */
1789 tree
translate_isl_ast_to_gimple::
1790 get_new_name (basic_block new_bb
, tree op
,
1791 basic_block old_bb
, phi_node_kind phi_kind
) const
1793 /* For constants the names are the same. */
1794 if (TREE_CODE (op
) != SSA_NAME
)
1797 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1800 /* Return a debug location for OP. */
1805 location_t loc
= UNKNOWN_LOCATION
;
1807 if (TREE_CODE (op
) == SSA_NAME
)
1808 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1812 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1813 the init edge (from outside the loop) and the second one is the back edge
1814 from the same loop. */
1816 std::pair
<edge
, edge
>
1817 get_edges (basic_block bb
)
1819 std::pair
<edge
, edge
> edges
;
1822 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1823 if (bb
->loop_father
!= e
->src
->loop_father
)
1830 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1831 must be found unless they can be POSTPONEd for later. */
1833 bool translate_isl_ast_to_gimple::
1834 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1835 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1838 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1840 basic_block new_bb
= gimple_bb (new_phi
);
1841 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1844 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1845 e
= ibp_new_bb
.first
;
1847 e
= ibp_new_bb
.second
;
1849 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1850 tree new_name
= get_new_name (new_bb
, old_name
,
1851 gimple_bb (old_phi
), loop_phi
);
1854 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1858 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1859 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1860 /* If the phi arg was a function arg, or wasn't defined, just use the
1862 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1865 /* Postpone code gen for later for those back-edges we don't have the
1867 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1869 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1872 /* Either we should add the arg to phi or, we should postpone. */
1878 /* Copy loop phi nodes from BB to NEW_BB. */
1880 bool translate_isl_ast_to_gimple::
1881 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1884 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1887 /* Loop phi nodes should have only two arguments. */
1888 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1890 /* First edge is the init edge and second is the back edge. */
1891 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1893 /* First edge is the init edge and second is the back edge. */
1894 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1896 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1899 gphi
*phi
= psi
.phi ();
1900 tree res
= gimple_phi_result (phi
);
1901 if (virtual_operand_p (res
))
1903 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1906 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1907 tree new_res
= create_new_def_for (res
, new_phi
,
1908 gimple_phi_result_ptr (new_phi
));
1909 set_rename (res
, new_res
);
1910 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1912 update_stmt (new_phi
);
1916 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1917 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
1924 /* Return the init value of PHI, the value coming from outside the loop. */
1927 get_loop_init_value (gphi
*phi
)
1930 loop_p loop
= gimple_bb (phi
)->loop_father
;
1934 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1935 if (e
->src
->loop_father
!= loop
)
1936 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1941 /* Find the init value (the value which comes from outside the loop), of one of
1942 the operands of DEF which is defined by a loop phi. */
1945 find_init_value (gimple
*def
)
1947 if (gimple_code (def
) == GIMPLE_PHI
)
1948 return get_loop_init_value (as_a
<gphi
*> (def
));
1950 if (gimple_vuse (def
))
1954 use_operand_p use_p
;
1955 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1957 tree use
= USE_FROM_PTR (use_p
);
1958 if (TREE_CODE (use
) == SSA_NAME
)
1960 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1968 /* Return the init value, the value coming from outside the loop. */
1971 find_init_value_close_phi (gphi
*phi
)
1973 gcc_assert (gimple_phi_num_args (phi
) == 1);
1974 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1975 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1976 return find_init_value (def
);
1980 tree
translate_isl_ast_to_gimple::
1981 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1982 gimple
*old_close_phi
)
1984 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1985 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1986 basic_block bb
= gimple_bb (stmt
);
1987 if (!bb_in_sese_p (bb
, codegen_region
))
1988 return last_merge_name
;
1990 loop_p loop
= bb
->loop_father
;
1991 if (!loop_in_sese_p (loop
, codegen_region
))
1992 return last_merge_name
;
1994 edge e
= single_exit (loop
);
1996 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1997 return last_merge_name
;
1999 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2000 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2003 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2004 bb
= split_edge (e
);
2006 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2007 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2008 gimple_phi_result_ptr (close_phi
));
2009 set_rename (old_close_phi_name
, res
);
2010 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2011 last_merge_name
= res
;
2013 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2016 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2017 the close phi node PHI. */
2019 bool translate_isl_ast_to_gimple::
2020 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2023 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2024 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2025 if (SSA_NAME
== TREE_CODE (default_value
))
2027 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2028 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2030 default_value_bb
= gimple_bb (stmt
);
2033 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2035 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2036 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2037 tree last_merge_name
= new_close_phi_name
;
2038 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2042 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2044 basic_block new_merge_bb
= merge_e
->src
;
2045 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2048 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2051 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2052 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2053 gimple_phi_result_ptr (merge_phi
));
2054 set_rename (old_close_phi_name
, merge_res
);
2056 edge from_loop
= NULL
, from_default_value
= NULL
;
2059 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2060 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2063 from_default_value
= e
;
2065 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2066 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2067 is contained in another condition. */
2068 if (!from_default_value
|| !from_loop
)
2071 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2072 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2076 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2077 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2080 update_stmt (merge_phi
);
2081 last_merge_name
= merge_res
;
2087 /* Copy all the loop-close phi args from BB to NEW_BB. */
2089 bool translate_isl_ast_to_gimple::
2090 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
, bool postpone
)
2092 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2095 gphi
*old_close_phi
= psi
.phi ();
2096 tree res
= gimple_phi_result (old_close_phi
);
2097 if (virtual_operand_p (res
))
2100 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2101 /* Loop close phi nodes should not be scev_analyzable_p. */
2104 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2105 tree new_res
= create_new_def_for (res
, new_close_phi
,
2106 gimple_phi_result_ptr (new_close_phi
));
2107 set_rename (res
, new_res
);
2109 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2110 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2112 /* Predecessor basic blocks of a loop close phi should have been code
2113 generated before. FIXME: This is fixable by merging PHIs from inner
2114 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2118 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2119 get_loc (old_name
));
2122 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2123 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2126 update_stmt (new_close_phi
);
2128 /* When there is no loop guard around this codegenerated loop, there is no
2129 need to collect the close-phi arg. */
2130 if (merge_points
.is_empty ())
2133 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2134 tree default_value
= find_init_value_close_phi (new_close_phi
);
2136 /* A close phi must come from a loop-phi having a default value. */
2142 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2146 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2147 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2152 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2160 /* Copy loop close phi nodes from BB to NEW_BB. */
2162 bool translate_isl_ast_to_gimple::
2163 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
)
2166 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2168 /* Loop close phi nodes should have only one argument. */
2169 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2171 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2175 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2176 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2177 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2178 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2181 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2182 In this case DOMINATING_PRED = NULL.
2184 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2186 Returns true on successful copy of the args, false otherwise. */
2188 bool translate_isl_ast_to_gimple::
2189 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2190 edge old_bb_dominating_edge
,
2191 edge old_bb_non_dominating_edge
,
2192 gphi
*phi
, gphi
*new_phi
,
2195 basic_block def_pred
[2] = { NULL
, NULL
};
2196 int not_found_bb_index
= -1;
2197 for (int i
= 0; i
< 2; i
++)
2199 /* If the corresponding def_bb could not be found the entry will be
2201 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2202 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2203 gimple_phi_arg_edge (phi
, i
)->src
);
2204 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2205 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2209 /* When non are available bail out. */
2210 if (not_found_bb_index
!= -1)
2212 not_found_bb_index
= i
;
2216 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2217 if (old_bb_dominating_edge
)
2219 if (not_found_bb_index
!= -1)
2222 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2223 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2224 vec
<basic_block
> *bbs
2225 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2227 /* Could not find a mapping. */
2231 basic_block new_pred
= NULL
;
2234 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2236 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2238 /* FIXME: If we have already found new_pred then we have to
2239 disambiguate, bail out for now. */
2242 new_pred
= new_pred1
;
2244 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2246 /* FIXME: If we have already found new_pred then we have to either
2247 it dominates both or we have to disambiguate, bail out. */
2250 new_pred
= new_pred2
;
2257 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2258 gcc_assert (new_non_dominating_edge
);
2259 /* FIXME: Validate each args just like in loop-phis. */
2260 /* By the process of elimination we first insert insert phi-edge for
2261 non-dominating pred which is computed above and then we insert the
2263 int inserted_edge
= 0;
2264 for (; inserted_edge
< 2; inserted_edge
++)
2266 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2267 if (new_non_dominating_edge
== new_bb_pred_edge
)
2269 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2270 new_non_dominating_edge
,
2271 get_loc (old_phi_args
[inserted_edge
]));
2275 if (inserted_edge
== 2)
2278 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2280 edge new_dominating_edge
= NULL
;
2281 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2283 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2284 if (e
!= new_non_dominating_edge
)
2286 new_dominating_edge
= e
;
2287 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2288 new_dominating_edge
,
2289 get_loc (old_phi_args
[inserted_edge
]));
2293 gcc_assert (new_dominating_edge
);
2297 /* Classic diamond structure: both edges are non-dominating. We need to
2298 find one unique edge then the other can be found be elimination. If
2299 any definition (def_pred) dominates both the preds of new_bb then we
2300 bail out. Entries of def_pred maybe NULL, in that case we must
2301 uniquely find pred with help of only one entry. */
2302 edge new_e
[2] = { NULL
, NULL
};
2303 for (int i
= 0; i
< 2; i
++)
2307 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2309 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2312 /* We do not know how to handle the case when def_pred
2313 dominates more than a predecessor. */
2319 gcc_assert (new_e
[0] || new_e
[1]);
2321 /* Find the other edge by process of elimination. */
2322 if (not_found_bb_index
!= -1)
2324 gcc_assert (!new_e
[not_found_bb_index
]);
2325 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2328 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2330 if (new_e
[found_bb_index
] == e
)
2332 new_e
[not_found_bb_index
] = e
;
2336 /* Add edges to phi args. */
2337 for (int i
= 0; i
< 2; i
++)
2338 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2339 get_loc (old_phi_args
[i
]));
2345 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2346 region. If postpone is true and it isn't possible to copy any arg of PHI,
2347 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2348 Returns false if the copying was unsuccessful. */
2350 bool translate_isl_ast_to_gimple::
2351 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2354 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2355 gcc_assert (2 == gimple_phi_num_args (phi
));
2357 basic_block new_bb
= gimple_bb (new_phi
);
2358 loop_p loop
= gimple_bb (phi
)->loop_father
;
2360 basic_block old_bb
= gimple_bb (phi
);
2361 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2365 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2366 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2367 old_bb_non_dominating_edge
= e
;
2369 old_bb_dominating_edge
= e
;
2371 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2372 old_bb_non_dominating_edge
->src
));
2374 tree new_phi_args
[2];
2375 tree old_phi_args
[2];
2377 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2379 tree old_name
= gimple_phi_arg_def (phi
, i
);
2380 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2381 old_phi_args
[i
] = old_name
;
2384 new_phi_args
[i
] = new_name
;
2388 /* If the phi-arg was a parameter. */
2389 if (vec_find (region
->params
, old_name
) != -1)
2391 new_phi_args
[i
] = old_name
;
2395 "[codegen] parameter argument to phi, new_expr: ");
2396 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2397 fprintf (dump_file
, "\n");
2402 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2403 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2404 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2410 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2411 if (is_gimple_reg (old_name
)
2412 && scev_analyzable_p (old_name
, region
->region
))
2415 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2416 new_bb
, old_bb
, iv_map
);
2417 if (codegen_error_p ())
2420 gcc_assert (new_expr
);
2424 "[codegen] scev analyzeable, new_expr: ");
2425 print_generic_expr (dump_file
, new_expr
, 0);
2426 fprintf (dump_file
, "\n");
2428 gsi_insert_earliest (stmts
);
2429 new_phi_args
[i
] = new_expr
;
2433 /* Postpone code gen for later for back-edges. */
2434 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2438 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2439 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2442 new_phi_args
[i
] = NULL_TREE
;
2446 /* Either we should add the arg to phi or, we should postpone. */
2450 /* If none of the args have been determined in the first stage then wait until
2452 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2455 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2456 old_bb_dominating_edge
,
2457 old_bb_non_dominating_edge
,
2458 phi
, new_phi
, new_bb
);
2461 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2462 containing phi nodes coming from two predecessors, and none of them are back
2465 bool translate_isl_ast_to_gimple::
2466 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2469 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2471 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2472 if (EDGE_COUNT (bb
->preds
) != 2)
2476 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2479 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2482 gphi
*phi
= psi
.phi ();
2483 tree res
= gimple_phi_result (phi
);
2484 if (virtual_operand_p (res
))
2487 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2488 tree new_res
= create_new_def_for (res
, new_phi
,
2489 gimple_phi_result_ptr (new_phi
));
2490 set_rename (res
, new_res
);
2492 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2495 update_stmt (new_phi
);
2501 /* Return true if STMT should be copied from region to the new code-generated
2502 region. LABELs, CONDITIONS, induction-variables and region parameters need
2506 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2508 /* Do not copy labels or conditions. */
2509 if (gimple_code (stmt
) == GIMPLE_LABEL
2510 || gimple_code (stmt
) == GIMPLE_COND
)
2514 /* Do not copy induction variables. */
2515 if (is_gimple_assign (stmt
)
2516 && (lhs
= gimple_assign_lhs (stmt
))
2517 && TREE_CODE (lhs
) == SSA_NAME
2518 && is_gimple_reg (lhs
)
2519 && scev_analyzable_p (lhs
, region
->region
))
2522 /* Do not copy parameters that have been generated in the header of the
2524 if (is_gimple_assign (stmt
)
2525 && (lhs
= gimple_assign_lhs (stmt
))
2526 && TREE_CODE (lhs
) == SSA_NAME
2527 && region
->parameter_rename_map
->get(lhs
))
2533 /* Create new names for all the definitions created by COPY and add replacement
2534 mappings for each new name. */
2536 void translate_isl_ast_to_gimple::
2537 set_rename_for_each_def (gimple
*stmt
)
2539 def_operand_p def_p
;
2540 ssa_op_iter op_iter
;
2541 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2543 tree old_name
= DEF_FROM_PTR (def_p
);
2544 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2545 set_rename (old_name
, new_name
);
2549 /* Duplicates the statements of basic block BB into basic block NEW_BB
2550 and compute the new induction variables according to the IV_MAP. */
2552 bool translate_isl_ast_to_gimple::
2553 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2556 /* Iterator poining to the place where new statement (s) will be inserted. */
2557 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2559 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2562 gimple
*stmt
= gsi_stmt (gsi
);
2563 if (!should_copy_to_new_region (stmt
, region
))
2566 /* Create a new copy of STMT and duplicate STMT's virtual
2568 gimple
*copy
= gimple_copy (stmt
);
2569 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2573 fprintf (dump_file
, "[codegen] inserting statement: ");
2574 print_gimple_stmt (dump_file
, copy
, 0, 0);
2577 maybe_duplicate_eh_stmt (copy
, stmt
);
2578 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2580 /* Crete new names for each def in the copied stmt. */
2581 set_rename_for_each_def (copy
);
2583 loop_p loop
= bb
->loop_father
;
2584 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2586 fold_stmt_inplace (&gsi_tgt
);
2587 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2590 if (codegen_error_p ())
2593 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2595 use_operand_p use_p
;
2596 if (!is_gimple_debug (copy
))
2597 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2599 tree old_name
= USE_FROM_PTR (use_p
);
2601 if (TREE_CODE (old_name
) != SSA_NAME
2602 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2605 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2609 replace_exp (use_p
, *new_expr
);
2619 /* Given a basic block containing close-phi it returns the new basic block where
2620 to insert a copy of the close-phi nodes. All the uses in close phis should
2621 come from a single loop otherwise it returns NULL. */
2623 edge
translate_isl_ast_to_gimple::
2624 edge_for_new_close_phis (basic_block bb
)
2626 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2627 of close phi in the original code and then find the mapping of basic block
2628 defining that variable. If there are multiple close-phis and they are
2629 defined in different loops (in the original or in the new code) because of
2630 loop splitting, then we bail out. */
2631 loop_p new_loop
= NULL
;
2632 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2635 gphi
*phi
= psi
.phi ();
2636 tree name
= gimple_phi_arg_def (phi
, 0);
2637 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2639 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2640 if (!bbs
|| bbs
->length () != 1)
2641 /* This is one of the places which shows preserving original structure
2642 is not always possible, as we may need to insert close PHI for a loop
2643 where the latch does not have any mapping, or the mapping is
2648 new_loop
= (*bbs
)[0]->loop_father
;
2649 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2656 return single_exit (new_loop
);
2659 /* Copies BB and includes in the copied BB all the statements that can
2660 be reached following the use-def chains from the memory accesses,
2661 and returns the next edge following this new block. */
2663 edge
translate_isl_ast_to_gimple::
2664 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2666 int num_phis
= number_of_phi_nodes (bb
);
2668 if (region
->copied_bb_map
->get (bb
))
2670 /* FIXME: we should be able to handle phi nodes with args coming from
2671 outside the region. */
2674 codegen_error
= true;
2679 basic_block new_bb
= NULL
;
2680 if (bb_contains_loop_close_phi_nodes (bb
))
2683 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2686 edge e
= edge_for_new_close_phis (bb
);
2689 codegen_error
= true;
2693 basic_block phi_bb
= e
->dest
;
2695 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2696 phi_bb
= split_edge (e
);
2698 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2699 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2701 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2703 codegen_error
= true;
2710 new_bb
= split_edge (next_e
);
2714 new_bb
= split_edge (next_e
);
2715 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2717 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2719 /* At this point we are unable to codegenerate by still preserving the SSA
2720 structure because maybe the loop is completely unrolled and the PHIs
2721 and cross-bb scalar dependencies are untrackable w.r.t. the original
2722 code. See gfortran.dg/graphite/pr29832.f90. */
2723 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2725 codegen_error
= true;
2729 /* In case isl did some loop peeling, like this:
2732 for (int c1 = 1; c1 <= 5; c1 += 1) {
2737 there should be no loop-phi nodes in S_8(0).
2739 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2740 values of all scalar variables: for the moment we instantiate only
2741 SCEV analyzable expressions on the iteration domain, and we need to
2742 extend that to reductions that cannot be analyzed by SCEV. */
2743 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2745 codegen_error
= true;
2750 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2752 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2754 codegen_error
= true;
2758 else if (num_phis
> 0)
2761 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2764 basic_block phi_bb
= single_pred (new_bb
);
2765 loop_p loop_father
= new_bb
->loop_father
;
2767 /* Move back until we find the block with two predecessors. */
2768 while (single_pred_p (phi_bb
))
2769 phi_bb
= single_pred_edge (phi_bb
)->src
;
2771 /* If a corresponding merge-point was not found, then abort codegen. */
2772 if (phi_bb
->loop_father
!= loop_father
2773 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2774 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2776 codegen_error
= true;
2783 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2784 bb
->index
, new_bb
->index
);
2786 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2788 copied_bbs
->safe_push (new_bb
);
2791 vec
<basic_block
> bbs
;
2793 bbs
.safe_push (new_bb
);
2794 region
->copied_bb_map
->put (bb
, bbs
);
2797 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2799 codegen_error
= true;
2803 return single_succ_edge (new_bb
);
2806 /* Patch the missing arguments of the phi nodes. */
2808 void translate_isl_ast_to_gimple::
2809 translate_pending_phi_nodes ()
2813 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2815 gphi
*old_phi
= rename
->first
;
2816 gphi
*new_phi
= rename
->second
;
2817 basic_block old_bb
= gimple_bb (old_phi
);
2818 basic_block new_bb
= gimple_bb (new_phi
);
2820 /* First edge is the init edge and second is the back edge. */
2821 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2822 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2826 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2827 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2830 auto_vec
<tree
, 1> iv_map
;
2831 if (bb_contains_loop_phi_nodes (new_bb
))
2832 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2834 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2835 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2837 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2841 fprintf (dump_file
, "[codegen] to new-phi: ");
2842 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2844 if (codegen_error_p ())
2849 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2851 void translate_isl_ast_to_gimple::
2852 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2854 sese_info_p region
= scop
->scop_info
;
2855 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2856 gcc_assert (nb_parameters
== region
->params
.length ());
2858 for (i
= 0; i
< nb_parameters
; i
++)
2860 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2862 ip
[tmp_id
] = region
->params
[i
];
2867 /* Generates a build, which specifies the constraints on the parameters. */
2869 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2870 generate_isl_context (scop_p scop
)
2872 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2873 return isl_ast_build_from_context (context_isl
);
2876 /* This method is executed before the construction of a for node. */
2878 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2880 isl_union_map
*dependences
= (isl_union_map
*) user
;
2881 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2882 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2883 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2884 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2885 for_info
->is_parallelizable
=
2886 !carries_deps (schedule
, dependences
, dimension
);
2887 isl_union_map_free (schedule
);
2888 isl_space_free (schedule_space
);
2889 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2893 /* Generate isl AST from schedule of SCOP. */
2895 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2896 scop_to_isl_ast (scop_p scop
)
2898 gcc_assert (scop
->transformed_schedule
);
2900 /* Set the separate option to reduce control flow overhead. */
2901 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2902 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2903 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2905 if (flag_loop_parallelize_all
)
2907 scop_get_dependences (scop
);
2909 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2913 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2914 (context_isl
, schedule
);
2915 isl_ast_build_free (context_isl
);
2919 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2920 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2923 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2924 gimple_stmt_iterator
*gsi
)
2926 if (!defined_in_sese_p (tr
, region
->region
))
2930 use_operand_p use_p
;
2931 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2933 tree use_tr
= USE_FROM_PTR (use_p
);
2935 /* Do not copy parameters that have been generated in the header of the
2937 if (region
->parameter_rename_map
->get(use_tr
))
2940 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2944 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2947 gimple
*copy
= gimple_copy (def_stmt
);
2948 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2950 /* Create new names for all the definitions created by COPY and
2951 add replacement mappings for each new name. */
2952 def_operand_p def_p
;
2953 ssa_op_iter op_iter
;
2954 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2956 tree old_name
= DEF_FROM_PTR (def_p
);
2957 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2958 region
->parameter_rename_map
->put(old_name
, new_name
);
2965 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2967 /* For all the parameters which definitino is in the if_region->false_region,
2968 insert code on true_region (if_region->true_region->entry). */
2972 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2974 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2976 // If def is not in region.
2977 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2979 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2983 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2984 Return true if code generation succeeded. */
2987 graphite_regenerate_ast_isl (scop_p scop
)
2989 sese_info_p region
= scop
->scop_info
;
2990 translate_isl_ast_to_gimple
t (region
);
2992 ifsese if_region
= NULL
;
2993 isl_ast_node
*root_node
;
2996 timevar_push (TV_GRAPHITE_CODE_GEN
);
2997 t
.add_parameters_to_ivs_params (scop
, ip
);
2998 root_node
= t
.scop_to_isl_ast (scop
);
3000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3002 fprintf (dump_file
, "[scheduler] original schedule:\n");
3003 print_isl_schedule (dump_file
, scop
->original_schedule
);
3004 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
3005 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
3007 fprintf (dump_file
, "[scheduler] original ast:\n");
3008 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
3009 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
3010 print_isl_ast (dump_file
, root_node
);
3013 recompute_all_dominators ();
3016 if_region
= move_sese_in_condition (region
);
3017 region
->if_region
= if_region
;
3018 recompute_all_dominators ();
3020 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3022 /* Copy all the parameters which are defined in the region. */
3023 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3025 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3026 basic_block bb
= split_edge (e
);
3028 /* Update the true_region exit edge. */
3029 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3031 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3032 if (t
.codegen_error_p ())
3035 fprintf (dump_file
, "codegen error: "
3036 "reverting back to the original code.\n");
3037 set_ifsese_condition (if_region
, integer_zero_node
);
3041 t
.translate_pending_phi_nodes ();
3042 if (!t
.codegen_error_p ())
3044 sese_insert_phis_for_liveouts (region
,
3045 if_region
->region
->region
.exit
->src
,
3046 if_region
->false_region
->region
.exit
,
3047 if_region
->true_region
->region
.exit
);
3048 mark_virtual_operands_for_renaming (cfun
);
3049 update_ssa (TODO_update_ssa
);
3054 recompute_all_dominators ();
3058 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
3063 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3064 " pending phis, reverting back to the original code.\n");
3065 set_ifsese_condition (if_region
, integer_zero_node
);
3069 free (if_region
->true_region
);
3070 free (if_region
->region
);
3073 ivs_params_clear (ip
);
3074 isl_ast_node_free (root_node
);
3075 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3077 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3080 int num_no_dependency
= 0;
3082 FOR_EACH_LOOP (loop
, 0)
3083 if (loop
->can_be_parallel
)
3084 num_no_dependency
++;
3086 fprintf (dump_file
, "%d loops carried no dependency.\n",
3090 return !t
.codegen_error_p ();
3093 #endif /* HAVE_isl */