1 /* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2016 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/>. */
28 #include "coretypes.h"
34 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
40 #include "tree-ssa-loop.h"
41 #include "tree-ssa-operands.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-pass.h"
45 #include "tree-data-ref.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-scalar-evolution.h"
48 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "tree-into-ssa.h"
51 #include "ssa-iterators.h"
53 #include "gimple-pretty-print.h"
55 #include "value-prof.h"
59 /* We always try to use signed 128 bit types, but fall back to smaller types
60 in case a platform does not provide types of these sizes. In the future we
61 should use isl to derive the optimal type for each subexpression. */
63 static int max_mode_int_precision
=
64 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
65 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
66 128 : max_mode_int_precision
;
71 : is_parallelizable(false)
73 bool is_parallelizable
;
76 /* Converts a GMP constant VAL to a tree and returns it. */
79 gmp_cst_to_tree (tree type
, mpz_t val
)
81 tree t
= type
? type
: integer_type_node
;
86 wide_int wi
= wi::from_mpz (t
, tmp
, true);
89 return wide_int_to_tree (t
, wi
);
92 /* Verifies properties that GRAPHITE should maintain during translation. */
95 graphite_verify (void)
97 checking_verify_loop_structure ();
98 checking_verify_loop_closed_ssa (true);
101 /* IVS_PARAMS maps isl's scattering and parameter identifiers
102 to corresponding trees. */
104 typedef std::map
<isl_id
*, tree
> ivs_params
;
106 /* Free all memory allocated for isl's identifiers. */
108 void ivs_params_clear (ivs_params
&ip
)
110 std::map
<isl_id
*, tree
>::iterator it
;
111 for (it
= ip
.begin ();
112 it
!= ip
.end (); it
++)
114 isl_id_free (it
->first
);
118 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
120 /* Set the "separate" option for the schedule node. */
122 static __isl_give isl_schedule_node
*
123 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
128 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
131 /* Set the "separate" option unless it is set earlier to another option. */
132 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
133 == isl_ast_loop_default
)
134 return isl_schedule_node_band_member_set_ast_loop_type
135 (node
, 0, isl_ast_loop_separate
);
149 class translate_isl_ast_to_gimple
152 translate_isl_ast_to_gimple (sese_info_p r
)
153 : region (r
), codegen_error (false)
156 /* Translates an isl AST node NODE to GCC representation in the
157 context of a SESE. */
158 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
159 edge next_e
, ivs_params
&ip
);
161 /* Translates an isl_ast_node_for to Gimple. */
162 edge
translate_isl_ast_node_for (loop_p context_loop
,
163 __isl_keep isl_ast_node
*node
,
164 edge next_e
, ivs_params
&ip
);
166 /* Create the loop for a isl_ast_node_for.
168 - NEXT_E is the edge where new generated code should be attached. */
169 edge
translate_isl_ast_for_loop (loop_p context_loop
,
170 __isl_keep isl_ast_node
*node_for
,
172 tree type
, tree lb
, tree ub
,
175 /* Translates an isl_ast_node_if to Gimple. */
176 edge
translate_isl_ast_node_if (loop_p context_loop
,
177 __isl_keep isl_ast_node
*node
,
178 edge next_e
, ivs_params
&ip
);
180 /* Translates an isl_ast_node_user to Gimple.
182 FIXME: We should remove iv_map.create (loop->num + 1), if it is
184 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
185 edge next_e
, ivs_params
&ip
);
187 /* Translates an isl_ast_node_block to Gimple. */
188 edge
translate_isl_ast_node_block (loop_p context_loop
,
189 __isl_keep isl_ast_node
*node
,
190 edge next_e
, ivs_params
&ip
);
192 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
194 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
197 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
199 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
202 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
204 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
207 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
208 to a GCC expression tree of type TYPE. */
209 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
212 /* Converts an isl AST expression E back to a GCC expression tree of
214 tree
gcc_expression_from_isl_expression (tree type
,
215 __isl_take isl_ast_expr
*,
218 /* Return the tree variable that corresponds to the given isl ast identifier
219 expression (an isl_ast_expr of type isl_ast_expr_id).
221 FIXME: We should replace blind conversation of id's type with derivation
222 of the optimal type when we get the corresponding isl support. Blindly
223 converting type sizes may be problematic when we switch to smaller
225 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
226 __isl_keep isl_ast_expr
*expr_id
,
229 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
231 tree
gcc_expression_from_isl_expr_int (tree type
,
232 __isl_take isl_ast_expr
*expr
);
234 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
236 tree
gcc_expression_from_isl_expr_op (tree type
,
237 __isl_take isl_ast_expr
*expr
,
240 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
241 induction variable for the new LOOP. New LOOP is attached to CFG
242 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
243 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
244 isl's scattering name to the induction variable created for the
245 loop of STMT. The new induction variable is inserted in the NEWIVS
246 vector and is of type TYPE. */
247 struct loop
*graphite_create_new_loop (edge entry_edge
,
248 __isl_keep isl_ast_node
*node_for
,
249 loop_p outer
, tree type
,
250 tree lb
, tree ub
, ivs_params
&ip
);
252 /* All loops generated by create_empty_loop_on_edge have the form of
259 } while (lower bound < upper bound);
261 We create a new if region protecting the loop to be executed, if
262 the execution count is zero (lower bound > upper bound). */
263 edge
graphite_create_new_loop_guard (edge entry_edge
,
264 __isl_keep isl_ast_node
*node_for
,
266 tree
*lb
, tree
*ub
, ivs_params
&ip
);
268 /* Creates a new if region corresponding to isl's cond. */
269 edge
graphite_create_new_guard (edge entry_edge
,
270 __isl_take isl_ast_expr
*if_cond
,
273 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
274 variables of the loops around GBB in SESE.
276 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
277 chrec, we could consider using a map<int, tree> that maps loop ids to the
278 corresponding tree expressions. */
279 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
280 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
283 /* Patch the missing arguments of the phi nodes. */
285 void translate_pending_phi_nodes (void);
287 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
289 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
291 /* Get the maximal number of schedule dimensions in the scop SCOP. */
293 int get_max_schedule_dimensions (scop_p scop
);
295 /* Generates a build, which specifies the constraints on the parameters. */
297 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
299 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
301 For schedules with different dimensionality, the isl AST generator can not
302 define an order and will just randomly choose an order. The solution to
303 this problem is to extend all schedules to the maximal number of schedule
304 dimensions (using '0's for the remaining values). */
306 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
307 int nb_schedule_dims
);
309 /* Generates a schedule, which specifies an order used to
310 visit elements in a domain. */
312 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
314 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
315 /* Set the "separate" option for all schedules. This helps reducing control
318 __isl_give isl_schedule
*
319 set_options_for_schedule_tree (__isl_take isl_schedule
*schedule
);
322 /* Set the separate option for all dimensions.
323 This helps to reduce control overhead. */
325 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
326 __isl_keep isl_union_map
*schedule
);
328 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
331 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
334 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
335 definition should flow into use, and the use should respect the loop-closed
338 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
339 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
341 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
342 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
343 within a loop PHI instruction. */
345 tree
get_rename (basic_block new_bb
, tree old_name
,
346 basic_block old_bb
, phi_node_kind
) const;
348 /* For ops which are scev_analyzeable, we can regenerate a new name from
349 its scalar evolution around LOOP. */
351 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
352 basic_block new_bb
, basic_block old_bb
,
355 /* Returns a basic block that could correspond to where a constant was defined
356 in the original code. In the original code OLD_BB had the definition, we
357 need to find which basic block out of the copies of old_bb, in the new
358 region, should a definition correspond to if it has to reach BB. */
360 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
362 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
363 true when we want to rename an OP within a loop PHI instruction. */
365 tree
get_new_name (basic_block new_bb
, tree op
,
366 basic_block old_bb
, phi_node_kind
) const;
368 /* Collect all the operands of NEW_EXPR by recursively visiting each
371 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
373 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
374 NEW_PHI must be found unless they can be POSTPONEd for later. */
376 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
377 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
380 /* Copy loop phi nodes from BB to NEW_BB. */
382 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
384 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
385 the close phi node PHI. */
387 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
390 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
391 gimple
*old_close_phi
);
393 /* Copy all the loop-close phi args from BB to NEW_BB. */
395 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
398 /* Copy loop close phi nodes from BB to NEW_BB. */
400 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
402 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
403 region. If postpone is true and it isn't possible to copy any arg of PHI,
404 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
405 Returns false if the copying was unsuccessful. */
407 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
410 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
411 containing phi nodes coming from two predecessors, and none of them are back
414 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
417 /* Duplicates the statements of basic block BB into basic block NEW_BB
418 and compute the new induction variables according to the IV_MAP.
419 CODEGEN_ERROR is set when the code generation cannot continue. */
421 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
424 /* Copies BB and includes in the copied BB all the statements that can
425 be reached following the use-def chains from the memory accesses,
426 and returns the next edge following this new block. codegen_error is
427 set when the code generation cannot continue. */
429 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
432 /* Given a basic block containing close-phi it returns the new basic block
433 where to insert a copy of the close-phi nodes. All the uses in close phis
434 should come from a single loop otherwise it returns NULL. */
435 edge
edge_for_new_close_phis (basic_block bb
);
437 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
438 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
439 the other pred of OLD_BB as well. If no such basic block exists then it is
440 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
443 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
444 versa. In this case DOMINATING_PRED = NULL.
446 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
448 Returns true on successful copy of the args, false otherwise. */
450 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
451 edge old_bb_dominating_edge
,
452 edge old_bb_non_dominating_edge
,
453 gphi
*phi
, gphi
*new_phi
,
456 /* Renames the scalar uses of the statement COPY, using the substitution map
457 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
458 translation REGION, with the original copied statement in LOOP, and using
459 the induction variable renaming map IV_MAP. Returns true when something
460 has been renamed. codegen_error is set when the code generation cannot
463 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
464 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
466 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
467 When OLD_NAME and EXPR are the same we assert. */
469 void set_rename (tree old_name
, tree expr
);
471 /* Create new names for all the definitions created by COPY and add
472 replacement mappings for each new name. */
474 void set_rename_for_each_def (gimple
*stmt
);
476 /* Insert each statement from SEQ at its earliest insertion p. */
478 void gsi_insert_earliest (gimple_seq seq
);
480 /* Rename all the operands of NEW_EXPR by recursively visiting each
483 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
485 bool codegen_error_p () const
486 { return codegen_error
; }
488 /* Prints NODE to FILE. */
490 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
491 __isl_keep isl_ctx
*ctx
) const;
493 /* Return true when OP is a constant tree. */
495 bool is_constant (tree op
) const
497 return TREE_CODE (op
) == INTEGER_CST
498 || TREE_CODE (op
) == REAL_CST
499 || TREE_CODE (op
) == COMPLEX_CST
500 || TREE_CODE (op
) == VECTOR_CST
;
504 /* The region to be translated. */
507 /* This flag is set when an error occurred during the translation of isl AST
511 /* A vector of all the edges at if_condition merge points. */
512 auto_vec
<edge
, 2> merge_points
;
515 /* Return the tree variable that corresponds to the given isl ast identifier
516 expression (an isl_ast_expr of type isl_ast_expr_id).
518 FIXME: We should replace blind conversion of id's type with derivation
519 of the optimal type when we get the corresponding isl support. Blindly
520 converting type sizes may be problematic when we switch to smaller
524 translate_isl_ast_to_gimple::
525 gcc_expression_from_isl_ast_expr_id (tree type
,
526 __isl_take isl_ast_expr
*expr_id
,
529 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
530 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
531 std::map
<isl_id
*, tree
>::iterator res
;
532 res
= ip
.find (tmp_isl_id
);
533 isl_id_free (tmp_isl_id
);
534 gcc_assert (res
!= ip
.end () &&
535 "Could not map isl_id to tree expression");
536 isl_ast_expr_free (expr_id
);
537 tree t
= res
->second
;
538 tree
*val
= region
->parameter_rename_map
->get(t
);
542 return fold_convert (type
, *val
);
545 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
549 translate_isl_ast_to_gimple::
550 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
552 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
553 isl_val
*val
= isl_ast_expr_get_val (expr
);
555 mpz_init (val_mpz_t
);
557 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
560 res
= gmp_cst_to_tree (type
, val_mpz_t
);
562 isl_ast_expr_free (expr
);
563 mpz_clear (val_mpz_t
);
567 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
571 translate_isl_ast_to_gimple::
572 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
574 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
575 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
576 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
577 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
579 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
580 isl_ast_expr_free (expr
);
588 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
591 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
594 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
597 /* As isl operates on arbitrary precision numbers, we may end up with
598 division by 2^64 that is folded to 0. */
599 if (integer_zerop (tree_rhs_expr
))
601 codegen_error
= true;
604 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
606 case isl_ast_op_pdiv_q
:
607 /* As isl operates on arbitrary precision numbers, we may end up with
608 division by 2^64 that is folded to 0. */
609 if (integer_zerop (tree_rhs_expr
))
611 codegen_error
= true;
614 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
616 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
617 /* isl 0.15 or later. */
618 case isl_ast_op_zdiv_r
:
620 case isl_ast_op_pdiv_r
:
621 /* As isl operates on arbitrary precision numbers, we may end up with
622 division by 2^64 that is folded to 0. */
623 if (integer_zerop (tree_rhs_expr
))
625 codegen_error
= true;
628 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
630 case isl_ast_op_fdiv_q
:
631 /* As isl operates on arbitrary precision numbers, we may end up with
632 division by 2^64 that is folded to 0. */
633 if (integer_zerop (tree_rhs_expr
))
635 codegen_error
= true;
638 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
641 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
642 tree_lhs_expr
, tree_rhs_expr
);
645 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
648 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
651 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
654 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
657 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
660 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
667 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
671 translate_isl_ast_to_gimple::
672 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
674 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
675 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
677 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
678 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
679 tree tree_second_expr
680 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
681 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
683 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
684 isl_ast_expr_free (expr
);
688 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
689 tree_second_expr
, tree_third_expr
);
692 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
696 translate_isl_ast_to_gimple::
697 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
699 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
700 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
701 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
702 isl_ast_expr_free (expr
);
703 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
706 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
707 to a GCC expression tree of type TYPE. */
710 translate_isl_ast_to_gimple::
711 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
713 enum tree_code op_code
;
714 switch (isl_ast_expr_get_op_type (expr
))
727 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
728 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
732 isl_ast_expr_free (expr
);
737 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
739 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
740 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
744 isl_ast_expr_free (expr
);
748 res
= fold_build2 (op_code
, type
, res
, t
);
750 isl_ast_expr_free (expr
);
754 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
758 translate_isl_ast_to_gimple::
759 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
764 isl_ast_expr_free (expr
);
768 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
769 switch (isl_ast_expr_get_op_type (expr
))
771 /* These isl ast expressions are not supported yet. */
772 case isl_ast_op_error
:
773 case isl_ast_op_call
:
774 case isl_ast_op_and_then
:
775 case isl_ast_op_or_else
:
776 case isl_ast_op_select
:
781 return nary_op_to_tree (type
, expr
, ip
);
787 case isl_ast_op_pdiv_q
:
788 case isl_ast_op_pdiv_r
:
789 case isl_ast_op_fdiv_q
:
790 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
791 /* isl 0.15 or later. */
792 case isl_ast_op_zdiv_r
:
801 return binary_op_to_tree (type
, expr
, ip
);
803 case isl_ast_op_minus
:
804 return unary_op_to_tree (type
, expr
, ip
);
806 case isl_ast_op_cond
:
807 return ternary_op_to_tree (type
, expr
, ip
);
816 /* Converts an isl AST expression E back to a GCC expression tree of
820 translate_isl_ast_to_gimple::
821 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
826 isl_ast_expr_free (expr
);
830 switch (isl_ast_expr_get_type (expr
))
832 case isl_ast_expr_id
:
833 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
835 case isl_ast_expr_int
:
836 return gcc_expression_from_isl_expr_int (type
, expr
);
838 case isl_ast_expr_op
:
839 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
848 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
849 induction variable for the new LOOP. New LOOP is attached to CFG
850 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
851 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
852 isl's scattering name to the induction variable created for the
853 loop of STMT. The new induction variable is inserted in the NEWIVS
854 vector and is of type TYPE. */
857 translate_isl_ast_to_gimple::
858 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
859 loop_p outer
, tree type
, tree lb
, tree ub
,
862 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
863 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
865 /* To fail code generation, we generate wrong code until we discard it. */
867 stride
= integer_zero_node
;
869 tree ivvar
= create_tmp_var (type
, "graphite_IV");
870 tree iv
, iv_after_increment
;
871 loop_p loop
= create_empty_loop_on_edge
872 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
873 outer
? outer
: entry_edge
->src
->loop_father
);
875 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
876 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
877 std::map
<isl_id
*, tree
>::iterator res
;
880 isl_id_free (res
->first
);
882 isl_ast_expr_free (for_iterator
);
886 /* Create the loop for a isl_ast_node_for.
888 - NEXT_E is the edge where new generated code should be attached. */
891 translate_isl_ast_to_gimple::
892 translate_isl_ast_for_loop (loop_p context_loop
,
893 __isl_keep isl_ast_node
*node_for
, edge next_e
,
894 tree type
, tree lb
, tree ub
,
897 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
898 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
900 edge last_e
= single_exit (loop
);
901 edge to_body
= single_succ_edge (loop
->header
);
902 basic_block after
= to_body
->dest
;
904 /* Translate the body of the loop. */
905 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
906 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
907 isl_ast_node_free (for_body
);
909 /* Early return if we failed to translate loop body. */
910 if (!next_e
|| codegen_error_p ())
913 if (next_e
->dest
!= after
)
914 redirect_edge_succ_nodup (next_e
, after
);
915 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
917 if (flag_loop_parallelize_all
)
919 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
921 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
922 loop
->can_be_parallel
= for_info
->is_parallelizable
;
930 /* We use this function to get the upper bound because of the form,
931 which is used by isl to represent loops:
933 for (iterator = init; cond; iterator += inc)
941 The loop condition is an arbitrary expression, which contains the
942 current loop iterator.
944 (e.g. iterator + 3 < B && C > iterator + A)
946 We have to know the upper bound of the iterator to generate a loop
947 in Gimple form. It can be obtained from the special representation
948 of the loop condition, which is generated by isl,
949 if the ast_build_atomic_upper_bound option is set. In this case,
950 isl generates a loop condition that consists of the current loop
951 iterator, + an operator (< or <=) and an expression not involving
952 the iterator, which is processed and returned by this function.
954 (e.g iterator <= upper-bound-expression-without-iterator) */
956 static __isl_give isl_ast_expr
*
957 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
959 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
960 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
961 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
963 switch (isl_ast_expr_get_op_type (for_cond
))
966 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
971 /* (iterator < ub) => (iterator <= ub - 1). */
973 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
974 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
975 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
982 isl_ast_expr_free (for_cond
);
986 /* All loops generated by create_empty_loop_on_edge have the form of
993 } while (lower bound < upper bound);
995 We create a new if region protecting the loop to be executed, if
996 the execution count is zero (lower bound > upper bound). */
999 translate_isl_ast_to_gimple::
1000 graphite_create_new_loop_guard (edge entry_edge
,
1001 __isl_keep isl_ast_node
*node_for
, tree
*type
,
1002 tree
*lb
, tree
*ub
, ivs_params
&ip
)
1004 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
1009 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1010 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
1011 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
1012 /* To fail code generation, we generate wrong code until we discard it. */
1014 *lb
= integer_zero_node
;
1015 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
1016 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
1017 /* To fail code generation, we generate wrong code until we discard it. */
1019 *ub
= integer_zero_node
;
1021 /* When ub is simply a constant or a parameter, use lb <= ub. */
1022 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
1023 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
1026 tree one
= (POINTER_TYPE_P (*type
)
1027 ? convert_to_ptrofftype (integer_one_node
)
1028 : fold_convert (*type
, integer_one_node
));
1029 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1030 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1031 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1032 is true, even if we do not want this. However lb < ub + 1 is false,
1034 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1035 : PLUS_EXPR
, *type
, *ub
, one
);
1037 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1040 if (integer_onep (cond_expr
))
1041 exit_edge
= entry_edge
;
1043 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1048 /* Translates an isl_ast_node_for to Gimple. */
1051 translate_isl_ast_to_gimple::
1052 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1053 edge next_e
, ivs_params
&ip
)
1055 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1057 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1060 if (last_e
== next_e
)
1062 /* There was no guard generated. */
1063 last_e
= single_succ_edge (split_edge (last_e
));
1065 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1070 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1071 merge_points
.safe_push (last_e
);
1073 last_e
= single_succ_edge (split_edge (last_e
));
1074 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1079 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1080 variables of the loops around GBB in SESE.
1082 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1083 chrec, we could consider using a map<int, tree> that maps loop ids to the
1084 corresponding tree expressions. */
1087 translate_isl_ast_to_gimple::
1088 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1089 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1092 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1093 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1095 isl_ast_expr
*arg_expr
;
1096 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1098 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1100 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1101 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1102 /* To fail code generation, we generate wrong code until we discard it. */
1104 t
= integer_zero_node
;
1106 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1107 iv_map
[old_loop
->num
] = t
;
1111 /* Translates an isl_ast_node_user to Gimple.
1113 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1116 translate_isl_ast_to_gimple::
1117 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1118 edge next_e
, ivs_params
&ip
)
1120 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1122 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1123 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1124 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1126 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1127 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1130 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1132 isl_ast_expr_free (name_expr
);
1133 isl_id_free (name_id
);
1135 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1136 "The entry block should not even appear within a scop");
1138 const int nb_loops
= number_of_loops (cfun
);
1140 iv_map
.create (nb_loops
);
1141 iv_map
.safe_grow_cleared (nb_loops
);
1143 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1144 isl_ast_expr_free (user_expr
);
1146 basic_block old_bb
= GBB_BB (gbb
);
1150 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1151 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1152 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1156 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1160 if (codegen_error_p ())
1165 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1166 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1172 /* Translates an isl_ast_node_block to Gimple. */
1175 translate_isl_ast_to_gimple::
1176 translate_isl_ast_node_block (loop_p context_loop
,
1177 __isl_keep isl_ast_node
*node
,
1178 edge next_e
, ivs_params
&ip
)
1180 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1181 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1183 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1185 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1186 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1187 isl_ast_node_free (tmp_node
);
1189 isl_ast_node_list_free (node_list
);
1193 /* Creates a new if region corresponding to isl's cond. */
1196 translate_isl_ast_to_gimple::
1197 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1201 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1202 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1203 /* To fail code generation, we generate wrong code until we discard it. */
1205 cond_expr
= integer_zero_node
;
1207 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1211 /* Translates an isl_ast_node_if to Gimple. */
1214 translate_isl_ast_to_gimple::
1215 translate_isl_ast_node_if (loop_p context_loop
,
1216 __isl_keep isl_ast_node
*node
,
1217 edge next_e
, ivs_params
&ip
)
1219 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1220 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1221 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1222 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1223 merge_points
.safe_push (last_e
);
1225 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1226 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1227 isl_ast_node_free (then_node
);
1229 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1230 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1231 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1232 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1234 isl_ast_node_free (else_node
);
1238 /* Translates an isl AST node NODE to GCC representation in the
1239 context of a SESE. */
1242 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1243 __isl_keep isl_ast_node
*node
,
1244 edge next_e
, ivs_params
&ip
)
1246 if (codegen_error_p ())
1249 switch (isl_ast_node_get_type (node
))
1251 case isl_ast_node_error
:
1254 case isl_ast_node_for
:
1255 return translate_isl_ast_node_for (context_loop
, node
,
1258 case isl_ast_node_if
:
1259 return translate_isl_ast_node_if (context_loop
, node
,
1262 case isl_ast_node_user
:
1263 return translate_isl_ast_node_user (node
, next_e
, ip
);
1265 case isl_ast_node_block
:
1266 return translate_isl_ast_node_block (context_loop
, node
,
1269 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1270 case isl_ast_node_mark
:
1272 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1273 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1274 isl_ast_node_free (n
);
1284 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1285 at the exit of loop which takes one argument that is the last value of the
1286 variable being used out of the loop. */
1289 bb_contains_loop_close_phi_nodes (basic_block bb
)
1291 return single_pred_p (bb
)
1292 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1295 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1296 header containing phi nodes which has one init-edge and one back-edge. */
1299 bb_contains_loop_phi_nodes (basic_block bb
)
1301 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1303 if (bb
->preds
->length () == 1)
1306 unsigned depth
= loop_depth (bb
->loop_father
);
1308 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1310 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1311 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1314 /* When one of the edges correspond to the same loop father and other
1316 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1317 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1320 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1321 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1327 /* Check if USE is defined in a basic block from where the definition of USE can
1328 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1331 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1333 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1336 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1337 if (bb_contains_loop_close_phi_nodes (bb
))
1340 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1341 basic_block def_bb
= gimple_bb (def
);
1343 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1346 /* Return the number of phi nodes in BB. */
1349 number_of_phi_nodes (basic_block bb
)
1352 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1358 /* Returns true if BB uses name in one of its PHIs. */
1361 phi_uses_name (basic_block bb
, tree name
)
1363 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1366 gphi
*phi
= psi
.phi ();
1367 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1369 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1370 if (use_arg
== name
)
1377 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1378 definition should flow into use, and the use should respect the loop-closed
1382 translate_isl_ast_to_gimple::
1383 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1384 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1386 /* The def of the rename must either dominate the uses or come from a
1387 back-edge. Also the def must respect the loop closed ssa form. */
1388 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1392 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1393 print_generic_expr (dump_file
, rename
, 0);
1394 fprintf (dump_file
, "\n");
1399 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1402 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1404 /* The loop-header dominates the loop-body. */
1405 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1408 /* RENAME would be used in loop-phi. */
1409 gcc_assert (number_of_phi_nodes (use_bb
));
1411 /* For definitions coming from back edges, we should check that
1412 old_name is used in a loop PHI node.
1413 FIXME: Verify if this is true. */
1414 if (phi_uses_name (old_bb
, old_name
))
1420 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1421 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1424 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1427 phi_node_kind phi_kind
) const
1429 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1430 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1432 if (!renames
|| renames
->is_empty ())
1435 if (1 == renames
->length ())
1437 tree rename
= (*renames
)[0];
1438 if (TREE_CODE (rename
) == SSA_NAME
)
1440 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1441 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1442 && (phi_kind
== close_phi
1443 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1448 if (is_constant (rename
))
1454 /* More than one renames corresponding to the old_name. Find the rename for
1455 which the definition flows into usage at new_bb. */
1457 tree t1
= NULL_TREE
, t2
;
1458 basic_block t1_bb
= NULL
;
1459 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1461 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1463 /* Defined in the same basic block as used. */
1464 if (t2_bb
== new_bb
)
1467 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1468 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1471 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1474 /* Compute the nearest dominator. */
1475 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1485 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1486 When OLD_NAME and EXPR are the same we assert. */
1489 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1493 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1494 print_generic_expr (dump_file
, old_name
, 0);
1495 fprintf (dump_file
, ", new_name = ");
1496 print_generic_expr (dump_file
, expr
, 0);
1497 fprintf (dump_file
, "\n");
1500 if (old_name
== expr
)
1503 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1506 renames
->safe_push (expr
);
1512 region
->rename_map
->put (old_name
, r
);
1517 /* For a parameter of a scop we don't want to rename it. */
1518 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1520 region
->parameter_rename_map
->put(old_name
, expr
);
1523 /* Return an iterator to the instructions comes last in the execution order.
1524 Either GSI1 and GSI2 should belong to the same basic block or one of their
1525 respective basic blocks should dominate the other. */
1527 gimple_stmt_iterator
1528 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1530 basic_block bb1
= gsi_bb (gsi1
);
1531 basic_block bb2
= gsi_bb (gsi2
);
1533 /* Find the iterator which is the latest. */
1536 /* For empty basic blocks gsis point to the end of the sequence. Since
1537 there is no operator== defined for gimple_stmt_iterator and for gsis
1538 not pointing to a valid statement gsi_next would assert. */
1539 gimple_stmt_iterator gsi
= gsi1
;
1541 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1544 } while (!gsi_end_p (gsi
));
1549 /* Find the basic block closest to the basic block which defines stmt. */
1550 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1553 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1557 /* Insert each statement from SEQ at its earliest insertion p. */
1560 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1562 update_modified_stmts (seq
);
1563 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1564 basic_block begin_bb
= get_entry_bb (codegen_region
);
1566 /* Inserting the gimple statements in a vector because gimple_seq behave
1567 in strage ways when inserting the stmts from it into different basic
1568 blocks one at a time. */
1569 auto_vec
<gimple
*, 3> stmts
;
1570 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1572 stmts
.safe_push (gsi_stmt (gsi
));
1576 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1578 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1579 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1581 use_operand_p use_p
;
1582 ssa_op_iter op_iter
;
1583 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1585 /* Iterator to the current def of use_p. For function parameters or
1586 anything where def is not found, insert at the beginning of the
1587 generated region. */
1588 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1590 tree op
= USE_FROM_PTR (use_p
);
1591 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1592 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1593 gsi_stmt
= gsi_for_stmt (stmt
);
1595 /* For region parameters, insert at the beginning of the generated
1597 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1598 gsi_stmt
= gsi_def_stmt
;
1600 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1603 if (!gsi_stmt (gsi_def_stmt
))
1605 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1606 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1608 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1610 gimple_stmt_iterator bsi
1611 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1612 /* Insert right after the PHI statements. */
1613 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1616 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1620 fprintf (dump_file
, "[codegen] inserting statement: ");
1621 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1622 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1627 /* Collect all the operands of NEW_EXPR by recursively visiting each
1631 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1635 /* Rename all uses in new_expr. */
1636 if (TREE_CODE (new_expr
) == SSA_NAME
)
1638 vec_ssa
->safe_push (new_expr
);
1642 /* Iterate over SSA_NAMES in NEW_EXPR. */
1643 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1645 tree op
= TREE_OPERAND (new_expr
, i
);
1646 collect_all_ssa_names (op
, vec_ssa
);
1650 /* This is abridged version of the function copied from:
1651 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1654 substitute_ssa_name (tree exp
, tree f
, tree r
)
1656 enum tree_code code
= TREE_CODE (exp
);
1657 tree op0
, op1
, op2
, op3
;
1660 /* We handle TREE_LIST and COMPONENT_REF separately. */
1661 if (code
== TREE_LIST
)
1663 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1664 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1665 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1668 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1670 else if (code
== COMPONENT_REF
)
1674 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1675 and it is the right field, replace it with R. */
1676 for (inner
= TREE_OPERAND (exp
, 0);
1677 REFERENCE_CLASS_P (inner
);
1678 inner
= TREE_OPERAND (inner
, 0))
1682 op1
= TREE_OPERAND (exp
, 1);
1684 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1687 /* If this expression hasn't been completed let, leave it alone. */
1688 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1691 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1692 if (op0
== TREE_OPERAND (exp
, 0))
1696 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1699 switch (TREE_CODE_CLASS (code
))
1704 case tcc_declaration
:
1710 case tcc_expression
:
1714 /* Fall through... */
1716 case tcc_exceptional
:
1719 case tcc_comparison
:
1721 switch (TREE_CODE_LENGTH (code
))
1729 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1730 if (op0
== TREE_OPERAND (exp
, 0))
1733 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1737 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1738 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1740 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1743 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1747 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1748 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1749 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1751 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1752 && op2
== TREE_OPERAND (exp
, 2))
1755 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1759 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1760 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1761 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1762 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1764 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1765 && op2
== TREE_OPERAND (exp
, 2)
1766 && op3
== TREE_OPERAND (exp
, 3))
1770 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1783 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1785 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1786 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1791 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1794 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1797 auto_vec
<tree
, 2> ssa_names
;
1798 collect_all_ssa_names (new_expr
, &ssa_names
);
1801 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1802 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1803 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1808 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1809 scalar evolution around LOOP. */
1812 translate_isl_ast_to_gimple::
1813 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1814 basic_block new_bb
, basic_block old_bb
,
1817 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1819 /* At this point we should know the exact scev for each
1820 scalar SSA_NAME used in the scop: all the other scalar
1821 SSA_NAMEs should have been translated out of SSA using
1822 arrays with one element. */
1824 if (chrec_contains_undetermined (scev
))
1826 codegen_error
= true;
1827 return build_zero_cst (TREE_TYPE (old_name
));
1830 new_expr
= chrec_apply_map (scev
, iv_map
);
1832 /* The apply should produce an expression tree containing
1833 the uses of the new induction variables. We should be
1834 able to use new_expr instead of the old_name in the newly
1835 generated loop nest. */
1836 if (chrec_contains_undetermined (new_expr
)
1837 || tree_contains_chrecs (new_expr
, NULL
))
1839 codegen_error
= true;
1840 return build_zero_cst (TREE_TYPE (old_name
));
1843 /* We should check all the operands and all of them should dominate the use at
1845 if (TREE_CODE (new_expr
) == SSA_NAME
)
1847 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1848 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1850 codegen_error
= true;
1851 return build_zero_cst (TREE_TYPE (old_name
));
1855 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1857 /* We check all the operands and all of them should dominate the use at
1859 auto_vec
<tree
, 2> new_ssa_names
;
1860 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1863 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1865 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1867 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1868 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1870 codegen_error
= true;
1871 return build_zero_cst (TREE_TYPE (old_name
));
1876 /* Replace the old_name with the new_expr. */
1877 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1881 /* Renames the scalar uses of the statement COPY, using the
1882 substitution map RENAME_MAP, inserting the gimplification code at
1883 GSI_TGT, for the translation REGION, with the original copied
1884 statement in LOOP, and using the induction variable renaming map
1885 IV_MAP. Returns true when something has been renamed. codegen_error
1886 is set when the code generation cannot continue. */
1889 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1890 gimple_stmt_iterator
*gsi_tgt
,
1892 loop_p loop
, vec
<tree
> iv_map
)
1894 bool changed
= false;
1896 if (is_gimple_debug (copy
))
1898 if (gimple_debug_bind_p (copy
))
1899 gimple_debug_bind_reset_value (copy
);
1900 else if (gimple_debug_source_bind_p (copy
))
1910 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1911 print_gimple_stmt (dump_file
, copy
, 0, 0);
1914 use_operand_p use_p
;
1915 ssa_op_iter op_iter
;
1916 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1918 tree old_name
= USE_FROM_PTR (use_p
);
1922 fprintf (dump_file
, "[codegen] renaming old_name = ");
1923 print_generic_expr (dump_file
, old_name
, 0);
1924 fprintf (dump_file
, "\n");
1927 if (TREE_CODE (old_name
) != SSA_NAME
1928 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1932 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1933 old_bb
, unknown_phi
);
1937 tree type_old_name
= TREE_TYPE (old_name
);
1938 tree type_new_expr
= TREE_TYPE (new_expr
);
1942 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1943 print_generic_expr (dump_file
, new_expr
, 0);
1944 fprintf (dump_file
, "\n");
1947 if (type_old_name
!= type_new_expr
1948 || TREE_CODE (new_expr
) != SSA_NAME
)
1950 tree var
= create_tmp_var (type_old_name
, "var");
1952 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1953 new_expr
= fold_convert (type_old_name
, new_expr
);
1956 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1957 gsi_insert_earliest (stmts
);
1960 replace_exp (use_p
, new_expr
);
1965 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1967 if (!new_expr
|| codegen_error_p ())
1972 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1973 print_generic_expr (dump_file
, new_expr
, 0);
1974 fprintf (dump_file
, "\n");
1977 gsi_insert_earliest (stmts
);
1978 replace_exp (use_p
, new_expr
);
1980 if (TREE_CODE (new_expr
) == INTEGER_CST
1981 && is_gimple_assign (copy
))
1983 tree rhs
= gimple_assign_rhs1 (copy
);
1985 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1986 recompute_tree_invariant_for_addr_expr (rhs
);
1989 set_rename (old_name
, new_expr
);
1995 /* Returns a basic block that could correspond to where a constant was defined
1996 in the original code. In the original code OLD_BB had the definition, we
1997 need to find which basic block out of the copies of old_bb, in the new
1998 region, should a definition correspond to if it has to reach BB. */
2001 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
2002 basic_block old_bb
) const
2004 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
2006 if (!bbs
|| bbs
->is_empty ())
2009 if (1 == bbs
->length ())
2013 basic_block b1
= NULL
, b2
;
2014 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
2019 /* BB and B2 are in two unrelated if-clauses. */
2020 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
2023 /* Compute the nearest dominator. */
2024 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
2032 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
2033 determines the kind of phi node. */
2036 translate_isl_ast_to_gimple::
2037 get_new_name (basic_block new_bb
, tree op
,
2038 basic_block old_bb
, phi_node_kind phi_kind
) const
2040 /* For constants the names are the same. */
2041 if (is_constant (op
))
2044 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
2047 /* Return a debug location for OP. */
2052 location_t loc
= UNKNOWN_LOCATION
;
2054 if (TREE_CODE (op
) == SSA_NAME
)
2055 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2059 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2060 the init edge (from outside the loop) and the second one is the back edge
2061 from the same loop. */
2063 std::pair
<edge
, edge
>
2064 get_edges (basic_block bb
)
2066 std::pair
<edge
, edge
> edges
;
2069 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2070 if (bb
->loop_father
!= e
->src
->loop_father
)
2077 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2078 must be found unless they can be POSTPONEd for later. */
2081 translate_isl_ast_to_gimple::
2082 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2083 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2086 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2088 basic_block new_bb
= gimple_bb (new_phi
);
2089 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2092 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2093 e
= ibp_new_bb
.first
;
2095 e
= ibp_new_bb
.second
;
2097 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2098 tree new_name
= get_new_name (new_bb
, old_name
,
2099 gimple_bb (old_phi
), loop_phi
);
2102 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2106 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2107 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2108 /* If the phi arg was a function arg, or wasn't defined, just use the
2110 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2113 /* Postpone code gen for later for those back-edges we don't have the
2115 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2117 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2120 /* Either we should add the arg to phi or, we should postpone. */
2126 /* Copy loop phi nodes from BB to NEW_BB. */
2129 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2133 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2136 /* Loop phi nodes should have only two arguments. */
2137 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2139 /* First edge is the init edge and second is the back edge. */
2140 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2142 /* First edge is the init edge and second is the back edge. */
2143 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2145 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2148 gphi
*phi
= psi
.phi ();
2149 tree res
= gimple_phi_result (phi
);
2150 if (virtual_operand_p (res
))
2152 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2155 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2156 tree new_res
= create_new_def_for (res
, new_phi
,
2157 gimple_phi_result_ptr (new_phi
));
2158 set_rename (res
, new_res
);
2159 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2161 update_stmt (new_phi
);
2165 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2166 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2173 /* Return the init value of PHI, the value coming from outside the loop. */
2176 get_loop_init_value (gphi
*phi
)
2179 loop_p loop
= gimple_bb (phi
)->loop_father
;
2183 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2184 if (e
->src
->loop_father
!= loop
)
2185 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2190 /* Find the init value (the value which comes from outside the loop), of one of
2191 the operands of DEF which is defined by a loop phi. */
2194 find_init_value (gimple
*def
)
2196 if (gimple_code (def
) == GIMPLE_PHI
)
2197 return get_loop_init_value (as_a
<gphi
*> (def
));
2199 if (gimple_vuse (def
))
2203 use_operand_p use_p
;
2204 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2206 tree use
= USE_FROM_PTR (use_p
);
2207 if (TREE_CODE (use
) == SSA_NAME
)
2209 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2217 /* Return the init value, the value coming from outside the loop. */
2220 find_init_value_close_phi (gphi
*phi
)
2222 gcc_assert (gimple_phi_num_args (phi
) == 1);
2223 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2224 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2225 return find_init_value (def
);
2229 tree
translate_isl_ast_to_gimple::
2230 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2231 gimple
*old_close_phi
)
2233 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2234 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2235 basic_block bb
= gimple_bb (stmt
);
2236 if (!bb_in_sese_p (bb
, codegen_region
))
2237 return last_merge_name
;
2239 loop_p loop
= bb
->loop_father
;
2240 if (!loop_in_sese_p (loop
, codegen_region
))
2241 return last_merge_name
;
2243 edge e
= single_exit (loop
);
2245 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2246 return last_merge_name
;
2248 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2249 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2252 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2253 bb
= split_edge (e
);
2255 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2256 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2257 gimple_phi_result_ptr (close_phi
));
2258 set_rename (old_close_phi_name
, res
);
2259 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2260 last_merge_name
= res
;
2262 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2265 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2266 the close phi node PHI. */
2268 bool translate_isl_ast_to_gimple::
2269 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2272 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2273 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2274 if (SSA_NAME
== TREE_CODE (default_value
))
2276 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2277 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2279 default_value_bb
= gimple_bb (stmt
);
2282 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2284 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2285 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2286 tree last_merge_name
= new_close_phi_name
;
2287 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2291 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2293 basic_block new_merge_bb
= merge_e
->src
;
2294 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2297 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2300 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2301 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2302 gimple_phi_result_ptr (merge_phi
));
2303 set_rename (old_close_phi_name
, merge_res
);
2305 edge from_loop
= NULL
, from_default_value
= NULL
;
2308 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2309 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2312 from_default_value
= e
;
2314 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2315 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2316 is contained in another condition. */
2317 if (!from_default_value
|| !from_loop
)
2320 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2321 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2325 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2326 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2329 update_stmt (merge_phi
);
2330 last_merge_name
= merge_res
;
2336 /* Copy all the loop-close phi args from BB to NEW_BB. */
2339 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2343 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2346 gphi
*old_close_phi
= psi
.phi ();
2347 tree res
= gimple_phi_result (old_close_phi
);
2348 if (virtual_operand_p (res
))
2351 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2352 /* Loop close phi nodes should not be scev_analyzable_p. */
2355 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2356 tree new_res
= create_new_def_for (res
, new_close_phi
,
2357 gimple_phi_result_ptr (new_close_phi
));
2358 set_rename (res
, new_res
);
2360 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2361 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2363 /* Predecessor basic blocks of a loop close phi should have been code
2364 generated before. FIXME: This is fixable by merging PHIs from inner
2365 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2369 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2370 get_loc (old_name
));
2373 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2374 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2377 update_stmt (new_close_phi
);
2379 /* When there is no loop guard around this codegenerated loop, there is no
2380 need to collect the close-phi arg. */
2381 if (merge_points
.is_empty ())
2384 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2385 tree default_value
= find_init_value_close_phi (new_close_phi
);
2387 /* A close phi must come from a loop-phi having a default value. */
2393 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2397 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2398 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2403 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2411 /* Copy loop close phi nodes from BB to NEW_BB. */
2414 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2418 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2420 /* Loop close phi nodes should have only one argument. */
2421 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2423 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2427 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2428 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2429 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2430 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2433 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2434 In this case DOMINATING_PRED = NULL.
2436 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2438 Returns true on successful copy of the args, false otherwise. */
2441 translate_isl_ast_to_gimple::
2442 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2443 edge old_bb_dominating_edge
,
2444 edge old_bb_non_dominating_edge
,
2445 gphi
*phi
, gphi
*new_phi
,
2448 basic_block def_pred
[2] = { NULL
, NULL
};
2449 int not_found_bb_index
= -1;
2450 for (int i
= 0; i
< 2; i
++)
2452 /* If the corresponding def_bb could not be found the entry will be
2454 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2455 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2456 gimple_phi_arg_edge (phi
, i
)->src
);
2457 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2458 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2462 /* When non are available bail out. */
2463 if (not_found_bb_index
!= -1)
2465 not_found_bb_index
= i
;
2469 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2470 if (old_bb_dominating_edge
)
2472 if (not_found_bb_index
!= -1)
2475 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2476 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2477 vec
<basic_block
> *bbs
2478 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2480 /* Could not find a mapping. */
2484 basic_block new_pred
= NULL
;
2487 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2489 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2491 /* FIXME: If we have already found new_pred then we have to
2492 disambiguate, bail out for now. */
2495 new_pred
= new_pred1
;
2497 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2499 /* FIXME: If we have already found new_pred then we have to either
2500 it dominates both or we have to disambiguate, bail out. */
2503 new_pred
= new_pred2
;
2510 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2511 gcc_assert (new_non_dominating_edge
);
2512 /* FIXME: Validate each args just like in loop-phis. */
2513 /* By the process of elimination we first insert insert phi-edge for
2514 non-dominating pred which is computed above and then we insert the
2516 int inserted_edge
= 0;
2517 for (; inserted_edge
< 2; inserted_edge
++)
2519 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2520 if (new_non_dominating_edge
== new_bb_pred_edge
)
2522 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2523 new_non_dominating_edge
,
2524 get_loc (old_phi_args
[inserted_edge
]));
2528 if (inserted_edge
== 2)
2531 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2533 edge new_dominating_edge
= NULL
;
2534 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2536 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2537 if (e
!= new_non_dominating_edge
)
2539 new_dominating_edge
= e
;
2540 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2541 new_dominating_edge
,
2542 get_loc (old_phi_args
[inserted_edge
]));
2546 gcc_assert (new_dominating_edge
);
2550 /* Classic diamond structure: both edges are non-dominating. We need to
2551 find one unique edge then the other can be found be elimination. If
2552 any definition (def_pred) dominates both the preds of new_bb then we
2553 bail out. Entries of def_pred maybe NULL, in that case we must
2554 uniquely find pred with help of only one entry. */
2555 edge new_e
[2] = { NULL
, NULL
};
2556 for (int i
= 0; i
< 2; i
++)
2560 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2562 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2565 /* We do not know how to handle the case when def_pred
2566 dominates more than a predecessor. */
2572 gcc_assert (new_e
[0] || new_e
[1]);
2574 /* Find the other edge by process of elimination. */
2575 if (not_found_bb_index
!= -1)
2577 gcc_assert (!new_e
[not_found_bb_index
]);
2578 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2581 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2583 if (new_e
[found_bb_index
] == e
)
2585 new_e
[not_found_bb_index
] = e
;
2589 /* Add edges to phi args. */
2590 for (int i
= 0; i
< 2; i
++)
2591 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2592 get_loc (old_phi_args
[i
]));
2598 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2599 region. If postpone is true and it isn't possible to copy any arg of PHI,
2600 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2601 Returns false if the copying was unsuccessful. */
2604 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2609 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2610 gcc_assert (2 == gimple_phi_num_args (phi
));
2612 basic_block new_bb
= gimple_bb (new_phi
);
2613 loop_p loop
= gimple_bb (phi
)->loop_father
;
2615 basic_block old_bb
= gimple_bb (phi
);
2616 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2620 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2621 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2622 old_bb_non_dominating_edge
= e
;
2624 old_bb_dominating_edge
= e
;
2626 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2627 old_bb_non_dominating_edge
->src
));
2629 tree new_phi_args
[2];
2630 tree old_phi_args
[2];
2632 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2634 tree old_name
= gimple_phi_arg_def (phi
, i
);
2635 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2636 old_phi_args
[i
] = old_name
;
2639 new_phi_args
[i
] = new_name
;
2643 /* If the phi-arg was a parameter. */
2644 if (vec_find (region
->params
, old_name
) != -1)
2646 new_phi_args
[i
] = old_name
;
2650 "[codegen] parameter argument to phi, new_expr: ");
2651 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2652 fprintf (dump_file
, "\n");
2657 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2658 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2659 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2665 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2666 if (is_gimple_reg (old_name
)
2667 && scev_analyzable_p (old_name
, region
->region
))
2670 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2671 new_bb
, old_bb
, iv_map
);
2672 if (codegen_error_p ())
2675 gcc_assert (new_expr
);
2679 "[codegen] scev analyzeable, new_expr: ");
2680 print_generic_expr (dump_file
, new_expr
, 0);
2681 fprintf (dump_file
, "\n");
2683 gsi_insert_earliest (stmts
);
2684 new_phi_args
[i
] = new_name
;
2688 /* Postpone code gen for later for back-edges. */
2689 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2693 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2694 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2697 new_phi_args
[i
] = NULL_TREE
;
2701 /* Either we should add the arg to phi or, we should postpone. */
2705 /* If none of the args have been determined in the first stage then wait until
2707 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2710 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2711 old_bb_dominating_edge
,
2712 old_bb_non_dominating_edge
,
2713 phi
, new_phi
, new_bb
);
2716 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2717 containing phi nodes coming from two predecessors, and none of them are back
2721 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2726 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2729 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2732 /* Cond phi nodes should have exactly two arguments. */
2733 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2735 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2738 gphi
*phi
= psi
.phi ();
2739 tree res
= gimple_phi_result (phi
);
2740 if (virtual_operand_p (res
))
2742 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2743 /* Cond phi nodes should not be scev_analyzable_p. */
2746 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2747 tree new_res
= create_new_def_for (res
, new_phi
,
2748 gimple_phi_result_ptr (new_phi
));
2749 set_rename (res
, new_res
);
2751 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2754 update_stmt (new_phi
);
2760 /* Return true if STMT should be copied from region to the new code-generated
2761 region. LABELs, CONDITIONS, induction-variables and region parameters need
2765 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2767 /* Do not copy labels or conditions. */
2768 if (gimple_code (stmt
) == GIMPLE_LABEL
2769 || gimple_code (stmt
) == GIMPLE_COND
)
2773 /* Do not copy induction variables. */
2774 if (is_gimple_assign (stmt
)
2775 && (lhs
= gimple_assign_lhs (stmt
))
2776 && TREE_CODE (lhs
) == SSA_NAME
2777 && is_gimple_reg (lhs
)
2778 && scev_analyzable_p (lhs
, region
->region
))
2781 /* Do not copy parameters that have been generated in the header of the
2783 if (is_gimple_assign (stmt
)
2784 && (lhs
= gimple_assign_lhs (stmt
))
2785 && TREE_CODE (lhs
) == SSA_NAME
2786 && region
->parameter_rename_map
->get(lhs
))
2792 /* Create new names for all the definitions created by COPY and add replacement
2793 mappings for each new name. */
2796 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2798 def_operand_p def_p
;
2799 ssa_op_iter op_iter
;
2800 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2802 tree old_name
= DEF_FROM_PTR (def_p
);
2803 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2804 set_rename (old_name
, new_name
);
2808 /* Duplicates the statements of basic block BB into basic block NEW_BB
2809 and compute the new induction variables according to the IV_MAP.
2810 CODEGEN_ERROR is set when the code generation cannot continue. */
2813 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2817 /* Iterator poining to the place where new statement (s) will be inserted. */
2818 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2820 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2823 gimple
*stmt
= gsi_stmt (gsi
);
2824 if (!should_copy_to_new_region (stmt
, region
))
2827 /* Create a new copy of STMT and duplicate STMT's virtual
2829 gimple
*copy
= gimple_copy (stmt
);
2830 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2834 fprintf (dump_file
, "[codegen] inserting statement: ");
2835 print_gimple_stmt (dump_file
, copy
, 0, 0);
2838 maybe_duplicate_eh_stmt (copy
, stmt
);
2839 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2841 /* Crete new names for each def in the copied stmt. */
2842 set_rename_for_each_def (copy
);
2844 loop_p loop
= bb
->loop_father
;
2845 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2847 fold_stmt_inplace (&gsi_tgt
);
2848 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2851 if (codegen_error_p ())
2854 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2856 use_operand_p use_p
;
2857 if (!is_gimple_debug (copy
))
2858 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2860 tree old_name
= USE_FROM_PTR (use_p
);
2862 if (TREE_CODE (old_name
) != SSA_NAME
2863 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2866 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2870 replace_exp (use_p
, *new_expr
);
2880 /* Given a basic block containing close-phi it returns the new basic block where
2881 to insert a copy of the close-phi nodes. All the uses in close phis should
2882 come from a single loop otherwise it returns NULL. */
2885 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2887 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2888 of close phi in the original code and then find the mapping of basic block
2889 defining that variable. If there are multiple close-phis and they are
2890 defined in different loops (in the original or in the new code) because of
2891 loop splitting, then we bail out. */
2892 loop_p new_loop
= NULL
;
2893 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2896 gphi
*phi
= psi
.phi ();
2897 tree name
= gimple_phi_arg_def (phi
, 0);
2898 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2900 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2901 if (!bbs
|| bbs
->length () != 1)
2902 /* This is one of the places which shows preserving original structure
2903 is not always possible, as we may need to insert close PHI for a loop
2904 where the latch does not have any mapping, or the mapping is
2909 new_loop
= (*bbs
)[0]->loop_father
;
2910 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2917 return single_exit (new_loop
);
2920 /* Copies BB and includes in the copied BB all the statements that can
2921 be reached following the use-def chains from the memory accesses,
2922 and returns the next edge following this new block. codegen_error is
2923 set when the code generation cannot continue. */
2926 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2930 int num_phis
= number_of_phi_nodes (bb
);
2932 if (region
->copied_bb_map
->get (bb
))
2934 /* FIXME: we should be able to handle phi nodes with args coming from
2935 outside the region. */
2938 codegen_error
= true;
2943 basic_block new_bb
= NULL
;
2944 if (bb_contains_loop_close_phi_nodes (bb
))
2947 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2950 edge e
= edge_for_new_close_phis (bb
);
2953 codegen_error
= true;
2957 basic_block phi_bb
= e
->dest
;
2959 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2960 phi_bb
= split_edge (e
);
2962 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2963 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2965 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2967 codegen_error
= true;
2974 new_bb
= split_edge (next_e
);
2978 new_bb
= split_edge (next_e
);
2979 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2981 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2983 /* At this point we are unable to codegenerate by still preserving the SSA
2984 structure because maybe the loop is completely unrolled and the PHIs
2985 and cross-bb scalar dependencies are untrackable w.r.t. the original
2986 code. See gfortran.dg/graphite/pr29832.f90. */
2987 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2989 codegen_error
= true;
2993 /* In case isl did some loop peeling, like this:
2996 for (int c1 = 1; c1 <= 5; c1 += 1) {
3001 there should be no loop-phi nodes in S_8(0).
3003 FIXME: We need to reason about dynamic instances of S_8, i.e., the
3004 values of all scalar variables: for the moment we instantiate only
3005 SCEV analyzable expressions on the iteration domain, and we need to
3006 extend that to reductions that cannot be analyzed by SCEV. */
3007 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
3009 codegen_error
= true;
3014 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
3016 if (!copy_loop_phi_nodes (bb
, phi_bb
))
3018 codegen_error
= true;
3022 else if (num_phis
> 0)
3025 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
3028 basic_block phi_bb
= single_pred (new_bb
);
3029 loop_p loop_father
= new_bb
->loop_father
;
3031 /* Move back until we find the block with two predecessors. */
3032 while (single_pred_p (phi_bb
))
3033 phi_bb
= single_pred_edge (phi_bb
)->src
;
3035 /* If a corresponding merge-point was not found, then abort codegen. */
3036 if (phi_bb
->loop_father
!= loop_father
3037 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
3038 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
3040 codegen_error
= true;
3047 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
3048 bb
->index
, new_bb
->index
);
3050 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
3052 copied_bbs
->safe_push (new_bb
);
3055 vec
<basic_block
> bbs
;
3057 bbs
.safe_push (new_bb
);
3058 region
->copied_bb_map
->put (bb
, bbs
);
3061 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3063 codegen_error
= true;
3067 return single_succ_edge (new_bb
);
3070 /* Patch the missing arguments of the phi nodes. */
3073 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3077 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3079 gphi
*old_phi
= rename
->first
;
3080 gphi
*new_phi
= rename
->second
;
3081 basic_block old_bb
= gimple_bb (old_phi
);
3082 basic_block new_bb
= gimple_bb (new_phi
);
3084 /* First edge is the init edge and second is the back edge. */
3085 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3086 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3090 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3091 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3094 auto_vec
<tree
, 1> iv_map
;
3095 if (bb_contains_loop_phi_nodes (new_bb
))
3096 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3098 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3099 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3101 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3105 fprintf (dump_file
, "[codegen] to new-phi: ");
3106 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3113 /* Prints NODE to FILE. */
3116 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3117 __isl_keep isl_ast_node
*node
,
3118 __isl_keep isl_ctx
*ctx
) const
3120 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3121 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3122 prn
= isl_printer_print_ast_node (prn
, node
);
3123 prn
= isl_printer_print_str (prn
, "\n");
3124 isl_printer_free (prn
);
3127 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
3130 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3133 sese_info_p region
= scop
->scop_info
;
3134 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3135 gcc_assert (nb_parameters
== region
->params
.length ());
3137 for (i
= 0; i
< nb_parameters
; i
++)
3139 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3141 ip
[tmp_id
] = region
->params
[i
];
3146 /* Generates a build, which specifies the constraints on the parameters. */
3148 __isl_give isl_ast_build
*
3149 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3151 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3152 return isl_ast_build_from_context (context_isl
);
3155 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3158 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3162 int schedule_dims
= 0;
3164 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3166 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3167 if (pbb_schedule_dims
> schedule_dims
)
3168 schedule_dims
= pbb_schedule_dims
;
3171 return schedule_dims
;
3174 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3176 For schedules with different dimensionality, the isl AST generator can not
3177 define an order and will just randomly choose an order. The solution to this
3178 problem is to extend all schedules to the maximal number of schedule
3179 dimensions (using '0's for the remaining values). */
3181 __isl_give isl_map
*
3182 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3183 int nb_schedule_dims
)
3185 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3187 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3189 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3191 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3194 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3196 isl_val_free (zero
);
3200 /* Generates a schedule, which specifies an order used to
3201 visit elements in a domain. */
3203 __isl_give isl_union_map
*
3204 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3206 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3209 isl_union_map
*schedule_isl
=
3210 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3212 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3214 /* Dead code elimination: when the domain of a PBB is empty,
3215 don't generate code for the PBB. */
3216 if (isl_set_is_empty (pbb
->domain
))
3219 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3220 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3221 isl_set_copy (pbb
->domain
));
3222 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3223 bb_schedule
= isl_map_coalesce (bb_schedule
);
3225 = isl_union_map_union (schedule_isl
,
3226 isl_union_map_from_map (bb_schedule
));
3227 schedule_isl
= isl_union_map_coalesce (schedule_isl
);
3229 return schedule_isl
;
3232 /* This method is executed before the construction of a for node. */
3234 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3236 isl_union_map
*dependences
= (isl_union_map
*) user
;
3237 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3238 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3239 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3240 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3241 for_info
->is_parallelizable
=
3242 !carries_deps (schedule
, dependences
, dimension
);
3243 isl_union_map_free (schedule
);
3244 isl_space_free (schedule_space
);
3245 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3249 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3250 /* Set the separate option for all schedules. This helps reducing control
3253 __isl_give isl_schedule
*
3254 translate_isl_ast_to_gimple::set_options_for_schedule_tree
3255 (__isl_take isl_schedule
*schedule
)
3257 return isl_schedule_map_schedule_node_bottom_up
3258 (schedule
, set_separate_option
, NULL
);
3262 /* Set the separate option for all dimensions.
3263 This helps to reduce control overhead. */
3265 __isl_give isl_ast_build
*
3266 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3267 __isl_keep isl_union_map
*schedule
)
3269 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3270 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3272 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3273 isl_union_set
*range
=
3274 isl_union_set_from_set (isl_set_universe (range_space
));
3275 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3276 domain
= isl_union_set_universe (domain
);
3277 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3278 return isl_ast_build_set_options (control
, options
);
3281 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3283 __isl_give isl_ast_node
*
3284 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3286 isl_ast_node
*ast_isl
= NULL
;
3287 /* Generate loop upper bounds that consist of the current loop iterator, an
3288 operator (< or <=) and an expression not involving the iterator. If this
3289 option is not set, then the current loop iterator may appear several times
3290 in the upper bound. See the isl manual for more details. */
3291 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3293 add_parameters_to_ivs_params (scop
, ip
);
3294 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3295 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3296 context_isl
= set_options (context_isl
, schedule_isl
);
3297 if (flag_loop_parallelize_all
)
3299 isl_union_map
*dependence
= scop_get_dependences (scop
);
3301 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3305 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3308 scop
->schedule
= set_options_for_schedule_tree (scop
->schedule
);
3309 ast_isl
= isl_ast_build_node_from_schedule (context_isl
, scop
->schedule
);
3310 isl_union_map_free(schedule_isl
);
3313 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3315 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3316 isl_schedule_free (scop
->schedule
);
3319 isl_ast_build_free (context_isl
);
3323 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
3324 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
3327 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
3328 gimple_stmt_iterator
*gsi
)
3330 if (!defined_in_sese_p (tr
, region
->region
))
3334 use_operand_p use_p
;
3335 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
3337 tree use_tr
= USE_FROM_PTR (use_p
);
3339 /* Do not copy parameters that have been generated in the header of the
3341 if (region
->parameter_rename_map
->get(use_tr
))
3344 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
3348 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
3351 gimple
*copy
= gimple_copy (def_stmt
);
3352 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
3354 /* Create new names for all the definitions created by COPY and
3355 add replacement mappings for each new name. */
3356 def_operand_p def_p
;
3357 ssa_op_iter op_iter
;
3358 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
3360 tree old_name
= DEF_FROM_PTR (def_p
);
3361 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
3362 region
->parameter_rename_map
->put(old_name
, new_name
);
3369 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
3371 /* For all the parameters which definitino is in the if_region->false_region,
3372 insert code on true_region (if_region->true_region->entry). */
3376 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
3378 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
3380 // If def is not in region.
3381 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
3383 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
3387 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3388 the given SCOP. Return true if code generation succeeded.
3390 FIXME: This is not yet a full implementation of the code generator
3391 with isl ASTs. Generation of GIMPLE code has to be completed. */
3394 graphite_regenerate_ast_isl (scop_p scop
)
3396 sese_info_p region
= scop
->scop_info
;
3397 translate_isl_ast_to_gimple
t (region
);
3399 ifsese if_region
= NULL
;
3400 isl_ast_node
*root_node
;
3403 timevar_push (TV_GRAPHITE_CODE_GEN
);
3404 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3408 fprintf (dump_file
, "AST generated by isl: \n");
3409 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3412 recompute_all_dominators ();
3415 if_region
= move_sese_in_condition (region
);
3416 region
->if_region
= if_region
;
3417 recompute_all_dominators ();
3419 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3421 /* Copy all the parameters which are defined in the region. */
3422 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3424 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3425 basic_block bb
= split_edge (e
);
3427 /* Update the true_region exit edge. */
3428 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3430 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3431 if (t
.codegen_error_p ())
3434 fprintf (dump_file
, "[codegen] unsuccessful,"
3435 " reverting back to the original code.\n");
3436 set_ifsese_condition (if_region
, integer_zero_node
);
3440 t
.translate_pending_phi_nodes ();
3441 if (!t
.codegen_error_p ())
3443 sese_insert_phis_for_liveouts (region
,
3444 if_region
->region
->region
.exit
->src
,
3445 if_region
->false_region
->region
.exit
,
3446 if_region
->true_region
->region
.exit
);
3447 mark_virtual_operands_for_renaming (cfun
);
3448 update_ssa (TODO_update_ssa
);
3453 recompute_all_dominators ();
3459 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3460 " pending phis, reverting back to the original code.\n");
3461 set_ifsese_condition (if_region
, integer_zero_node
);
3465 free (if_region
->true_region
);
3466 free (if_region
->region
);
3469 ivs_params_clear (ip
);
3470 isl_ast_node_free (root_node
);
3471 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3476 int num_no_dependency
= 0;
3478 FOR_EACH_LOOP (loop
, 0)
3479 if (loop
->can_be_parallel
)
3480 num_no_dependency
++;
3482 fprintf (dump_file
, "%d loops carried no dependency.\n",
3486 return !t
.codegen_error_p ();
3489 #endif /* HAVE_isl */