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 bool is_constant (tree op
) const
245 return TREE_CODE (op
) == INTEGER_CST
246 || TREE_CODE (op
) == REAL_CST
247 || TREE_CODE (op
) == COMPLEX_CST
248 || TREE_CODE (op
) == VECTOR_CST
;
252 /* The region to be translated. */
255 /* This flag is set when an error occurred during the translation of isl AST
259 /* A vector of all the edges at if_condition merge points. */
260 auto_vec
<edge
, 2> merge_points
;
263 /* Return the tree variable that corresponds to the given isl ast identifier
264 expression (an isl_ast_expr of type isl_ast_expr_id).
266 FIXME: We should replace blind conversion of id's type with derivation
267 of the optimal type when we get the corresponding isl support. Blindly
268 converting type sizes may be problematic when we switch to smaller
271 tree
translate_isl_ast_to_gimple::
272 gcc_expression_from_isl_ast_expr_id (tree type
,
273 __isl_take isl_ast_expr
*expr_id
,
276 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
277 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
278 std::map
<isl_id
*, tree
>::iterator res
;
279 res
= ip
.find (tmp_isl_id
);
280 isl_id_free (tmp_isl_id
);
281 gcc_assert (res
!= ip
.end () &&
282 "Could not map isl_id to tree expression");
283 isl_ast_expr_free (expr_id
);
284 tree t
= res
->second
;
285 tree
*val
= region
->parameter_rename_map
->get(t
);
289 return fold_convert (type
, *val
);
292 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
295 tree
translate_isl_ast_to_gimple::
296 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
298 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
299 isl_val
*val
= isl_ast_expr_get_val (expr
);
300 size_t n
= isl_val_n_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
));
301 HOST_WIDE_INT
*chunks
= XALLOCAVEC (HOST_WIDE_INT
, n
);
303 if (isl_val_get_abs_num_chunks (val
, sizeof (HOST_WIDE_INT
), chunks
) == -1)
307 widest_int wi
= widest_int::from_array (chunks
, n
, true);
308 if (isl_val_is_neg (val
))
310 res
= wide_int_to_tree (type
, wi
);
313 isl_ast_expr_free (expr
);
317 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
320 tree
translate_isl_ast_to_gimple::
321 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
323 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
324 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
325 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
326 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
328 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
329 isl_ast_expr_free (expr
);
331 if (codegen_error_p ())
337 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
340 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
343 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
346 /* As isl operates on arbitrary precision numbers, we may end up with
347 division by 2^64 that is folded to 0. */
348 if (integer_zerop (tree_rhs_expr
))
350 codegen_error
= true;
353 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
355 case isl_ast_op_pdiv_q
:
356 /* As isl operates on arbitrary precision numbers, we may end up with
357 division by 2^64 that is folded to 0. */
358 if (integer_zerop (tree_rhs_expr
))
360 codegen_error
= true;
363 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
365 case isl_ast_op_zdiv_r
:
366 case isl_ast_op_pdiv_r
:
367 /* As isl operates on arbitrary precision numbers, we may end up with
368 division by 2^64 that is folded to 0. */
369 if (integer_zerop (tree_rhs_expr
))
371 codegen_error
= true;
374 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
376 case isl_ast_op_fdiv_q
:
377 /* As isl operates on arbitrary precision numbers, we may end up with
378 division by 2^64 that is folded to 0. */
379 if (integer_zerop (tree_rhs_expr
))
381 codegen_error
= true;
384 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
387 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
388 tree_lhs_expr
, tree_rhs_expr
);
391 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
394 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
397 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
400 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
403 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
406 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
413 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
416 tree
translate_isl_ast_to_gimple::
417 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
419 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
420 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
421 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
422 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
423 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
424 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
425 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
426 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
427 isl_ast_expr_free (expr
);
429 if (codegen_error_p ())
432 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
435 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
438 tree
translate_isl_ast_to_gimple::
439 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
441 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
442 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
443 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
444 isl_ast_expr_free (expr
);
445 return codegen_error_p () ? NULL_TREE
446 : fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
449 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
450 to a GCC expression tree of type TYPE. */
452 tree
translate_isl_ast_to_gimple::
453 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
455 enum tree_code op_code
;
456 switch (isl_ast_expr_get_op_type (expr
))
469 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
470 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
472 if (codegen_error_p ())
474 isl_ast_expr_free (expr
);
479 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
481 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
482 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
484 if (codegen_error_p ())
486 isl_ast_expr_free (expr
);
490 res
= fold_build2 (op_code
, type
, res
, t
);
492 isl_ast_expr_free (expr
);
496 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
499 tree
translate_isl_ast_to_gimple::
500 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
503 if (codegen_error_p ())
505 isl_ast_expr_free (expr
);
509 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
510 switch (isl_ast_expr_get_op_type (expr
))
512 /* These isl ast expressions are not supported yet. */
513 case isl_ast_op_error
:
514 case isl_ast_op_call
:
515 case isl_ast_op_and_then
:
516 case isl_ast_op_or_else
:
521 return nary_op_to_tree (type
, expr
, ip
);
527 case isl_ast_op_pdiv_q
:
528 case isl_ast_op_pdiv_r
:
529 case isl_ast_op_fdiv_q
:
530 case isl_ast_op_zdiv_r
:
538 return binary_op_to_tree (type
, expr
, ip
);
540 case isl_ast_op_minus
:
541 return unary_op_to_tree (type
, expr
, ip
);
543 case isl_ast_op_cond
:
544 case isl_ast_op_select
:
545 return ternary_op_to_tree (type
, expr
, ip
);
554 /* Converts an isl AST expression E back to a GCC expression tree of
557 tree
translate_isl_ast_to_gimple::
558 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
561 if (codegen_error_p ())
563 isl_ast_expr_free (expr
);
567 switch (isl_ast_expr_get_type (expr
))
569 case isl_ast_expr_id
:
570 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
572 case isl_ast_expr_int
:
573 return gcc_expression_from_isl_expr_int (type
, expr
);
575 case isl_ast_expr_op
:
576 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
585 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
586 induction variable for the new LOOP. New LOOP is attached to CFG
587 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
588 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
589 isl's scattering name to the induction variable created for the
590 loop of STMT. The new induction variable is inserted in the NEWIVS
591 vector and is of type TYPE. */
593 struct loop
*translate_isl_ast_to_gimple::
594 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
595 loop_p outer
, tree type
, tree lb
, tree ub
,
598 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
599 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
601 /* To fail code generation, we generate wrong code until we discard it. */
602 if (codegen_error_p ())
603 stride
= integer_zero_node
;
605 tree ivvar
= create_tmp_var (type
, "graphite_IV");
606 tree iv
, iv_after_increment
;
607 loop_p loop
= create_empty_loop_on_edge
608 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
609 outer
? outer
: entry_edge
->src
->loop_father
);
611 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
612 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
613 std::map
<isl_id
*, tree
>::iterator res
;
616 isl_id_free (res
->first
);
618 isl_ast_expr_free (for_iterator
);
622 /* Create the loop for a isl_ast_node_for.
624 - NEXT_E is the edge where new generated code should be attached. */
626 edge
translate_isl_ast_to_gimple::
627 translate_isl_ast_for_loop (loop_p context_loop
,
628 __isl_keep isl_ast_node
*node_for
, edge next_e
,
629 tree type
, tree lb
, tree ub
,
632 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
633 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
635 edge last_e
= single_exit (loop
);
636 edge to_body
= single_succ_edge (loop
->header
);
637 basic_block after
= to_body
->dest
;
639 /* Translate the body of the loop. */
640 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
641 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
642 isl_ast_node_free (for_body
);
644 /* Early return if we failed to translate loop body. */
645 if (!next_e
|| codegen_error_p ())
648 if (next_e
->dest
!= after
)
649 redirect_edge_succ_nodup (next_e
, after
);
650 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
652 if (flag_loop_parallelize_all
)
654 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
656 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
657 loop
->can_be_parallel
= for_info
->is_parallelizable
;
665 /* We use this function to get the upper bound because of the form,
666 which is used by isl to represent loops:
668 for (iterator = init; cond; iterator += inc)
676 The loop condition is an arbitrary expression, which contains the
677 current loop iterator.
679 (e.g. iterator + 3 < B && C > iterator + A)
681 We have to know the upper bound of the iterator to generate a loop
682 in Gimple form. It can be obtained from the special representation
683 of the loop condition, which is generated by isl,
684 if the ast_build_atomic_upper_bound option is set. In this case,
685 isl generates a loop condition that consists of the current loop
686 iterator, + an operator (< or <=) and an expression not involving
687 the iterator, which is processed and returned by this function.
689 (e.g iterator <= upper-bound-expression-without-iterator) */
691 static __isl_give isl_ast_expr
*
692 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
694 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
695 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
696 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
698 switch (isl_ast_expr_get_op_type (for_cond
))
701 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
706 /* (iterator < ub) => (iterator <= ub - 1). */
708 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
709 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
710 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
717 isl_ast_expr_free (for_cond
);
721 /* Translates an isl_ast_node_for to Gimple. */
723 edge
translate_isl_ast_to_gimple::
724 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
725 edge next_e
, ivs_params
&ip
)
727 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
729 = build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
731 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node
);
732 tree lb
= gcc_expression_from_isl_expression (type
, for_init
, ip
);
733 /* To fail code generation, we generate wrong code until we discard it. */
734 if (codegen_error_p ())
735 lb
= integer_zero_node
;
737 isl_ast_expr
*upper_bound
= get_upper_bound (node
);
738 tree ub
= gcc_expression_from_isl_expression (type
, upper_bound
, ip
);
739 /* To fail code generation, we generate wrong code until we discard it. */
740 if (codegen_error_p ())
741 ub
= integer_zero_node
;
743 edge last_e
= single_succ_edge (split_edge (next_e
));
744 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
749 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
750 variables of the loops around GBB in SESE.
752 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
753 chrec, we could consider using a map<int, tree> that maps loop ids to the
754 corresponding tree expressions. */
756 void translate_isl_ast_to_gimple::
757 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
758 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
761 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
762 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
764 isl_ast_expr
*arg_expr
;
765 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
767 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
769 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
770 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
772 /* To fail code generation, we generate wrong code until we discard it. */
773 if (codegen_error_p ())
774 t
= integer_zero_node
;
776 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
777 iv_map
[old_loop
->num
] = t
;
781 /* Translates an isl_ast_node_user to Gimple.
783 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
785 edge
translate_isl_ast_to_gimple::
786 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
787 edge next_e
, ivs_params
&ip
)
789 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
791 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
792 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
793 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
795 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
796 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
799 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
801 isl_ast_expr_free (name_expr
);
802 isl_id_free (name_id
);
804 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
805 "The entry block should not even appear within a scop");
807 const int nb_loops
= number_of_loops (cfun
);
809 iv_map
.create (nb_loops
);
810 iv_map
.safe_grow_cleared (nb_loops
);
812 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
813 isl_ast_expr_free (user_expr
);
815 basic_block old_bb
= GBB_BB (gbb
);
819 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
820 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
821 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
825 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
829 if (codegen_error_p ())
834 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
835 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
841 /* Translates an isl_ast_node_block to Gimple. */
843 edge
translate_isl_ast_to_gimple::
844 translate_isl_ast_node_block (loop_p context_loop
,
845 __isl_keep isl_ast_node
*node
,
846 edge next_e
, ivs_params
&ip
)
848 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
849 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
851 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
853 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
854 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
855 isl_ast_node_free (tmp_node
);
857 isl_ast_node_list_free (node_list
);
861 /* Creates a new if region corresponding to isl's cond. */
863 edge
translate_isl_ast_to_gimple::
864 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
868 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
869 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
871 /* To fail code generation, we generate wrong code until we discard it. */
872 if (codegen_error_p ())
873 cond_expr
= integer_zero_node
;
875 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
879 /* Translates an isl_ast_node_if to Gimple. */
881 edge
translate_isl_ast_to_gimple::
882 translate_isl_ast_node_if (loop_p context_loop
,
883 __isl_keep isl_ast_node
*node
,
884 edge next_e
, ivs_params
&ip
)
886 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
887 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
888 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
889 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
890 merge_points
.safe_push (last_e
);
892 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
893 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
894 isl_ast_node_free (then_node
);
896 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
897 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
898 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
899 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
901 isl_ast_node_free (else_node
);
905 /* Translates an isl AST node NODE to GCC representation in the
906 context of a SESE. */
908 edge
translate_isl_ast_to_gimple::
909 translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
910 edge next_e
, ivs_params
&ip
)
912 if (codegen_error_p ())
915 switch (isl_ast_node_get_type (node
))
917 case isl_ast_node_error
:
920 case isl_ast_node_for
:
921 return translate_isl_ast_node_for (context_loop
, node
,
924 case isl_ast_node_if
:
925 return translate_isl_ast_node_if (context_loop
, node
,
928 case isl_ast_node_user
:
929 return translate_isl_ast_node_user (node
, next_e
, ip
);
931 case isl_ast_node_block
:
932 return translate_isl_ast_node_block (context_loop
, node
,
935 case isl_ast_node_mark
:
937 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
938 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
939 isl_ast_node_free (n
);
948 /* Return true when BB contains loop close phi nodes. A loop close phi node is
949 at the exit of loop which takes one argument that is the last value of the
950 variable being used out of the loop. */
953 bb_contains_loop_close_phi_nodes (basic_block bb
)
955 return single_pred_p (bb
)
956 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
959 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
960 header containing phi nodes which has one init-edge and one back-edge. */
963 bb_contains_loop_phi_nodes (basic_block bb
)
965 if (EDGE_COUNT (bb
->preds
) != 2)
968 unsigned depth
= loop_depth (bb
->loop_father
);
970 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
972 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
973 || depth
> loop_depth (preds
[1]->src
->loop_father
))
976 /* When one of the edges correspond to the same loop father and other
978 if (bb
->loop_father
!= preds
[0]->src
->loop_father
979 && bb
->loop_father
== preds
[1]->src
->loop_father
)
982 if (bb
->loop_father
!= preds
[1]->src
->loop_father
983 && bb
->loop_father
== preds
[0]->src
->loop_father
)
989 /* Check if USE is defined in a basic block from where the definition of USE can
990 propagate from all the paths. FIXME: Verify checks for virtual operands. */
993 is_loop_closed_ssa_use (basic_block bb
, tree use
)
995 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
998 /* For close-phi nodes def always comes from a loop which has a back-edge. */
999 if (bb_contains_loop_close_phi_nodes (bb
))
1002 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1003 basic_block def_bb
= gimple_bb (def
);
1005 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1008 /* Return the number of phi nodes in BB. */
1011 number_of_phi_nodes (basic_block bb
)
1014 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1020 /* Returns true if BB uses name in one of its PHIs. */
1023 phi_uses_name (basic_block bb
, tree name
)
1025 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1028 gphi
*phi
= psi
.phi ();
1029 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1031 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1032 if (use_arg
== name
)
1039 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1040 definition should flow into use, and the use should respect the loop-closed
1043 bool translate_isl_ast_to_gimple::
1044 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1045 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1047 if (SSA_NAME_IS_DEFAULT_DEF (rename
))
1050 /* The def of the rename must either dominate the uses or come from a
1051 back-edge. Also the def must respect the loop closed ssa form. */
1052 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1056 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1057 print_generic_expr (dump_file
, rename
);
1058 fprintf (dump_file
, "\n");
1063 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1066 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1068 /* The loop-header dominates the loop-body. */
1069 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1072 /* RENAME would be used in loop-phi. */
1073 gcc_assert (number_of_phi_nodes (use_bb
));
1075 /* For definitions coming from back edges, we should check that
1076 old_name is used in a loop PHI node.
1077 FIXME: Verify if this is true. */
1078 if (phi_uses_name (old_bb
, old_name
))
1084 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1085 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1087 tree
translate_isl_ast_to_gimple::
1088 get_rename (basic_block new_bb
, tree old_name
, basic_block old_bb
,
1089 phi_node_kind phi_kind
) const
1091 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1092 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1094 if (!renames
|| renames
->is_empty ())
1097 if (1 == renames
->length ())
1099 tree rename
= (*renames
)[0];
1100 if (TREE_CODE (rename
) == SSA_NAME
)
1102 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1103 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1104 && (phi_kind
== close_phi
1106 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1111 if (is_constant (rename
))
1117 /* More than one renames corresponding to the old_name. Find the rename for
1118 which the definition flows into usage at new_bb. */
1120 tree t1
= NULL_TREE
, t2
;
1121 basic_block t1_bb
= NULL
;
1122 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1124 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1126 /* Defined in the same basic block as used. */
1127 if (t2_bb
== new_bb
)
1130 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1131 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1134 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1137 /* Compute the nearest dominator. */
1138 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1148 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1149 When OLD_NAME and EXPR are the same we assert. */
1151 void translate_isl_ast_to_gimple::
1152 set_rename (tree old_name
, tree expr
)
1156 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1157 print_generic_expr (dump_file
, old_name
);
1158 fprintf (dump_file
, ", new_name = ");
1159 print_generic_expr (dump_file
, expr
);
1160 fprintf (dump_file
, "\n");
1163 if (old_name
== expr
)
1166 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1169 renames
->safe_push (expr
);
1175 region
->rename_map
->put (old_name
, r
);
1180 /* For a parameter of a scop we don't want to rename it. */
1181 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1183 region
->parameter_rename_map
->put(old_name
, expr
);
1186 /* Return an iterator to the instructions comes last in the execution order.
1187 Either GSI1 and GSI2 should belong to the same basic block or one of their
1188 respective basic blocks should dominate the other. */
1190 gimple_stmt_iterator
1191 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1193 basic_block bb1
= gsi_bb (gsi1
);
1194 basic_block bb2
= gsi_bb (gsi2
);
1196 /* Find the iterator which is the latest. */
1199 gimple
*stmt1
= gsi_stmt (gsi1
);
1200 gimple
*stmt2
= gsi_stmt (gsi2
);
1202 if (stmt1
!= NULL
&& stmt2
!= NULL
)
1204 bool is_phi1
= gimple_code (stmt1
) == GIMPLE_PHI
;
1205 bool is_phi2
= gimple_code (stmt2
) == GIMPLE_PHI
;
1207 if (is_phi1
!= is_phi2
)
1208 return is_phi1
? gsi2
: gsi1
;
1211 /* For empty basic blocks gsis point to the end of the sequence. Since
1212 there is no operator== defined for gimple_stmt_iterator and for gsis
1213 not pointing to a valid statement gsi_next would assert. */
1214 gimple_stmt_iterator gsi
= gsi1
;
1216 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1219 } while (!gsi_end_p (gsi
));
1224 /* Find the basic block closest to the basic block which defines stmt. */
1225 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1228 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1232 /* Insert each statement from SEQ at its earliest insertion p. */
1234 void translate_isl_ast_to_gimple::
1235 gsi_insert_earliest (gimple_seq seq
)
1237 update_modified_stmts (seq
);
1238 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1239 basic_block begin_bb
= get_entry_bb (codegen_region
);
1241 /* Inserting the gimple statements in a vector because gimple_seq behave
1242 in strage ways when inserting the stmts from it into different basic
1243 blocks one at a time. */
1244 auto_vec
<gimple
*, 3> stmts
;
1245 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1247 stmts
.safe_push (gsi_stmt (gsi
));
1251 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1253 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1254 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1256 use_operand_p use_p
;
1257 ssa_op_iter op_iter
;
1258 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1260 /* Iterator to the current def of use_p. For function parameters or
1261 anything where def is not found, insert at the beginning of the
1262 generated region. */
1263 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1265 tree op
= USE_FROM_PTR (use_p
);
1266 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1267 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1268 gsi_stmt
= gsi_for_stmt (stmt
);
1270 /* For region parameters, insert at the beginning of the generated
1272 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1273 gsi_stmt
= gsi_def_stmt
;
1275 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1278 if (!gsi_stmt (gsi_def_stmt
))
1280 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1281 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1283 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1285 gimple_stmt_iterator bsi
1286 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1287 /* Insert right after the PHI statements. */
1288 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1291 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1295 fprintf (dump_file
, "[codegen] inserting statement: ");
1296 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1297 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1302 /* Collect all the operands of NEW_EXPR by recursively visiting each
1305 void translate_isl_ast_to_gimple::
1306 collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
)
1308 if (new_expr
== NULL_TREE
)
1311 /* Rename all uses in new_expr. */
1312 if (TREE_CODE (new_expr
) == SSA_NAME
)
1314 vec_ssa
->safe_push (new_expr
);
1318 /* Iterate over SSA_NAMES in NEW_EXPR. */
1319 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1321 tree op
= TREE_OPERAND (new_expr
, i
);
1322 collect_all_ssa_names (op
, vec_ssa
);
1326 /* This is abridged version of the function copied from:
1327 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1330 substitute_ssa_name (tree exp
, tree f
, tree r
)
1332 enum tree_code code
= TREE_CODE (exp
);
1333 tree op0
, op1
, op2
, op3
;
1336 /* We handle TREE_LIST and COMPONENT_REF separately. */
1337 if (code
== TREE_LIST
)
1339 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1340 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1341 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1344 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1346 else if (code
== COMPONENT_REF
)
1350 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1351 and it is the right field, replace it with R. */
1352 for (inner
= TREE_OPERAND (exp
, 0);
1353 REFERENCE_CLASS_P (inner
);
1354 inner
= TREE_OPERAND (inner
, 0))
1358 op1
= TREE_OPERAND (exp
, 1);
1360 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1363 /* If this expression hasn't been completed let, leave it alone. */
1364 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1367 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1368 if (op0
== TREE_OPERAND (exp
, 0))
1372 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1375 switch (TREE_CODE_CLASS (code
))
1380 case tcc_declaration
:
1386 case tcc_expression
:
1392 case tcc_exceptional
:
1395 case tcc_comparison
:
1397 switch (TREE_CODE_LENGTH (code
))
1405 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1406 if (op0
== TREE_OPERAND (exp
, 0))
1409 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1413 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1414 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1416 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1419 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1423 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1424 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1425 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1427 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1428 && op2
== TREE_OPERAND (exp
, 2))
1431 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1435 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1436 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1437 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1438 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1440 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1441 && op2
== TREE_OPERAND (exp
, 2)
1442 && op3
== TREE_OPERAND (exp
, 3))
1446 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1459 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1461 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1462 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1467 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1469 tree
translate_isl_ast_to_gimple::
1470 rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
)
1472 auto_vec
<tree
, 2> ssa_names
;
1473 collect_all_ssa_names (new_expr
, &ssa_names
);
1476 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1477 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1478 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1483 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1484 scalar evolution around LOOP. */
1486 tree
translate_isl_ast_to_gimple::
1487 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1488 basic_block new_bb
, basic_block old_bb
,
1491 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1493 /* At this point we should know the exact scev for each
1494 scalar SSA_NAME used in the scop: all the other scalar
1495 SSA_NAMEs should have been translated out of SSA using
1496 arrays with one element. */
1498 if (chrec_contains_undetermined (scev
))
1500 codegen_error
= true;
1501 return build_zero_cst (TREE_TYPE (old_name
));
1504 new_expr
= chrec_apply_map (scev
, iv_map
);
1506 /* The apply should produce an expression tree containing
1507 the uses of the new induction variables. We should be
1508 able to use new_expr instead of the old_name in the newly
1509 generated loop nest. */
1510 if (chrec_contains_undetermined (new_expr
)
1511 || tree_contains_chrecs (new_expr
, NULL
))
1513 codegen_error
= true;
1514 return build_zero_cst (TREE_TYPE (old_name
));
1517 if (TREE_CODE (new_expr
) == SSA_NAME
)
1519 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1520 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1522 codegen_error
= true;
1523 return build_zero_cst (TREE_TYPE (old_name
));
1527 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1529 /* We check all the operands and all of them should dominate the use at
1531 auto_vec
<tree
, 2> new_ssa_names
;
1532 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1535 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1537 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1539 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1540 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1542 codegen_error
= true;
1543 return build_zero_cst (TREE_TYPE (old_name
));
1548 /* Replace the old_name with the new_expr. */
1549 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1553 /* Renames the scalar uses of the statement COPY, using the
1554 substitution map RENAME_MAP, inserting the gimplification code at
1555 GSI_TGT, for the translation REGION, with the original copied
1556 statement in LOOP, and using the induction variable renaming map
1557 IV_MAP. Returns true when something has been renamed. */
1559 bool translate_isl_ast_to_gimple::
1560 rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
, basic_block old_bb
,
1561 loop_p loop
, vec
<tree
> iv_map
)
1563 bool changed
= false;
1565 if (is_gimple_debug (copy
))
1567 if (gimple_debug_bind_p (copy
))
1568 gimple_debug_bind_reset_value (copy
);
1569 else if (gimple_debug_source_bind_p (copy
))
1579 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1580 print_gimple_stmt (dump_file
, copy
, 0);
1583 use_operand_p use_p
;
1584 ssa_op_iter op_iter
;
1585 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1587 tree old_name
= USE_FROM_PTR (use_p
);
1591 fprintf (dump_file
, "[codegen] renaming old_name = ");
1592 print_generic_expr (dump_file
, old_name
);
1593 fprintf (dump_file
, "\n");
1596 if (TREE_CODE (old_name
) != SSA_NAME
1597 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1601 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1602 old_bb
, unknown_phi
);
1606 tree type_old_name
= TREE_TYPE (old_name
);
1607 tree type_new_expr
= TREE_TYPE (new_expr
);
1611 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1612 print_generic_expr (dump_file
, new_expr
);
1613 fprintf (dump_file
, "\n");
1616 if (type_old_name
!= type_new_expr
1617 || TREE_CODE (new_expr
) != SSA_NAME
)
1619 tree var
= create_tmp_var (type_old_name
, "var");
1621 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1622 new_expr
= fold_convert (type_old_name
, new_expr
);
1625 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1626 gsi_insert_earliest (stmts
);
1629 replace_exp (use_p
, new_expr
);
1634 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1636 if (!new_expr
|| codegen_error_p ())
1641 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1642 print_generic_expr (dump_file
, new_expr
);
1643 fprintf (dump_file
, "\n");
1646 gsi_insert_earliest (stmts
);
1647 replace_exp (use_p
, new_expr
);
1649 if (TREE_CODE (new_expr
) == INTEGER_CST
1650 && is_gimple_assign (copy
))
1652 tree rhs
= gimple_assign_rhs1 (copy
);
1654 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1655 recompute_tree_invariant_for_addr_expr (rhs
);
1658 set_rename (old_name
, new_expr
);
1664 /* Returns a basic block that could correspond to where a constant was defined
1665 in the original code. In the original code OLD_BB had the definition, we
1666 need to find which basic block out of the copies of old_bb, in the new
1667 region, should a definition correspond to if it has to reach BB. */
1669 basic_block
translate_isl_ast_to_gimple::
1670 get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const
1672 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1674 if (!bbs
|| bbs
->is_empty ())
1677 if (1 == bbs
->length ())
1681 basic_block b1
= NULL
, b2
;
1682 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1687 /* BB and B2 are in two unrelated if-clauses. */
1688 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1691 /* Compute the nearest dominator. */
1692 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1699 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1700 determines the kind of phi node. */
1702 tree
translate_isl_ast_to_gimple::
1703 get_new_name (basic_block new_bb
, tree op
,
1704 basic_block old_bb
, phi_node_kind phi_kind
) const
1706 /* For constants the names are the same. */
1707 if (TREE_CODE (op
) != SSA_NAME
)
1710 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
1713 /* Return a debug location for OP. */
1718 location_t loc
= UNKNOWN_LOCATION
;
1720 if (TREE_CODE (op
) == SSA_NAME
)
1721 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1725 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1726 the init edge (from outside the loop) and the second one is the back edge
1727 from the same loop. */
1729 std::pair
<edge
, edge
>
1730 get_edges (basic_block bb
)
1732 std::pair
<edge
, edge
> edges
;
1735 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1736 if (bb
->loop_father
!= e
->src
->loop_father
)
1743 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1744 must be found unless they can be POSTPONEd for later. */
1746 bool translate_isl_ast_to_gimple::
1747 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1748 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1751 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1753 basic_block new_bb
= gimple_bb (new_phi
);
1754 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1757 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1758 e
= ibp_new_bb
.first
;
1760 e
= ibp_new_bb
.second
;
1762 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1763 tree new_name
= get_new_name (new_bb
, old_name
,
1764 gimple_bb (old_phi
), loop_phi
);
1767 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1771 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1772 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1773 /* If the phi arg was a function arg, or wasn't defined, just use the
1775 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1778 /* Postpone code gen for later for those back-edges we don't have the
1780 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1782 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1785 /* Either we should add the arg to phi or, we should postpone. */
1791 /* Copy loop phi nodes from BB to NEW_BB. */
1793 bool translate_isl_ast_to_gimple::
1794 copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
)
1797 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1800 /* Loop phi nodes should have only two arguments. */
1801 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1803 /* First edge is the init edge and second is the back edge. */
1804 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1806 /* First edge is the init edge and second is the back edge. */
1807 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1809 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1812 gphi
*phi
= psi
.phi ();
1813 tree res
= gimple_phi_result (phi
);
1814 if (virtual_operand_p (res
))
1816 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1819 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
1820 tree new_res
= create_new_def_for (res
, new_phi
,
1821 gimple_phi_result_ptr (new_phi
));
1822 set_rename (res
, new_res
);
1823 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1825 update_stmt (new_phi
);
1829 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
1830 print_gimple_stmt (dump_file
, new_phi
, 0);
1837 /* Return the init value of PHI, the value coming from outside the loop. */
1840 get_loop_init_value (gphi
*phi
)
1843 loop_p loop
= gimple_bb (phi
)->loop_father
;
1847 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1848 if (e
->src
->loop_father
!= loop
)
1849 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1854 /* Find the init value (the value which comes from outside the loop), of one of
1855 the operands of DEF which is defined by a loop phi. */
1858 find_init_value (gimple
*def
)
1860 if (gimple_code (def
) == GIMPLE_PHI
)
1861 return get_loop_init_value (as_a
<gphi
*> (def
));
1863 if (gimple_vuse (def
))
1867 use_operand_p use_p
;
1868 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
1870 tree use
= USE_FROM_PTR (use_p
);
1871 if (TREE_CODE (use
) == SSA_NAME
)
1873 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
1881 /* Return the init value, the value coming from outside the loop. */
1884 find_init_value_close_phi (gphi
*phi
)
1886 gcc_assert (gimple_phi_num_args (phi
) == 1);
1887 tree use_arg
= gimple_phi_arg_def (phi
, 0);
1888 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
1889 return find_init_value (def
);
1893 tree
translate_isl_ast_to_gimple::
1894 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
1895 gimple
*old_close_phi
)
1897 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1898 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
1899 basic_block bb
= gimple_bb (stmt
);
1900 if (!bb_in_sese_p (bb
, codegen_region
))
1901 return last_merge_name
;
1903 loop_p loop
= bb
->loop_father
;
1904 if (!loop_in_sese_p (loop
, codegen_region
))
1905 return last_merge_name
;
1907 edge e
= single_exit (loop
);
1909 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
1910 return last_merge_name
;
1912 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1913 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1916 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
1917 bb
= split_edge (e
);
1919 gphi
*close_phi
= create_phi_node (NULL_TREE
, bb
);
1920 tree res
= create_new_def_for (last_merge_name
, close_phi
,
1921 gimple_phi_result_ptr (close_phi
));
1922 set_rename (old_close_phi_name
, res
);
1923 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
1924 last_merge_name
= res
;
1926 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
1929 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
1930 the close phi node PHI. */
1932 bool translate_isl_ast_to_gimple::
1933 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
1936 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1937 basic_block default_value_bb
= get_entry_bb (codegen_region
);
1938 if (SSA_NAME
== TREE_CODE (default_value
))
1940 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
1941 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
1943 default_value_bb
= gimple_bb (stmt
);
1946 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
1948 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
1949 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
1950 tree last_merge_name
= new_close_phi_name
;
1951 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
1955 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
1957 basic_block new_merge_bb
= merge_e
->src
;
1958 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
1961 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
1964 gphi
*merge_phi
= create_phi_node (NULL_TREE
, new_merge_bb
);
1965 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
1966 gimple_phi_result_ptr (merge_phi
));
1967 set_rename (old_close_phi_name
, merge_res
);
1969 edge from_loop
= NULL
, from_default_value
= NULL
;
1972 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
1973 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
1976 from_default_value
= e
;
1978 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
1979 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
1980 is contained in another condition. */
1981 if (!from_default_value
|| !from_loop
)
1984 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
1985 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
1989 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
1990 print_gimple_stmt (dump_file
, merge_phi
, 0);
1993 update_stmt (merge_phi
);
1994 last_merge_name
= merge_res
;
2000 /* Copy all the loop-close phi args from BB to NEW_BB. */
2002 bool translate_isl_ast_to_gimple::
2003 copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
2004 vec
<tree
> iv_map
, bool postpone
)
2006 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2009 gphi
*old_close_phi
= psi
.phi ();
2010 tree res
= gimple_phi_result (old_close_phi
);
2011 if (virtual_operand_p (res
))
2014 gphi
*new_close_phi
= create_phi_node (NULL_TREE
, new_bb
);
2015 tree new_res
= create_new_def_for (res
, new_close_phi
,
2016 gimple_phi_result_ptr (new_close_phi
));
2017 set_rename (res
, new_res
);
2019 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2021 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2024 new_name
= get_rename_from_scev (old_name
, &stmts
,
2025 old_bb
->loop_father
,
2026 new_bb
, old_bb
, iv_map
);
2027 if (! codegen_error_p ())
2028 gsi_insert_earliest (stmts
);
2031 new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2033 /* Predecessor basic blocks of a loop close phi should have been code
2034 generated before. FIXME: This is fixable by merging PHIs from inner
2035 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2036 if (!new_name
|| codegen_error_p ())
2039 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2040 get_loc (old_name
));
2043 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2044 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2047 update_stmt (new_close_phi
);
2049 /* When there is no loop guard around this codegenerated loop, there is no
2050 need to collect the close-phi arg. */
2051 if (merge_points
.is_empty ())
2054 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2055 tree default_value
= find_init_value_close_phi (new_close_phi
);
2057 /* A close phi must come from a loop-phi having a default value. */
2063 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2067 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2068 print_gimple_stmt (dump_file
, new_close_phi
, 0);
2073 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2081 /* Copy loop close phi nodes from BB to NEW_BB. */
2083 bool translate_isl_ast_to_gimple::
2084 copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
,
2088 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2090 /* Loop close phi nodes should have only one argument. */
2091 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2093 return copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, true);
2097 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2098 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2099 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2100 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2103 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2104 In this case DOMINATING_PRED = NULL.
2106 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2108 Returns true on successful copy of the args, false otherwise. */
2110 bool translate_isl_ast_to_gimple::
2111 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2112 edge old_bb_dominating_edge
,
2113 edge old_bb_non_dominating_edge
,
2114 gphi
*phi
, gphi
*new_phi
,
2117 basic_block def_pred
[2] = { NULL
, NULL
};
2118 int not_found_bb_index
= -1;
2119 for (int i
= 0; i
< 2; i
++)
2121 /* If the corresponding def_bb could not be found the entry will be
2123 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2124 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2125 gimple_phi_arg_edge (phi
, i
)->src
);
2126 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2127 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2131 /* When non are available bail out. */
2132 if (not_found_bb_index
!= -1)
2134 not_found_bb_index
= i
;
2138 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2139 if (old_bb_dominating_edge
)
2141 if (not_found_bb_index
!= -1)
2144 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2145 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2146 vec
<basic_block
> *bbs
2147 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2149 /* Could not find a mapping. */
2153 basic_block new_pred
= NULL
;
2156 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2158 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2160 /* FIXME: If we have already found new_pred then we have to
2161 disambiguate, bail out for now. */
2164 new_pred
= new_pred1
;
2166 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2168 /* FIXME: If we have already found new_pred then we have to either
2169 it dominates both or we have to disambiguate, bail out. */
2172 new_pred
= new_pred2
;
2179 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2180 gcc_assert (new_non_dominating_edge
);
2181 /* FIXME: Validate each args just like in loop-phis. */
2182 /* By the process of elimination we first insert insert phi-edge for
2183 non-dominating pred which is computed above and then we insert the
2185 int inserted_edge
= 0;
2186 for (; inserted_edge
< 2; inserted_edge
++)
2188 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2189 if (new_non_dominating_edge
== new_bb_pred_edge
)
2191 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2192 new_non_dominating_edge
,
2193 get_loc (old_phi_args
[inserted_edge
]));
2197 if (inserted_edge
== 2)
2200 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2202 edge new_dominating_edge
= NULL
;
2203 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2205 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2206 if (e
!= new_non_dominating_edge
)
2208 new_dominating_edge
= e
;
2209 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2210 new_dominating_edge
,
2211 get_loc (old_phi_args
[inserted_edge
]));
2215 gcc_assert (new_dominating_edge
);
2219 /* Classic diamond structure: both edges are non-dominating. We need to
2220 find one unique edge then the other can be found be elimination. If
2221 any definition (def_pred) dominates both the preds of new_bb then we
2222 bail out. Entries of def_pred maybe NULL, in that case we must
2223 uniquely find pred with help of only one entry. */
2224 edge new_e
[2] = { NULL
, NULL
};
2225 for (int i
= 0; i
< 2; i
++)
2229 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2231 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2234 /* We do not know how to handle the case when def_pred
2235 dominates more than a predecessor. */
2241 gcc_assert (new_e
[0] || new_e
[1]);
2243 /* Find the other edge by process of elimination. */
2244 if (not_found_bb_index
!= -1)
2246 gcc_assert (!new_e
[not_found_bb_index
]);
2247 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2250 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2252 if (new_e
[found_bb_index
] == e
)
2254 new_e
[not_found_bb_index
] = e
;
2258 /* Add edges to phi args. */
2259 for (int i
= 0; i
< 2; i
++)
2260 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2261 get_loc (old_phi_args
[i
]));
2267 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2268 region. If postpone is true and it isn't possible to copy any arg of PHI,
2269 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2270 Returns false if the copying was unsuccessful. */
2272 bool translate_isl_ast_to_gimple::
2273 copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
, bool postpone
)
2276 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2277 gcc_assert (2 == gimple_phi_num_args (phi
));
2279 basic_block new_bb
= gimple_bb (new_phi
);
2280 loop_p loop
= gimple_bb (phi
)->loop_father
;
2282 basic_block old_bb
= gimple_bb (phi
);
2283 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2287 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2288 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2289 old_bb_non_dominating_edge
= e
;
2291 old_bb_dominating_edge
= e
;
2293 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2294 old_bb_non_dominating_edge
->src
));
2296 tree new_phi_args
[2];
2297 tree old_phi_args
[2];
2299 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2301 tree old_name
= gimple_phi_arg_def (phi
, i
);
2302 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2303 old_phi_args
[i
] = old_name
;
2306 new_phi_args
[i
] = new_name
;
2310 /* If the phi-arg was a parameter. */
2311 if (vec_find (region
->params
, old_name
) != -1)
2313 new_phi_args
[i
] = old_name
;
2317 "[codegen] parameter argument to phi, new_expr: ");
2318 print_generic_expr (dump_file
, new_phi_args
[i
]);
2319 fprintf (dump_file
, "\n");
2324 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2325 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2326 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2332 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2333 if (is_gimple_reg (old_name
)
2334 && scev_analyzable_p (old_name
, region
->region
))
2337 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2338 new_bb
, old_bb
, iv_map
);
2339 if (codegen_error_p ())
2342 gcc_assert (new_expr
);
2346 "[codegen] scev analyzeable, new_expr: ");
2347 print_generic_expr (dump_file
, new_expr
);
2348 fprintf (dump_file
, "\n");
2350 gsi_insert_earliest (stmts
);
2351 new_phi_args
[i
] = new_expr
;
2355 /* Postpone code gen for later for back-edges. */
2356 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2360 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2361 print_gimple_stmt (dump_file
, new_phi
, 0);
2364 new_phi_args
[i
] = NULL_TREE
;
2368 /* Either we should add the arg to phi or, we should postpone. */
2372 /* If none of the args have been determined in the first stage then wait until
2374 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2377 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2378 old_bb_dominating_edge
,
2379 old_bb_non_dominating_edge
,
2380 phi
, new_phi
, new_bb
);
2383 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2384 containing phi nodes coming from two predecessors, and none of them are back
2387 bool translate_isl_ast_to_gimple::
2388 copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
, vec
<tree
> iv_map
)
2391 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2393 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2394 if (EDGE_COUNT (bb
->preds
) != 2)
2398 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2401 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2404 gphi
*phi
= psi
.phi ();
2405 tree res
= gimple_phi_result (phi
);
2406 if (virtual_operand_p (res
))
2409 gphi
*new_phi
= create_phi_node (NULL_TREE
, new_bb
);
2410 tree new_res
= create_new_def_for (res
, new_phi
,
2411 gimple_phi_result_ptr (new_phi
));
2412 set_rename (res
, new_res
);
2414 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2417 update_stmt (new_phi
);
2423 /* Return true if STMT should be copied from region to the new code-generated
2424 region. LABELs, CONDITIONS, induction-variables and region parameters need
2428 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2430 /* Do not copy labels or conditions. */
2431 if (gimple_code (stmt
) == GIMPLE_LABEL
2432 || gimple_code (stmt
) == GIMPLE_COND
)
2436 /* Do not copy induction variables. */
2437 if (is_gimple_assign (stmt
)
2438 && (lhs
= gimple_assign_lhs (stmt
))
2439 && TREE_CODE (lhs
) == SSA_NAME
2440 && is_gimple_reg (lhs
)
2441 && scev_analyzable_p (lhs
, region
->region
))
2444 /* Do not copy parameters that have been generated in the header of the
2446 if (is_gimple_assign (stmt
)
2447 && (lhs
= gimple_assign_lhs (stmt
))
2448 && TREE_CODE (lhs
) == SSA_NAME
2449 && region
->parameter_rename_map
->get(lhs
))
2455 /* Create new names for all the definitions created by COPY and add replacement
2456 mappings for each new name. */
2458 void translate_isl_ast_to_gimple::
2459 set_rename_for_each_def (gimple
*stmt
)
2461 def_operand_p def_p
;
2462 ssa_op_iter op_iter
;
2463 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2465 tree old_name
= DEF_FROM_PTR (def_p
);
2466 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2467 set_rename (old_name
, new_name
);
2471 /* Duplicates the statements of basic block BB into basic block NEW_BB
2472 and compute the new induction variables according to the IV_MAP. */
2474 bool translate_isl_ast_to_gimple::
2475 graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
2478 /* Iterator poining to the place where new statement (s) will be inserted. */
2479 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2481 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2484 gimple
*stmt
= gsi_stmt (gsi
);
2485 if (!should_copy_to_new_region (stmt
, region
))
2488 /* Create a new copy of STMT and duplicate STMT's virtual
2490 gimple
*copy
= gimple_copy (stmt
);
2491 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2495 fprintf (dump_file
, "[codegen] inserting statement: ");
2496 print_gimple_stmt (dump_file
, copy
, 0);
2499 maybe_duplicate_eh_stmt (copy
, stmt
);
2500 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2502 /* Crete new names for each def in the copied stmt. */
2503 set_rename_for_each_def (copy
);
2505 loop_p loop
= bb
->loop_father
;
2506 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2508 fold_stmt_inplace (&gsi_tgt
);
2509 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2512 if (codegen_error_p ())
2515 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2517 use_operand_p use_p
;
2518 if (!is_gimple_debug (copy
))
2519 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2521 tree old_name
= USE_FROM_PTR (use_p
);
2523 if (TREE_CODE (old_name
) != SSA_NAME
2524 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2527 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2531 replace_exp (use_p
, *new_expr
);
2541 /* Given a basic block containing close-phi it returns the new basic block where
2542 to insert a copy of the close-phi nodes. All the uses in close phis should
2543 come from a single loop otherwise it returns NULL. */
2545 edge
translate_isl_ast_to_gimple::
2546 edge_for_new_close_phis (basic_block bb
)
2548 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2549 of close phi in the original code and then find the mapping of basic block
2550 defining that variable. If there are multiple close-phis and they are
2551 defined in different loops (in the original or in the new code) because of
2552 loop splitting, then we bail out. */
2553 loop_p new_loop
= NULL
;
2554 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2557 gphi
*phi
= psi
.phi ();
2558 tree name
= gimple_phi_arg_def (phi
, 0);
2559 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2561 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2562 if (!bbs
|| bbs
->length () != 1)
2563 /* This is one of the places which shows preserving original structure
2564 is not always possible, as we may need to insert close PHI for a loop
2565 where the latch does not have any mapping, or the mapping is
2570 new_loop
= (*bbs
)[0]->loop_father
;
2571 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2578 return single_exit (new_loop
);
2581 /* Copies BB and includes in the copied BB all the statements that can
2582 be reached following the use-def chains from the memory accesses,
2583 and returns the next edge following this new block. */
2585 edge
translate_isl_ast_to_gimple::
2586 copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
, vec
<tree
> iv_map
)
2588 int num_phis
= number_of_phi_nodes (bb
);
2590 if (region
->copied_bb_map
->get (bb
))
2592 /* FIXME: we should be able to handle phi nodes with args coming from
2593 outside the region. */
2596 codegen_error
= true;
2601 basic_block new_bb
= NULL
;
2602 if (bb_contains_loop_close_phi_nodes (bb
))
2605 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2608 edge e
= edge_for_new_close_phis (bb
);
2611 codegen_error
= true;
2615 basic_block phi_bb
= e
->dest
;
2617 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2618 phi_bb
= split_edge (e
);
2620 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2621 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2623 if (!copy_loop_close_phi_nodes (bb
, phi_bb
, iv_map
))
2625 codegen_error
= true;
2632 new_bb
= split_edge (next_e
);
2636 new_bb
= split_edge (next_e
);
2637 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2639 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2641 /* At this point we are unable to codegenerate by still preserving the SSA
2642 structure because maybe the loop is completely unrolled and the PHIs
2643 and cross-bb scalar dependencies are untrackable w.r.t. the original
2644 code. See gfortran.dg/graphite/pr29832.f90. */
2645 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2647 codegen_error
= true;
2651 /* In case isl did some loop peeling, like this:
2654 for (int c1 = 1; c1 <= 5; c1 += 1) {
2659 there should be no loop-phi nodes in S_8(0).
2661 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2662 values of all scalar variables: for the moment we instantiate only
2663 SCEV analyzable expressions on the iteration domain, and we need to
2664 extend that to reductions that cannot be analyzed by SCEV. */
2665 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2667 codegen_error
= true;
2672 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2674 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2676 codegen_error
= true;
2680 else if (num_phis
> 0)
2683 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2686 basic_block phi_bb
= single_pred (new_bb
);
2687 loop_p loop_father
= new_bb
->loop_father
;
2689 /* Move back until we find the block with two predecessors. */
2690 while (single_pred_p (phi_bb
))
2691 phi_bb
= single_pred_edge (phi_bb
)->src
;
2693 /* If a corresponding merge-point was not found, then abort codegen. */
2694 if (phi_bb
->loop_father
!= loop_father
2695 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2696 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2698 codegen_error
= true;
2705 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2706 bb
->index
, new_bb
->index
);
2708 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2710 copied_bbs
->safe_push (new_bb
);
2713 vec
<basic_block
> bbs
;
2715 bbs
.safe_push (new_bb
);
2716 region
->copied_bb_map
->put (bb
, bbs
);
2719 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2721 codegen_error
= true;
2725 return single_succ_edge (new_bb
);
2728 /* Patch the missing arguments of the phi nodes. */
2730 void translate_isl_ast_to_gimple::
2731 translate_pending_phi_nodes ()
2735 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2737 gphi
*old_phi
= rename
->first
;
2738 gphi
*new_phi
= rename
->second
;
2739 basic_block old_bb
= gimple_bb (old_phi
);
2740 basic_block new_bb
= gimple_bb (new_phi
);
2742 /* First edge is the init edge and second is the back edge. */
2743 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2744 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2748 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2749 print_gimple_stmt (dump_file
, old_phi
, 0);
2752 auto_vec
<tree
, 1> iv_map
;
2753 if (bb_contains_loop_phi_nodes (new_bb
)
2754 && bb_contains_loop_phi_nodes (old_bb
))
2755 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2757 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2758 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, iv_map
, false);
2760 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2764 fprintf (dump_file
, "[codegen] to new-phi: ");
2765 print_gimple_stmt (dump_file
, new_phi
, 0);
2767 if (codegen_error_p ())
2772 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2774 void translate_isl_ast_to_gimple::
2775 add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
)
2777 sese_info_p region
= scop
->scop_info
;
2778 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2779 gcc_assert (nb_parameters
== region
->params
.length ());
2781 for (i
= 0; i
< nb_parameters
; i
++)
2783 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2785 ip
[tmp_id
] = region
->params
[i
];
2790 /* Generates a build, which specifies the constraints on the parameters. */
2792 __isl_give isl_ast_build
*translate_isl_ast_to_gimple::
2793 generate_isl_context (scop_p scop
)
2795 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2796 return isl_ast_build_from_context (context_isl
);
2799 /* This method is executed before the construction of a for node. */
2801 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2803 isl_union_map
*dependences
= (isl_union_map
*) user
;
2804 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2805 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2806 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2807 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2808 for_info
->is_parallelizable
=
2809 !carries_deps (schedule
, dependences
, dimension
);
2810 isl_union_map_free (schedule
);
2811 isl_space_free (schedule_space
);
2812 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2816 /* Generate isl AST from schedule of SCOP. */
2818 __isl_give isl_ast_node
*translate_isl_ast_to_gimple::
2819 scop_to_isl_ast (scop_p scop
)
2821 gcc_assert (scop
->transformed_schedule
);
2823 /* Set the separate option to reduce control flow overhead. */
2824 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
2825 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
2826 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2828 if (flag_loop_parallelize_all
)
2830 scop_get_dependences (scop
);
2832 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2836 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
2837 (context_isl
, schedule
);
2838 isl_ast_build_free (context_isl
);
2842 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
2843 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
2846 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
2847 gimple_stmt_iterator
*gsi
)
2849 if (!defined_in_sese_p (tr
, region
->region
))
2853 use_operand_p use_p
;
2854 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
2856 tree use_tr
= USE_FROM_PTR (use_p
);
2858 /* Do not copy parameters that have been generated in the header of the
2860 if (region
->parameter_rename_map
->get(use_tr
))
2863 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
2867 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
2870 gimple
*copy
= gimple_copy (def_stmt
);
2871 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
2873 /* Create new names for all the definitions created by COPY and
2874 add replacement mappings for each new name. */
2875 def_operand_p def_p
;
2876 ssa_op_iter op_iter
;
2877 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
2879 tree old_name
= DEF_FROM_PTR (def_p
);
2880 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
2881 region
->parameter_rename_map
->put(old_name
, new_name
);
2888 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
2890 /* For all the parameters which definitino is in the if_region->false_region,
2891 insert code on true_region (if_region->true_region->entry). */
2895 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
2897 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
2899 // If def is not in region.
2900 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
2902 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
2906 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
2907 Return true if code generation succeeded. */
2910 graphite_regenerate_ast_isl (scop_p scop
)
2912 sese_info_p region
= scop
->scop_info
;
2913 translate_isl_ast_to_gimple
t (region
);
2915 ifsese if_region
= NULL
;
2916 isl_ast_node
*root_node
;
2919 timevar_push (TV_GRAPHITE_CODE_GEN
);
2920 t
.add_parameters_to_ivs_params (scop
, ip
);
2921 root_node
= t
.scop_to_isl_ast (scop
);
2923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2925 fprintf (dump_file
, "[scheduler] original schedule:\n");
2926 print_isl_schedule (dump_file
, scop
->original_schedule
);
2927 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
2928 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
2930 fprintf (dump_file
, "[scheduler] original ast:\n");
2931 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
2932 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
2933 print_isl_ast (dump_file
, root_node
);
2936 if_region
= move_sese_in_condition (region
);
2937 region
->if_region
= if_region
;
2939 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2941 /* Copy all the parameters which are defined in the region. */
2942 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
2944 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2945 basic_block bb
= split_edge (e
);
2947 /* Update the true_region exit edge. */
2948 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2950 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2951 if (! t
.codegen_error_p ())
2952 t
.translate_pending_phi_nodes ();
2953 if (! t
.codegen_error_p ())
2955 sese_insert_phis_for_liveouts (region
,
2956 if_region
->region
->region
.exit
->src
,
2957 if_region
->false_region
->region
.exit
,
2958 if_region
->true_region
->region
.exit
);
2960 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
2962 mark_virtual_operands_for_renaming (cfun
);
2963 update_ssa (TODO_update_ssa
);
2966 if (t
.codegen_error_p ())
2969 fprintf (dump_file
, "codegen error: "
2970 "reverting back to the original code.\n");
2971 set_ifsese_condition (if_region
, integer_zero_node
);
2973 /* We registered new names, scrap that. */
2974 if (need_ssa_update_p (cfun
))
2975 delete_update_ssa ();
2976 /* Remove the unreachable region. */
2977 remove_edge_and_dominated_blocks (if_region
->true_region
->region
.entry
);
2978 basic_block ifb
= if_region
->false_region
->region
.entry
->src
;
2979 gimple_stmt_iterator gsi
= gsi_last_bb (ifb
);
2980 gsi_remove (&gsi
, true);
2981 if_region
->false_region
->region
.entry
->flags
&= ~EDGE_FALSE_VALUE
;
2982 if_region
->false_region
->region
.entry
->flags
|= EDGE_FALLTHRU
;
2983 /* remove_edge_and_dominated_blocks marks loops for removal but
2984 doesn't actually remove them (fix that...). */
2986 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2991 /* Verifies properties that GRAPHITE should maintain during translation. */
2992 checking_verify_loop_structure ();
2993 checking_verify_loop_closed_ssa (true);
2995 free (if_region
->true_region
);
2996 free (if_region
->region
);
2999 ivs_params_clear (ip
);
3000 isl_ast_node_free (root_node
);
3001 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3003 return !t
.codegen_error_p ();
3006 #endif /* HAVE_isl */