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
; }
244 void set_codegen_error ()
246 codegen_error
= true;
247 gcc_assert (! flag_checking
248 || PARAM_VALUE (PARAM_GRAPHITE_ALLOW_CODEGEN_ERRORS
));
251 bool is_constant (tree op
) const
253 return TREE_CODE (op
) == INTEGER_CST
254 || TREE_CODE (op
) == REAL_CST
255 || TREE_CODE (op
) == COMPLEX_CST
256 || TREE_CODE (op
) == VECTOR_CST
;
260 /* The region to be translated. */
263 /* This flag is set when an error occurred during the translation of isl AST
267 /* A vector of all the edges at if_condition merge points. */
268 auto_vec
<edge
, 2> merge_points
;
271 /* Return the tree variable that corresponds to the given isl ast identifier
272 expression (an isl_ast_expr of type isl_ast_expr_id).
274 FIXME: We should replace blind conversion of id's type with derivation
275 of the optimal type when we get the corresponding isl support. Blindly
276 converting type sizes may be problematic when we switch to smaller
279 tree
translate_isl_ast_to_gimple::
280 gcc_expression_from_isl_ast_expr_id (tree type
,
281 __isl_take isl_ast_expr
*expr_id
,
284 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
285 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
286 std::map
<isl_id
*, tree
>::iterator res
;
287 res
= ip
.find (tmp_isl_id
);
288 isl_id_free (tmp_isl_id
);
289 gcc_assert (res
!= ip
.end () &&
290 "Could not map isl_id to tree expression");
291 isl_ast_expr_free (expr_id
);
292 tree t
= res
->second
;
293 tree
*val
= region
->parameter_rename_map
->get(t
);
297 return fold_convert (type
, *val
);
300 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
303 tree
translate_isl_ast_to_gimple::
304 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
306 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
307 isl_val
*val
= isl_ast_expr_get_val (expr
);
308 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
309 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
311 if (isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
315 widest_int wi
= widest_int::from_array (chunks
, n
, true);
316 if (isl_val_is_neg (val
))
318 res
= wide_int_to_tree (type
, wi
);
321 isl_ast_expr_free (expr
);
325 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
328 tree
translate_isl_ast_to_gimple::
329 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
331 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
332 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
333 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
334 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
336 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
337 isl_ast_expr_free (expr
);
339 if (codegen_error_p ())
345 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
348 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
351 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
354 /* As isl operates on arbitrary precision numbers, we may end up with
355 division by 2^64 that is folded to 0. */
356 if (integer_zerop (tree_rhs_expr
))
358 set_codegen_error ();
361 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
363 case isl_ast_op_pdiv_q
:
364 /* As isl operates on arbitrary precision numbers, we may end up with
365 division by 2^64 that is folded to 0. */
366 if (integer_zerop (tree_rhs_expr
))
368 set_codegen_error ();
371 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
373 case isl_ast_op_zdiv_r
:
374 case isl_ast_op_pdiv_r
:
375 /* As isl operates on arbitrary precision numbers, we may end up with
376 division by 2^64 that is folded to 0. */
377 if (integer_zerop (tree_rhs_expr
))
379 set_codegen_error ();
382 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
384 case isl_ast_op_fdiv_q
:
385 /* As isl operates on arbitrary precision numbers, we may end up with
386 division by 2^64 that is folded to 0. */
387 if (integer_zerop (tree_rhs_expr
))
389 set_codegen_error ();
392 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
395 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
396 tree_lhs_expr
, tree_rhs_expr
);
399 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
402 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
405 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
408 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
411 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
414 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
421 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
424 tree
translate_isl_ast_to_gimple::
425 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
427 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
428 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
429 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
430 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
431 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
432 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
433 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
434 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
435 isl_ast_expr_free (expr
);
437 if (codegen_error_p ())
440 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
443 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
446 tree
translate_isl_ast_to_gimple::
447 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
449 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
450 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
451 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
452 isl_ast_expr_free (expr
);
453 return codegen_error_p () ? NULL_TREE
454 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
457 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
458 to a GCC expression tree of type TYPE. */
460 tree
translate_isl_ast_to_gimple::
461 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
463 enum tree_code op_code
;
464 switch (isl_ast_expr_get_op_type (expr
))
477 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
478 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
480 if (codegen_error_p ())
482 isl_ast_expr_free (expr
);
487 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
489 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
490 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
492 if (codegen_error_p ())
494 isl_ast_expr_free (expr
);
498 res
= fold_build2 (op_code
, type
, res
, t
);
500 isl_ast_expr_free (expr
);
504 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
507 tree
translate_isl_ast_to_gimple::
508 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
511 if (codegen_error_p ())
513 isl_ast_expr_free (expr
);
517 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
518 switch (isl_ast_expr_get_op_type (expr
))
520 /* These isl ast expressions are not supported yet. */
521 case isl_ast_op_error
:
522 case isl_ast_op_call
:
523 case isl_ast_op_and_then
:
524 case isl_ast_op_or_else
:
529 return nary_op_to_tree (type
, expr
, ip
);
535 case isl_ast_op_pdiv_q
:
536 case isl_ast_op_pdiv_r
:
537 case isl_ast_op_fdiv_q
:
538 case isl_ast_op_zdiv_r
:
546 return binary_op_to_tree (type
, expr
, ip
);
548 case isl_ast_op_minus
:
549 return unary_op_to_tree (type
, expr
, ip
);
551 case isl_ast_op_cond
:
552 case isl_ast_op_select
:
553 return ternary_op_to_tree (type
, expr
, ip
);
562 /* Converts an isl AST expression E back to a GCC expression tree of
565 tree
translate_isl_ast_to_gimple::
566 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
569 if (codegen_error_p ())
571 isl_ast_expr_free (expr
);
575 switch (isl_ast_expr_get_type (expr
))
577 case isl_ast_expr_id
:
578 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
580 case isl_ast_expr_int
:
581 return gcc_expression_from_isl_expr_int (type
, expr
);
583 case isl_ast_expr_op
:
584 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
593 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
594 induction variable for the new LOOP. New LOOP is attached to CFG
595 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
596 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
597 isl's scattering name to the induction variable created for the
598 loop of STMT. The new induction variable is inserted in the NEWIVS
599 vector and is of type TYPE. */
601 struct loop
*translate_isl_ast_to_gimple::
602 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
603 loop_p outer
, tree type
, tree lb
, tree ub
,
606 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
607 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
609 /* To fail code generation, we generate wrong code until we discard it. */
610 if (codegen_error_p ())
611 stride
= integer_zero_node
;
613 tree ivvar
= create_tmp_var (type
, "graphite_IV");
614 tree iv
, iv_after_increment
;
615 loop_p loop
= create_empty_loop_on_edge
616 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
617 outer
? outer
: entry_edge
->src
->loop_father
);
619 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
620 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
621 std::map
<isl_id
*, tree
>::iterator res
;
624 isl_id_free (res
->first
);
626 isl_ast_expr_free (for_iterator
);
630 /* Create the loop for a isl_ast_node_for.
632 - NEXT_E is the edge where new generated code should be attached. */
634 edge
translate_isl_ast_to_gimple::
635 translate_isl_ast_for_loop (loop_p context_loop
,
636 __isl_keep isl_ast_node
*node_for
, edge next_e
,
637 tree type
, tree lb
, tree ub
,
640 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
641 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
643 edge last_e
= single_exit (loop
);
644 edge to_body
= single_succ_edge (loop
->header
);
645 basic_block after
= to_body
->dest
;
647 /* Translate the body of the loop. */
648 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
649 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
650 isl_ast_node_free (for_body
);
652 /* Early return if we failed to translate loop body. */
653 if (!next_e
|| codegen_error_p ())
656 if (next_e
->dest
!= after
)
657 redirect_edge_succ_nodup (next_e
, after
);
658 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
660 if (flag_loop_parallelize_all
)
662 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
664 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
665 loop
->can_be_parallel
= for_info
->is_parallelizable
;
673 /* We use this function to get the upper bound because of the form,
674 which is used by isl to represent loops:
676 for (iterator = init; cond; iterator += inc)
684 The loop condition is an arbitrary expression, which contains the
685 current loop iterator.
687 (e.g. iterator + 3 < B && C > iterator + A)
689 We have to know the upper bound of the iterator to generate a loop
690 in Gimple form. It can be obtained from the special representation
691 of the loop condition, which is generated by isl,
692 if the ast_build_atomic_upper_bound option is set. In this case,
693 isl generates a loop condition that consists of the current loop
694 iterator, + an operator (< or <=) and an expression not involving
695 the iterator, which is processed and returned by this function.
697 (e.g iterator <= upper-bound-expression-without-iterator) */
699 static __isl_give isl_ast_expr
*
700 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
702 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
703 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
704 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
706 switch (isl_ast_expr_get_op_type (for_cond
))
709 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
714 /* (iterator < ub) => (iterator <= ub - 1). */
716 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
717 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
718 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
725 isl_ast_expr_free (for_cond
);
729 /* Translates an isl_ast_node_for to Gimple. */
731 edge
translate_isl_ast_to_gimple::
732 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
733 edge next_e
, ivs_params
&ip
)
735 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
737 = build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
739 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
740 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
741 /* To fail code generation, we generate wrong code until we discard it. */
742 if (codegen_error_p ())
743 lb
= integer_zero_node
;
745 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
746 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
747 /* To fail code generation, we generate wrong code until we discard it. */
748 if (codegen_error_p ())
749 ub
= integer_zero_node
;
751 edge last_e
= single_succ_edge (split_edge (next_e
));
752 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
757 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
758 variables of the loops around GBB in SESE.
760 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
761 chrec, we could consider using a map<int, tree> that maps loop ids to the
762 corresponding tree expressions. */
764 void translate_isl_ast_to_gimple::
765 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
766 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
769 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
770 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
772 isl_ast_expr
*arg_expr
;
773 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
775 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
777 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
778 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
780 /* To fail code generation, we generate wrong code until we discard it. */
781 if (codegen_error_p ())
782 t
= integer_zero_node
;
784 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 2);
785 /* Record sth only for real loops. */
786 if (loop_in_sese_p (old_loop
, region
))
787 iv_map
[old_loop
->num
] = t
;
791 /* Translates an isl_ast_node_user to Gimple.
793 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
795 edge
translate_isl_ast_to_gimple::
796 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
797 edge next_e
, ivs_params
&ip
)
799 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
801 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
802 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
803 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
805 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
806 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
809 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
811 isl_ast_expr_free (name_expr
);
812 isl_id_free (name_id
);
814 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
815 "The entry block should not even appear within a scop");
817 const int nb_loops
= number_of_loops (cfun
);
819 iv_map
.create (nb_loops
);
820 iv_map
.safe_grow_cleared (nb_loops
);
822 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
823 isl_ast_expr_free (user_expr
);
825 basic_block old_bb
= GBB_BB (gbb
);
829 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
830 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
831 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
835 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
839 if (codegen_error_p ())
844 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
845 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
851 /* Translates an isl_ast_node_block to Gimple. */
853 edge
translate_isl_ast_to_gimple::
854 translate_isl_ast_node_block (loop_p context_loop
,
855 __isl_keep isl_ast_node
*node
,
856 edge next_e
, ivs_params
&ip
)
858 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
859 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
861 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
863 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
864 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
865 isl_ast_node_free (tmp_node
);
867 isl_ast_node_list_free (node_list
);
871 /* Creates a new if region corresponding to isl's cond. */
873 edge
translate_isl_ast_to_gimple::
874 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
878 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
879 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
881 /* To fail code generation, we generate wrong code until we discard it. */
882 if (codegen_error_p ())
883 cond_expr
= integer_zero_node
;
885 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
889 /* Translates an isl_ast_node_if to Gimple. */
891 edge
translate_isl_ast_to_gimple::
892 translate_isl_ast_node_if (loop_p context_loop
,
893 __isl_keep isl_ast_node
*node
,
894 edge next_e
, ivs_params
&ip
)
896 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
897 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
898 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
899 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
900 merge_points
.safe_push (last_e
);
902 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
903 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
904 isl_ast_node_free (then_node
);
906 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
907 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
908 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
909 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
911 isl_ast_node_free (else_node
);
915 /* Translates an isl AST node NODE to GCC representation in the
916 context of a SESE. */
918 edge
translate_isl_ast_to_gimple::
919 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
920 edge next_e
, ivs_params
&ip
)
922 if (codegen_error_p ())
925 switch (isl_ast_node_get_type (node
))
927 case isl_ast_node_error
:
930 case isl_ast_node_for
:
931 return translate_isl_ast_node_for (context_loop
, node
,
934 case isl_ast_node_if
:
935 return translate_isl_ast_node_if (context_loop
, node
,
938 case isl_ast_node_user
:
939 return translate_isl_ast_node_user (node
, next_e
, ip
);
941 case isl_ast_node_block
:
942 return translate_isl_ast_node_block (context_loop
, node
,
945 case isl_ast_node_mark
:
947 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
948 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
949 isl_ast_node_free (n
);
958 /* Return true when BB contains loop close phi nodes. A loop close phi node is
959 at the exit of loop which takes one argument that is the last value of the
960 variable being used out of the loop. */
963 bb_contains_loop_close_phi_nodes (basic_block bb
)
965 return single_pred_p (bb
)
966 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
969 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
970 header containing phi nodes which has one init-edge and one back-edge. */
973 bb_contains_loop_phi_nodes (basic_block bb
)
975 if (EDGE_COUNT (bb
->preds
) != 2)
978 unsigned depth
= loop_depth (bb
->loop_father
);
980 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
982 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
983 || depth
> loop_depth (preds
[1]->src
->loop_father
))
986 /* When one of the edges correspond to the same loop father and other
988 if (bb
->loop_father
!= preds
[0]->src
->loop_father
989 && bb
->loop_father
== preds
[1]->src
->loop_father
)
992 if (bb
->loop_father
!= preds
[1]->src
->loop_father
993 && bb
->loop_father
== preds
[0]->src
->loop_father
)
999 /* Check if USE is defined in a basic block from where the definition of USE can
1000 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1003 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1005 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1008 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1009 if (bb_contains_loop_close_phi_nodes (bb
))
1012 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1013 basic_block def_bb
= gimple_bb (def
);
1015 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1018 /* Return the number of phi nodes in BB. */
1021 number_of_phi_nodes (basic_block bb
)
1024 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1030 /* Returns true if BB uses name in one of its PHIs. */
1033 phi_uses_name (basic_block bb
, tree name
)
1035 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1038 gphi
*phi
= psi
.phi ();
1039 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1041 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1042 if (use_arg
== name
)
1049 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1050 definition should flow into use, and the use should respect the loop-closed
1053 bool translate_isl_ast_to_gimple::
1054 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1055 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1057 if (SSA_NAME_IS_DEFAULT_DEF (rename
))
1060 /* The def of the rename must either dominate the uses or come from a
1061 back-edge. Also the def must respect the loop closed ssa form. */
1062 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1066 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1067 print_generic_expr (dump_file
, rename
);
1068 fprintf (dump_file
, "\n");
1073 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1076 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1078 /* The loop-header dominates the loop-body. */
1079 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1082 /* RENAME would be used in loop-phi. */
1083 gcc_assert (number_of_phi_nodes (use_bb
));
1085 /* For definitions coming from back edges, we should check that
1086 old_name is used in a loop PHI node.
1087 FIXME: Verify if this is true. */
1088 if (phi_uses_name (old_bb
, old_name
))
1094 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1095 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1097 tree
translate_isl_ast_to_gimple::
1098 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1099 phi_node_kind phi_kind
) const
1101 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1102 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1104 if (!renames
|| renames
->is_empty ())
1107 if (1 == renames
->length ())
1109 tree rename
= (*renames
)[0];
1110 if (TREE_CODE (rename
) == SSA_NAME
)
1112 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1113 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1114 && (phi_kind
== close_phi
1116 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1121 if (is_constant (rename
))
1127 /* More than one renames corresponding to the old_name. Find the rename for
1128 which the definition flows into usage at new_bb. */
1130 tree t1
= NULL_TREE
, t2
;
1131 basic_block t1_bb
= NULL
;
1132 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1134 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1136 /* Defined in the same basic block as used. */
1137 if (t2_bb
== new_bb
)
1140 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1141 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1144 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1147 /* Compute the nearest dominator. */
1148 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1158 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1159 When OLD_NAME and EXPR are the same we assert. */
1161 void translate_isl_ast_to_gimple::
1162 set_rename (tree old_name
, tree expr
)
1166 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1167 print_generic_expr (dump_file
, old_name
);
1168 fprintf (dump_file
, ", new_name = ");
1169 print_generic_expr (dump_file
, expr
);
1170 fprintf (dump_file
, "\n");
1173 if (old_name
== expr
)
1176 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1179 renames
->safe_push (expr
);
1185 region
->rename_map
->put (old_name
, r
);
1190 /* For a parameter of a scop we don't want to rename it. */
1191 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1193 region
->parameter_rename_map
->put(old_name
, expr
);
1196 /* Return an iterator to the instructions comes last in the execution order.
1197 Either GSI1 and GSI2 should belong to the same basic block or one of their
1198 respective basic blocks should dominate the other. */
1200 gimple_stmt_iterator
1201 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1203 basic_block bb1
= gsi_bb (gsi1
);
1204 basic_block bb2
= gsi_bb (gsi2
);
1206 /* Find the iterator which is the latest. */
1209 gimple
*stmt1
= gsi_stmt (gsi1
);
1210 gimple
*stmt2
= gsi_stmt (gsi2
);
1212 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1214 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1215 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1217 if (is_phi1
!= is_phi2
)
1218 return is_phi1
? gsi2
: gsi1
;
1221 /* For empty basic blocks gsis point to the end of the sequence. Since
1222 there is no operator== defined for gimple_stmt_iterator and for gsis
1223 not pointing to a valid statement gsi_next would assert. */
1224 gimple_stmt_iterator gsi
= gsi1
;
1226 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1229 } while (!gsi_end_p (gsi
));
1234 /* Find the basic block closest to the basic block which defines stmt. */
1235 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1238 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1242 /* Insert each statement from SEQ at its earliest insertion p. */
1244 void translate_isl_ast_to_gimple::
1245 gsi_insert_earliest (gimple_seq seq
)
1247 update_modified_stmts (seq
);
1248 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1249 basic_block begin_bb
= get_entry_bb (codegen_region
);
1251 /* Inserting the gimple statements in a vector because gimple_seq behave
1252 in strage ways when inserting the stmts from it into different basic
1253 blocks one at a time. */
1254 auto_vec
<gimple
*, 3> stmts
;
1255 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1257 stmts
.safe_push (gsi_stmt (gsi
));
1261 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1263 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1264 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1266 use_operand_p use_p
;
1267 ssa_op_iter op_iter
;
1268 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1270 /* Iterator to the current def of use_p. For function parameters or
1271 anything where def is not found, insert at the beginning of the
1272 generated region. */
1273 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1275 tree op
= USE_FROM_PTR (use_p
);
1276 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1277 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1278 gsi_stmt
= gsi_for_stmt (stmt
);
1280 /* For region parameters, insert at the beginning of the generated
1282 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1283 gsi_stmt
= gsi_def_stmt
;
1285 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1288 if (!gsi_stmt (gsi_def_stmt
))
1290 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1291 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1293 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1295 gimple_stmt_iterator bsi
1296 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1297 /* Insert right after the PHI statements. */
1298 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1301 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1305 fprintf (dump_file
, "[codegen] inserting statement: ");
1306 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1307 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1312 /* Collect all the operands of NEW_EXPR by recursively visiting each
1315 void translate_isl_ast_to_gimple::
1316 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1318 if (new_expr
== NULL_TREE
)
1321 /* Rename all uses in new_expr. */
1322 if (TREE_CODE (new_expr
) == SSA_NAME
)
1324 vec_ssa
->safe_push (new_expr
);
1328 /* Iterate over SSA_NAMES in NEW_EXPR. */
1329 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1331 tree op
= TREE_OPERAND (new_expr
, i
);
1332 collect_all_ssa_names (op
, vec_ssa
);
1336 /* This is abridged version of the function copied from:
1337 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1340 substitute_ssa_name (tree exp
, tree f
, tree r
)
1342 enum tree_code code
= TREE_CODE (exp
);
1343 tree op0
, op1
, op2
, op3
;
1346 /* We handle TREE_LIST and COMPONENT_REF separately. */
1347 if (code
== TREE_LIST
)
1349 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1350 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1351 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1354 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1356 else if (code
== COMPONENT_REF
)
1360 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1361 and it is the right field, replace it with R. */
1362 for (inner
= TREE_OPERAND (exp
, 0);
1363 REFERENCE_CLASS_P (inner
);
1364 inner
= TREE_OPERAND (inner
, 0))
1368 op1
= TREE_OPERAND (exp
, 1);
1370 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1373 /* If this expression hasn't been completed let, leave it alone. */
1374 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1377 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1378 if (op0
== TREE_OPERAND (exp
, 0))
1382 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1385 switch (TREE_CODE_CLASS (code
))
1390 case tcc_declaration
:
1396 case tcc_expression
:
1402 case tcc_exceptional
:
1405 case tcc_comparison
:
1407 switch (TREE_CODE_LENGTH (code
))
1415 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1416 if (op0
== TREE_OPERAND (exp
, 0))
1419 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1423 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1424 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1426 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1429 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1433 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1434 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1435 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1437 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1438 && op2
== TREE_OPERAND (exp
, 2))
1441 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1445 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1446 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1447 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1448 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1450 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1451 && op2
== TREE_OPERAND (exp
, 2)
1452 && op3
== TREE_OPERAND (exp
, 3))
1456 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1469 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1471 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1472 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1477 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1479 tree
translate_isl_ast_to_gimple::
1480 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1482 auto_vec
<tree
, 2> ssa_names
;
1483 collect_all_ssa_names (new_expr
, &ssa_names
);
1486 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1487 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1488 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1493 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1494 scalar evolution around LOOP. */
1496 tree
translate_isl_ast_to_gimple::
1497 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1498 basic_block new_bb
, basic_block old_bb
,
1501 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1503 /* At this point we should know the exact scev for each
1504 scalar SSA_NAME used in the scop: all the other scalar
1505 SSA_NAMEs should have been translated out of SSA using
1506 arrays with one element. */
1508 if (chrec_contains_undetermined (scev
))
1510 set_codegen_error ();
1511 return build_zero_cst (TREE_TYPE (old_name
));
1514 new_expr
= chrec_apply_map (scev
, iv_map
);
1516 /* The apply should produce an expression tree containing
1517 the uses of the new induction variables. We should be
1518 able to use new_expr instead of the old_name in the newly
1519 generated loop nest. */
1520 if (chrec_contains_undetermined (new_expr
)
1521 || tree_contains_chrecs (new_expr
, NULL
))
1523 set_codegen_error ();
1524 return build_zero_cst (TREE_TYPE (old_name
));
1527 if (TREE_CODE (new_expr
) == SSA_NAME
)
1529 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1530 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1532 set_codegen_error ();
1533 return build_zero_cst (TREE_TYPE (old_name
));
1537 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1539 /* We check all the operands and all of them should dominate the use at
1541 auto_vec
<tree
, 2> new_ssa_names
;
1542 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1545 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1547 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1549 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1550 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1552 set_codegen_error ();
1553 return build_zero_cst (TREE_TYPE (old_name
));
1558 /* Replace the old_name with the new_expr. */
1559 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1563 /* Renames the scalar uses of the statement COPY, using the
1564 substitution map RENAME_MAP, inserting the gimplification code at
1565 GSI_TGT, for the translation REGION, with the original copied
1566 statement in LOOP, and using the induction variable renaming map
1567 IV_MAP. Returns true when something has been renamed. */
1569 bool translate_isl_ast_to_gimple::
1570 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1571 loop_p loop
, vec
<tree
> iv_map
)
1573 bool changed
= false;
1575 if (is_gimple_debug (copy
))
1577 if (gimple_debug_bind_p (copy
))
1578 gimple_debug_bind_reset_value (copy
);
1579 else if (gimple_debug_source_bind_p (copy
))
1589 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1590 print_gimple_stmt (dump_file
, copy
, 0);
1593 use_operand_p use_p
;
1594 ssa_op_iter op_iter
;
1595 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1597 tree old_name
= USE_FROM_PTR (use_p
);
1601 fprintf (dump_file
, "[codegen] renaming old_name = ");
1602 print_generic_expr (dump_file
, old_name
);
1603 fprintf (dump_file
, "\n");
1606 if (TREE_CODE (old_name
) != SSA_NAME
1607 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1611 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1612 old_bb
, unknown_phi
);
1616 tree type_old_name
= TREE_TYPE (old_name
);
1617 tree type_new_expr
= TREE_TYPE (new_expr
);
1621 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1622 print_generic_expr (dump_file
, new_expr
);
1623 fprintf (dump_file
, "\n");
1626 if (type_old_name
!= type_new_expr
1627 || TREE_CODE (new_expr
) != SSA_NAME
)
1629 tree var
= create_tmp_var (type_old_name
, "var");
1631 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1632 new_expr
= fold_convert (type_old_name
, new_expr
);
1635 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1636 gsi_insert_earliest (stmts
);
1639 replace_exp (use_p
, new_expr
);
1644 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1646 if (!new_expr
|| codegen_error_p ())
1651 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1652 print_generic_expr (dump_file
, new_expr
);
1653 fprintf (dump_file
, "\n");
1656 gsi_insert_earliest (stmts
);
1657 replace_exp (use_p
, new_expr
);
1659 if (TREE_CODE (new_expr
) == INTEGER_CST
1660 && is_gimple_assign (copy
))
1662 tree rhs
= gimple_assign_rhs1 (copy
);
1664 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1665 recompute_tree_invariant_for_addr_expr (rhs
);
1668 set_rename (old_name
, new_expr
);
1674 /* Returns a basic block that could correspond to where a constant was defined
1675 in the original code. In the original code OLD_BB had the definition, we
1676 need to find which basic block out of the copies of old_bb, in the new
1677 region, should a definition correspond to if it has to reach BB. */
1679 basic_block
translate_isl_ast_to_gimple::
1680 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1682 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1684 if (!bbs
|| bbs
->is_empty ())
1687 if (1 == bbs
->length ())
1691 basic_block b1
= NULL
, b2
;
1692 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1697 /* BB and B2 are in two unrelated if-clauses. */
1698 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1701 /* Compute the nearest dominator. */
1702 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1709 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1710 determines the kind of phi node. */
1712 tree
translate_isl_ast_to_gimple::
1713 get_new_name (basic_block new_bb
, tree op
,
1714 basic_block old_bb
, phi_node_kind phi_kind
) const
1716 /* For constants the names are the same. */
1717 if (TREE_CODE (op
) != SSA_NAME
)
1720 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1723 /* Return a debug location for OP. */
1728 location_t loc
= UNKNOWN_LOCATION
;
1730 if (TREE_CODE (op
) == SSA_NAME
)
1731 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1735 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1736 the init edge (from outside the loop) and the second one is the back edge
1737 from the same loop. */
1739 std::pair
<edge
, edge
>
1740 get_edges (basic_block bb
)
1742 std::pair
<edge
, edge
> edges
;
1745 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1746 if (bb
->loop_father
!= e
->src
->loop_father
)
1753 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1754 must be found unless they can be POSTPONEd for later. */
1756 bool translate_isl_ast_to_gimple::
1757 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1758 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1761 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1763 basic_block new_bb
= gimple_bb (new_phi
);
1764 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1767 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1768 e
= ibp_new_bb
.first
;
1770 e
= ibp_new_bb
.second
;
1772 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1773 tree new_name
= get_new_name (new_bb
, old_name
,
1774 gimple_bb (old_phi
), loop_phi
);
1777 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1781 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1782 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1783 /* If the phi arg was a function arg, or wasn't defined, just use the
1785 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1788 /* Postpone code gen for later for those back-edges we don't have the
1790 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1792 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1795 /* Either we should add the arg to phi or, we should postpone. */
1801 /* Copy loop phi nodes from BB to NEW_BB. */
1803 bool translate_isl_ast_to_gimple::
1804 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1807 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1810 /* Loop phi nodes should have only two arguments. */
1811 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1813 /* First edge is the init edge and second is the back edge. */
1814 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1816 /* First edge is the init edge and second is the back edge. */
1817 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1819 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1822 gphi
*phi
= psi
.phi ();
1823 tree res
= gimple_phi_result (phi
);
1824 if (virtual_operand_p (res
))
1826 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1829 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
1830 tree new_res
= create_new_def_for (res
, new_phi
,
1831 gimple_phi_result_ptr (new_phi
));
1832 set_rename (res
, new_res
);
1833 if (!copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
, ibp_new_bb
, true))
1834 set_codegen_error ();
1835 update_stmt (new_phi
);
1839 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1840 print_gimple_stmt (dump_file
, new_phi
, 0);
1847 /* Return the init value of PHI, the value coming from outside the loop. */
1850 get_loop_init_value (gphi
*phi
)
1853 loop_p loop
= gimple_bb (phi
)->loop_father
;
1857 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1858 if (e
->src
->loop_father
!= loop
)
1859 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1864 /* Find the init value (the value which comes from outside the loop), of one of
1865 the operands of DEF which is defined by a loop phi. */
1868 find_init_value (gimple
*def
)
1870 if (gimple_code (def
) == GIMPLE_PHI
)
1871 return get_loop_init_value (as_a
<gphi
*> (def
));
1873 if (gimple_vuse (def
))
1877 use_operand_p use_p
;
1878 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1880 tree use
= USE_FROM_PTR (use_p
);
1881 if (TREE_CODE (use
) == SSA_NAME
)
1883 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1891 /* Return the init value, the value coming from outside the loop. */
1894 find_init_value_close_phi (gphi
*phi
)
1896 gcc_assert (gimple_phi_num_args (phi
) == 1);
1897 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1898 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1899 return find_init_value (def
);
1903 tree
translate_isl_ast_to_gimple::
1904 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1905 gimple
*old_close_phi
)
1907 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1908 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1909 basic_block bb
= gimple_bb (stmt
);
1910 if (!bb_in_sese_p (bb
, codegen_region
))
1911 return last_merge_name
;
1913 loop_p loop
= bb
->loop_father
;
1914 if (!loop_in_sese_p (loop
, codegen_region
))
1915 return last_merge_name
;
1917 edge e
= single_exit (loop
);
1919 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1920 return last_merge_name
;
1922 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1923 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1926 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
1927 bb
= split_edge (e
);
1929 gphi
*close_phi
= create_phi_node (NULL_TREE
, bb
);
1930 tree res
= create_new_def_for (last_merge_name
, close_phi
,
1931 gimple_phi_result_ptr (close_phi
));
1932 set_rename (old_close_phi_name
, res
);
1933 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
1934 last_merge_name
= res
;
1936 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
1939 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
1940 the close phi node PHI. */
1942 bool translate_isl_ast_to_gimple::
1943 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
1946 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1947 basic_block default_value_bb
= get_entry_bb (codegen_region
);
1948 if (SSA_NAME
== TREE_CODE (default_value
))
1950 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
1951 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
1953 default_value_bb
= gimple_bb (stmt
);
1956 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
1958 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1959 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
1960 tree last_merge_name
= new_close_phi_name
;
1961 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1965 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
1967 basic_block new_merge_bb
= merge_e
->src
;
1968 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
1971 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
1974 gphi
*merge_phi
= create_phi_node (NULL_TREE
, new_merge_bb
);
1975 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
1976 gimple_phi_result_ptr (merge_phi
));
1977 set_rename (old_close_phi_name
, merge_res
);
1979 edge from_loop
= NULL
, from_default_value
= NULL
;
1982 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
1983 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
1986 from_default_value
= e
;
1988 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
1989 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
1990 is contained in another condition. */
1991 if (!from_default_value
|| !from_loop
)
1994 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
1995 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
1999 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2000 print_gimple_stmt (dump_file
, merge_phi
, 0);
2003 update_stmt (merge_phi
);
2004 last_merge_name
= merge_res
;
2010 /* Copy all the loop-close phi args from BB to NEW_BB. */
2012 bool translate_isl_ast_to_gimple::
2013 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
2014 vec
<tree
> iv_map
, bool postpone
)
2016 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2019 gphi
*old_close_phi
= psi
.phi ();
2020 tree res
= gimple_phi_result (old_close_phi
);
2021 if (virtual_operand_p (res
))
2024 gphi
*new_close_phi
= create_phi_node (NULL_TREE
, new_bb
);
2025 tree new_res
= create_new_def_for (res
, new_close_phi
,
2026 gimple_phi_result_ptr (new_close_phi
));
2027 set_rename (res
, new_res
);
2029 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2031 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2034 new_name
= get_rename_from_scev (old_name
, &stmts
,
2035 old_bb
->loop_father
,
2036 new_bb
, old_bb
, iv_map
);
2037 if (! codegen_error_p ())
2038 gsi_insert_earliest (stmts
);
2041 new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2043 /* Predecessor basic blocks of a loop close phi should have been code
2044 generated before. FIXME: This is fixable by merging PHIs from inner
2045 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2046 if (!new_name
|| codegen_error_p ())
2049 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2050 get_loc (old_name
));
2053 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2054 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2057 update_stmt (new_close_phi
);
2059 /* When there is no loop guard around this codegenerated loop, there is no
2060 need to collect the close-phi arg. */
2061 if (merge_points
.is_empty ())
2064 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2065 tree default_value
= find_init_value_close_phi (new_close_phi
);
2067 /* A close phi must come from a loop-phi having a default value. */
2073 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2077 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2078 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2083 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2091 /* Copy loop close phi nodes from BB to NEW_BB. */
2093 bool translate_isl_ast_to_gimple::
2094 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
2098 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2100 /* Loop close phi nodes should have only one argument. */
2101 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2103 return copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, true);
2107 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2108 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2109 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2110 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2113 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2114 In this case DOMINATING_PRED = NULL.
2116 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2118 Returns true on successful copy of the args, false otherwise. */
2120 bool translate_isl_ast_to_gimple::
2121 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2122 edge old_bb_dominating_edge
,
2123 edge old_bb_non_dominating_edge
,
2124 gphi
*phi
, gphi
*new_phi
,
2127 basic_block def_pred
[2] = { NULL
, NULL
};
2128 int not_found_bb_index
= -1;
2129 for (int i
= 0; i
< 2; i
++)
2131 /* If the corresponding def_bb could not be found the entry will be
2133 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2134 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2135 gimple_phi_arg_edge (phi
, i
)->src
);
2136 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2137 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2141 /* When non are available bail out. */
2142 if (not_found_bb_index
!= -1)
2144 not_found_bb_index
= i
;
2148 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2149 if (old_bb_dominating_edge
)
2151 if (not_found_bb_index
!= -1)
2154 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2155 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2156 vec
<basic_block
> *bbs
2157 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2159 /* Could not find a mapping. */
2163 basic_block new_pred
= NULL
;
2166 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2168 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2170 /* FIXME: If we have already found new_pred then we have to
2171 disambiguate, bail out for now. */
2174 new_pred
= new_pred1
;
2176 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2178 /* FIXME: If we have already found new_pred then we have to either
2179 it dominates both or we have to disambiguate, bail out. */
2182 new_pred
= new_pred2
;
2189 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2190 gcc_assert (new_non_dominating_edge
);
2191 /* FIXME: Validate each args just like in loop-phis. */
2192 /* By the process of elimination we first insert insert phi-edge for
2193 non-dominating pred which is computed above and then we insert the
2195 int inserted_edge
= 0;
2196 for (; inserted_edge
< 2; inserted_edge
++)
2198 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2199 if (new_non_dominating_edge
== new_bb_pred_edge
)
2201 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2202 new_non_dominating_edge
,
2203 get_loc (old_phi_args
[inserted_edge
]));
2207 if (inserted_edge
== 2)
2210 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2212 edge new_dominating_edge
= NULL
;
2213 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2215 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2216 if (e
!= new_non_dominating_edge
)
2218 new_dominating_edge
= e
;
2219 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2220 new_dominating_edge
,
2221 get_loc (old_phi_args
[inserted_edge
]));
2225 gcc_assert (new_dominating_edge
);
2229 /* Classic diamond structure: both edges are non-dominating. We need to
2230 find one unique edge then the other can be found be elimination. If
2231 any definition (def_pred) dominates both the preds of new_bb then we
2232 bail out. Entries of def_pred maybe NULL, in that case we must
2233 uniquely find pred with help of only one entry. */
2234 edge new_e
[2] = { NULL
, NULL
};
2235 for (int i
= 0; i
< 2; i
++)
2239 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2241 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2244 /* We do not know how to handle the case when def_pred
2245 dominates more than a predecessor. */
2251 gcc_assert (new_e
[0] || new_e
[1]);
2253 /* Find the other edge by process of elimination. */
2254 if (not_found_bb_index
!= -1)
2256 gcc_assert (!new_e
[not_found_bb_index
]);
2257 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2260 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2262 if (new_e
[found_bb_index
] == e
)
2264 new_e
[not_found_bb_index
] = e
;
2268 /* Add edges to phi args. */
2269 for (int i
= 0; i
< 2; i
++)
2270 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2271 get_loc (old_phi_args
[i
]));
2277 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2278 region. If postpone is true and it isn't possible to copy any arg of PHI,
2279 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2280 Returns false if the copying was unsuccessful. */
2282 bool translate_isl_ast_to_gimple::
2283 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2286 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2287 gcc_assert (2 == gimple_phi_num_args (phi
));
2289 basic_block new_bb
= gimple_bb (new_phi
);
2290 loop_p loop
= gimple_bb (phi
)->loop_father
;
2292 basic_block old_bb
= gimple_bb (phi
);
2293 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2297 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2298 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2299 old_bb_non_dominating_edge
= e
;
2301 old_bb_dominating_edge
= e
;
2303 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2304 old_bb_non_dominating_edge
->src
));
2306 tree new_phi_args
[2];
2307 tree old_phi_args
[2];
2309 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2311 tree old_name
= gimple_phi_arg_def (phi
, i
);
2312 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2313 old_phi_args
[i
] = old_name
;
2316 new_phi_args
[i
] = new_name
;
2320 /* If the phi-arg was a parameter. */
2321 if (vec_find (region
->params
, old_name
) != -1)
2323 new_phi_args
[i
] = old_name
;
2327 "[codegen] parameter argument to phi, new_expr: ");
2328 print_generic_expr (dump_file
, new_phi_args
[i
]);
2329 fprintf (dump_file
, "\n");
2334 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2335 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2336 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2342 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2343 if (is_gimple_reg (old_name
)
2344 && scev_analyzable_p (old_name
, region
->region
))
2347 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2348 new_bb
, old_bb
, iv_map
);
2349 if (codegen_error_p ())
2352 gcc_assert (new_expr
);
2356 "[codegen] scev analyzeable, new_expr: ");
2357 print_generic_expr (dump_file
, new_expr
);
2358 fprintf (dump_file
, "\n");
2360 gsi_insert_earliest (stmts
);
2361 new_phi_args
[i
] = new_expr
;
2365 /* Postpone code gen for later for back-edges. */
2366 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2370 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2371 print_gimple_stmt (dump_file
, new_phi
, 0);
2374 new_phi_args
[i
] = NULL_TREE
;
2378 /* Either we should add the arg to phi or, we should postpone. */
2382 /* If none of the args have been determined in the first stage then wait until
2384 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2387 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2388 old_bb_dominating_edge
,
2389 old_bb_non_dominating_edge
,
2390 phi
, new_phi
, new_bb
);
2393 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2394 containing phi nodes coming from two predecessors, and none of them are back
2397 bool translate_isl_ast_to_gimple::
2398 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2401 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2403 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2404 if (EDGE_COUNT (bb
->preds
) != 2)
2408 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2411 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2414 gphi
*phi
= psi
.phi ();
2415 tree res
= gimple_phi_result (phi
);
2416 if (virtual_operand_p (res
))
2419 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
2420 tree new_res
= create_new_def_for (res
, new_phi
,
2421 gimple_phi_result_ptr (new_phi
));
2422 set_rename (res
, new_res
);
2424 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2427 update_stmt (new_phi
);
2433 /* Return true if STMT should be copied from region to the new code-generated
2434 region. LABELs, CONDITIONS, induction-variables and region parameters need
2438 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2440 /* Do not copy labels or conditions. */
2441 if (gimple_code (stmt
) == GIMPLE_LABEL
2442 || gimple_code (stmt
) == GIMPLE_COND
)
2446 /* Do not copy induction variables. */
2447 if (is_gimple_assign (stmt
)
2448 && (lhs
= gimple_assign_lhs (stmt
))
2449 && TREE_CODE (lhs
) == SSA_NAME
2450 && is_gimple_reg (lhs
)
2451 && scev_analyzable_p (lhs
, region
->region
))
2454 /* Do not copy parameters that have been generated in the header of the
2456 if (is_gimple_assign (stmt
)
2457 && (lhs
= gimple_assign_lhs (stmt
))
2458 && TREE_CODE (lhs
) == SSA_NAME
2459 && region
->parameter_rename_map
->get(lhs
))
2465 /* Create new names for all the definitions created by COPY and add replacement
2466 mappings for each new name. */
2468 void translate_isl_ast_to_gimple::
2469 set_rename_for_each_def (gimple
*stmt
)
2471 def_operand_p def_p
;
2472 ssa_op_iter op_iter
;
2473 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2475 tree old_name
= DEF_FROM_PTR (def_p
);
2476 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2477 set_rename (old_name
, new_name
);
2481 /* Duplicates the statements of basic block BB into basic block NEW_BB
2482 and compute the new induction variables according to the IV_MAP. */
2484 bool translate_isl_ast_to_gimple::
2485 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2488 /* Iterator poining to the place where new statement (s) will be inserted. */
2489 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2491 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2494 gimple
*stmt
= gsi_stmt (gsi
);
2495 if (!should_copy_to_new_region (stmt
, region
))
2498 /* Create a new copy of STMT and duplicate STMT's virtual
2500 gimple
*copy
= gimple_copy (stmt
);
2501 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2505 fprintf (dump_file
, "[codegen] inserting statement: ");
2506 print_gimple_stmt (dump_file
, copy
, 0);
2509 maybe_duplicate_eh_stmt (copy
, stmt
);
2510 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2512 /* Crete new names for each def in the copied stmt. */
2513 set_rename_for_each_def (copy
);
2515 loop_p loop
= bb
->loop_father
;
2516 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2518 fold_stmt_inplace (&gsi_tgt
);
2519 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2522 if (codegen_error_p ())
2525 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2527 use_operand_p use_p
;
2528 if (!is_gimple_debug (copy
))
2529 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2531 tree old_name
= USE_FROM_PTR (use_p
);
2533 if (TREE_CODE (old_name
) != SSA_NAME
2534 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2537 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2541 replace_exp (use_p
, *new_expr
);
2551 /* Given a basic block containing close-phi it returns the new basic block where
2552 to insert a copy of the close-phi nodes. All the uses in close phis should
2553 come from a single loop otherwise it returns NULL. */
2555 edge
translate_isl_ast_to_gimple::
2556 edge_for_new_close_phis (basic_block bb
)
2558 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2559 of close phi in the original code and then find the mapping of basic block
2560 defining that variable. If there are multiple close-phis and they are
2561 defined in different loops (in the original or in the new code) because of
2562 loop splitting, then we bail out. */
2563 loop_p new_loop
= NULL
;
2564 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2567 gphi
*phi
= psi
.phi ();
2568 tree name
= gimple_phi_arg_def (phi
, 0);
2569 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2571 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2572 if (!bbs
|| bbs
->length () != 1)
2573 /* This is one of the places which shows preserving original structure
2574 is not always possible, as we may need to insert close PHI for a loop
2575 where the latch does not have any mapping, or the mapping is
2580 new_loop
= (*bbs
)[0]->loop_father
;
2581 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2588 return single_exit (new_loop
);
2591 /* Copies BB and includes in the copied BB all the statements that can
2592 be reached following the use-def chains from the memory accesses,
2593 and returns the next edge following this new block. */
2595 edge
translate_isl_ast_to_gimple::
2596 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2598 int num_phis
= number_of_phi_nodes (bb
);
2599 basic_block new_bb
= NULL
;
2600 if (bb_contains_loop_close_phi_nodes (bb
))
2603 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2606 edge e
= edge_for_new_close_phis (bb
);
2609 set_codegen_error ();
2613 basic_block phi_bb
= e
->dest
;
2615 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2616 phi_bb
= split_edge (e
);
2618 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2619 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2621 if (!copy_loop_close_phi_nodes (bb
, phi_bb
, iv_map
))
2623 set_codegen_error ();
2630 new_bb
= split_edge (next_e
);
2634 new_bb
= split_edge (next_e
);
2635 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2637 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2639 /* At this point we are unable to codegenerate by still preserving the SSA
2640 structure because maybe the loop is completely unrolled and the PHIs
2641 and cross-bb scalar dependencies are untrackable w.r.t. the original
2642 code. See gfortran.dg/graphite/pr29832.f90. */
2643 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2645 set_codegen_error ();
2649 /* In case isl did some loop peeling, like this:
2652 for (int c1 = 1; c1 <= 5; c1 += 1) {
2657 there should be no loop-phi nodes in S_8(0).
2659 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2660 values of all scalar variables: for the moment we instantiate only
2661 SCEV analyzable expressions on the iteration domain, and we need to
2662 extend that to reductions that cannot be analyzed by SCEV. */
2663 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2665 set_codegen_error ();
2670 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2672 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2674 set_codegen_error ();
2678 else if (num_phis
> 0)
2681 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2684 basic_block phi_bb
= single_pred (new_bb
);
2685 loop_p loop_father
= new_bb
->loop_father
;
2687 /* Move back until we find the block with two predecessors. */
2688 while (single_pred_p (phi_bb
))
2689 phi_bb
= single_pred_edge (phi_bb
)->src
;
2691 /* If a corresponding merge-point was not found, then abort codegen. */
2692 if (phi_bb
->loop_father
!= loop_father
2693 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2694 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2696 set_codegen_error ();
2703 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2704 bb
->index
, new_bb
->index
);
2706 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2708 copied_bbs
->safe_push (new_bb
);
2711 vec
<basic_block
> bbs
;
2713 bbs
.safe_push (new_bb
);
2714 region
->copied_bb_map
->put (bb
, bbs
);
2717 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2719 set_codegen_error ();
2723 return single_succ_edge (new_bb
);
2726 /* Patch the missing arguments of the phi nodes. */
2728 void translate_isl_ast_to_gimple::
2729 translate_pending_phi_nodes ()
2733 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2735 gphi
*old_phi
= rename
->first
;
2736 gphi
*new_phi
= rename
->second
;
2737 basic_block old_bb
= gimple_bb (old_phi
);
2738 basic_block new_bb
= gimple_bb (new_phi
);
2740 /* First edge is the init edge and second is the back edge. */
2741 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2742 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2746 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2747 print_gimple_stmt (dump_file
, old_phi
, 0);
2750 auto_vec
<tree
, 1> iv_map
;
2751 if (bb_contains_loop_phi_nodes (new_bb
)
2752 && bb_contains_loop_phi_nodes (old_bb
))
2754 if (!copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2756 set_codegen_error ();
2758 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2760 if (!copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, false))
2761 set_codegen_error ();
2763 else if (!copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false))
2764 set_codegen_error ();
2768 fprintf (dump_file
, "[codegen] to new-phi: ");
2769 print_gimple_stmt (dump_file
, new_phi
, 0);
2771 if (codegen_error_p ())
2776 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2778 void translate_isl_ast_to_gimple::
2779 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2781 sese_info_p region
= scop
->scop_info
;
2782 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2783 gcc_assert (nb_parameters
== region
->params
.length ());
2785 for (i
= 0; i
< nb_parameters
; i
++)
2787 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2789 ip
[tmp_id
] = region
->params
[i
];
2794 /* Generates a build, which specifies the constraints on the parameters. */
2796 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2797 generate_isl_context (scop_p scop
)
2799 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2800 return isl_ast_build_from_context (context_isl
);
2803 /* This method is executed before the construction of a for node. */
2805 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2807 isl_union_map
*dependences
= (isl_union_map
*) user
;
2808 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2809 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2810 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2811 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2812 for_info
->is_parallelizable
=
2813 !carries_deps (schedule
, dependences
, dimension
);
2814 isl_union_map_free (schedule
);
2815 isl_space_free (schedule_space
);
2816 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2820 /* Generate isl AST from schedule of SCOP. */
2822 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2823 scop_to_isl_ast (scop_p scop
)
2825 gcc_assert (scop
->transformed_schedule
);
2827 /* Set the separate option to reduce control flow overhead. */
2828 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2829 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2830 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2832 if (flag_loop_parallelize_all
)
2834 scop_get_dependences (scop
);
2836 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2840 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2841 (context_isl
, schedule
);
2842 isl_ast_build_free (context_isl
);
2846 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2847 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2850 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2851 gimple_stmt_iterator
*gsi
)
2853 if (!defined_in_sese_p (tr
, region
->region
))
2857 use_operand_p use_p
;
2858 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2860 tree use_tr
= USE_FROM_PTR (use_p
);
2862 /* Do not copy parameters that have been generated in the header of the
2864 if (region
->parameter_rename_map
->get(use_tr
))
2867 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2871 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2874 gimple
*copy
= gimple_copy (def_stmt
);
2875 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2877 /* Create new names for all the definitions created by COPY and
2878 add replacement mappings for each new name. */
2879 def_operand_p def_p
;
2880 ssa_op_iter op_iter
;
2881 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2883 tree old_name
= DEF_FROM_PTR (def_p
);
2884 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2885 region
->parameter_rename_map
->put(old_name
, new_name
);
2892 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2894 /* For all the parameters which definitino is in the if_region->false_region,
2895 insert code on true_region (if_region->true_region->entry). */
2899 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2901 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2903 // If def is not in region.
2904 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2906 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2910 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2911 Return true if code generation succeeded. */
2914 graphite_regenerate_ast_isl (scop_p scop
)
2916 sese_info_p region
= scop
->scop_info
;
2917 translate_isl_ast_to_gimple
t (region
);
2919 ifsese if_region
= NULL
;
2920 isl_ast_node
*root_node
;
2923 timevar_push (TV_GRAPHITE_CODE_GEN
);
2924 t
.add_parameters_to_ivs_params (scop
, ip
);
2925 root_node
= t
.scop_to_isl_ast (scop
);
2927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2929 fprintf (dump_file
, "[scheduler] original schedule:\n");
2930 print_isl_schedule (dump_file
, scop
->original_schedule
);
2931 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
2932 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
2934 fprintf (dump_file
, "[scheduler] original ast:\n");
2935 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
2936 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
2937 print_isl_ast (dump_file
, root_node
);
2940 if_region
= move_sese_in_condition (region
);
2941 region
->if_region
= if_region
;
2943 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2945 /* Copy all the parameters which are defined in the region. */
2946 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
2948 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2949 basic_block bb
= split_edge (e
);
2951 /* Update the true_region exit edge. */
2952 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2954 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2955 if (! t
.codegen_error_p ())
2956 t
.translate_pending_phi_nodes ();
2957 if (! t
.codegen_error_p ())
2959 sese_insert_phis_for_liveouts (region
,
2960 if_region
->region
->region
.exit
->src
,
2961 if_region
->false_region
->region
.exit
,
2962 if_region
->true_region
->region
.exit
);
2964 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
2966 mark_virtual_operands_for_renaming (cfun
);
2967 update_ssa (TODO_update_ssa
);
2970 if (t
.codegen_error_p ())
2973 fprintf (dump_file
, "codegen error: "
2974 "reverting back to the original code.\n");
2975 set_ifsese_condition (if_region
, integer_zero_node
);
2977 /* We registered new names, scrap that. */
2978 if (need_ssa_update_p (cfun
))
2979 delete_update_ssa ();
2980 /* Remove the unreachable region. */
2981 remove_edge_and_dominated_blocks (if_region
->true_region
->region
.entry
);
2982 basic_block ifb
= if_region
->false_region
->region
.entry
->src
;
2983 gimple_stmt_iterator gsi
= gsi_last_bb (ifb
);
2984 gsi_remove (&gsi
, true);
2985 if_region
->false_region
->region
.entry
->flags
&= ~EDGE_FALSE_VALUE
;
2986 if_region
->false_region
->region
.entry
->flags
|= EDGE_FALLTHRU
;
2987 /* remove_edge_and_dominated_blocks marks loops for removal but
2988 doesn't actually remove them (fix that...). */
2990 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2995 /* Verifies properties that GRAPHITE should maintain during translation. */
2996 checking_verify_loop_structure ();
2997 checking_verify_loop_closed_ssa (true);
2999 free (if_region
->true_region
);
3000 free (if_region
->region
);
3003 ivs_params_clear (ip
);
3004 isl_ast_node_free (root_node
);
3005 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3007 return !t
.codegen_error_p ();
3010 #endif /* HAVE_isl */