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 /* IVS_PARAMS maps isl's scattering and parameter identifiers
77 to corresponding trees. */
79 typedef std::map
<isl_id
*, tree
> ivs_params
;
81 /* Free all memory allocated for isl's identifiers. */
83 static void ivs_params_clear (ivs_params
&ip
)
85 std::map
<isl_id
*, tree
>::iterator it
;
86 for (it
= ip
.begin ();
87 it
!= ip
.end (); it
++)
89 isl_id_free (it
->first
);
93 /* Set the "separate" option for the schedule node. */
95 static isl_schedule_node
*
96 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
101 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
104 /* Set the "separate" option unless it is set earlier to another option. */
105 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
106 == isl_ast_loop_default
)
107 return isl_schedule_node_band_member_set_ast_loop_type
108 (node
, 0, isl_ast_loop_separate
);
113 /* Print SCHEDULE under an AST form on file F. */
116 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
118 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
119 isl_ast_build
*context
= isl_ast_build_from_context (set
);
121 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
122 isl_ast_build_free (context
);
123 print_isl_ast (f
, ast
);
124 isl_ast_node_free (ast
);
128 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
130 print_schedule_ast (stderr
, s
, scop
);
141 class translate_isl_ast_to_gimple
144 translate_isl_ast_to_gimple (sese_info_p r
)
145 : region (r
), codegen_error (false) { }
146 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
147 edge next_e
, ivs_params
&ip
);
148 edge
translate_isl_ast_node_for (loop_p context_loop
,
149 __isl_keep isl_ast_node
*node
,
150 edge next_e
, ivs_params
&ip
);
151 edge
translate_isl_ast_for_loop (loop_p context_loop
,
152 __isl_keep isl_ast_node
*node_for
,
154 tree type
, tree lb
, tree ub
,
156 edge
translate_isl_ast_node_if (loop_p context_loop
,
157 __isl_keep isl_ast_node
*node
,
158 edge next_e
, ivs_params
&ip
);
159 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
160 edge next_e
, ivs_params
&ip
);
161 edge
translate_isl_ast_node_block (loop_p context_loop
,
162 __isl_keep isl_ast_node
*node
,
163 edge next_e
, ivs_params
&ip
);
164 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
166 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
168 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
170 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
172 tree
gcc_expression_from_isl_expression (tree type
,
173 __isl_take isl_ast_expr
*,
175 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
176 __isl_keep isl_ast_expr
*expr_id
,
178 tree
gcc_expression_from_isl_expr_int (tree type
,
179 __isl_take isl_ast_expr
*expr
);
180 tree
gcc_expression_from_isl_expr_op (tree type
,
181 __isl_take isl_ast_expr
*expr
,
183 struct loop
*graphite_create_new_loop (edge entry_edge
,
184 __isl_keep isl_ast_node
*node_for
,
185 loop_p outer
, tree type
,
186 tree lb
, tree ub
, ivs_params
&ip
);
187 edge
graphite_create_new_guard (edge entry_edge
,
188 __isl_take isl_ast_expr
*if_cond
,
190 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
191 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
193 void translate_pending_phi_nodes (void);
194 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
195 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
197 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
199 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
200 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
201 tree
get_rename (basic_block new_bb
, tree old_name
,
202 basic_block old_bb
, phi_node_kind
) const;
203 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
204 basic_block new_bb
, basic_block old_bb
,
206 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
207 tree
get_new_name (basic_block new_bb
, tree op
,
208 basic_block old_bb
, phi_node_kind
) const;
209 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
210 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
211 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
213 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
214 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
216 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
217 gimple
*old_close_phi
);
218 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
219 vec
<tree
> iv_map
, bool postpone
);
220 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
222 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
224 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
226 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
228 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
230 edge
edge_for_new_close_phis (basic_block bb
);
231 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
232 edge old_bb_dominating_edge
,
233 edge old_bb_non_dominating_edge
,
234 gphi
*phi
, gphi
*new_phi
,
236 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
237 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
238 void set_rename (tree old_name
, tree expr
);
239 void set_rename_for_each_def (gimple
*stmt
);
240 void gsi_insert_earliest (gimple_seq seq
);
241 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
242 bool codegen_error_p () const { return codegen_error
; }
243 void set_codegen_error () { codegen_error
= true; }
244 bool is_constant (tree op
) const
246 return TREE_CODE (op
) == INTEGER_CST
247 || TREE_CODE (op
) == REAL_CST
248 || TREE_CODE (op
) == COMPLEX_CST
249 || TREE_CODE (op
) == VECTOR_CST
;
253 /* The region to be translated. */
256 /* This flag is set when an error occurred during the translation of isl AST
260 /* A vector of all the edges at if_condition merge points. */
261 auto_vec
<edge
, 2> merge_points
;
264 /* Return the tree variable that corresponds to the given isl ast identifier
265 expression (an isl_ast_expr of type isl_ast_expr_id).
267 FIXME: We should replace blind conversion of id's type with derivation
268 of the optimal type when we get the corresponding isl support. Blindly
269 converting type sizes may be problematic when we switch to smaller
272 tree
translate_isl_ast_to_gimple::
273 gcc_expression_from_isl_ast_expr_id (tree type
,
274 __isl_take isl_ast_expr
*expr_id
,
277 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
278 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
279 std::map
<isl_id
*, tree
>::iterator res
;
280 res
= ip
.find (tmp_isl_id
);
281 isl_id_free (tmp_isl_id
);
282 gcc_assert (res
!= ip
.end () &&
283 "Could not map isl_id to tree expression");
284 isl_ast_expr_free (expr_id
);
285 tree t
= res
->second
;
286 tree
*val
= region
->parameter_rename_map
->get(t
);
290 return fold_convert (type
, *val
);
293 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
296 tree
translate_isl_ast_to_gimple::
297 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
299 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
300 isl_val
*val
= isl_ast_expr_get_val (expr
);
301 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
302 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
304 if (isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
308 widest_int wi
= widest_int::from_array (chunks
, n
, true);
309 if (isl_val_is_neg (val
))
311 res
= wide_int_to_tree (type
, wi
);
314 isl_ast_expr_free (expr
);
318 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
321 tree
translate_isl_ast_to_gimple::
322 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
324 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
325 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
326 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
327 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
329 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
330 isl_ast_expr_free (expr
);
332 if (codegen_error_p ())
338 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
341 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
344 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
347 /* As isl operates on arbitrary precision numbers, we may end up with
348 division by 2^64 that is folded to 0. */
349 if (integer_zerop (tree_rhs_expr
))
351 set_codegen_error ();
354 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
356 case isl_ast_op_pdiv_q
:
357 /* As isl operates on arbitrary precision numbers, we may end up with
358 division by 2^64 that is folded to 0. */
359 if (integer_zerop (tree_rhs_expr
))
361 set_codegen_error ();
364 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
366 case isl_ast_op_zdiv_r
:
367 case isl_ast_op_pdiv_r
:
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 set_codegen_error ();
375 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
377 case isl_ast_op_fdiv_q
:
378 /* As isl operates on arbitrary precision numbers, we may end up with
379 division by 2^64 that is folded to 0. */
380 if (integer_zerop (tree_rhs_expr
))
382 set_codegen_error ();
385 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
388 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
389 tree_lhs_expr
, tree_rhs_expr
);
392 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
395 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
398 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
401 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
404 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
407 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
414 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
417 tree
translate_isl_ast_to_gimple::
418 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
420 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
421 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
422 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
423 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
424 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
425 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
426 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
427 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
428 isl_ast_expr_free (expr
);
430 if (codegen_error_p ())
433 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
436 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
439 tree
translate_isl_ast_to_gimple::
440 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
442 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
443 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
444 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
445 isl_ast_expr_free (expr
);
446 return codegen_error_p () ? NULL_TREE
447 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
450 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
451 to a GCC expression tree of type TYPE. */
453 tree
translate_isl_ast_to_gimple::
454 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
456 enum tree_code op_code
;
457 switch (isl_ast_expr_get_op_type (expr
))
470 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
471 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
473 if (codegen_error_p ())
475 isl_ast_expr_free (expr
);
480 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
482 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
483 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
485 if (codegen_error_p ())
487 isl_ast_expr_free (expr
);
491 res
= fold_build2 (op_code
, type
, res
, t
);
493 isl_ast_expr_free (expr
);
497 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
500 tree
translate_isl_ast_to_gimple::
501 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
504 if (codegen_error_p ())
506 isl_ast_expr_free (expr
);
510 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
511 switch (isl_ast_expr_get_op_type (expr
))
513 /* These isl ast expressions are not supported yet. */
514 case isl_ast_op_error
:
515 case isl_ast_op_call
:
516 case isl_ast_op_and_then
:
517 case isl_ast_op_or_else
:
522 return nary_op_to_tree (type
, expr
, ip
);
528 case isl_ast_op_pdiv_q
:
529 case isl_ast_op_pdiv_r
:
530 case isl_ast_op_fdiv_q
:
531 case isl_ast_op_zdiv_r
:
539 return binary_op_to_tree (type
, expr
, ip
);
541 case isl_ast_op_minus
:
542 return unary_op_to_tree (type
, expr
, ip
);
544 case isl_ast_op_cond
:
545 case isl_ast_op_select
:
546 return ternary_op_to_tree (type
, expr
, ip
);
555 /* Converts an isl AST expression E back to a GCC expression tree of
558 tree
translate_isl_ast_to_gimple::
559 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
562 if (codegen_error_p ())
564 isl_ast_expr_free (expr
);
568 switch (isl_ast_expr_get_type (expr
))
570 case isl_ast_expr_id
:
571 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
573 case isl_ast_expr_int
:
574 return gcc_expression_from_isl_expr_int (type
, expr
);
576 case isl_ast_expr_op
:
577 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
586 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
587 induction variable for the new LOOP. New LOOP is attached to CFG
588 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
589 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
590 isl's scattering name to the induction variable created for the
591 loop of STMT. The new induction variable is inserted in the NEWIVS
592 vector and is of type TYPE. */
594 struct loop
*translate_isl_ast_to_gimple::
595 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
596 loop_p outer
, tree type
, tree lb
, tree ub
,
599 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
600 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
602 /* To fail code generation, we generate wrong code until we discard it. */
603 if (codegen_error_p ())
604 stride
= integer_zero_node
;
606 tree ivvar
= create_tmp_var (type
, "graphite_IV");
607 tree iv
, iv_after_increment
;
608 loop_p loop
= create_empty_loop_on_edge
609 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
610 outer
? outer
: entry_edge
->src
->loop_father
);
612 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
613 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
614 std::map
<isl_id
*, tree
>::iterator res
;
617 isl_id_free (res
->first
);
619 isl_ast_expr_free (for_iterator
);
623 /* Create the loop for a isl_ast_node_for.
625 - NEXT_E is the edge where new generated code should be attached. */
627 edge
translate_isl_ast_to_gimple::
628 translate_isl_ast_for_loop (loop_p context_loop
,
629 __isl_keep isl_ast_node
*node_for
, edge next_e
,
630 tree type
, tree lb
, tree ub
,
633 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
634 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
636 edge last_e
= single_exit (loop
);
637 edge to_body
= single_succ_edge (loop
->header
);
638 basic_block after
= to_body
->dest
;
640 /* Translate the body of the loop. */
641 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
642 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
643 isl_ast_node_free (for_body
);
645 /* Early return if we failed to translate loop body. */
646 if (!next_e
|| codegen_error_p ())
649 if (next_e
->dest
!= after
)
650 redirect_edge_succ_nodup (next_e
, after
);
651 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
653 if (flag_loop_parallelize_all
)
655 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
657 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
658 loop
->can_be_parallel
= for_info
->is_parallelizable
;
666 /* We use this function to get the upper bound because of the form,
667 which is used by isl to represent loops:
669 for (iterator = init; cond; iterator += inc)
677 The loop condition is an arbitrary expression, which contains the
678 current loop iterator.
680 (e.g. iterator + 3 < B && C > iterator + A)
682 We have to know the upper bound of the iterator to generate a loop
683 in Gimple form. It can be obtained from the special representation
684 of the loop condition, which is generated by isl,
685 if the ast_build_atomic_upper_bound option is set. In this case,
686 isl generates a loop condition that consists of the current loop
687 iterator, + an operator (< or <=) and an expression not involving
688 the iterator, which is processed and returned by this function.
690 (e.g iterator <= upper-bound-expression-without-iterator) */
692 static __isl_give isl_ast_expr
*
693 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
695 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
696 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
697 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
699 switch (isl_ast_expr_get_op_type (for_cond
))
702 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
707 /* (iterator < ub) => (iterator <= ub - 1). */
709 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
710 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
711 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
718 isl_ast_expr_free (for_cond
);
722 /* Translates an isl_ast_node_for to Gimple. */
724 edge
translate_isl_ast_to_gimple::
725 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
726 edge next_e
, ivs_params
&ip
)
728 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
730 = build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
732 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
733 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
734 /* To fail code generation, we generate wrong code until we discard it. */
735 if (codegen_error_p ())
736 lb
= integer_zero_node
;
738 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
739 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
740 /* To fail code generation, we generate wrong code until we discard it. */
741 if (codegen_error_p ())
742 ub
= integer_zero_node
;
744 edge last_e
= single_succ_edge (split_edge (next_e
));
745 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
750 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
751 variables of the loops around GBB in SESE.
753 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
754 chrec, we could consider using a map<int, tree> that maps loop ids to the
755 corresponding tree expressions. */
757 void translate_isl_ast_to_gimple::
758 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
759 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
762 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
763 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
765 isl_ast_expr
*arg_expr
;
766 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
768 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
770 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
771 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
773 /* To fail code generation, we generate wrong code until we discard it. */
774 if (codegen_error_p ())
775 t
= integer_zero_node
;
777 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
778 iv_map
[old_loop
->num
] = t
;
782 /* Translates an isl_ast_node_user to Gimple.
784 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
786 edge
translate_isl_ast_to_gimple::
787 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
788 edge next_e
, ivs_params
&ip
)
790 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
792 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
793 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
794 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
796 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
797 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
800 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
802 isl_ast_expr_free (name_expr
);
803 isl_id_free (name_id
);
805 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
806 "The entry block should not even appear within a scop");
808 const int nb_loops
= number_of_loops (cfun
);
810 iv_map
.create (nb_loops
);
811 iv_map
.safe_grow_cleared (nb_loops
);
813 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
814 isl_ast_expr_free (user_expr
);
816 basic_block old_bb
= GBB_BB (gbb
);
820 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
821 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
822 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
826 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
830 if (codegen_error_p ())
835 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
836 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
842 /* Translates an isl_ast_node_block to Gimple. */
844 edge
translate_isl_ast_to_gimple::
845 translate_isl_ast_node_block (loop_p context_loop
,
846 __isl_keep isl_ast_node
*node
,
847 edge next_e
, ivs_params
&ip
)
849 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
850 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
852 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
854 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
855 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
856 isl_ast_node_free (tmp_node
);
858 isl_ast_node_list_free (node_list
);
862 /* Creates a new if region corresponding to isl's cond. */
864 edge
translate_isl_ast_to_gimple::
865 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
869 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
870 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
872 /* To fail code generation, we generate wrong code until we discard it. */
873 if (codegen_error_p ())
874 cond_expr
= integer_zero_node
;
876 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
880 /* Translates an isl_ast_node_if to Gimple. */
882 edge
translate_isl_ast_to_gimple::
883 translate_isl_ast_node_if (loop_p context_loop
,
884 __isl_keep isl_ast_node
*node
,
885 edge next_e
, ivs_params
&ip
)
887 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
888 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
889 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
890 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
891 merge_points
.safe_push (last_e
);
893 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
894 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
895 isl_ast_node_free (then_node
);
897 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
898 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
899 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
900 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
902 isl_ast_node_free (else_node
);
906 /* Translates an isl AST node NODE to GCC representation in the
907 context of a SESE. */
909 edge
translate_isl_ast_to_gimple::
910 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
911 edge next_e
, ivs_params
&ip
)
913 if (codegen_error_p ())
916 switch (isl_ast_node_get_type (node
))
918 case isl_ast_node_error
:
921 case isl_ast_node_for
:
922 return translate_isl_ast_node_for (context_loop
, node
,
925 case isl_ast_node_if
:
926 return translate_isl_ast_node_if (context_loop
, node
,
929 case isl_ast_node_user
:
930 return translate_isl_ast_node_user (node
, next_e
, ip
);
932 case isl_ast_node_block
:
933 return translate_isl_ast_node_block (context_loop
, node
,
936 case isl_ast_node_mark
:
938 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
939 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
940 isl_ast_node_free (n
);
949 /* Return true when BB contains loop close phi nodes. A loop close phi node is
950 at the exit of loop which takes one argument that is the last value of the
951 variable being used out of the loop. */
954 bb_contains_loop_close_phi_nodes (basic_block bb
)
956 return single_pred_p (bb
)
957 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
960 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
961 header containing phi nodes which has one init-edge and one back-edge. */
964 bb_contains_loop_phi_nodes (basic_block bb
)
966 if (EDGE_COUNT (bb
->preds
) != 2)
969 unsigned depth
= loop_depth (bb
->loop_father
);
971 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
973 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
974 || depth
> loop_depth (preds
[1]->src
->loop_father
))
977 /* When one of the edges correspond to the same loop father and other
979 if (bb
->loop_father
!= preds
[0]->src
->loop_father
980 && bb
->loop_father
== preds
[1]->src
->loop_father
)
983 if (bb
->loop_father
!= preds
[1]->src
->loop_father
984 && bb
->loop_father
== preds
[0]->src
->loop_father
)
990 /* Check if USE is defined in a basic block from where the definition of USE can
991 propagate from all the paths. FIXME: Verify checks for virtual operands. */
994 is_loop_closed_ssa_use (basic_block bb
, tree use
)
996 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
999 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1000 if (bb_contains_loop_close_phi_nodes (bb
))
1003 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1004 basic_block def_bb
= gimple_bb (def
);
1006 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1009 /* Return the number of phi nodes in BB. */
1012 number_of_phi_nodes (basic_block bb
)
1015 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1021 /* Returns true if BB uses name in one of its PHIs. */
1024 phi_uses_name (basic_block bb
, tree name
)
1026 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1029 gphi
*phi
= psi
.phi ();
1030 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1032 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1033 if (use_arg
== name
)
1040 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1041 definition should flow into use, and the use should respect the loop-closed
1044 bool translate_isl_ast_to_gimple::
1045 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1046 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1048 if (SSA_NAME_IS_DEFAULT_DEF (rename
))
1051 /* The def of the rename must either dominate the uses or come from a
1052 back-edge. Also the def must respect the loop closed ssa form. */
1053 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1057 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1058 print_generic_expr (dump_file
, rename
);
1059 fprintf (dump_file
, "\n");
1064 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1067 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1069 /* The loop-header dominates the loop-body. */
1070 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1073 /* RENAME would be used in loop-phi. */
1074 gcc_assert (number_of_phi_nodes (use_bb
));
1076 /* For definitions coming from back edges, we should check that
1077 old_name is used in a loop PHI node.
1078 FIXME: Verify if this is true. */
1079 if (phi_uses_name (old_bb
, old_name
))
1085 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1086 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1088 tree
translate_isl_ast_to_gimple::
1089 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1090 phi_node_kind phi_kind
) const
1092 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1093 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1095 if (!renames
|| renames
->is_empty ())
1098 if (1 == renames
->length ())
1100 tree rename
= (*renames
)[0];
1101 if (TREE_CODE (rename
) == SSA_NAME
)
1103 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1104 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1105 && (phi_kind
== close_phi
1107 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1112 if (is_constant (rename
))
1118 /* More than one renames corresponding to the old_name. Find the rename for
1119 which the definition flows into usage at new_bb. */
1121 tree t1
= NULL_TREE
, t2
;
1122 basic_block t1_bb
= NULL
;
1123 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1125 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1127 /* Defined in the same basic block as used. */
1128 if (t2_bb
== new_bb
)
1131 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1132 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1135 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1138 /* Compute the nearest dominator. */
1139 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1149 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1150 When OLD_NAME and EXPR are the same we assert. */
1152 void translate_isl_ast_to_gimple::
1153 set_rename (tree old_name
, tree expr
)
1157 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1158 print_generic_expr (dump_file
, old_name
);
1159 fprintf (dump_file
, ", new_name = ");
1160 print_generic_expr (dump_file
, expr
);
1161 fprintf (dump_file
, "\n");
1164 if (old_name
== expr
)
1167 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1170 renames
->safe_push (expr
);
1176 region
->rename_map
->put (old_name
, r
);
1181 /* For a parameter of a scop we don't want to rename it. */
1182 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1184 region
->parameter_rename_map
->put(old_name
, expr
);
1187 /* Return an iterator to the instructions comes last in the execution order.
1188 Either GSI1 and GSI2 should belong to the same basic block or one of their
1189 respective basic blocks should dominate the other. */
1191 gimple_stmt_iterator
1192 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1194 basic_block bb1
= gsi_bb (gsi1
);
1195 basic_block bb2
= gsi_bb (gsi2
);
1197 /* Find the iterator which is the latest. */
1200 gimple
*stmt1
= gsi_stmt (gsi1
);
1201 gimple
*stmt2
= gsi_stmt (gsi2
);
1203 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1205 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1206 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1208 if (is_phi1
!= is_phi2
)
1209 return is_phi1
? gsi2
: gsi1
;
1212 /* For empty basic blocks gsis point to the end of the sequence. Since
1213 there is no operator== defined for gimple_stmt_iterator and for gsis
1214 not pointing to a valid statement gsi_next would assert. */
1215 gimple_stmt_iterator gsi
= gsi1
;
1217 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1220 } while (!gsi_end_p (gsi
));
1225 /* Find the basic block closest to the basic block which defines stmt. */
1226 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1229 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1233 /* Insert each statement from SEQ at its earliest insertion p. */
1235 void translate_isl_ast_to_gimple::
1236 gsi_insert_earliest (gimple_seq seq
)
1238 update_modified_stmts (seq
);
1239 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1240 basic_block begin_bb
= get_entry_bb (codegen_region
);
1242 /* Inserting the gimple statements in a vector because gimple_seq behave
1243 in strage ways when inserting the stmts from it into different basic
1244 blocks one at a time. */
1245 auto_vec
<gimple
*, 3> stmts
;
1246 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1248 stmts
.safe_push (gsi_stmt (gsi
));
1252 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1254 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1255 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1257 use_operand_p use_p
;
1258 ssa_op_iter op_iter
;
1259 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1261 /* Iterator to the current def of use_p. For function parameters or
1262 anything where def is not found, insert at the beginning of the
1263 generated region. */
1264 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1266 tree op
= USE_FROM_PTR (use_p
);
1267 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1268 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1269 gsi_stmt
= gsi_for_stmt (stmt
);
1271 /* For region parameters, insert at the beginning of the generated
1273 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1274 gsi_stmt
= gsi_def_stmt
;
1276 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1279 if (!gsi_stmt (gsi_def_stmt
))
1281 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1282 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1284 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1286 gimple_stmt_iterator bsi
1287 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1288 /* Insert right after the PHI statements. */
1289 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1292 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1296 fprintf (dump_file
, "[codegen] inserting statement: ");
1297 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1298 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1303 /* Collect all the operands of NEW_EXPR by recursively visiting each
1306 void translate_isl_ast_to_gimple::
1307 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1309 if (new_expr
== NULL_TREE
)
1312 /* Rename all uses in new_expr. */
1313 if (TREE_CODE (new_expr
) == SSA_NAME
)
1315 vec_ssa
->safe_push (new_expr
);
1319 /* Iterate over SSA_NAMES in NEW_EXPR. */
1320 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1322 tree op
= TREE_OPERAND (new_expr
, i
);
1323 collect_all_ssa_names (op
, vec_ssa
);
1327 /* This is abridged version of the function copied from:
1328 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1331 substitute_ssa_name (tree exp
, tree f
, tree r
)
1333 enum tree_code code
= TREE_CODE (exp
);
1334 tree op0
, op1
, op2
, op3
;
1337 /* We handle TREE_LIST and COMPONENT_REF separately. */
1338 if (code
== TREE_LIST
)
1340 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1341 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1342 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1345 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1347 else if (code
== COMPONENT_REF
)
1351 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1352 and it is the right field, replace it with R. */
1353 for (inner
= TREE_OPERAND (exp
, 0);
1354 REFERENCE_CLASS_P (inner
);
1355 inner
= TREE_OPERAND (inner
, 0))
1359 op1
= TREE_OPERAND (exp
, 1);
1361 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1364 /* If this expression hasn't been completed let, leave it alone. */
1365 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1368 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1369 if (op0
== TREE_OPERAND (exp
, 0))
1373 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1376 switch (TREE_CODE_CLASS (code
))
1381 case tcc_declaration
:
1387 case tcc_expression
:
1393 case tcc_exceptional
:
1396 case tcc_comparison
:
1398 switch (TREE_CODE_LENGTH (code
))
1406 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1407 if (op0
== TREE_OPERAND (exp
, 0))
1410 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1414 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1415 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1417 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1420 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1424 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1425 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1426 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1428 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1429 && op2
== TREE_OPERAND (exp
, 2))
1432 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1436 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1437 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1438 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1439 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1441 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1442 && op2
== TREE_OPERAND (exp
, 2)
1443 && op3
== TREE_OPERAND (exp
, 3))
1447 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1460 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1462 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1463 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1468 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1470 tree
translate_isl_ast_to_gimple::
1471 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1473 auto_vec
<tree
, 2> ssa_names
;
1474 collect_all_ssa_names (new_expr
, &ssa_names
);
1477 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1478 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1479 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1484 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1485 scalar evolution around LOOP. */
1487 tree
translate_isl_ast_to_gimple::
1488 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1489 basic_block new_bb
, basic_block old_bb
,
1492 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1494 /* At this point we should know the exact scev for each
1495 scalar SSA_NAME used in the scop: all the other scalar
1496 SSA_NAMEs should have been translated out of SSA using
1497 arrays with one element. */
1499 if (chrec_contains_undetermined (scev
))
1501 set_codegen_error ();
1502 return build_zero_cst (TREE_TYPE (old_name
));
1505 new_expr
= chrec_apply_map (scev
, iv_map
);
1507 /* The apply should produce an expression tree containing
1508 the uses of the new induction variables. We should be
1509 able to use new_expr instead of the old_name in the newly
1510 generated loop nest. */
1511 if (chrec_contains_undetermined (new_expr
)
1512 || tree_contains_chrecs (new_expr
, NULL
))
1514 set_codegen_error ();
1515 return build_zero_cst (TREE_TYPE (old_name
));
1518 if (TREE_CODE (new_expr
) == SSA_NAME
)
1520 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1521 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1523 set_codegen_error ();
1524 return build_zero_cst (TREE_TYPE (old_name
));
1528 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1530 /* We check all the operands and all of them should dominate the use at
1532 auto_vec
<tree
, 2> new_ssa_names
;
1533 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1536 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1538 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1540 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1541 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1543 set_codegen_error ();
1544 return build_zero_cst (TREE_TYPE (old_name
));
1549 /* Replace the old_name with the new_expr. */
1550 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1554 /* Renames the scalar uses of the statement COPY, using the
1555 substitution map RENAME_MAP, inserting the gimplification code at
1556 GSI_TGT, for the translation REGION, with the original copied
1557 statement in LOOP, and using the induction variable renaming map
1558 IV_MAP. Returns true when something has been renamed. */
1560 bool translate_isl_ast_to_gimple::
1561 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1562 loop_p loop
, vec
<tree
> iv_map
)
1564 bool changed
= false;
1566 if (is_gimple_debug (copy
))
1568 if (gimple_debug_bind_p (copy
))
1569 gimple_debug_bind_reset_value (copy
);
1570 else if (gimple_debug_source_bind_p (copy
))
1580 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1581 print_gimple_stmt (dump_file
, copy
, 0);
1584 use_operand_p use_p
;
1585 ssa_op_iter op_iter
;
1586 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1588 tree old_name
= USE_FROM_PTR (use_p
);
1592 fprintf (dump_file
, "[codegen] renaming old_name = ");
1593 print_generic_expr (dump_file
, old_name
);
1594 fprintf (dump_file
, "\n");
1597 if (TREE_CODE (old_name
) != SSA_NAME
1598 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1602 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1603 old_bb
, unknown_phi
);
1607 tree type_old_name
= TREE_TYPE (old_name
);
1608 tree type_new_expr
= TREE_TYPE (new_expr
);
1612 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1613 print_generic_expr (dump_file
, new_expr
);
1614 fprintf (dump_file
, "\n");
1617 if (type_old_name
!= type_new_expr
1618 || TREE_CODE (new_expr
) != SSA_NAME
)
1620 tree var
= create_tmp_var (type_old_name
, "var");
1622 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1623 new_expr
= fold_convert (type_old_name
, new_expr
);
1626 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1627 gsi_insert_earliest (stmts
);
1630 replace_exp (use_p
, new_expr
);
1635 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1637 if (!new_expr
|| codegen_error_p ())
1642 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1643 print_generic_expr (dump_file
, new_expr
);
1644 fprintf (dump_file
, "\n");
1647 gsi_insert_earliest (stmts
);
1648 replace_exp (use_p
, new_expr
);
1650 if (TREE_CODE (new_expr
) == INTEGER_CST
1651 && is_gimple_assign (copy
))
1653 tree rhs
= gimple_assign_rhs1 (copy
);
1655 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1656 recompute_tree_invariant_for_addr_expr (rhs
);
1659 set_rename (old_name
, new_expr
);
1665 /* Returns a basic block that could correspond to where a constant was defined
1666 in the original code. In the original code OLD_BB had the definition, we
1667 need to find which basic block out of the copies of old_bb, in the new
1668 region, should a definition correspond to if it has to reach BB. */
1670 basic_block
translate_isl_ast_to_gimple::
1671 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1673 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1675 if (!bbs
|| bbs
->is_empty ())
1678 if (1 == bbs
->length ())
1682 basic_block b1
= NULL
, b2
;
1683 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1688 /* BB and B2 are in two unrelated if-clauses. */
1689 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1692 /* Compute the nearest dominator. */
1693 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1700 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1701 determines the kind of phi node. */
1703 tree
translate_isl_ast_to_gimple::
1704 get_new_name (basic_block new_bb
, tree op
,
1705 basic_block old_bb
, phi_node_kind phi_kind
) const
1707 /* For constants the names are the same. */
1708 if (TREE_CODE (op
) != SSA_NAME
)
1711 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1714 /* Return a debug location for OP. */
1719 location_t loc
= UNKNOWN_LOCATION
;
1721 if (TREE_CODE (op
) == SSA_NAME
)
1722 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1726 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1727 the init edge (from outside the loop) and the second one is the back edge
1728 from the same loop. */
1730 std::pair
<edge
, edge
>
1731 get_edges (basic_block bb
)
1733 std::pair
<edge
, edge
> edges
;
1736 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1737 if (bb
->loop_father
!= e
->src
->loop_father
)
1744 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1745 must be found unless they can be POSTPONEd for later. */
1747 bool translate_isl_ast_to_gimple::
1748 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1749 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1752 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1754 basic_block new_bb
= gimple_bb (new_phi
);
1755 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1758 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1759 e
= ibp_new_bb
.first
;
1761 e
= ibp_new_bb
.second
;
1763 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1764 tree new_name
= get_new_name (new_bb
, old_name
,
1765 gimple_bb (old_phi
), loop_phi
);
1768 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1772 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1773 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1774 /* If the phi arg was a function arg, or wasn't defined, just use the
1776 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1779 /* Postpone code gen for later for those back-edges we don't have the
1781 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1783 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1786 /* Either we should add the arg to phi or, we should postpone. */
1792 /* Copy loop phi nodes from BB to NEW_BB. */
1794 bool translate_isl_ast_to_gimple::
1795 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1798 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1801 /* Loop phi nodes should have only two arguments. */
1802 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1804 /* First edge is the init edge and second is the back edge. */
1805 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1807 /* First edge is the init edge and second is the back edge. */
1808 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1810 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1813 gphi
*phi
= psi
.phi ();
1814 tree res
= gimple_phi_result (phi
);
1815 if (virtual_operand_p (res
))
1817 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1820 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
1821 tree new_res
= create_new_def_for (res
, new_phi
,
1822 gimple_phi_result_ptr (new_phi
));
1823 set_rename (res
, new_res
);
1824 if (!copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
, ibp_new_bb
, true))
1825 set_codegen_error ();
1826 update_stmt (new_phi
);
1830 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1831 print_gimple_stmt (dump_file
, new_phi
, 0);
1838 /* Return the init value of PHI, the value coming from outside the loop. */
1841 get_loop_init_value (gphi
*phi
)
1844 loop_p loop
= gimple_bb (phi
)->loop_father
;
1848 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1849 if (e
->src
->loop_father
!= loop
)
1850 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1855 /* Find the init value (the value which comes from outside the loop), of one of
1856 the operands of DEF which is defined by a loop phi. */
1859 find_init_value (gimple
*def
)
1861 if (gimple_code (def
) == GIMPLE_PHI
)
1862 return get_loop_init_value (as_a
<gphi
*> (def
));
1864 if (gimple_vuse (def
))
1868 use_operand_p use_p
;
1869 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1871 tree use
= USE_FROM_PTR (use_p
);
1872 if (TREE_CODE (use
) == SSA_NAME
)
1874 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1882 /* Return the init value, the value coming from outside the loop. */
1885 find_init_value_close_phi (gphi
*phi
)
1887 gcc_assert (gimple_phi_num_args (phi
) == 1);
1888 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1889 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1890 return find_init_value (def
);
1894 tree
translate_isl_ast_to_gimple::
1895 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1896 gimple
*old_close_phi
)
1898 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1899 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1900 basic_block bb
= gimple_bb (stmt
);
1901 if (!bb_in_sese_p (bb
, codegen_region
))
1902 return last_merge_name
;
1904 loop_p loop
= bb
->loop_father
;
1905 if (!loop_in_sese_p (loop
, codegen_region
))
1906 return last_merge_name
;
1908 edge e
= single_exit (loop
);
1910 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1911 return last_merge_name
;
1913 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1914 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1917 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
1918 bb
= split_edge (e
);
1920 gphi
*close_phi
= create_phi_node (NULL_TREE
, bb
);
1921 tree res
= create_new_def_for (last_merge_name
, close_phi
,
1922 gimple_phi_result_ptr (close_phi
));
1923 set_rename (old_close_phi_name
, res
);
1924 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
1925 last_merge_name
= res
;
1927 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
1930 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
1931 the close phi node PHI. */
1933 bool translate_isl_ast_to_gimple::
1934 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
1937 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1938 basic_block default_value_bb
= get_entry_bb (codegen_region
);
1939 if (SSA_NAME
== TREE_CODE (default_value
))
1941 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
1942 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
1944 default_value_bb
= gimple_bb (stmt
);
1947 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
1949 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1950 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
1951 tree last_merge_name
= new_close_phi_name
;
1952 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1956 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
1958 basic_block new_merge_bb
= merge_e
->src
;
1959 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
1962 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
1965 gphi
*merge_phi
= create_phi_node (NULL_TREE
, new_merge_bb
);
1966 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
1967 gimple_phi_result_ptr (merge_phi
));
1968 set_rename (old_close_phi_name
, merge_res
);
1970 edge from_loop
= NULL
, from_default_value
= NULL
;
1973 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
1974 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
1977 from_default_value
= e
;
1979 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
1980 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
1981 is contained in another condition. */
1982 if (!from_default_value
|| !from_loop
)
1985 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
1986 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
1990 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
1991 print_gimple_stmt (dump_file
, merge_phi
, 0);
1994 update_stmt (merge_phi
);
1995 last_merge_name
= merge_res
;
2001 /* Copy all the loop-close phi args from BB to NEW_BB. */
2003 bool translate_isl_ast_to_gimple::
2004 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
2005 vec
<tree
> iv_map
, bool postpone
)
2007 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2010 gphi
*old_close_phi
= psi
.phi ();
2011 tree res
= gimple_phi_result (old_close_phi
);
2012 if (virtual_operand_p (res
))
2015 gphi
*new_close_phi
= create_phi_node (NULL_TREE
, new_bb
);
2016 tree new_res
= create_new_def_for (res
, new_close_phi
,
2017 gimple_phi_result_ptr (new_close_phi
));
2018 set_rename (res
, new_res
);
2020 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2022 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2025 new_name
= get_rename_from_scev (old_name
, &stmts
,
2026 old_bb
->loop_father
,
2027 new_bb
, old_bb
, iv_map
);
2028 if (! codegen_error_p ())
2029 gsi_insert_earliest (stmts
);
2032 new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2034 /* Predecessor basic blocks of a loop close phi should have been code
2035 generated before. FIXME: This is fixable by merging PHIs from inner
2036 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2037 if (!new_name
|| codegen_error_p ())
2040 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2041 get_loc (old_name
));
2044 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2045 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2048 update_stmt (new_close_phi
);
2050 /* When there is no loop guard around this codegenerated loop, there is no
2051 need to collect the close-phi arg. */
2052 if (merge_points
.is_empty ())
2055 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2056 tree default_value
= find_init_value_close_phi (new_close_phi
);
2058 /* A close phi must come from a loop-phi having a default value. */
2064 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2068 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2069 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2074 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2082 /* Copy loop close phi nodes from BB to NEW_BB. */
2084 bool translate_isl_ast_to_gimple::
2085 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
2089 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2091 /* Loop close phi nodes should have only one argument. */
2092 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2094 return copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, true);
2098 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2099 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2100 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2101 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2104 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2105 In this case DOMINATING_PRED = NULL.
2107 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2109 Returns true on successful copy of the args, false otherwise. */
2111 bool translate_isl_ast_to_gimple::
2112 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2113 edge old_bb_dominating_edge
,
2114 edge old_bb_non_dominating_edge
,
2115 gphi
*phi
, gphi
*new_phi
,
2118 basic_block def_pred
[2] = { NULL
, NULL
};
2119 int not_found_bb_index
= -1;
2120 for (int i
= 0; i
< 2; i
++)
2122 /* If the corresponding def_bb could not be found the entry will be
2124 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2125 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2126 gimple_phi_arg_edge (phi
, i
)->src
);
2127 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2128 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2132 /* When non are available bail out. */
2133 if (not_found_bb_index
!= -1)
2135 not_found_bb_index
= i
;
2139 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2140 if (old_bb_dominating_edge
)
2142 if (not_found_bb_index
!= -1)
2145 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2146 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2147 vec
<basic_block
> *bbs
2148 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2150 /* Could not find a mapping. */
2154 basic_block new_pred
= NULL
;
2157 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2159 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2161 /* FIXME: If we have already found new_pred then we have to
2162 disambiguate, bail out for now. */
2165 new_pred
= new_pred1
;
2167 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2169 /* FIXME: If we have already found new_pred then we have to either
2170 it dominates both or we have to disambiguate, bail out. */
2173 new_pred
= new_pred2
;
2180 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2181 gcc_assert (new_non_dominating_edge
);
2182 /* FIXME: Validate each args just like in loop-phis. */
2183 /* By the process of elimination we first insert insert phi-edge for
2184 non-dominating pred which is computed above and then we insert the
2186 int inserted_edge
= 0;
2187 for (; inserted_edge
< 2; inserted_edge
++)
2189 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2190 if (new_non_dominating_edge
== new_bb_pred_edge
)
2192 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2193 new_non_dominating_edge
,
2194 get_loc (old_phi_args
[inserted_edge
]));
2198 if (inserted_edge
== 2)
2201 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2203 edge new_dominating_edge
= NULL
;
2204 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2206 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2207 if (e
!= new_non_dominating_edge
)
2209 new_dominating_edge
= e
;
2210 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2211 new_dominating_edge
,
2212 get_loc (old_phi_args
[inserted_edge
]));
2216 gcc_assert (new_dominating_edge
);
2220 /* Classic diamond structure: both edges are non-dominating. We need to
2221 find one unique edge then the other can be found be elimination. If
2222 any definition (def_pred) dominates both the preds of new_bb then we
2223 bail out. Entries of def_pred maybe NULL, in that case we must
2224 uniquely find pred with help of only one entry. */
2225 edge new_e
[2] = { NULL
, NULL
};
2226 for (int i
= 0; i
< 2; i
++)
2230 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2232 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2235 /* We do not know how to handle the case when def_pred
2236 dominates more than a predecessor. */
2242 gcc_assert (new_e
[0] || new_e
[1]);
2244 /* Find the other edge by process of elimination. */
2245 if (not_found_bb_index
!= -1)
2247 gcc_assert (!new_e
[not_found_bb_index
]);
2248 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2251 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2253 if (new_e
[found_bb_index
] == e
)
2255 new_e
[not_found_bb_index
] = e
;
2259 /* Add edges to phi args. */
2260 for (int i
= 0; i
< 2; i
++)
2261 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2262 get_loc (old_phi_args
[i
]));
2268 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2269 region. If postpone is true and it isn't possible to copy any arg of PHI,
2270 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2271 Returns false if the copying was unsuccessful. */
2273 bool translate_isl_ast_to_gimple::
2274 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2277 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2278 gcc_assert (2 == gimple_phi_num_args (phi
));
2280 basic_block new_bb
= gimple_bb (new_phi
);
2281 loop_p loop
= gimple_bb (phi
)->loop_father
;
2283 basic_block old_bb
= gimple_bb (phi
);
2284 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2288 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2289 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2290 old_bb_non_dominating_edge
= e
;
2292 old_bb_dominating_edge
= e
;
2294 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2295 old_bb_non_dominating_edge
->src
));
2297 tree new_phi_args
[2];
2298 tree old_phi_args
[2];
2300 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2302 tree old_name
= gimple_phi_arg_def (phi
, i
);
2303 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2304 old_phi_args
[i
] = old_name
;
2307 new_phi_args
[i
] = new_name
;
2311 /* If the phi-arg was a parameter. */
2312 if (vec_find (region
->params
, old_name
) != -1)
2314 new_phi_args
[i
] = old_name
;
2318 "[codegen] parameter argument to phi, new_expr: ");
2319 print_generic_expr (dump_file
, new_phi_args
[i
]);
2320 fprintf (dump_file
, "\n");
2325 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2326 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2327 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2333 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2334 if (is_gimple_reg (old_name
)
2335 && scev_analyzable_p (old_name
, region
->region
))
2338 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2339 new_bb
, old_bb
, iv_map
);
2340 if (codegen_error_p ())
2343 gcc_assert (new_expr
);
2347 "[codegen] scev analyzeable, new_expr: ");
2348 print_generic_expr (dump_file
, new_expr
);
2349 fprintf (dump_file
, "\n");
2351 gsi_insert_earliest (stmts
);
2352 new_phi_args
[i
] = new_expr
;
2356 /* Postpone code gen for later for back-edges. */
2357 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2361 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2362 print_gimple_stmt (dump_file
, new_phi
, 0);
2365 new_phi_args
[i
] = NULL_TREE
;
2369 /* Either we should add the arg to phi or, we should postpone. */
2373 /* If none of the args have been determined in the first stage then wait until
2375 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2378 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2379 old_bb_dominating_edge
,
2380 old_bb_non_dominating_edge
,
2381 phi
, new_phi
, new_bb
);
2384 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2385 containing phi nodes coming from two predecessors, and none of them are back
2388 bool translate_isl_ast_to_gimple::
2389 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2392 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2394 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2395 if (EDGE_COUNT (bb
->preds
) != 2)
2399 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2402 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2405 gphi
*phi
= psi
.phi ();
2406 tree res
= gimple_phi_result (phi
);
2407 if (virtual_operand_p (res
))
2410 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
2411 tree new_res
= create_new_def_for (res
, new_phi
,
2412 gimple_phi_result_ptr (new_phi
));
2413 set_rename (res
, new_res
);
2415 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2418 update_stmt (new_phi
);
2424 /* Return true if STMT should be copied from region to the new code-generated
2425 region. LABELs, CONDITIONS, induction-variables and region parameters need
2429 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2431 /* Do not copy labels or conditions. */
2432 if (gimple_code (stmt
) == GIMPLE_LABEL
2433 || gimple_code (stmt
) == GIMPLE_COND
)
2437 /* Do not copy induction variables. */
2438 if (is_gimple_assign (stmt
)
2439 && (lhs
= gimple_assign_lhs (stmt
))
2440 && TREE_CODE (lhs
) == SSA_NAME
2441 && is_gimple_reg (lhs
)
2442 && scev_analyzable_p (lhs
, region
->region
))
2445 /* Do not copy parameters that have been generated in the header of the
2447 if (is_gimple_assign (stmt
)
2448 && (lhs
= gimple_assign_lhs (stmt
))
2449 && TREE_CODE (lhs
) == SSA_NAME
2450 && region
->parameter_rename_map
->get(lhs
))
2456 /* Create new names for all the definitions created by COPY and add replacement
2457 mappings for each new name. */
2459 void translate_isl_ast_to_gimple::
2460 set_rename_for_each_def (gimple
*stmt
)
2462 def_operand_p def_p
;
2463 ssa_op_iter op_iter
;
2464 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2466 tree old_name
= DEF_FROM_PTR (def_p
);
2467 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2468 set_rename (old_name
, new_name
);
2472 /* Duplicates the statements of basic block BB into basic block NEW_BB
2473 and compute the new induction variables according to the IV_MAP. */
2475 bool translate_isl_ast_to_gimple::
2476 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2479 /* Iterator poining to the place where new statement (s) will be inserted. */
2480 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2482 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2485 gimple
*stmt
= gsi_stmt (gsi
);
2486 if (!should_copy_to_new_region (stmt
, region
))
2489 /* Create a new copy of STMT and duplicate STMT's virtual
2491 gimple
*copy
= gimple_copy (stmt
);
2492 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2496 fprintf (dump_file
, "[codegen] inserting statement: ");
2497 print_gimple_stmt (dump_file
, copy
, 0);
2500 maybe_duplicate_eh_stmt (copy
, stmt
);
2501 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2503 /* Crete new names for each def in the copied stmt. */
2504 set_rename_for_each_def (copy
);
2506 loop_p loop
= bb
->loop_father
;
2507 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2509 fold_stmt_inplace (&gsi_tgt
);
2510 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2513 if (codegen_error_p ())
2516 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2518 use_operand_p use_p
;
2519 if (!is_gimple_debug (copy
))
2520 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2522 tree old_name
= USE_FROM_PTR (use_p
);
2524 if (TREE_CODE (old_name
) != SSA_NAME
2525 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2528 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2532 replace_exp (use_p
, *new_expr
);
2542 /* Given a basic block containing close-phi it returns the new basic block where
2543 to insert a copy of the close-phi nodes. All the uses in close phis should
2544 come from a single loop otherwise it returns NULL. */
2546 edge
translate_isl_ast_to_gimple::
2547 edge_for_new_close_phis (basic_block bb
)
2549 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2550 of close phi in the original code and then find the mapping of basic block
2551 defining that variable. If there are multiple close-phis and they are
2552 defined in different loops (in the original or in the new code) because of
2553 loop splitting, then we bail out. */
2554 loop_p new_loop
= NULL
;
2555 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2558 gphi
*phi
= psi
.phi ();
2559 tree name
= gimple_phi_arg_def (phi
, 0);
2560 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2562 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2563 if (!bbs
|| bbs
->length () != 1)
2564 /* This is one of the places which shows preserving original structure
2565 is not always possible, as we may need to insert close PHI for a loop
2566 where the latch does not have any mapping, or the mapping is
2571 new_loop
= (*bbs
)[0]->loop_father
;
2572 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2579 return single_exit (new_loop
);
2582 /* Copies BB and includes in the copied BB all the statements that can
2583 be reached following the use-def chains from the memory accesses,
2584 and returns the next edge following this new block. */
2586 edge
translate_isl_ast_to_gimple::
2587 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2589 int num_phis
= number_of_phi_nodes (bb
);
2591 if (region
->copied_bb_map
->get (bb
))
2593 /* FIXME: we should be able to handle phi nodes with args coming from
2594 outside the region. */
2597 set_codegen_error ();
2602 basic_block new_bb
= NULL
;
2603 if (bb_contains_loop_close_phi_nodes (bb
))
2606 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2609 edge e
= edge_for_new_close_phis (bb
);
2612 set_codegen_error ();
2616 basic_block phi_bb
= e
->dest
;
2618 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2619 phi_bb
= split_edge (e
);
2621 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2622 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2624 if (!copy_loop_close_phi_nodes (bb
, phi_bb
, iv_map
))
2626 set_codegen_error ();
2633 new_bb
= split_edge (next_e
);
2637 new_bb
= split_edge (next_e
);
2638 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2640 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2642 /* At this point we are unable to codegenerate by still preserving the SSA
2643 structure because maybe the loop is completely unrolled and the PHIs
2644 and cross-bb scalar dependencies are untrackable w.r.t. the original
2645 code. See gfortran.dg/graphite/pr29832.f90. */
2646 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2648 set_codegen_error ();
2652 /* In case isl did some loop peeling, like this:
2655 for (int c1 = 1; c1 <= 5; c1 += 1) {
2660 there should be no loop-phi nodes in S_8(0).
2662 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2663 values of all scalar variables: for the moment we instantiate only
2664 SCEV analyzable expressions on the iteration domain, and we need to
2665 extend that to reductions that cannot be analyzed by SCEV. */
2666 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2668 set_codegen_error ();
2673 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2675 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2677 set_codegen_error ();
2681 else if (num_phis
> 0)
2684 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2687 basic_block phi_bb
= single_pred (new_bb
);
2688 loop_p loop_father
= new_bb
->loop_father
;
2690 /* Move back until we find the block with two predecessors. */
2691 while (single_pred_p (phi_bb
))
2692 phi_bb
= single_pred_edge (phi_bb
)->src
;
2694 /* If a corresponding merge-point was not found, then abort codegen. */
2695 if (phi_bb
->loop_father
!= loop_father
2696 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2697 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2699 set_codegen_error ();
2706 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2707 bb
->index
, new_bb
->index
);
2709 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2711 copied_bbs
->safe_push (new_bb
);
2714 vec
<basic_block
> bbs
;
2716 bbs
.safe_push (new_bb
);
2717 region
->copied_bb_map
->put (bb
, bbs
);
2720 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2722 set_codegen_error ();
2726 return single_succ_edge (new_bb
);
2729 /* Patch the missing arguments of the phi nodes. */
2731 void translate_isl_ast_to_gimple::
2732 translate_pending_phi_nodes ()
2736 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2738 gphi
*old_phi
= rename
->first
;
2739 gphi
*new_phi
= rename
->second
;
2740 basic_block old_bb
= gimple_bb (old_phi
);
2741 basic_block new_bb
= gimple_bb (new_phi
);
2743 /* First edge is the init edge and second is the back edge. */
2744 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2745 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2749 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2750 print_gimple_stmt (dump_file
, old_phi
, 0);
2753 auto_vec
<tree
, 1> iv_map
;
2754 if (bb_contains_loop_phi_nodes (new_bb
)
2755 && bb_contains_loop_phi_nodes (old_bb
))
2757 if (!copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2759 set_codegen_error ();
2761 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2763 if (!copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, false))
2764 set_codegen_error ();
2766 else if (!copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false))
2767 set_codegen_error ();
2771 fprintf (dump_file
, "[codegen] to new-phi: ");
2772 print_gimple_stmt (dump_file
, new_phi
, 0);
2774 if (codegen_error_p ())
2779 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2781 void translate_isl_ast_to_gimple::
2782 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2784 sese_info_p region
= scop
->scop_info
;
2785 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2786 gcc_assert (nb_parameters
== region
->params
.length ());
2788 for (i
= 0; i
< nb_parameters
; i
++)
2790 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2792 ip
[tmp_id
] = region
->params
[i
];
2797 /* Generates a build, which specifies the constraints on the parameters. */
2799 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2800 generate_isl_context (scop_p scop
)
2802 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2803 return isl_ast_build_from_context (context_isl
);
2806 /* This method is executed before the construction of a for node. */
2808 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2810 isl_union_map
*dependences
= (isl_union_map
*) user
;
2811 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2812 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2813 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2814 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2815 for_info
->is_parallelizable
=
2816 !carries_deps (schedule
, dependences
, dimension
);
2817 isl_union_map_free (schedule
);
2818 isl_space_free (schedule_space
);
2819 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2823 /* Generate isl AST from schedule of SCOP. */
2825 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2826 scop_to_isl_ast (scop_p scop
)
2828 gcc_assert (scop
->transformed_schedule
);
2830 /* Set the separate option to reduce control flow overhead. */
2831 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2832 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2833 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2835 if (flag_loop_parallelize_all
)
2837 scop_get_dependences (scop
);
2839 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2843 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2844 (context_isl
, schedule
);
2845 isl_ast_build_free (context_isl
);
2849 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2850 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2853 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2854 gimple_stmt_iterator
*gsi
)
2856 if (!defined_in_sese_p (tr
, region
->region
))
2860 use_operand_p use_p
;
2861 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2863 tree use_tr
= USE_FROM_PTR (use_p
);
2865 /* Do not copy parameters that have been generated in the header of the
2867 if (region
->parameter_rename_map
->get(use_tr
))
2870 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2874 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2877 gimple
*copy
= gimple_copy (def_stmt
);
2878 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2880 /* Create new names for all the definitions created by COPY and
2881 add replacement mappings for each new name. */
2882 def_operand_p def_p
;
2883 ssa_op_iter op_iter
;
2884 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2886 tree old_name
= DEF_FROM_PTR (def_p
);
2887 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2888 region
->parameter_rename_map
->put(old_name
, new_name
);
2895 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2897 /* For all the parameters which definitino is in the if_region->false_region,
2898 insert code on true_region (if_region->true_region->entry). */
2902 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2904 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2906 // If def is not in region.
2907 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2909 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2913 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2914 Return true if code generation succeeded. */
2917 graphite_regenerate_ast_isl (scop_p scop
)
2919 sese_info_p region
= scop
->scop_info
;
2920 translate_isl_ast_to_gimple
t (region
);
2922 ifsese if_region
= NULL
;
2923 isl_ast_node
*root_node
;
2926 timevar_push (TV_GRAPHITE_CODE_GEN
);
2927 t
.add_parameters_to_ivs_params (scop
, ip
);
2928 root_node
= t
.scop_to_isl_ast (scop
);
2930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2932 fprintf (dump_file
, "[scheduler] original schedule:\n");
2933 print_isl_schedule (dump_file
, scop
->original_schedule
);
2934 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
2935 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
2937 fprintf (dump_file
, "[scheduler] original ast:\n");
2938 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
2939 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
2940 print_isl_ast (dump_file
, root_node
);
2943 if_region
= move_sese_in_condition (region
);
2944 region
->if_region
= if_region
;
2946 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2948 /* Copy all the parameters which are defined in the region. */
2949 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
2951 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2952 basic_block bb
= split_edge (e
);
2954 /* Update the true_region exit edge. */
2955 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2957 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2958 if (! t
.codegen_error_p ())
2959 t
.translate_pending_phi_nodes ();
2960 if (! t
.codegen_error_p ())
2962 sese_insert_phis_for_liveouts (region
,
2963 if_region
->region
->region
.exit
->src
,
2964 if_region
->false_region
->region
.exit
,
2965 if_region
->true_region
->region
.exit
);
2967 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
2969 mark_virtual_operands_for_renaming (cfun
);
2970 update_ssa (TODO_update_ssa
);
2973 if (t
.codegen_error_p ())
2976 fprintf (dump_file
, "codegen error: "
2977 "reverting back to the original code.\n");
2978 set_ifsese_condition (if_region
, integer_zero_node
);
2980 /* We registered new names, scrap that. */
2981 if (need_ssa_update_p (cfun
))
2982 delete_update_ssa ();
2983 /* Remove the unreachable region. */
2984 remove_edge_and_dominated_blocks (if_region
->true_region
->region
.entry
);
2985 basic_block ifb
= if_region
->false_region
->region
.entry
->src
;
2986 gimple_stmt_iterator gsi
= gsi_last_bb (ifb
);
2987 gsi_remove (&gsi
, true);
2988 if_region
->false_region
->region
.entry
->flags
&= ~EDGE_FALSE_VALUE
;
2989 if_region
->false_region
->region
.entry
->flags
|= EDGE_FALLTHRU
;
2990 /* remove_edge_and_dominated_blocks marks loops for removal but
2991 doesn't actually remove them (fix that...). */
2993 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2998 /* Verifies properties that GRAPHITE should maintain during translation. */
2999 checking_verify_loop_structure ();
3000 checking_verify_loop_closed_ssa (true);
3002 free (if_region
->true_region
);
3003 free (if_region
->region
);
3006 ivs_params_clear (ip
);
3007 isl_ast_node_free (root_node
);
3008 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3010 return !t
.codegen_error_p ();
3013 #endif /* HAVE_isl */