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 (int_mode_for_size (MAX_FIXED_MODE_SIZE
, 0).require ());
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_guard (edge entry_edge
,
197 __isl_take isl_ast_expr
*if_cond
,
199 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
200 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
202 void translate_pending_phi_nodes (void);
203 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
204 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
206 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
208 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
209 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
210 tree
get_rename (basic_block new_bb
, tree old_name
,
211 basic_block old_bb
, phi_node_kind
) const;
212 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
213 basic_block new_bb
, basic_block old_bb
,
215 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
216 tree
get_new_name (basic_block new_bb
, tree op
,
217 basic_block old_bb
, phi_node_kind
) const;
218 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
219 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
220 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
222 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
223 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
225 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
226 gimple
*old_close_phi
);
227 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
228 vec
<tree
> iv_map
, bool postpone
);
229 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
231 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
233 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
235 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
237 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
239 edge
edge_for_new_close_phis (basic_block bb
);
240 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
241 edge old_bb_dominating_edge
,
242 edge old_bb_non_dominating_edge
,
243 gphi
*phi
, gphi
*new_phi
,
245 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
246 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
247 void set_rename (tree old_name
, tree expr
);
248 void set_rename_for_each_def (gimple
*stmt
);
249 void gsi_insert_earliest (gimple_seq seq
);
250 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
251 bool codegen_error_p () const { return codegen_error
; }
252 bool is_constant (tree op
) const
254 return TREE_CODE (op
) == INTEGER_CST
255 || TREE_CODE (op
) == REAL_CST
256 || TREE_CODE (op
) == COMPLEX_CST
257 || TREE_CODE (op
) == VECTOR_CST
;
261 /* The region to be translated. */
264 /* This flag is set when an error occurred during the translation of isl AST
268 /* A vector of all the edges at if_condition merge points. */
269 auto_vec
<edge
, 2> merge_points
;
272 /* Return the tree variable that corresponds to the given isl ast identifier
273 expression (an isl_ast_expr of type isl_ast_expr_id).
275 FIXME: We should replace blind conversion of id's type with derivation
276 of the optimal type when we get the corresponding isl support. Blindly
277 converting type sizes may be problematic when we switch to smaller
280 tree
translate_isl_ast_to_gimple::
281 gcc_expression_from_isl_ast_expr_id (tree type
,
282 __isl_take isl_ast_expr
*expr_id
,
285 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
286 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
287 std::map
<isl_id
*, tree
>::iterator res
;
288 res
= ip
.find (tmp_isl_id
);
289 isl_id_free (tmp_isl_id
);
290 gcc_assert (res
!= ip
.end () &&
291 "Could not map isl_id to tree expression");
292 isl_ast_expr_free (expr_id
);
293 tree t
= res
->second
;
294 tree
*val
= region
->parameter_rename_map
->get(t
);
298 return fold_convert (type
, *val
);
301 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
304 tree
translate_isl_ast_to_gimple::
305 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
307 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
308 isl_val
*val
= isl_ast_expr_get_val (expr
);
309 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
310 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
312 if (isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
316 widest_int wi
= widest_int::from_array (chunks
, n
, true);
317 if (isl_val_is_neg (val
))
319 res
= wide_int_to_tree (type
, wi
);
322 isl_ast_expr_free (expr
);
326 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
329 tree
translate_isl_ast_to_gimple::
330 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
332 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
333 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
334 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
335 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
337 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
338 isl_ast_expr_free (expr
);
340 if (codegen_error_p ())
346 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
349 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
352 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
355 /* As isl operates on arbitrary precision numbers, we may end up with
356 division by 2^64 that is folded to 0. */
357 if (integer_zerop (tree_rhs_expr
))
359 codegen_error
= true;
362 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
364 case isl_ast_op_pdiv_q
:
365 /* As isl operates on arbitrary precision numbers, we may end up with
366 division by 2^64 that is folded to 0. */
367 if (integer_zerop (tree_rhs_expr
))
369 codegen_error
= true;
372 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
374 case isl_ast_op_zdiv_r
:
375 case isl_ast_op_pdiv_r
:
376 /* As isl operates on arbitrary precision numbers, we may end up with
377 division by 2^64 that is folded to 0. */
378 if (integer_zerop (tree_rhs_expr
))
380 codegen_error
= true;
383 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
385 case isl_ast_op_fdiv_q
:
386 /* As isl operates on arbitrary precision numbers, we may end up with
387 division by 2^64 that is folded to 0. */
388 if (integer_zerop (tree_rhs_expr
))
390 codegen_error
= true;
393 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
396 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
397 tree_lhs_expr
, tree_rhs_expr
);
400 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
403 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
406 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
409 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
412 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
415 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
422 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
425 tree
translate_isl_ast_to_gimple::
426 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
428 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
429 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
430 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
431 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
432 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
433 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
434 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
435 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
436 isl_ast_expr_free (expr
);
438 if (codegen_error_p ())
441 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
444 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
447 tree
translate_isl_ast_to_gimple::
448 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
450 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
451 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
452 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
453 isl_ast_expr_free (expr
);
454 return codegen_error_p () ? NULL_TREE
455 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
458 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
459 to a GCC expression tree of type TYPE. */
461 tree
translate_isl_ast_to_gimple::
462 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
464 enum tree_code op_code
;
465 switch (isl_ast_expr_get_op_type (expr
))
478 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
479 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
481 if (codegen_error_p ())
483 isl_ast_expr_free (expr
);
488 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
490 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
491 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
493 if (codegen_error_p ())
495 isl_ast_expr_free (expr
);
499 res
= fold_build2 (op_code
, type
, res
, t
);
501 isl_ast_expr_free (expr
);
505 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
508 tree
translate_isl_ast_to_gimple::
509 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
512 if (codegen_error_p ())
514 isl_ast_expr_free (expr
);
518 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
519 switch (isl_ast_expr_get_op_type (expr
))
521 /* These isl ast expressions are not supported yet. */
522 case isl_ast_op_error
:
523 case isl_ast_op_call
:
524 case isl_ast_op_and_then
:
525 case isl_ast_op_or_else
:
530 return nary_op_to_tree (type
, expr
, ip
);
536 case isl_ast_op_pdiv_q
:
537 case isl_ast_op_pdiv_r
:
538 case isl_ast_op_fdiv_q
:
539 case isl_ast_op_zdiv_r
:
547 return binary_op_to_tree (type
, expr
, ip
);
549 case isl_ast_op_minus
:
550 return unary_op_to_tree (type
, expr
, ip
);
552 case isl_ast_op_cond
:
553 case isl_ast_op_select
:
554 return ternary_op_to_tree (type
, expr
, ip
);
563 /* Converts an isl AST expression E back to a GCC expression tree of
566 tree
translate_isl_ast_to_gimple::
567 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
570 if (codegen_error_p ())
572 isl_ast_expr_free (expr
);
576 switch (isl_ast_expr_get_type (expr
))
578 case isl_ast_expr_id
:
579 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
581 case isl_ast_expr_int
:
582 return gcc_expression_from_isl_expr_int (type
, expr
);
584 case isl_ast_expr_op
:
585 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
594 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
595 induction variable for the new LOOP. New LOOP is attached to CFG
596 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
597 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
598 isl's scattering name to the induction variable created for the
599 loop of STMT. The new induction variable is inserted in the NEWIVS
600 vector and is of type TYPE. */
602 struct loop
*translate_isl_ast_to_gimple::
603 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
604 loop_p outer
, tree type
, tree lb
, tree ub
,
607 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
608 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
610 /* To fail code generation, we generate wrong code until we discard it. */
611 if (codegen_error_p ())
612 stride
= integer_zero_node
;
614 tree ivvar
= create_tmp_var (type
, "graphite_IV");
615 tree iv
, iv_after_increment
;
616 loop_p loop
= create_empty_loop_on_edge
617 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
618 outer
? outer
: entry_edge
->src
->loop_father
);
620 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
621 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
622 std::map
<isl_id
*, tree
>::iterator res
;
625 isl_id_free (res
->first
);
627 isl_ast_expr_free (for_iterator
);
631 /* Create the loop for a isl_ast_node_for.
633 - NEXT_E is the edge where new generated code should be attached. */
635 edge
translate_isl_ast_to_gimple::
636 translate_isl_ast_for_loop (loop_p context_loop
,
637 __isl_keep isl_ast_node
*node_for
, edge next_e
,
638 tree type
, tree lb
, tree ub
,
641 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
642 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
644 edge last_e
= single_exit (loop
);
645 edge to_body
= single_succ_edge (loop
->header
);
646 basic_block after
= to_body
->dest
;
648 /* Translate the body of the loop. */
649 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
650 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
651 isl_ast_node_free (for_body
);
653 /* Early return if we failed to translate loop body. */
654 if (!next_e
|| codegen_error_p ())
657 if (next_e
->dest
!= after
)
658 redirect_edge_succ_nodup (next_e
, after
);
659 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
661 if (flag_loop_parallelize_all
)
663 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
665 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
666 loop
->can_be_parallel
= for_info
->is_parallelizable
;
674 /* We use this function to get the upper bound because of the form,
675 which is used by isl to represent loops:
677 for (iterator = init; cond; iterator += inc)
685 The loop condition is an arbitrary expression, which contains the
686 current loop iterator.
688 (e.g. iterator + 3 < B && C > iterator + A)
690 We have to know the upper bound of the iterator to generate a loop
691 in Gimple form. It can be obtained from the special representation
692 of the loop condition, which is generated by isl,
693 if the ast_build_atomic_upper_bound option is set. In this case,
694 isl generates a loop condition that consists of the current loop
695 iterator, + an operator (< or <=) and an expression not involving
696 the iterator, which is processed and returned by this function.
698 (e.g iterator <= upper-bound-expression-without-iterator) */
700 static __isl_give isl_ast_expr
*
701 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
703 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
704 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
705 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
707 switch (isl_ast_expr_get_op_type (for_cond
))
710 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
715 /* (iterator < ub) => (iterator <= ub - 1). */
717 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
718 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
719 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
726 isl_ast_expr_free (for_cond
);
730 /* Translates an isl_ast_node_for to Gimple. */
732 edge
translate_isl_ast_to_gimple::
733 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
734 edge next_e
, ivs_params
&ip
)
736 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
738 = build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
740 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
741 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
742 /* To fail code generation, we generate wrong code until we discard it. */
743 if (codegen_error_p ())
744 lb
= integer_zero_node
;
746 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
747 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
748 /* To fail code generation, we generate wrong code until we discard it. */
749 if (codegen_error_p ())
750 ub
= integer_zero_node
;
752 edge last_e
= single_succ_edge (split_edge (next_e
));
753 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
758 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
759 variables of the loops around GBB in SESE.
761 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
762 chrec, we could consider using a map<int, tree> that maps loop ids to the
763 corresponding tree expressions. */
765 void translate_isl_ast_to_gimple::
766 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
767 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
770 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
771 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
773 isl_ast_expr
*arg_expr
;
774 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
776 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
778 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
779 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
781 /* To fail code generation, we generate wrong code until we discard it. */
782 if (codegen_error_p ())
783 t
= integer_zero_node
;
785 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
786 iv_map
[old_loop
->num
] = t
;
790 /* Translates an isl_ast_node_user to Gimple.
792 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
794 edge
translate_isl_ast_to_gimple::
795 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
796 edge next_e
, ivs_params
&ip
)
798 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
800 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
801 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
802 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
804 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
805 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
808 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
810 isl_ast_expr_free (name_expr
);
811 isl_id_free (name_id
);
813 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
814 "The entry block should not even appear within a scop");
816 const int nb_loops
= number_of_loops (cfun
);
818 iv_map
.create (nb_loops
);
819 iv_map
.safe_grow_cleared (nb_loops
);
821 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
822 isl_ast_expr_free (user_expr
);
824 basic_block old_bb
= GBB_BB (gbb
);
828 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
829 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
830 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
834 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
838 if (codegen_error_p ())
843 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
844 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
850 /* Translates an isl_ast_node_block to Gimple. */
852 edge
translate_isl_ast_to_gimple::
853 translate_isl_ast_node_block (loop_p context_loop
,
854 __isl_keep isl_ast_node
*node
,
855 edge next_e
, ivs_params
&ip
)
857 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
858 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
860 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
862 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
863 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
864 isl_ast_node_free (tmp_node
);
866 isl_ast_node_list_free (node_list
);
870 /* Creates a new if region corresponding to isl's cond. */
872 edge
translate_isl_ast_to_gimple::
873 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
877 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
878 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
880 /* To fail code generation, we generate wrong code until we discard it. */
881 if (codegen_error_p ())
882 cond_expr
= integer_zero_node
;
884 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
888 /* Translates an isl_ast_node_if to Gimple. */
890 edge
translate_isl_ast_to_gimple::
891 translate_isl_ast_node_if (loop_p context_loop
,
892 __isl_keep isl_ast_node
*node
,
893 edge next_e
, ivs_params
&ip
)
895 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
896 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
897 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
898 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
899 merge_points
.safe_push (last_e
);
901 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
902 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
903 isl_ast_node_free (then_node
);
905 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
906 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
907 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
908 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
910 isl_ast_node_free (else_node
);
914 /* Translates an isl AST node NODE to GCC representation in the
915 context of a SESE. */
917 edge
translate_isl_ast_to_gimple::
918 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
919 edge next_e
, ivs_params
&ip
)
921 if (codegen_error_p ())
924 switch (isl_ast_node_get_type (node
))
926 case isl_ast_node_error
:
929 case isl_ast_node_for
:
930 return translate_isl_ast_node_for (context_loop
, node
,
933 case isl_ast_node_if
:
934 return translate_isl_ast_node_if (context_loop
, node
,
937 case isl_ast_node_user
:
938 return translate_isl_ast_node_user (node
, next_e
, ip
);
940 case isl_ast_node_block
:
941 return translate_isl_ast_node_block (context_loop
, node
,
944 case isl_ast_node_mark
:
946 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
947 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
948 isl_ast_node_free (n
);
957 /* Return true when BB contains loop close phi nodes. A loop close phi node is
958 at the exit of loop which takes one argument that is the last value of the
959 variable being used out of the loop. */
962 bb_contains_loop_close_phi_nodes (basic_block bb
)
964 return single_pred_p (bb
)
965 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
968 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
969 header containing phi nodes which has one init-edge and one back-edge. */
972 bb_contains_loop_phi_nodes (basic_block bb
)
974 if (EDGE_COUNT (bb
->preds
) != 2)
977 unsigned depth
= loop_depth (bb
->loop_father
);
979 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
981 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
982 || depth
> loop_depth (preds
[1]->src
->loop_father
))
985 /* When one of the edges correspond to the same loop father and other
987 if (bb
->loop_father
!= preds
[0]->src
->loop_father
988 && bb
->loop_father
== preds
[1]->src
->loop_father
)
991 if (bb
->loop_father
!= preds
[1]->src
->loop_father
992 && bb
->loop_father
== preds
[0]->src
->loop_father
)
998 /* Check if USE is defined in a basic block from where the definition of USE can
999 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1002 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1004 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1007 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1008 if (bb_contains_loop_close_phi_nodes (bb
))
1011 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1012 basic_block def_bb
= gimple_bb (def
);
1014 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1017 /* Return the number of phi nodes in BB. */
1020 number_of_phi_nodes (basic_block bb
)
1023 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1029 /* Returns true if BB uses name in one of its PHIs. */
1032 phi_uses_name (basic_block bb
, tree name
)
1034 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1037 gphi
*phi
= psi
.phi ();
1038 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1040 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1041 if (use_arg
== name
)
1048 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1049 definition should flow into use, and the use should respect the loop-closed
1052 bool translate_isl_ast_to_gimple::
1053 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1054 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1056 if (SSA_NAME_IS_DEFAULT_DEF (rename
))
1059 /* The def of the rename must either dominate the uses or come from a
1060 back-edge. Also the def must respect the loop closed ssa form. */
1061 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1065 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1066 print_generic_expr (dump_file
, rename
);
1067 fprintf (dump_file
, "\n");
1072 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1075 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1077 /* The loop-header dominates the loop-body. */
1078 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1081 /* RENAME would be used in loop-phi. */
1082 gcc_assert (number_of_phi_nodes (use_bb
));
1084 /* For definitions coming from back edges, we should check that
1085 old_name is used in a loop PHI node.
1086 FIXME: Verify if this is true. */
1087 if (phi_uses_name (old_bb
, old_name
))
1093 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1094 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1096 tree
translate_isl_ast_to_gimple::
1097 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1098 phi_node_kind phi_kind
) const
1100 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1101 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1103 if (!renames
|| renames
->is_empty ())
1106 if (1 == renames
->length ())
1108 tree rename
= (*renames
)[0];
1109 if (TREE_CODE (rename
) == SSA_NAME
)
1111 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1112 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1113 && (phi_kind
== close_phi
1115 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1120 if (is_constant (rename
))
1126 /* More than one renames corresponding to the old_name. Find the rename for
1127 which the definition flows into usage at new_bb. */
1129 tree t1
= NULL_TREE
, t2
;
1130 basic_block t1_bb
= NULL
;
1131 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1133 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1135 /* Defined in the same basic block as used. */
1136 if (t2_bb
== new_bb
)
1139 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1140 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1143 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1146 /* Compute the nearest dominator. */
1147 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1157 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1158 When OLD_NAME and EXPR are the same we assert. */
1160 void translate_isl_ast_to_gimple::
1161 set_rename (tree old_name
, tree expr
)
1165 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1166 print_generic_expr (dump_file
, old_name
);
1167 fprintf (dump_file
, ", new_name = ");
1168 print_generic_expr (dump_file
, expr
);
1169 fprintf (dump_file
, "\n");
1172 if (old_name
== expr
)
1175 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1178 renames
->safe_push (expr
);
1184 region
->rename_map
->put (old_name
, r
);
1189 /* For a parameter of a scop we don't want to rename it. */
1190 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1192 region
->parameter_rename_map
->put(old_name
, expr
);
1195 /* Return an iterator to the instructions comes last in the execution order.
1196 Either GSI1 and GSI2 should belong to the same basic block or one of their
1197 respective basic blocks should dominate the other. */
1199 gimple_stmt_iterator
1200 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1202 basic_block bb1
= gsi_bb (gsi1
);
1203 basic_block bb2
= gsi_bb (gsi2
);
1205 /* Find the iterator which is the latest. */
1208 gimple
*stmt1
= gsi_stmt (gsi1
);
1209 gimple
*stmt2
= gsi_stmt (gsi2
);
1211 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1213 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1214 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1216 if (is_phi1
!= is_phi2
)
1217 return is_phi1
? gsi2
: gsi1
;
1220 /* For empty basic blocks gsis point to the end of the sequence. Since
1221 there is no operator== defined for gimple_stmt_iterator and for gsis
1222 not pointing to a valid statement gsi_next would assert. */
1223 gimple_stmt_iterator gsi
= gsi1
;
1225 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1228 } while (!gsi_end_p (gsi
));
1233 /* Find the basic block closest to the basic block which defines stmt. */
1234 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1237 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1241 /* Insert each statement from SEQ at its earliest insertion p. */
1243 void translate_isl_ast_to_gimple::
1244 gsi_insert_earliest (gimple_seq seq
)
1246 update_modified_stmts (seq
);
1247 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1248 basic_block begin_bb
= get_entry_bb (codegen_region
);
1250 /* Inserting the gimple statements in a vector because gimple_seq behave
1251 in strage ways when inserting the stmts from it into different basic
1252 blocks one at a time. */
1253 auto_vec
<gimple
*, 3> stmts
;
1254 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1256 stmts
.safe_push (gsi_stmt (gsi
));
1260 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1262 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1263 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1265 use_operand_p use_p
;
1266 ssa_op_iter op_iter
;
1267 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1269 /* Iterator to the current def of use_p. For function parameters or
1270 anything where def is not found, insert at the beginning of the
1271 generated region. */
1272 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1274 tree op
= USE_FROM_PTR (use_p
);
1275 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1276 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1277 gsi_stmt
= gsi_for_stmt (stmt
);
1279 /* For region parameters, insert at the beginning of the generated
1281 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1282 gsi_stmt
= gsi_def_stmt
;
1284 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1287 if (!gsi_stmt (gsi_def_stmt
))
1289 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1290 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1292 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1294 gimple_stmt_iterator bsi
1295 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1296 /* Insert right after the PHI statements. */
1297 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1300 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1304 fprintf (dump_file
, "[codegen] inserting statement: ");
1305 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1306 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1311 /* Collect all the operands of NEW_EXPR by recursively visiting each
1314 void translate_isl_ast_to_gimple::
1315 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1317 if (new_expr
== NULL_TREE
)
1320 /* Rename all uses in new_expr. */
1321 if (TREE_CODE (new_expr
) == SSA_NAME
)
1323 vec_ssa
->safe_push (new_expr
);
1327 /* Iterate over SSA_NAMES in NEW_EXPR. */
1328 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1330 tree op
= TREE_OPERAND (new_expr
, i
);
1331 collect_all_ssa_names (op
, vec_ssa
);
1335 /* This is abridged version of the function copied from:
1336 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1339 substitute_ssa_name (tree exp
, tree f
, tree r
)
1341 enum tree_code code
= TREE_CODE (exp
);
1342 tree op0
, op1
, op2
, op3
;
1345 /* We handle TREE_LIST and COMPONENT_REF separately. */
1346 if (code
== TREE_LIST
)
1348 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1349 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1350 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1353 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1355 else if (code
== COMPONENT_REF
)
1359 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1360 and it is the right field, replace it with R. */
1361 for (inner
= TREE_OPERAND (exp
, 0);
1362 REFERENCE_CLASS_P (inner
);
1363 inner
= TREE_OPERAND (inner
, 0))
1367 op1
= TREE_OPERAND (exp
, 1);
1369 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1372 /* If this expression hasn't been completed let, leave it alone. */
1373 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1376 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1377 if (op0
== TREE_OPERAND (exp
, 0))
1381 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1384 switch (TREE_CODE_CLASS (code
))
1389 case tcc_declaration
:
1395 case tcc_expression
:
1401 case tcc_exceptional
:
1404 case tcc_comparison
:
1406 switch (TREE_CODE_LENGTH (code
))
1414 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1415 if (op0
== TREE_OPERAND (exp
, 0))
1418 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1422 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1423 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1425 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1428 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1432 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1433 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1434 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1436 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1437 && op2
== TREE_OPERAND (exp
, 2))
1440 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1444 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1445 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1446 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1447 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1449 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1450 && op2
== TREE_OPERAND (exp
, 2)
1451 && op3
== TREE_OPERAND (exp
, 3))
1455 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1468 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1470 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1471 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1476 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1478 tree
translate_isl_ast_to_gimple::
1479 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1481 auto_vec
<tree
, 2> ssa_names
;
1482 collect_all_ssa_names (new_expr
, &ssa_names
);
1485 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1486 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1487 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1492 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1493 scalar evolution around LOOP. */
1495 tree
translate_isl_ast_to_gimple::
1496 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1497 basic_block new_bb
, basic_block old_bb
,
1500 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1502 /* At this point we should know the exact scev for each
1503 scalar SSA_NAME used in the scop: all the other scalar
1504 SSA_NAMEs should have been translated out of SSA using
1505 arrays with one element. */
1507 if (chrec_contains_undetermined (scev
))
1509 codegen_error
= true;
1510 return build_zero_cst (TREE_TYPE (old_name
));
1513 new_expr
= chrec_apply_map (scev
, iv_map
);
1515 /* The apply should produce an expression tree containing
1516 the uses of the new induction variables. We should be
1517 able to use new_expr instead of the old_name in the newly
1518 generated loop nest. */
1519 if (chrec_contains_undetermined (new_expr
)
1520 || tree_contains_chrecs (new_expr
, NULL
))
1522 codegen_error
= true;
1523 return build_zero_cst (TREE_TYPE (old_name
));
1526 if (TREE_CODE (new_expr
) == SSA_NAME
)
1528 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1529 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1531 codegen_error
= true;
1532 return build_zero_cst (TREE_TYPE (old_name
));
1536 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1538 /* We check all the operands and all of them should dominate the use at
1540 auto_vec
<tree
, 2> new_ssa_names
;
1541 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1544 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1546 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1548 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1549 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1551 codegen_error
= true;
1552 return build_zero_cst (TREE_TYPE (old_name
));
1557 /* Replace the old_name with the new_expr. */
1558 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1562 /* Renames the scalar uses of the statement COPY, using the
1563 substitution map RENAME_MAP, inserting the gimplification code at
1564 GSI_TGT, for the translation REGION, with the original copied
1565 statement in LOOP, and using the induction variable renaming map
1566 IV_MAP. Returns true when something has been renamed. */
1568 bool translate_isl_ast_to_gimple::
1569 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1570 loop_p loop
, vec
<tree
> iv_map
)
1572 bool changed
= false;
1574 if (is_gimple_debug (copy
))
1576 if (gimple_debug_bind_p (copy
))
1577 gimple_debug_bind_reset_value (copy
);
1578 else if (gimple_debug_source_bind_p (copy
))
1588 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1589 print_gimple_stmt (dump_file
, copy
, 0);
1592 use_operand_p use_p
;
1593 ssa_op_iter op_iter
;
1594 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1596 tree old_name
= USE_FROM_PTR (use_p
);
1600 fprintf (dump_file
, "[codegen] renaming old_name = ");
1601 print_generic_expr (dump_file
, old_name
);
1602 fprintf (dump_file
, "\n");
1605 if (TREE_CODE (old_name
) != SSA_NAME
1606 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1610 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1611 old_bb
, unknown_phi
);
1615 tree type_old_name
= TREE_TYPE (old_name
);
1616 tree type_new_expr
= TREE_TYPE (new_expr
);
1620 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1621 print_generic_expr (dump_file
, new_expr
);
1622 fprintf (dump_file
, "\n");
1625 if (type_old_name
!= type_new_expr
1626 || TREE_CODE (new_expr
) != SSA_NAME
)
1628 tree var
= create_tmp_var (type_old_name
, "var");
1630 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1631 new_expr
= fold_convert (type_old_name
, new_expr
);
1634 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1635 gsi_insert_earliest (stmts
);
1638 replace_exp (use_p
, new_expr
);
1643 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1645 if (!new_expr
|| codegen_error_p ())
1650 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1651 print_generic_expr (dump_file
, new_expr
);
1652 fprintf (dump_file
, "\n");
1655 gsi_insert_earliest (stmts
);
1656 replace_exp (use_p
, new_expr
);
1658 if (TREE_CODE (new_expr
) == INTEGER_CST
1659 && is_gimple_assign (copy
))
1661 tree rhs
= gimple_assign_rhs1 (copy
);
1663 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1664 recompute_tree_invariant_for_addr_expr (rhs
);
1667 set_rename (old_name
, new_expr
);
1673 /* Returns a basic block that could correspond to where a constant was defined
1674 in the original code. In the original code OLD_BB had the definition, we
1675 need to find which basic block out of the copies of old_bb, in the new
1676 region, should a definition correspond to if it has to reach BB. */
1678 basic_block
translate_isl_ast_to_gimple::
1679 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1681 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1683 if (!bbs
|| bbs
->is_empty ())
1686 if (1 == bbs
->length ())
1690 basic_block b1
= NULL
, b2
;
1691 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1696 /* BB and B2 are in two unrelated if-clauses. */
1697 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1700 /* Compute the nearest dominator. */
1701 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1708 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1709 determines the kind of phi node. */
1711 tree
translate_isl_ast_to_gimple::
1712 get_new_name (basic_block new_bb
, tree op
,
1713 basic_block old_bb
, phi_node_kind phi_kind
) const
1715 /* For constants the names are the same. */
1716 if (TREE_CODE (op
) != SSA_NAME
)
1719 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1722 /* Return a debug location for OP. */
1727 location_t loc
= UNKNOWN_LOCATION
;
1729 if (TREE_CODE (op
) == SSA_NAME
)
1730 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1734 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1735 the init edge (from outside the loop) and the second one is the back edge
1736 from the same loop. */
1738 std::pair
<edge
, edge
>
1739 get_edges (basic_block bb
)
1741 std::pair
<edge
, edge
> edges
;
1744 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1745 if (bb
->loop_father
!= e
->src
->loop_father
)
1752 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1753 must be found unless they can be POSTPONEd for later. */
1755 bool translate_isl_ast_to_gimple::
1756 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1757 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1760 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1762 basic_block new_bb
= gimple_bb (new_phi
);
1763 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1766 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1767 e
= ibp_new_bb
.first
;
1769 e
= ibp_new_bb
.second
;
1771 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1772 tree new_name
= get_new_name (new_bb
, old_name
,
1773 gimple_bb (old_phi
), loop_phi
);
1776 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1780 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1781 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1782 /* If the phi arg was a function arg, or wasn't defined, just use the
1784 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1787 /* Postpone code gen for later for those back-edges we don't have the
1789 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1791 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1794 /* Either we should add the arg to phi or, we should postpone. */
1800 /* Copy loop phi nodes from BB to NEW_BB. */
1802 bool translate_isl_ast_to_gimple::
1803 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1806 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1809 /* Loop phi nodes should have only two arguments. */
1810 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1812 /* First edge is the init edge and second is the back edge. */
1813 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1815 /* First edge is the init edge and second is the back edge. */
1816 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1818 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1821 gphi
*phi
= psi
.phi ();
1822 tree res
= gimple_phi_result (phi
);
1823 if (virtual_operand_p (res
))
1825 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1828 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
1829 tree new_res
= create_new_def_for (res
, new_phi
,
1830 gimple_phi_result_ptr (new_phi
));
1831 set_rename (res
, new_res
);
1832 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1834 update_stmt (new_phi
);
1838 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1839 print_gimple_stmt (dump_file
, new_phi
, 0);
1846 /* Return the init value of PHI, the value coming from outside the loop. */
1849 get_loop_init_value (gphi
*phi
)
1852 loop_p loop
= gimple_bb (phi
)->loop_father
;
1856 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1857 if (e
->src
->loop_father
!= loop
)
1858 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1863 /* Find the init value (the value which comes from outside the loop), of one of
1864 the operands of DEF which is defined by a loop phi. */
1867 find_init_value (gimple
*def
)
1869 if (gimple_code (def
) == GIMPLE_PHI
)
1870 return get_loop_init_value (as_a
<gphi
*> (def
));
1872 if (gimple_vuse (def
))
1876 use_operand_p use_p
;
1877 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1879 tree use
= USE_FROM_PTR (use_p
);
1880 if (TREE_CODE (use
) == SSA_NAME
)
1882 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1890 /* Return the init value, the value coming from outside the loop. */
1893 find_init_value_close_phi (gphi
*phi
)
1895 gcc_assert (gimple_phi_num_args (phi
) == 1);
1896 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1897 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1898 return find_init_value (def
);
1902 tree
translate_isl_ast_to_gimple::
1903 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1904 gimple
*old_close_phi
)
1906 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1907 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1908 basic_block bb
= gimple_bb (stmt
);
1909 if (!bb_in_sese_p (bb
, codegen_region
))
1910 return last_merge_name
;
1912 loop_p loop
= bb
->loop_father
;
1913 if (!loop_in_sese_p (loop
, codegen_region
))
1914 return last_merge_name
;
1916 edge e
= single_exit (loop
);
1918 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1919 return last_merge_name
;
1921 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1922 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1925 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
1926 bb
= split_edge (e
);
1928 gphi
*close_phi
= create_phi_node (NULL_TREE
, bb
);
1929 tree res
= create_new_def_for (last_merge_name
, close_phi
,
1930 gimple_phi_result_ptr (close_phi
));
1931 set_rename (old_close_phi_name
, res
);
1932 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
1933 last_merge_name
= res
;
1935 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
1938 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
1939 the close phi node PHI. */
1941 bool translate_isl_ast_to_gimple::
1942 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
1945 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1946 basic_block default_value_bb
= get_entry_bb (codegen_region
);
1947 if (SSA_NAME
== TREE_CODE (default_value
))
1949 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
1950 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
1952 default_value_bb
= gimple_bb (stmt
);
1955 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
1957 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1958 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
1959 tree last_merge_name
= new_close_phi_name
;
1960 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1964 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
1966 basic_block new_merge_bb
= merge_e
->src
;
1967 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
1970 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
1973 gphi
*merge_phi
= create_phi_node (NULL_TREE
, new_merge_bb
);
1974 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
1975 gimple_phi_result_ptr (merge_phi
));
1976 set_rename (old_close_phi_name
, merge_res
);
1978 edge from_loop
= NULL
, from_default_value
= NULL
;
1981 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
1982 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
1985 from_default_value
= e
;
1987 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
1988 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
1989 is contained in another condition. */
1990 if (!from_default_value
|| !from_loop
)
1993 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
1994 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
1998 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
1999 print_gimple_stmt (dump_file
, merge_phi
, 0);
2002 update_stmt (merge_phi
);
2003 last_merge_name
= merge_res
;
2009 /* Copy all the loop-close phi args from BB to NEW_BB. */
2011 bool translate_isl_ast_to_gimple::
2012 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
2013 vec
<tree
> iv_map
, bool postpone
)
2015 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2018 gphi
*old_close_phi
= psi
.phi ();
2019 tree res
= gimple_phi_result (old_close_phi
);
2020 if (virtual_operand_p (res
))
2023 gphi
*new_close_phi
= create_phi_node (NULL_TREE
, new_bb
);
2024 tree new_res
= create_new_def_for (res
, new_close_phi
,
2025 gimple_phi_result_ptr (new_close_phi
));
2026 set_rename (res
, new_res
);
2028 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2030 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2033 new_name
= get_rename_from_scev (old_name
, &stmts
,
2034 old_bb
->loop_father
,
2035 new_bb
, old_bb
, iv_map
);
2036 if (! codegen_error_p ())
2037 gsi_insert_earliest (stmts
);
2040 new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2042 /* Predecessor basic blocks of a loop close phi should have been code
2043 generated before. FIXME: This is fixable by merging PHIs from inner
2044 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2045 if (!new_name
|| codegen_error_p ())
2048 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2049 get_loc (old_name
));
2052 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2053 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2056 update_stmt (new_close_phi
);
2058 /* When there is no loop guard around this codegenerated loop, there is no
2059 need to collect the close-phi arg. */
2060 if (merge_points
.is_empty ())
2063 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2064 tree default_value
= find_init_value_close_phi (new_close_phi
);
2066 /* A close phi must come from a loop-phi having a default value. */
2072 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2076 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2077 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2082 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2090 /* Copy loop close phi nodes from BB to NEW_BB. */
2092 bool translate_isl_ast_to_gimple::
2093 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
2097 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2099 /* Loop close phi nodes should have only one argument. */
2100 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2102 return copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, true);
2106 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2107 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2108 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2109 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2112 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2113 In this case DOMINATING_PRED = NULL.
2115 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2117 Returns true on successful copy of the args, false otherwise. */
2119 bool translate_isl_ast_to_gimple::
2120 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2121 edge old_bb_dominating_edge
,
2122 edge old_bb_non_dominating_edge
,
2123 gphi
*phi
, gphi
*new_phi
,
2126 basic_block def_pred
[2] = { NULL
, NULL
};
2127 int not_found_bb_index
= -1;
2128 for (int i
= 0; i
< 2; i
++)
2130 /* If the corresponding def_bb could not be found the entry will be
2132 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2133 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2134 gimple_phi_arg_edge (phi
, i
)->src
);
2135 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2136 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2140 /* When non are available bail out. */
2141 if (not_found_bb_index
!= -1)
2143 not_found_bb_index
= i
;
2147 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2148 if (old_bb_dominating_edge
)
2150 if (not_found_bb_index
!= -1)
2153 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2154 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2155 vec
<basic_block
> *bbs
2156 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2158 /* Could not find a mapping. */
2162 basic_block new_pred
= NULL
;
2165 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2167 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2169 /* FIXME: If we have already found new_pred then we have to
2170 disambiguate, bail out for now. */
2173 new_pred
= new_pred1
;
2175 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2177 /* FIXME: If we have already found new_pred then we have to either
2178 it dominates both or we have to disambiguate, bail out. */
2181 new_pred
= new_pred2
;
2188 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2189 gcc_assert (new_non_dominating_edge
);
2190 /* FIXME: Validate each args just like in loop-phis. */
2191 /* By the process of elimination we first insert insert phi-edge for
2192 non-dominating pred which is computed above and then we insert the
2194 int inserted_edge
= 0;
2195 for (; inserted_edge
< 2; inserted_edge
++)
2197 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2198 if (new_non_dominating_edge
== new_bb_pred_edge
)
2200 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2201 new_non_dominating_edge
,
2202 get_loc (old_phi_args
[inserted_edge
]));
2206 if (inserted_edge
== 2)
2209 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2211 edge new_dominating_edge
= NULL
;
2212 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2214 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2215 if (e
!= new_non_dominating_edge
)
2217 new_dominating_edge
= e
;
2218 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2219 new_dominating_edge
,
2220 get_loc (old_phi_args
[inserted_edge
]));
2224 gcc_assert (new_dominating_edge
);
2228 /* Classic diamond structure: both edges are non-dominating. We need to
2229 find one unique edge then the other can be found be elimination. If
2230 any definition (def_pred) dominates both the preds of new_bb then we
2231 bail out. Entries of def_pred maybe NULL, in that case we must
2232 uniquely find pred with help of only one entry. */
2233 edge new_e
[2] = { NULL
, NULL
};
2234 for (int i
= 0; i
< 2; i
++)
2238 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2240 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2243 /* We do not know how to handle the case when def_pred
2244 dominates more than a predecessor. */
2250 gcc_assert (new_e
[0] || new_e
[1]);
2252 /* Find the other edge by process of elimination. */
2253 if (not_found_bb_index
!= -1)
2255 gcc_assert (!new_e
[not_found_bb_index
]);
2256 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2259 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2261 if (new_e
[found_bb_index
] == e
)
2263 new_e
[not_found_bb_index
] = e
;
2267 /* Add edges to phi args. */
2268 for (int i
= 0; i
< 2; i
++)
2269 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2270 get_loc (old_phi_args
[i
]));
2276 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2277 region. If postpone is true and it isn't possible to copy any arg of PHI,
2278 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2279 Returns false if the copying was unsuccessful. */
2281 bool translate_isl_ast_to_gimple::
2282 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2285 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2286 gcc_assert (2 == gimple_phi_num_args (phi
));
2288 basic_block new_bb
= gimple_bb (new_phi
);
2289 loop_p loop
= gimple_bb (phi
)->loop_father
;
2291 basic_block old_bb
= gimple_bb (phi
);
2292 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2296 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2297 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2298 old_bb_non_dominating_edge
= e
;
2300 old_bb_dominating_edge
= e
;
2302 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2303 old_bb_non_dominating_edge
->src
));
2305 tree new_phi_args
[2];
2306 tree old_phi_args
[2];
2308 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2310 tree old_name
= gimple_phi_arg_def (phi
, i
);
2311 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2312 old_phi_args
[i
] = old_name
;
2315 new_phi_args
[i
] = new_name
;
2319 /* If the phi-arg was a parameter. */
2320 if (vec_find (region
->params
, old_name
) != -1)
2322 new_phi_args
[i
] = old_name
;
2326 "[codegen] parameter argument to phi, new_expr: ");
2327 print_generic_expr (dump_file
, new_phi_args
[i
]);
2328 fprintf (dump_file
, "\n");
2333 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2334 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2335 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2341 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2342 if (is_gimple_reg (old_name
)
2343 && scev_analyzable_p (old_name
, region
->region
))
2346 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2347 new_bb
, old_bb
, iv_map
);
2348 if (codegen_error_p ())
2351 gcc_assert (new_expr
);
2355 "[codegen] scev analyzeable, new_expr: ");
2356 print_generic_expr (dump_file
, new_expr
);
2357 fprintf (dump_file
, "\n");
2359 gsi_insert_earliest (stmts
);
2360 new_phi_args
[i
] = new_expr
;
2364 /* Postpone code gen for later for back-edges. */
2365 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2369 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2370 print_gimple_stmt (dump_file
, new_phi
, 0);
2373 new_phi_args
[i
] = NULL_TREE
;
2377 /* Either we should add the arg to phi or, we should postpone. */
2381 /* If none of the args have been determined in the first stage then wait until
2383 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2386 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2387 old_bb_dominating_edge
,
2388 old_bb_non_dominating_edge
,
2389 phi
, new_phi
, new_bb
);
2392 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2393 containing phi nodes coming from two predecessors, and none of them are back
2396 bool translate_isl_ast_to_gimple::
2397 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2400 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2402 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2403 if (EDGE_COUNT (bb
->preds
) != 2)
2407 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2410 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2413 gphi
*phi
= psi
.phi ();
2414 tree res
= gimple_phi_result (phi
);
2415 if (virtual_operand_p (res
))
2418 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
2419 tree new_res
= create_new_def_for (res
, new_phi
,
2420 gimple_phi_result_ptr (new_phi
));
2421 set_rename (res
, new_res
);
2423 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2426 update_stmt (new_phi
);
2432 /* Return true if STMT should be copied from region to the new code-generated
2433 region. LABELs, CONDITIONS, induction-variables and region parameters need
2437 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2439 /* Do not copy labels or conditions. */
2440 if (gimple_code (stmt
) == GIMPLE_LABEL
2441 || gimple_code (stmt
) == GIMPLE_COND
)
2445 /* Do not copy induction variables. */
2446 if (is_gimple_assign (stmt
)
2447 && (lhs
= gimple_assign_lhs (stmt
))
2448 && TREE_CODE (lhs
) == SSA_NAME
2449 && is_gimple_reg (lhs
)
2450 && scev_analyzable_p (lhs
, region
->region
))
2453 /* Do not copy parameters that have been generated in the header of the
2455 if (is_gimple_assign (stmt
)
2456 && (lhs
= gimple_assign_lhs (stmt
))
2457 && TREE_CODE (lhs
) == SSA_NAME
2458 && region
->parameter_rename_map
->get(lhs
))
2464 /* Create new names for all the definitions created by COPY and add replacement
2465 mappings for each new name. */
2467 void translate_isl_ast_to_gimple::
2468 set_rename_for_each_def (gimple
*stmt
)
2470 def_operand_p def_p
;
2471 ssa_op_iter op_iter
;
2472 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2474 tree old_name
= DEF_FROM_PTR (def_p
);
2475 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2476 set_rename (old_name
, new_name
);
2480 /* Duplicates the statements of basic block BB into basic block NEW_BB
2481 and compute the new induction variables according to the IV_MAP. */
2483 bool translate_isl_ast_to_gimple::
2484 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2487 /* Iterator poining to the place where new statement (s) will be inserted. */
2488 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2490 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2493 gimple
*stmt
= gsi_stmt (gsi
);
2494 if (!should_copy_to_new_region (stmt
, region
))
2497 /* Create a new copy of STMT and duplicate STMT's virtual
2499 gimple
*copy
= gimple_copy (stmt
);
2500 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2504 fprintf (dump_file
, "[codegen] inserting statement: ");
2505 print_gimple_stmt (dump_file
, copy
, 0);
2508 maybe_duplicate_eh_stmt (copy
, stmt
);
2509 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2511 /* Crete new names for each def in the copied stmt. */
2512 set_rename_for_each_def (copy
);
2514 loop_p loop
= bb
->loop_father
;
2515 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2517 fold_stmt_inplace (&gsi_tgt
);
2518 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2521 if (codegen_error_p ())
2524 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2526 use_operand_p use_p
;
2527 if (!is_gimple_debug (copy
))
2528 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2530 tree old_name
= USE_FROM_PTR (use_p
);
2532 if (TREE_CODE (old_name
) != SSA_NAME
2533 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2536 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2540 replace_exp (use_p
, *new_expr
);
2550 /* Given a basic block containing close-phi it returns the new basic block where
2551 to insert a copy of the close-phi nodes. All the uses in close phis should
2552 come from a single loop otherwise it returns NULL. */
2554 edge
translate_isl_ast_to_gimple::
2555 edge_for_new_close_phis (basic_block bb
)
2557 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2558 of close phi in the original code and then find the mapping of basic block
2559 defining that variable. If there are multiple close-phis and they are
2560 defined in different loops (in the original or in the new code) because of
2561 loop splitting, then we bail out. */
2562 loop_p new_loop
= NULL
;
2563 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2566 gphi
*phi
= psi
.phi ();
2567 tree name
= gimple_phi_arg_def (phi
, 0);
2568 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2570 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2571 if (!bbs
|| bbs
->length () != 1)
2572 /* This is one of the places which shows preserving original structure
2573 is not always possible, as we may need to insert close PHI for a loop
2574 where the latch does not have any mapping, or the mapping is
2579 new_loop
= (*bbs
)[0]->loop_father
;
2580 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2587 return single_exit (new_loop
);
2590 /* Copies BB and includes in the copied BB all the statements that can
2591 be reached following the use-def chains from the memory accesses,
2592 and returns the next edge following this new block. */
2594 edge
translate_isl_ast_to_gimple::
2595 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2597 int num_phis
= number_of_phi_nodes (bb
);
2599 if (region
->copied_bb_map
->get (bb
))
2601 /* FIXME: we should be able to handle phi nodes with args coming from
2602 outside the region. */
2605 codegen_error
= true;
2610 basic_block new_bb
= NULL
;
2611 if (bb_contains_loop_close_phi_nodes (bb
))
2614 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2617 edge e
= edge_for_new_close_phis (bb
);
2620 codegen_error
= true;
2624 basic_block phi_bb
= e
->dest
;
2626 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2627 phi_bb
= split_edge (e
);
2629 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2630 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2632 if (!copy_loop_close_phi_nodes (bb
, phi_bb
, iv_map
))
2634 codegen_error
= true;
2641 new_bb
= split_edge (next_e
);
2645 new_bb
= split_edge (next_e
);
2646 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2648 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2650 /* At this point we are unable to codegenerate by still preserving the SSA
2651 structure because maybe the loop is completely unrolled and the PHIs
2652 and cross-bb scalar dependencies are untrackable w.r.t. the original
2653 code. See gfortran.dg/graphite/pr29832.f90. */
2654 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2656 codegen_error
= true;
2660 /* In case isl did some loop peeling, like this:
2663 for (int c1 = 1; c1 <= 5; c1 += 1) {
2668 there should be no loop-phi nodes in S_8(0).
2670 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2671 values of all scalar variables: for the moment we instantiate only
2672 SCEV analyzable expressions on the iteration domain, and we need to
2673 extend that to reductions that cannot be analyzed by SCEV. */
2674 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2676 codegen_error
= true;
2681 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2683 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2685 codegen_error
= true;
2689 else if (num_phis
> 0)
2692 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2695 basic_block phi_bb
= single_pred (new_bb
);
2696 loop_p loop_father
= new_bb
->loop_father
;
2698 /* Move back until we find the block with two predecessors. */
2699 while (single_pred_p (phi_bb
))
2700 phi_bb
= single_pred_edge (phi_bb
)->src
;
2702 /* If a corresponding merge-point was not found, then abort codegen. */
2703 if (phi_bb
->loop_father
!= loop_father
2704 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2705 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2707 codegen_error
= true;
2714 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2715 bb
->index
, new_bb
->index
);
2717 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2719 copied_bbs
->safe_push (new_bb
);
2722 vec
<basic_block
> bbs
;
2724 bbs
.safe_push (new_bb
);
2725 region
->copied_bb_map
->put (bb
, bbs
);
2728 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2730 codegen_error
= true;
2734 return single_succ_edge (new_bb
);
2737 /* Patch the missing arguments of the phi nodes. */
2739 void translate_isl_ast_to_gimple::
2740 translate_pending_phi_nodes ()
2744 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2746 gphi
*old_phi
= rename
->first
;
2747 gphi
*new_phi
= rename
->second
;
2748 basic_block old_bb
= gimple_bb (old_phi
);
2749 basic_block new_bb
= gimple_bb (new_phi
);
2751 /* First edge is the init edge and second is the back edge. */
2752 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2753 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2757 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2758 print_gimple_stmt (dump_file
, old_phi
, 0);
2761 auto_vec
<tree
, 1> iv_map
;
2762 if (bb_contains_loop_phi_nodes (new_bb
))
2763 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2765 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2766 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, false);
2768 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2772 fprintf (dump_file
, "[codegen] to new-phi: ");
2773 print_gimple_stmt (dump_file
, new_phi
, 0);
2775 if (codegen_error_p ())
2780 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2782 void translate_isl_ast_to_gimple::
2783 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2785 sese_info_p region
= scop
->scop_info
;
2786 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2787 gcc_assert (nb_parameters
== region
->params
.length ());
2789 for (i
= 0; i
< nb_parameters
; i
++)
2791 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2793 ip
[tmp_id
] = region
->params
[i
];
2798 /* Generates a build, which specifies the constraints on the parameters. */
2800 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2801 generate_isl_context (scop_p scop
)
2803 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2804 return isl_ast_build_from_context (context_isl
);
2807 /* This method is executed before the construction of a for node. */
2809 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2811 isl_union_map
*dependences
= (isl_union_map
*) user
;
2812 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2813 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2814 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2815 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2816 for_info
->is_parallelizable
=
2817 !carries_deps (schedule
, dependences
, dimension
);
2818 isl_union_map_free (schedule
);
2819 isl_space_free (schedule_space
);
2820 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2824 /* Generate isl AST from schedule of SCOP. */
2826 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2827 scop_to_isl_ast (scop_p scop
)
2829 gcc_assert (scop
->transformed_schedule
);
2831 /* Set the separate option to reduce control flow overhead. */
2832 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2833 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2834 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2836 if (flag_loop_parallelize_all
)
2838 scop_get_dependences (scop
);
2840 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2844 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2845 (context_isl
, schedule
);
2846 isl_ast_build_free (context_isl
);
2850 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2851 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2854 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2855 gimple_stmt_iterator
*gsi
)
2857 if (!defined_in_sese_p (tr
, region
->region
))
2861 use_operand_p use_p
;
2862 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2864 tree use_tr
= USE_FROM_PTR (use_p
);
2866 /* Do not copy parameters that have been generated in the header of the
2868 if (region
->parameter_rename_map
->get(use_tr
))
2871 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2875 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2878 gimple
*copy
= gimple_copy (def_stmt
);
2879 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2881 /* Create new names for all the definitions created by COPY and
2882 add replacement mappings for each new name. */
2883 def_operand_p def_p
;
2884 ssa_op_iter op_iter
;
2885 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2887 tree old_name
= DEF_FROM_PTR (def_p
);
2888 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2889 region
->parameter_rename_map
->put(old_name
, new_name
);
2896 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2898 /* For all the parameters which definitino is in the if_region->false_region,
2899 insert code on true_region (if_region->true_region->entry). */
2903 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2905 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2907 // If def is not in region.
2908 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2910 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2914 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2915 Return true if code generation succeeded. */
2918 graphite_regenerate_ast_isl (scop_p scop
)
2920 sese_info_p region
= scop
->scop_info
;
2921 translate_isl_ast_to_gimple
t (region
);
2923 ifsese if_region
= NULL
;
2924 isl_ast_node
*root_node
;
2927 timevar_push (TV_GRAPHITE_CODE_GEN
);
2928 t
.add_parameters_to_ivs_params (scop
, ip
);
2929 root_node
= t
.scop_to_isl_ast (scop
);
2931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2933 fprintf (dump_file
, "[scheduler] original schedule:\n");
2934 print_isl_schedule (dump_file
, scop
->original_schedule
);
2935 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
2936 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
2938 fprintf (dump_file
, "[scheduler] original ast:\n");
2939 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
2940 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
2941 print_isl_ast (dump_file
, root_node
);
2944 recompute_all_dominators ();
2947 if_region
= move_sese_in_condition (region
);
2948 region
->if_region
= if_region
;
2949 recompute_all_dominators ();
2951 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2953 /* Copy all the parameters which are defined in the region. */
2954 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
2956 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2957 basic_block bb
= split_edge (e
);
2959 /* Update the true_region exit edge. */
2960 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2962 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2963 if (t
.codegen_error_p ())
2966 fprintf (dump_file
, "codegen error: "
2967 "reverting back to the original code.\n");
2968 set_ifsese_condition (if_region
, integer_zero_node
);
2972 t
.translate_pending_phi_nodes ();
2973 if (!t
.codegen_error_p ())
2975 sese_insert_phis_for_liveouts (region
,
2976 if_region
->region
->region
.exit
->src
,
2977 if_region
->false_region
->region
.exit
,
2978 if_region
->true_region
->region
.exit
);
2979 mark_virtual_operands_for_renaming (cfun
);
2980 update_ssa (TODO_update_ssa
);
2985 recompute_all_dominators ();
2989 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
2994 fprintf (dump_file
, "[codegen] unsuccessful in translating"
2995 " pending phis, reverting back to the original code.\n");
2996 set_ifsese_condition (if_region
, integer_zero_node
);
3000 free (if_region
->true_region
);
3001 free (if_region
->region
);
3004 ivs_params_clear (ip
);
3005 isl_ast_node_free (root_node
);
3006 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3011 int num_no_dependency
= 0;
3013 FOR_EACH_LOOP (loop
, 0)
3014 if (loop
->can_be_parallel
)
3015 num_no_dependency
++;
3017 fprintf (dump_file
, "%d loops carried no dependency.\n",
3021 return !t
.codegen_error_p ();
3024 #endif /* HAVE_isl */