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 /* Verifies properties that GRAPHITE should maintain during translation. */
79 graphite_verify (void)
81 checking_verify_loop_structure ();
82 checking_verify_loop_closed_ssa (true);
85 /* IVS_PARAMS maps isl's scattering and parameter identifiers
86 to corresponding trees. */
88 typedef std::map
<isl_id
*, tree
> ivs_params
;
90 /* Free all memory allocated for isl's identifiers. */
92 static void ivs_params_clear (ivs_params
&ip
)
94 std::map
<isl_id
*, tree
>::iterator it
;
95 for (it
= ip
.begin ();
96 it
!= ip
.end (); it
++)
98 isl_id_free (it
->first
);
102 /* Set the "separate" option for the schedule node. */
104 static isl_schedule_node
*
105 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
110 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
113 /* Set the "separate" option unless it is set earlier to another option. */
114 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
115 == isl_ast_loop_default
)
116 return isl_schedule_node_band_member_set_ast_loop_type
117 (node
, 0, isl_ast_loop_separate
);
122 /* Print SCHEDULE under an AST form on file F. */
125 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
127 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
128 isl_ast_build
*context
= isl_ast_build_from_context (set
);
130 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
131 isl_ast_build_free (context
);
132 print_isl_ast (f
, ast
);
133 isl_ast_node_free (ast
);
137 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
139 print_schedule_ast (stderr
, s
, scop
);
150 class translate_isl_ast_to_gimple
153 translate_isl_ast_to_gimple (sese_info_p r
)
154 : region (r
), codegen_error (false) { }
155 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
156 edge next_e
, ivs_params
&ip
);
157 edge
translate_isl_ast_node_for (loop_p context_loop
,
158 __isl_keep isl_ast_node
*node
,
159 edge next_e
, ivs_params
&ip
);
160 edge
translate_isl_ast_for_loop (loop_p context_loop
,
161 __isl_keep isl_ast_node
*node_for
,
163 tree type
, tree lb
, tree ub
,
165 edge
translate_isl_ast_node_if (loop_p context_loop
,
166 __isl_keep isl_ast_node
*node
,
167 edge next_e
, ivs_params
&ip
);
168 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
169 edge next_e
, ivs_params
&ip
);
170 edge
translate_isl_ast_node_block (loop_p context_loop
,
171 __isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
173 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
175 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
177 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
179 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
181 tree
gcc_expression_from_isl_expression (tree type
,
182 __isl_take isl_ast_expr
*,
184 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
185 __isl_keep isl_ast_expr
*expr_id
,
187 tree
gcc_expression_from_isl_expr_int (tree type
,
188 __isl_take isl_ast_expr
*expr
);
189 tree
gcc_expression_from_isl_expr_op (tree type
,
190 __isl_take isl_ast_expr
*expr
,
192 struct loop
*graphite_create_new_loop (edge entry_edge
,
193 __isl_keep isl_ast_node
*node_for
,
194 loop_p outer
, tree type
,
195 tree lb
, tree ub
, ivs_params
&ip
);
196 edge
graphite_create_new_loop_guard (edge entry_edge
,
197 __isl_keep isl_ast_node
*node_for
,
199 tree
*lb
, tree
*ub
, ivs_params
&ip
);
200 edge
graphite_create_new_guard (edge entry_edge
,
201 __isl_take isl_ast_expr
*if_cond
,
203 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
204 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
206 void translate_pending_phi_nodes (void);
207 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
208 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
210 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
212 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
213 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
214 tree
get_rename (basic_block new_bb
, tree old_name
,
215 basic_block old_bb
, phi_node_kind
) const;
216 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
217 basic_block new_bb
, basic_block old_bb
,
219 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
220 tree
get_new_name (basic_block new_bb
, tree op
,
221 basic_block old_bb
, phi_node_kind
) const;
222 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
223 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
224 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
226 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
227 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
229 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
230 gimple
*old_close_phi
);
231 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
233 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
234 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
236 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
238 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
240 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
242 edge
edge_for_new_close_phis (basic_block bb
);
243 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
244 edge old_bb_dominating_edge
,
245 edge old_bb_non_dominating_edge
,
246 gphi
*phi
, gphi
*new_phi
,
248 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
249 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
250 void set_rename (tree old_name
, tree expr
);
251 void set_rename_for_each_def (gimple
*stmt
);
252 void gsi_insert_earliest (gimple_seq seq
);
253 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
254 bool codegen_error_p () const { return codegen_error
; }
255 bool is_constant (tree op
) const
257 return TREE_CODE (op
) == INTEGER_CST
258 || TREE_CODE (op
) == REAL_CST
259 || TREE_CODE (op
) == COMPLEX_CST
260 || TREE_CODE (op
) == VECTOR_CST
;
264 /* The region to be translated. */
267 /* This flag is set when an error occurred during the translation of isl AST
271 /* A vector of all the edges at if_condition merge points. */
272 auto_vec
<edge
, 2> merge_points
;
275 /* Return the tree variable that corresponds to the given isl ast identifier
276 expression (an isl_ast_expr of type isl_ast_expr_id).
278 FIXME: We should replace blind conversion of id's type with derivation
279 of the optimal type when we get the corresponding isl support. Blindly
280 converting type sizes may be problematic when we switch to smaller
283 tree
translate_isl_ast_to_gimple::
284 gcc_expression_from_isl_ast_expr_id (tree type
,
285 __isl_take isl_ast_expr
*expr_id
,
288 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
289 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
290 std::map
<isl_id
*, tree
>::iterator res
;
291 res
= ip
.find (tmp_isl_id
);
292 isl_id_free (tmp_isl_id
);
293 gcc_assert (res
!= ip
.end () &&
294 "Could not map isl_id to tree expression");
295 isl_ast_expr_free (expr_id
);
296 tree t
= res
->second
;
297 tree
*val
= region
->parameter_rename_map
->get(t
);
301 return fold_convert (type
, *val
);
304 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
307 tree
translate_isl_ast_to_gimple::
308 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
310 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
311 isl_val
*val
= isl_ast_expr_get_val (expr
);
312 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
313 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
315 if (isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
319 widest_int wi
= widest_int::from_array (chunks
, n
, true);
320 if (isl_val_is_neg (val
))
322 res
= wide_int_to_tree (type
, wi
);
325 isl_ast_expr_free (expr
);
329 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
332 tree
translate_isl_ast_to_gimple::
333 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
335 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
336 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
337 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
338 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
340 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
341 isl_ast_expr_free (expr
);
343 if (codegen_error_p ())
349 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
352 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
355 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
358 /* As isl operates on arbitrary precision numbers, we may end up with
359 division by 2^64 that is folded to 0. */
360 if (integer_zerop (tree_rhs_expr
))
362 codegen_error
= true;
365 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
367 case isl_ast_op_pdiv_q
:
368 /* As isl operates on arbitrary precision numbers, we may end up with
369 division by 2^64 that is folded to 0. */
370 if (integer_zerop (tree_rhs_expr
))
372 codegen_error
= true;
375 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
377 case isl_ast_op_zdiv_r
:
378 case isl_ast_op_pdiv_r
:
379 /* As isl operates on arbitrary precision numbers, we may end up with
380 division by 2^64 that is folded to 0. */
381 if (integer_zerop (tree_rhs_expr
))
383 codegen_error
= true;
386 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
388 case isl_ast_op_fdiv_q
:
389 /* As isl operates on arbitrary precision numbers, we may end up with
390 division by 2^64 that is folded to 0. */
391 if (integer_zerop (tree_rhs_expr
))
393 codegen_error
= true;
396 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
399 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
400 tree_lhs_expr
, tree_rhs_expr
);
403 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
406 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
409 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
412 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
415 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
418 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
425 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
428 tree
translate_isl_ast_to_gimple::
429 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
431 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
432 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
433 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
434 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
435 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
436 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
437 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
438 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
439 isl_ast_expr_free (expr
);
441 if (codegen_error_p ())
444 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
447 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
450 tree
translate_isl_ast_to_gimple::
451 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
453 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
454 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
455 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
456 isl_ast_expr_free (expr
);
457 return codegen_error_p () ? NULL_TREE
458 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
461 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
462 to a GCC expression tree of type TYPE. */
464 tree
translate_isl_ast_to_gimple::
465 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
467 enum tree_code op_code
;
468 switch (isl_ast_expr_get_op_type (expr
))
481 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
482 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
484 if (codegen_error_p ())
486 isl_ast_expr_free (expr
);
491 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
493 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
494 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
496 if (codegen_error_p ())
498 isl_ast_expr_free (expr
);
502 res
= fold_build2 (op_code
, type
, res
, t
);
504 isl_ast_expr_free (expr
);
508 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
511 tree
translate_isl_ast_to_gimple::
512 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
515 if (codegen_error_p ())
517 isl_ast_expr_free (expr
);
521 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
522 switch (isl_ast_expr_get_op_type (expr
))
524 /* These isl ast expressions are not supported yet. */
525 case isl_ast_op_error
:
526 case isl_ast_op_call
:
527 case isl_ast_op_and_then
:
528 case isl_ast_op_or_else
:
533 return nary_op_to_tree (type
, expr
, ip
);
539 case isl_ast_op_pdiv_q
:
540 case isl_ast_op_pdiv_r
:
541 case isl_ast_op_fdiv_q
:
542 case isl_ast_op_zdiv_r
:
550 return binary_op_to_tree (type
, expr
, ip
);
552 case isl_ast_op_minus
:
553 return unary_op_to_tree (type
, expr
, ip
);
555 case isl_ast_op_cond
:
556 case isl_ast_op_select
:
557 return ternary_op_to_tree (type
, expr
, ip
);
566 /* Converts an isl AST expression E back to a GCC expression tree of
569 tree
translate_isl_ast_to_gimple::
570 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
573 if (codegen_error_p ())
575 isl_ast_expr_free (expr
);
579 switch (isl_ast_expr_get_type (expr
))
581 case isl_ast_expr_id
:
582 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
584 case isl_ast_expr_int
:
585 return gcc_expression_from_isl_expr_int (type
, expr
);
587 case isl_ast_expr_op
:
588 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
597 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
598 induction variable for the new LOOP. New LOOP is attached to CFG
599 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
600 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
601 isl's scattering name to the induction variable created for the
602 loop of STMT. The new induction variable is inserted in the NEWIVS
603 vector and is of type TYPE. */
605 struct loop
*translate_isl_ast_to_gimple::
606 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
607 loop_p outer
, tree type
, tree lb
, tree ub
,
610 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
611 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
613 /* To fail code generation, we generate wrong code until we discard it. */
614 if (codegen_error_p ())
615 stride
= integer_zero_node
;
617 tree ivvar
= create_tmp_var (type
, "graphite_IV");
618 tree iv
, iv_after_increment
;
619 loop_p loop
= create_empty_loop_on_edge
620 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
621 outer
? outer
: entry_edge
->src
->loop_father
);
623 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
624 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
625 std::map
<isl_id
*, tree
>::iterator res
;
628 isl_id_free (res
->first
);
630 isl_ast_expr_free (for_iterator
);
634 /* Create the loop for a isl_ast_node_for.
636 - NEXT_E is the edge where new generated code should be attached. */
638 edge
translate_isl_ast_to_gimple::
639 translate_isl_ast_for_loop (loop_p context_loop
,
640 __isl_keep isl_ast_node
*node_for
, edge next_e
,
641 tree type
, tree lb
, tree ub
,
644 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
645 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
647 edge last_e
= single_exit (loop
);
648 edge to_body
= single_succ_edge (loop
->header
);
649 basic_block after
= to_body
->dest
;
651 /* Translate the body of the loop. */
652 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
653 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
654 isl_ast_node_free (for_body
);
656 /* Early return if we failed to translate loop body. */
657 if (!next_e
|| codegen_error_p ())
660 if (next_e
->dest
!= after
)
661 redirect_edge_succ_nodup (next_e
, after
);
662 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
664 if (flag_loop_parallelize_all
)
666 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
668 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
669 loop
->can_be_parallel
= for_info
->is_parallelizable
;
677 /* We use this function to get the upper bound because of the form,
678 which is used by isl to represent loops:
680 for (iterator = init; cond; iterator += inc)
688 The loop condition is an arbitrary expression, which contains the
689 current loop iterator.
691 (e.g. iterator + 3 < B && C > iterator + A)
693 We have to know the upper bound of the iterator to generate a loop
694 in Gimple form. It can be obtained from the special representation
695 of the loop condition, which is generated by isl,
696 if the ast_build_atomic_upper_bound option is set. In this case,
697 isl generates a loop condition that consists of the current loop
698 iterator, + an operator (< or <=) and an expression not involving
699 the iterator, which is processed and returned by this function.
701 (e.g iterator <= upper-bound-expression-without-iterator) */
703 static __isl_give isl_ast_expr
*
704 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
706 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
707 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
708 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
710 switch (isl_ast_expr_get_op_type (for_cond
))
713 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
718 /* (iterator < ub) => (iterator <= ub - 1). */
720 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
721 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
722 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
729 isl_ast_expr_free (for_cond
);
733 /* All loops generated by create_empty_loop_on_edge have the form of
740 } while (lower bound < upper bound);
742 We create a new if region protecting the loop to be executed, if
743 the execution count is zero (lower bound > upper bound). */
745 edge
translate_isl_ast_to_gimple::
746 graphite_create_new_loop_guard (edge entry_edge
,
747 __isl_keep isl_ast_node
*node_for
, tree
*type
,
748 tree
*lb
, tree
*ub
, ivs_params
&ip
)
750 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
755 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
756 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
757 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
759 /* To fail code generation, we generate wrong code until we discard it. */
760 if (codegen_error_p ())
761 *lb
= integer_zero_node
;
763 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
764 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
766 /* To fail code generation, we generate wrong code until we discard it. */
767 if (codegen_error_p ())
768 *ub
= integer_zero_node
;
770 /* When ub is simply a constant or a parameter, use lb <= ub. */
771 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
772 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
775 tree one
= (POINTER_TYPE_P (*type
)
776 ? convert_to_ptrofftype (integer_one_node
)
777 : fold_convert (*type
, integer_one_node
));
778 /* Adding +1 and using LT_EXPR helps with loop latches that have a
779 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
780 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
781 is true, even if we do not want this. However lb < ub + 1 is false,
783 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
784 : PLUS_EXPR
, *type
, *ub
, one
);
786 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
789 if (integer_onep (cond_expr
))
790 exit_edge
= entry_edge
;
792 exit_edge
= create_empty_if_region_on_edge (entry_edge
,
793 unshare_expr (cond_expr
));
798 /* Translates an isl_ast_node_for to Gimple. */
800 edge
translate_isl_ast_to_gimple::
801 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
802 edge next_e
, ivs_params
&ip
)
804 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
806 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
809 if (last_e
== next_e
)
811 /* There was no guard generated. */
812 last_e
= single_succ_edge (split_edge (last_e
));
814 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
819 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
820 merge_points
.safe_push (last_e
);
822 last_e
= single_succ_edge (split_edge (last_e
));
823 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
828 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
829 variables of the loops around GBB in SESE.
831 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
832 chrec, we could consider using a map<int, tree> that maps loop ids to the
833 corresponding tree expressions. */
835 void translate_isl_ast_to_gimple::
836 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
837 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
840 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
841 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
843 isl_ast_expr
*arg_expr
;
844 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
846 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
848 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
849 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
851 /* To fail code generation, we generate wrong code until we discard it. */
852 if (codegen_error_p ())
853 t
= integer_zero_node
;
855 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
856 iv_map
[old_loop
->num
] = t
;
860 /* Translates an isl_ast_node_user to Gimple.
862 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
864 edge
translate_isl_ast_to_gimple::
865 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
866 edge next_e
, ivs_params
&ip
)
868 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
870 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
871 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
872 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
874 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
875 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
878 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
880 isl_ast_expr_free (name_expr
);
881 isl_id_free (name_id
);
883 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
884 "The entry block should not even appear within a scop");
886 const int nb_loops
= number_of_loops (cfun
);
888 iv_map
.create (nb_loops
);
889 iv_map
.safe_grow_cleared (nb_loops
);
891 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
892 isl_ast_expr_free (user_expr
);
894 basic_block old_bb
= GBB_BB (gbb
);
898 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
899 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
900 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
904 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
908 if (codegen_error_p ())
913 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
914 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
920 /* Translates an isl_ast_node_block to Gimple. */
922 edge
translate_isl_ast_to_gimple::
923 translate_isl_ast_node_block (loop_p context_loop
,
924 __isl_keep isl_ast_node
*node
,
925 edge next_e
, ivs_params
&ip
)
927 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
928 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
930 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
932 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
933 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
934 isl_ast_node_free (tmp_node
);
936 isl_ast_node_list_free (node_list
);
940 /* Creates a new if region corresponding to isl's cond. */
942 edge
translate_isl_ast_to_gimple::
943 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
947 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
948 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
950 /* To fail code generation, we generate wrong code until we discard it. */
951 if (codegen_error_p ())
952 cond_expr
= integer_zero_node
;
954 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
958 /* Translates an isl_ast_node_if to Gimple. */
960 edge
translate_isl_ast_to_gimple::
961 translate_isl_ast_node_if (loop_p context_loop
,
962 __isl_keep isl_ast_node
*node
,
963 edge next_e
, ivs_params
&ip
)
965 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
966 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
967 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
968 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
969 merge_points
.safe_push (last_e
);
971 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
972 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
973 isl_ast_node_free (then_node
);
975 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
976 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
977 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
978 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
980 isl_ast_node_free (else_node
);
984 /* Translates an isl AST node NODE to GCC representation in the
985 context of a SESE. */
987 edge
translate_isl_ast_to_gimple::
988 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
989 edge next_e
, ivs_params
&ip
)
991 if (codegen_error_p ())
994 switch (isl_ast_node_get_type (node
))
996 case isl_ast_node_error
:
999 case isl_ast_node_for
:
1000 return translate_isl_ast_node_for (context_loop
, node
,
1003 case isl_ast_node_if
:
1004 return translate_isl_ast_node_if (context_loop
, node
,
1007 case isl_ast_node_user
:
1008 return translate_isl_ast_node_user (node
, next_e
, ip
);
1010 case isl_ast_node_block
:
1011 return translate_isl_ast_node_block (context_loop
, node
,
1014 case isl_ast_node_mark
:
1016 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1017 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1018 isl_ast_node_free (n
);
1027 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1028 at the exit of loop which takes one argument that is the last value of the
1029 variable being used out of the loop. */
1032 bb_contains_loop_close_phi_nodes (basic_block bb
)
1034 return single_pred_p (bb
)
1035 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1038 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1039 header containing phi nodes which has one init-edge and one back-edge. */
1042 bb_contains_loop_phi_nodes (basic_block bb
)
1044 if (EDGE_COUNT (bb
->preds
) != 2)
1047 unsigned depth
= loop_depth (bb
->loop_father
);
1049 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1051 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1052 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1055 /* When one of the edges correspond to the same loop father and other
1057 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1058 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1061 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1062 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1068 /* Check if USE is defined in a basic block from where the definition of USE can
1069 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1072 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1074 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1077 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1078 if (bb_contains_loop_close_phi_nodes (bb
))
1081 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1082 basic_block def_bb
= gimple_bb (def
);
1084 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1087 /* Return the number of phi nodes in BB. */
1090 number_of_phi_nodes (basic_block bb
)
1093 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1099 /* Returns true if BB uses name in one of its PHIs. */
1102 phi_uses_name (basic_block bb
, tree name
)
1104 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1107 gphi
*phi
= psi
.phi ();
1108 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1110 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1111 if (use_arg
== name
)
1118 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1119 definition should flow into use, and the use should respect the loop-closed
1122 bool translate_isl_ast_to_gimple::
1123 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1124 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1126 /* The def of the rename must either dominate the uses or come from a
1127 back-edge. Also the def must respect the loop closed ssa form. */
1128 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1132 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1133 print_generic_expr (dump_file
, rename
, 0);
1134 fprintf (dump_file
, "\n");
1139 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1142 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1144 /* The loop-header dominates the loop-body. */
1145 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1148 /* RENAME would be used in loop-phi. */
1149 gcc_assert (number_of_phi_nodes (use_bb
));
1151 /* For definitions coming from back edges, we should check that
1152 old_name is used in a loop PHI node.
1153 FIXME: Verify if this is true. */
1154 if (phi_uses_name (old_bb
, old_name
))
1160 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1161 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1163 tree
translate_isl_ast_to_gimple::
1164 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1165 phi_node_kind phi_kind
) const
1167 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1168 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1170 if (!renames
|| renames
->is_empty ())
1173 if (1 == renames
->length ())
1175 tree rename
= (*renames
)[0];
1176 if (TREE_CODE (rename
) == SSA_NAME
)
1178 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1179 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1180 && (phi_kind
== close_phi
1181 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1186 if (is_constant (rename
))
1192 /* More than one renames corresponding to the old_name. Find the rename for
1193 which the definition flows into usage at new_bb. */
1195 tree t1
= NULL_TREE
, t2
;
1196 basic_block t1_bb
= NULL
;
1197 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1199 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1201 /* Defined in the same basic block as used. */
1202 if (t2_bb
== new_bb
)
1205 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1206 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1209 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1212 /* Compute the nearest dominator. */
1213 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1223 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1224 When OLD_NAME and EXPR are the same we assert. */
1226 void translate_isl_ast_to_gimple::
1227 set_rename (tree old_name
, tree expr
)
1231 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1232 print_generic_expr (dump_file
, old_name
, 0);
1233 fprintf (dump_file
, ", new_name = ");
1234 print_generic_expr (dump_file
, expr
, 0);
1235 fprintf (dump_file
, "\n");
1238 if (old_name
== expr
)
1241 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1244 renames
->safe_push (expr
);
1250 region
->rename_map
->put (old_name
, r
);
1255 /* For a parameter of a scop we don't want to rename it. */
1256 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1258 region
->parameter_rename_map
->put(old_name
, expr
);
1261 /* Return an iterator to the instructions comes last in the execution order.
1262 Either GSI1 and GSI2 should belong to the same basic block or one of their
1263 respective basic blocks should dominate the other. */
1265 gimple_stmt_iterator
1266 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1268 basic_block bb1
= gsi_bb (gsi1
);
1269 basic_block bb2
= gsi_bb (gsi2
);
1271 /* Find the iterator which is the latest. */
1274 gimple
*stmt1
= gsi_stmt (gsi1
);
1275 gimple
*stmt2
= gsi_stmt (gsi2
);
1277 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1279 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1280 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1282 if (is_phi1
!= is_phi2
)
1283 return is_phi1
? gsi2
: gsi1
;
1286 /* For empty basic blocks gsis point to the end of the sequence. Since
1287 there is no operator== defined for gimple_stmt_iterator and for gsis
1288 not pointing to a valid statement gsi_next would assert. */
1289 gimple_stmt_iterator gsi
= gsi1
;
1291 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1294 } while (!gsi_end_p (gsi
));
1299 /* Find the basic block closest to the basic block which defines stmt. */
1300 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1303 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1307 /* Insert each statement from SEQ at its earliest insertion p. */
1309 void translate_isl_ast_to_gimple::
1310 gsi_insert_earliest (gimple_seq seq
)
1312 update_modified_stmts (seq
);
1313 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1314 basic_block begin_bb
= get_entry_bb (codegen_region
);
1316 /* Inserting the gimple statements in a vector because gimple_seq behave
1317 in strage ways when inserting the stmts from it into different basic
1318 blocks one at a time. */
1319 auto_vec
<gimple
*, 3> stmts
;
1320 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1322 stmts
.safe_push (gsi_stmt (gsi
));
1326 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1328 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1329 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1331 use_operand_p use_p
;
1332 ssa_op_iter op_iter
;
1333 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1335 /* Iterator to the current def of use_p. For function parameters or
1336 anything where def is not found, insert at the beginning of the
1337 generated region. */
1338 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1340 tree op
= USE_FROM_PTR (use_p
);
1341 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1342 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1343 gsi_stmt
= gsi_for_stmt (stmt
);
1345 /* For region parameters, insert at the beginning of the generated
1347 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1348 gsi_stmt
= gsi_def_stmt
;
1350 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1353 if (!gsi_stmt (gsi_def_stmt
))
1355 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1356 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1358 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1360 gimple_stmt_iterator bsi
1361 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1362 /* Insert right after the PHI statements. */
1363 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1366 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1370 fprintf (dump_file
, "[codegen] inserting statement: ");
1371 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1372 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1377 /* Collect all the operands of NEW_EXPR by recursively visiting each
1380 void translate_isl_ast_to_gimple::
1381 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1383 if (new_expr
== NULL_TREE
)
1386 /* Rename all uses in new_expr. */
1387 if (TREE_CODE (new_expr
) == SSA_NAME
)
1389 vec_ssa
->safe_push (new_expr
);
1393 /* Iterate over SSA_NAMES in NEW_EXPR. */
1394 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1396 tree op
= TREE_OPERAND (new_expr
, i
);
1397 collect_all_ssa_names (op
, vec_ssa
);
1401 /* This is abridged version of the function copied from:
1402 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1405 substitute_ssa_name (tree exp
, tree f
, tree r
)
1407 enum tree_code code
= TREE_CODE (exp
);
1408 tree op0
, op1
, op2
, op3
;
1411 /* We handle TREE_LIST and COMPONENT_REF separately. */
1412 if (code
== TREE_LIST
)
1414 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1415 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1416 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1419 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1421 else if (code
== COMPONENT_REF
)
1425 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1426 and it is the right field, replace it with R. */
1427 for (inner
= TREE_OPERAND (exp
, 0);
1428 REFERENCE_CLASS_P (inner
);
1429 inner
= TREE_OPERAND (inner
, 0))
1433 op1
= TREE_OPERAND (exp
, 1);
1435 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1438 /* If this expression hasn't been completed let, leave it alone. */
1439 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1442 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1443 if (op0
== TREE_OPERAND (exp
, 0))
1447 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1450 switch (TREE_CODE_CLASS (code
))
1455 case tcc_declaration
:
1461 case tcc_expression
:
1467 case tcc_exceptional
:
1470 case tcc_comparison
:
1472 switch (TREE_CODE_LENGTH (code
))
1480 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1481 if (op0
== TREE_OPERAND (exp
, 0))
1484 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1488 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1489 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1491 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1494 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1498 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1499 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1500 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1502 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1503 && op2
== TREE_OPERAND (exp
, 2))
1506 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
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
);
1513 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1515 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1516 && op2
== TREE_OPERAND (exp
, 2)
1517 && op3
== TREE_OPERAND (exp
, 3))
1521 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1534 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1536 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1537 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1542 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1544 tree
translate_isl_ast_to_gimple::
1545 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1547 auto_vec
<tree
, 2> ssa_names
;
1548 collect_all_ssa_names (new_expr
, &ssa_names
);
1551 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1552 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1553 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1558 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1559 scalar evolution around LOOP. */
1561 tree
translate_isl_ast_to_gimple::
1562 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1563 basic_block new_bb
, basic_block old_bb
,
1566 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1568 /* At this point we should know the exact scev for each
1569 scalar SSA_NAME used in the scop: all the other scalar
1570 SSA_NAMEs should have been translated out of SSA using
1571 arrays with one element. */
1573 if (chrec_contains_undetermined (scev
))
1575 codegen_error
= true;
1576 return build_zero_cst (TREE_TYPE (old_name
));
1579 new_expr
= chrec_apply_map (scev
, iv_map
);
1581 /* The apply should produce an expression tree containing
1582 the uses of the new induction variables. We should be
1583 able to use new_expr instead of the old_name in the newly
1584 generated loop nest. */
1585 if (chrec_contains_undetermined (new_expr
)
1586 || tree_contains_chrecs (new_expr
, NULL
))
1588 codegen_error
= true;
1589 return build_zero_cst (TREE_TYPE (old_name
));
1592 if (TREE_CODE (new_expr
) == SSA_NAME
)
1594 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1595 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1597 codegen_error
= true;
1598 return build_zero_cst (TREE_TYPE (old_name
));
1602 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1604 /* We check all the operands and all of them should dominate the use at
1606 auto_vec
<tree
, 2> new_ssa_names
;
1607 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1610 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1612 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1614 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1615 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1617 codegen_error
= true;
1618 return build_zero_cst (TREE_TYPE (old_name
));
1623 /* Replace the old_name with the new_expr. */
1624 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1628 /* Renames the scalar uses of the statement COPY, using the
1629 substitution map RENAME_MAP, inserting the gimplification code at
1630 GSI_TGT, for the translation REGION, with the original copied
1631 statement in LOOP, and using the induction variable renaming map
1632 IV_MAP. Returns true when something has been renamed. */
1634 bool translate_isl_ast_to_gimple::
1635 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1636 loop_p loop
, vec
<tree
> iv_map
)
1638 bool changed
= false;
1640 if (is_gimple_debug (copy
))
1642 if (gimple_debug_bind_p (copy
))
1643 gimple_debug_bind_reset_value (copy
);
1644 else if (gimple_debug_source_bind_p (copy
))
1654 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1655 print_gimple_stmt (dump_file
, copy
, 0, 0);
1658 use_operand_p use_p
;
1659 ssa_op_iter op_iter
;
1660 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1662 tree old_name
= USE_FROM_PTR (use_p
);
1666 fprintf (dump_file
, "[codegen] renaming old_name = ");
1667 print_generic_expr (dump_file
, old_name
, 0);
1668 fprintf (dump_file
, "\n");
1671 if (TREE_CODE (old_name
) != SSA_NAME
1672 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1676 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1677 old_bb
, unknown_phi
);
1681 tree type_old_name
= TREE_TYPE (old_name
);
1682 tree type_new_expr
= TREE_TYPE (new_expr
);
1686 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1687 print_generic_expr (dump_file
, new_expr
, 0);
1688 fprintf (dump_file
, "\n");
1691 if (type_old_name
!= type_new_expr
1692 || TREE_CODE (new_expr
) != SSA_NAME
)
1694 tree var
= create_tmp_var (type_old_name
, "var");
1696 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1697 new_expr
= fold_convert (type_old_name
, new_expr
);
1700 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1701 gsi_insert_earliest (stmts
);
1704 replace_exp (use_p
, new_expr
);
1709 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1711 if (!new_expr
|| codegen_error_p ())
1716 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1717 print_generic_expr (dump_file
, new_expr
, 0);
1718 fprintf (dump_file
, "\n");
1721 gsi_insert_earliest (stmts
);
1722 replace_exp (use_p
, new_expr
);
1724 if (TREE_CODE (new_expr
) == INTEGER_CST
1725 && is_gimple_assign (copy
))
1727 tree rhs
= gimple_assign_rhs1 (copy
);
1729 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1730 recompute_tree_invariant_for_addr_expr (rhs
);
1733 set_rename (old_name
, new_expr
);
1739 /* Returns a basic block that could correspond to where a constant was defined
1740 in the original code. In the original code OLD_BB had the definition, we
1741 need to find which basic block out of the copies of old_bb, in the new
1742 region, should a definition correspond to if it has to reach BB. */
1744 basic_block
translate_isl_ast_to_gimple::
1745 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1747 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1749 if (!bbs
|| bbs
->is_empty ())
1752 if (1 == bbs
->length ())
1756 basic_block b1
= NULL
, b2
;
1757 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1762 /* BB and B2 are in two unrelated if-clauses. */
1763 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1766 /* Compute the nearest dominator. */
1767 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1774 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1775 determines the kind of phi node. */
1777 tree
translate_isl_ast_to_gimple::
1778 get_new_name (basic_block new_bb
, tree op
,
1779 basic_block old_bb
, phi_node_kind phi_kind
) const
1781 /* For constants the names are the same. */
1782 if (TREE_CODE (op
) != SSA_NAME
)
1785 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1788 /* Return a debug location for OP. */
1793 location_t loc
= UNKNOWN_LOCATION
;
1795 if (TREE_CODE (op
) == SSA_NAME
)
1796 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1800 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1801 the init edge (from outside the loop) and the second one is the back edge
1802 from the same loop. */
1804 std::pair
<edge
, edge
>
1805 get_edges (basic_block bb
)
1807 std::pair
<edge
, edge
> edges
;
1810 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1811 if (bb
->loop_father
!= e
->src
->loop_father
)
1818 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1819 must be found unless they can be POSTPONEd for later. */
1821 bool translate_isl_ast_to_gimple::
1822 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1823 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1826 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1828 basic_block new_bb
= gimple_bb (new_phi
);
1829 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1832 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1833 e
= ibp_new_bb
.first
;
1835 e
= ibp_new_bb
.second
;
1837 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1838 tree new_name
= get_new_name (new_bb
, old_name
,
1839 gimple_bb (old_phi
), loop_phi
);
1842 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1846 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1847 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1848 /* If the phi arg was a function arg, or wasn't defined, just use the
1850 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1853 /* Postpone code gen for later for those back-edges we don't have the
1855 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1857 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1860 /* Either we should add the arg to phi or, we should postpone. */
1866 /* Copy loop phi nodes from BB to NEW_BB. */
1868 bool translate_isl_ast_to_gimple::
1869 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1872 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1875 /* Loop phi nodes should have only two arguments. */
1876 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1878 /* First edge is the init edge and second is the back edge. */
1879 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1881 /* First edge is the init edge and second is the back edge. */
1882 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1884 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1887 gphi
*phi
= psi
.phi ();
1888 tree res
= gimple_phi_result (phi
);
1889 if (virtual_operand_p (res
))
1891 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1894 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1895 tree new_res
= create_new_def_for (res
, new_phi
,
1896 gimple_phi_result_ptr (new_phi
));
1897 set_rename (res
, new_res
);
1898 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1900 update_stmt (new_phi
);
1904 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1905 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
1912 /* Return the init value of PHI, the value coming from outside the loop. */
1915 get_loop_init_value (gphi
*phi
)
1918 loop_p loop
= gimple_bb (phi
)->loop_father
;
1922 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1923 if (e
->src
->loop_father
!= loop
)
1924 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1929 /* Find the init value (the value which comes from outside the loop), of one of
1930 the operands of DEF which is defined by a loop phi. */
1933 find_init_value (gimple
*def
)
1935 if (gimple_code (def
) == GIMPLE_PHI
)
1936 return get_loop_init_value (as_a
<gphi
*> (def
));
1938 if (gimple_vuse (def
))
1942 use_operand_p use_p
;
1943 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1945 tree use
= USE_FROM_PTR (use_p
);
1946 if (TREE_CODE (use
) == SSA_NAME
)
1948 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1956 /* Return the init value, the value coming from outside the loop. */
1959 find_init_value_close_phi (gphi
*phi
)
1961 gcc_assert (gimple_phi_num_args (phi
) == 1);
1962 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1963 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1964 return find_init_value (def
);
1968 tree
translate_isl_ast_to_gimple::
1969 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1970 gimple
*old_close_phi
)
1972 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1973 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1974 basic_block bb
= gimple_bb (stmt
);
1975 if (!bb_in_sese_p (bb
, codegen_region
))
1976 return last_merge_name
;
1978 loop_p loop
= bb
->loop_father
;
1979 if (!loop_in_sese_p (loop
, codegen_region
))
1980 return last_merge_name
;
1982 edge e
= single_exit (loop
);
1984 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1985 return last_merge_name
;
1987 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1988 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1991 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
1992 bb
= split_edge (e
);
1994 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
1995 tree res
= create_new_def_for (last_merge_name
, close_phi
,
1996 gimple_phi_result_ptr (close_phi
));
1997 set_rename (old_close_phi_name
, res
);
1998 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
1999 last_merge_name
= res
;
2001 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2004 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2005 the close phi node PHI. */
2007 bool translate_isl_ast_to_gimple::
2008 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2011 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2012 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2013 if (SSA_NAME
== TREE_CODE (default_value
))
2015 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2016 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2018 default_value_bb
= gimple_bb (stmt
);
2021 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2023 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2024 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2025 tree last_merge_name
= new_close_phi_name
;
2026 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2030 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2032 basic_block new_merge_bb
= merge_e
->src
;
2033 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2036 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2039 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2040 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2041 gimple_phi_result_ptr (merge_phi
));
2042 set_rename (old_close_phi_name
, merge_res
);
2044 edge from_loop
= NULL
, from_default_value
= NULL
;
2047 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2048 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2051 from_default_value
= e
;
2053 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2054 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2055 is contained in another condition. */
2056 if (!from_default_value
|| !from_loop
)
2059 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2060 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2064 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2065 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2068 update_stmt (merge_phi
);
2069 last_merge_name
= merge_res
;
2075 /* Copy all the loop-close phi args from BB to NEW_BB. */
2077 bool translate_isl_ast_to_gimple::
2078 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
, bool postpone
)
2080 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2083 gphi
*old_close_phi
= psi
.phi ();
2084 tree res
= gimple_phi_result (old_close_phi
);
2085 if (virtual_operand_p (res
))
2088 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2089 /* Loop close phi nodes should not be scev_analyzable_p. */
2092 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2093 tree new_res
= create_new_def_for (res
, new_close_phi
,
2094 gimple_phi_result_ptr (new_close_phi
));
2095 set_rename (res
, new_res
);
2097 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2098 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2100 /* Predecessor basic blocks of a loop close phi should have been code
2101 generated before. FIXME: This is fixable by merging PHIs from inner
2102 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2106 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2107 get_loc (old_name
));
2110 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2111 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2114 update_stmt (new_close_phi
);
2116 /* When there is no loop guard around this codegenerated loop, there is no
2117 need to collect the close-phi arg. */
2118 if (merge_points
.is_empty ())
2121 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2122 tree default_value
= find_init_value_close_phi (new_close_phi
);
2124 /* A close phi must come from a loop-phi having a default value. */
2130 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2134 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2135 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2140 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2148 /* Copy loop close phi nodes from BB to NEW_BB. */
2150 bool translate_isl_ast_to_gimple::
2151 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
)
2154 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2156 /* Loop close phi nodes should have only one argument. */
2157 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2159 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2163 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2164 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2165 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2166 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2169 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2170 In this case DOMINATING_PRED = NULL.
2172 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2174 Returns true on successful copy of the args, false otherwise. */
2176 bool translate_isl_ast_to_gimple::
2177 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2178 edge old_bb_dominating_edge
,
2179 edge old_bb_non_dominating_edge
,
2180 gphi
*phi
, gphi
*new_phi
,
2183 basic_block def_pred
[2] = { NULL
, NULL
};
2184 int not_found_bb_index
= -1;
2185 for (int i
= 0; i
< 2; i
++)
2187 /* If the corresponding def_bb could not be found the entry will be
2189 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2190 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2191 gimple_phi_arg_edge (phi
, i
)->src
);
2192 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2193 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2197 /* When non are available bail out. */
2198 if (not_found_bb_index
!= -1)
2200 not_found_bb_index
= i
;
2204 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2205 if (old_bb_dominating_edge
)
2207 if (not_found_bb_index
!= -1)
2210 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2211 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2212 vec
<basic_block
> *bbs
2213 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2215 /* Could not find a mapping. */
2219 basic_block new_pred
= NULL
;
2222 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2224 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2226 /* FIXME: If we have already found new_pred then we have to
2227 disambiguate, bail out for now. */
2230 new_pred
= new_pred1
;
2232 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2234 /* FIXME: If we have already found new_pred then we have to either
2235 it dominates both or we have to disambiguate, bail out. */
2238 new_pred
= new_pred2
;
2245 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2246 gcc_assert (new_non_dominating_edge
);
2247 /* FIXME: Validate each args just like in loop-phis. */
2248 /* By the process of elimination we first insert insert phi-edge for
2249 non-dominating pred which is computed above and then we insert the
2251 int inserted_edge
= 0;
2252 for (; inserted_edge
< 2; inserted_edge
++)
2254 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2255 if (new_non_dominating_edge
== new_bb_pred_edge
)
2257 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2258 new_non_dominating_edge
,
2259 get_loc (old_phi_args
[inserted_edge
]));
2263 if (inserted_edge
== 2)
2266 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2268 edge new_dominating_edge
= NULL
;
2269 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2271 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2272 if (e
!= new_non_dominating_edge
)
2274 new_dominating_edge
= e
;
2275 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2276 new_dominating_edge
,
2277 get_loc (old_phi_args
[inserted_edge
]));
2281 gcc_assert (new_dominating_edge
);
2285 /* Classic diamond structure: both edges are non-dominating. We need to
2286 find one unique edge then the other can be found be elimination. If
2287 any definition (def_pred) dominates both the preds of new_bb then we
2288 bail out. Entries of def_pred maybe NULL, in that case we must
2289 uniquely find pred with help of only one entry. */
2290 edge new_e
[2] = { NULL
, NULL
};
2291 for (int i
= 0; i
< 2; i
++)
2295 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2297 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2300 /* We do not know how to handle the case when def_pred
2301 dominates more than a predecessor. */
2307 gcc_assert (new_e
[0] || new_e
[1]);
2309 /* Find the other edge by process of elimination. */
2310 if (not_found_bb_index
!= -1)
2312 gcc_assert (!new_e
[not_found_bb_index
]);
2313 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2316 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2318 if (new_e
[found_bb_index
] == e
)
2320 new_e
[not_found_bb_index
] = e
;
2324 /* Add edges to phi args. */
2325 for (int i
= 0; i
< 2; i
++)
2326 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2327 get_loc (old_phi_args
[i
]));
2333 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2334 region. If postpone is true and it isn't possible to copy any arg of PHI,
2335 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2336 Returns false if the copying was unsuccessful. */
2338 bool translate_isl_ast_to_gimple::
2339 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2342 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2343 gcc_assert (2 == gimple_phi_num_args (phi
));
2345 basic_block new_bb
= gimple_bb (new_phi
);
2346 loop_p loop
= gimple_bb (phi
)->loop_father
;
2348 basic_block old_bb
= gimple_bb (phi
);
2349 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2353 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2354 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2355 old_bb_non_dominating_edge
= e
;
2357 old_bb_dominating_edge
= e
;
2359 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2360 old_bb_non_dominating_edge
->src
));
2362 tree new_phi_args
[2];
2363 tree old_phi_args
[2];
2365 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2367 tree old_name
= gimple_phi_arg_def (phi
, i
);
2368 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2369 old_phi_args
[i
] = old_name
;
2372 new_phi_args
[i
] = new_name
;
2376 /* If the phi-arg was a parameter. */
2377 if (vec_find (region
->params
, old_name
) != -1)
2379 new_phi_args
[i
] = old_name
;
2383 "[codegen] parameter argument to phi, new_expr: ");
2384 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2385 fprintf (dump_file
, "\n");
2390 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2391 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2392 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2398 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2399 if (is_gimple_reg (old_name
)
2400 && scev_analyzable_p (old_name
, region
->region
))
2403 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2404 new_bb
, old_bb
, iv_map
);
2405 if (codegen_error_p ())
2408 gcc_assert (new_expr
);
2412 "[codegen] scev analyzeable, new_expr: ");
2413 print_generic_expr (dump_file
, new_expr
, 0);
2414 fprintf (dump_file
, "\n");
2416 gsi_insert_earliest (stmts
);
2417 new_phi_args
[i
] = new_expr
;
2421 /* Postpone code gen for later for back-edges. */
2422 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2426 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2427 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2430 new_phi_args
[i
] = NULL_TREE
;
2434 /* Either we should add the arg to phi or, we should postpone. */
2438 /* If none of the args have been determined in the first stage then wait until
2440 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2443 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2444 old_bb_dominating_edge
,
2445 old_bb_non_dominating_edge
,
2446 phi
, new_phi
, new_bb
);
2449 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2450 containing phi nodes coming from two predecessors, and none of them are back
2453 bool translate_isl_ast_to_gimple::
2454 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2457 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2459 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2460 if (EDGE_COUNT (bb
->preds
) != 2)
2464 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2467 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2470 gphi
*phi
= psi
.phi ();
2471 tree res
= gimple_phi_result (phi
);
2472 if (virtual_operand_p (res
))
2475 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2476 tree new_res
= create_new_def_for (res
, new_phi
,
2477 gimple_phi_result_ptr (new_phi
));
2478 set_rename (res
, new_res
);
2480 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2483 update_stmt (new_phi
);
2489 /* Return true if STMT should be copied from region to the new code-generated
2490 region. LABELs, CONDITIONS, induction-variables and region parameters need
2494 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2496 /* Do not copy labels or conditions. */
2497 if (gimple_code (stmt
) == GIMPLE_LABEL
2498 || gimple_code (stmt
) == GIMPLE_COND
)
2502 /* Do not copy induction variables. */
2503 if (is_gimple_assign (stmt
)
2504 && (lhs
= gimple_assign_lhs (stmt
))
2505 && TREE_CODE (lhs
) == SSA_NAME
2506 && is_gimple_reg (lhs
)
2507 && scev_analyzable_p (lhs
, region
->region
))
2510 /* Do not copy parameters that have been generated in the header of the
2512 if (is_gimple_assign (stmt
)
2513 && (lhs
= gimple_assign_lhs (stmt
))
2514 && TREE_CODE (lhs
) == SSA_NAME
2515 && region
->parameter_rename_map
->get(lhs
))
2521 /* Create new names for all the definitions created by COPY and add replacement
2522 mappings for each new name. */
2524 void translate_isl_ast_to_gimple::
2525 set_rename_for_each_def (gimple
*stmt
)
2527 def_operand_p def_p
;
2528 ssa_op_iter op_iter
;
2529 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2531 tree old_name
= DEF_FROM_PTR (def_p
);
2532 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2533 set_rename (old_name
, new_name
);
2537 /* Duplicates the statements of basic block BB into basic block NEW_BB
2538 and compute the new induction variables according to the IV_MAP. */
2540 bool translate_isl_ast_to_gimple::
2541 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2544 /* Iterator poining to the place where new statement (s) will be inserted. */
2545 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2547 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2550 gimple
*stmt
= gsi_stmt (gsi
);
2551 if (!should_copy_to_new_region (stmt
, region
))
2554 /* Create a new copy of STMT and duplicate STMT's virtual
2556 gimple
*copy
= gimple_copy (stmt
);
2557 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2561 fprintf (dump_file
, "[codegen] inserting statement: ");
2562 print_gimple_stmt (dump_file
, copy
, 0, 0);
2565 maybe_duplicate_eh_stmt (copy
, stmt
);
2566 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2568 /* Crete new names for each def in the copied stmt. */
2569 set_rename_for_each_def (copy
);
2571 loop_p loop
= bb
->loop_father
;
2572 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2574 fold_stmt_inplace (&gsi_tgt
);
2575 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2578 if (codegen_error_p ())
2581 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2583 use_operand_p use_p
;
2584 if (!is_gimple_debug (copy
))
2585 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2587 tree old_name
= USE_FROM_PTR (use_p
);
2589 if (TREE_CODE (old_name
) != SSA_NAME
2590 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2593 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2597 replace_exp (use_p
, *new_expr
);
2607 /* Given a basic block containing close-phi it returns the new basic block where
2608 to insert a copy of the close-phi nodes. All the uses in close phis should
2609 come from a single loop otherwise it returns NULL. */
2611 edge
translate_isl_ast_to_gimple::
2612 edge_for_new_close_phis (basic_block bb
)
2614 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2615 of close phi in the original code and then find the mapping of basic block
2616 defining that variable. If there are multiple close-phis and they are
2617 defined in different loops (in the original or in the new code) because of
2618 loop splitting, then we bail out. */
2619 loop_p new_loop
= NULL
;
2620 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2623 gphi
*phi
= psi
.phi ();
2624 tree name
= gimple_phi_arg_def (phi
, 0);
2625 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2627 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2628 if (!bbs
|| bbs
->length () != 1)
2629 /* This is one of the places which shows preserving original structure
2630 is not always possible, as we may need to insert close PHI for a loop
2631 where the latch does not have any mapping, or the mapping is
2636 new_loop
= (*bbs
)[0]->loop_father
;
2637 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2644 return single_exit (new_loop
);
2647 /* Copies BB and includes in the copied BB all the statements that can
2648 be reached following the use-def chains from the memory accesses,
2649 and returns the next edge following this new block. */
2651 edge
translate_isl_ast_to_gimple::
2652 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2654 int num_phis
= number_of_phi_nodes (bb
);
2656 if (region
->copied_bb_map
->get (bb
))
2658 /* FIXME: we should be able to handle phi nodes with args coming from
2659 outside the region. */
2662 codegen_error
= true;
2667 basic_block new_bb
= NULL
;
2668 if (bb_contains_loop_close_phi_nodes (bb
))
2671 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2674 edge e
= edge_for_new_close_phis (bb
);
2677 codegen_error
= true;
2681 basic_block phi_bb
= e
->dest
;
2683 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2684 phi_bb
= split_edge (e
);
2686 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2687 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2689 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2691 codegen_error
= true;
2698 new_bb
= split_edge (next_e
);
2702 new_bb
= split_edge (next_e
);
2703 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2705 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2707 /* At this point we are unable to codegenerate by still preserving the SSA
2708 structure because maybe the loop is completely unrolled and the PHIs
2709 and cross-bb scalar dependencies are untrackable w.r.t. the original
2710 code. See gfortran.dg/graphite/pr29832.f90. */
2711 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2713 codegen_error
= true;
2717 /* In case isl did some loop peeling, like this:
2720 for (int c1 = 1; c1 <= 5; c1 += 1) {
2725 there should be no loop-phi nodes in S_8(0).
2727 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2728 values of all scalar variables: for the moment we instantiate only
2729 SCEV analyzable expressions on the iteration domain, and we need to
2730 extend that to reductions that cannot be analyzed by SCEV. */
2731 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2733 codegen_error
= true;
2738 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2740 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2742 codegen_error
= true;
2746 else if (num_phis
> 0)
2749 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2752 basic_block phi_bb
= single_pred (new_bb
);
2753 loop_p loop_father
= new_bb
->loop_father
;
2755 /* Move back until we find the block with two predecessors. */
2756 while (single_pred_p (phi_bb
))
2757 phi_bb
= single_pred_edge (phi_bb
)->src
;
2759 /* If a corresponding merge-point was not found, then abort codegen. */
2760 if (phi_bb
->loop_father
!= loop_father
2761 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2762 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2764 codegen_error
= true;
2771 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2772 bb
->index
, new_bb
->index
);
2774 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2776 copied_bbs
->safe_push (new_bb
);
2779 vec
<basic_block
> bbs
;
2781 bbs
.safe_push (new_bb
);
2782 region
->copied_bb_map
->put (bb
, bbs
);
2785 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2787 codegen_error
= true;
2791 return single_succ_edge (new_bb
);
2794 /* Patch the missing arguments of the phi nodes. */
2796 void translate_isl_ast_to_gimple::
2797 translate_pending_phi_nodes ()
2801 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2803 gphi
*old_phi
= rename
->first
;
2804 gphi
*new_phi
= rename
->second
;
2805 basic_block old_bb
= gimple_bb (old_phi
);
2806 basic_block new_bb
= gimple_bb (new_phi
);
2808 /* First edge is the init edge and second is the back edge. */
2809 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2810 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2814 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2815 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2818 auto_vec
<tree
, 1> iv_map
;
2819 if (bb_contains_loop_phi_nodes (new_bb
))
2820 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2822 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2823 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2825 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2829 fprintf (dump_file
, "[codegen] to new-phi: ");
2830 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2832 if (codegen_error_p ())
2837 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2839 void translate_isl_ast_to_gimple::
2840 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2842 sese_info_p region
= scop
->scop_info
;
2843 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2844 gcc_assert (nb_parameters
== region
->params
.length ());
2846 for (i
= 0; i
< nb_parameters
; i
++)
2848 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2850 ip
[tmp_id
] = region
->params
[i
];
2855 /* Generates a build, which specifies the constraints on the parameters. */
2857 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2858 generate_isl_context (scop_p scop
)
2860 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2861 return isl_ast_build_from_context (context_isl
);
2864 /* This method is executed before the construction of a for node. */
2866 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2868 isl_union_map
*dependences
= (isl_union_map
*) user
;
2869 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2870 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2871 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2872 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2873 for_info
->is_parallelizable
=
2874 !carries_deps (schedule
, dependences
, dimension
);
2875 isl_union_map_free (schedule
);
2876 isl_space_free (schedule_space
);
2877 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2881 /* Generate isl AST from schedule of SCOP. */
2883 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2884 scop_to_isl_ast (scop_p scop
)
2886 gcc_assert (scop
->transformed_schedule
);
2888 /* Set the separate option to reduce control flow overhead. */
2889 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2890 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2891 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2893 if (flag_loop_parallelize_all
)
2895 scop_get_dependences (scop
);
2897 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2901 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2902 (context_isl
, schedule
);
2903 isl_ast_build_free (context_isl
);
2907 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2908 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2911 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2912 gimple_stmt_iterator
*gsi
)
2914 if (!defined_in_sese_p (tr
, region
->region
))
2918 use_operand_p use_p
;
2919 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2921 tree use_tr
= USE_FROM_PTR (use_p
);
2923 /* Do not copy parameters that have been generated in the header of the
2925 if (region
->parameter_rename_map
->get(use_tr
))
2928 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2932 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2935 gimple
*copy
= gimple_copy (def_stmt
);
2936 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2938 /* Create new names for all the definitions created by COPY and
2939 add replacement mappings for each new name. */
2940 def_operand_p def_p
;
2941 ssa_op_iter op_iter
;
2942 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2944 tree old_name
= DEF_FROM_PTR (def_p
);
2945 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2946 region
->parameter_rename_map
->put(old_name
, new_name
);
2953 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2955 /* For all the parameters which definitino is in the if_region->false_region,
2956 insert code on true_region (if_region->true_region->entry). */
2960 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2962 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2964 // If def is not in region.
2965 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2967 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2971 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2972 Return true if code generation succeeded. */
2975 graphite_regenerate_ast_isl (scop_p scop
)
2977 sese_info_p region
= scop
->scop_info
;
2978 translate_isl_ast_to_gimple
t (region
);
2980 ifsese if_region
= NULL
;
2981 isl_ast_node
*root_node
;
2984 timevar_push (TV_GRAPHITE_CODE_GEN
);
2985 t
.add_parameters_to_ivs_params (scop
, ip
);
2986 root_node
= t
.scop_to_isl_ast (scop
);
2988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2990 fprintf (dump_file
, "[scheduler] original schedule:\n");
2991 print_isl_schedule (dump_file
, scop
->original_schedule
);
2992 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
2993 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
2995 fprintf (dump_file
, "[scheduler] original ast:\n");
2996 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
2997 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
2998 print_isl_ast (dump_file
, root_node
);
3001 recompute_all_dominators ();
3004 if_region
= move_sese_in_condition (region
);
3005 region
->if_region
= if_region
;
3006 recompute_all_dominators ();
3008 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3010 /* Copy all the parameters which are defined in the region. */
3011 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3013 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3014 basic_block bb
= split_edge (e
);
3016 /* Update the true_region exit edge. */
3017 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3019 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3020 if (t
.codegen_error_p ())
3023 fprintf (dump_file
, "codegen error: "
3024 "reverting back to the original code.\n");
3025 set_ifsese_condition (if_region
, integer_zero_node
);
3029 t
.translate_pending_phi_nodes ();
3030 if (!t
.codegen_error_p ())
3032 sese_insert_phis_for_liveouts (region
,
3033 if_region
->region
->region
.exit
->src
,
3034 if_region
->false_region
->region
.exit
,
3035 if_region
->true_region
->region
.exit
);
3036 mark_virtual_operands_for_renaming (cfun
);
3037 update_ssa (TODO_update_ssa
);
3042 recompute_all_dominators ();
3046 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
3051 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3052 " pending phis, reverting back to the original code.\n");
3053 set_ifsese_condition (if_region
, integer_zero_node
);
3057 free (if_region
->true_region
);
3058 free (if_region
->region
);
3061 ivs_params_clear (ip
);
3062 isl_ast_node_free (root_node
);
3063 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3068 int num_no_dependency
= 0;
3070 FOR_EACH_LOOP (loop
, 0)
3071 if (loop
->can_be_parallel
)
3072 num_no_dependency
++;
3074 fprintf (dump_file
, "%d loops carried no dependency.\n",
3078 return !t
.codegen_error_p ();
3081 #endif /* HAVE_isl */