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
);
141 class translate_isl_ast_to_gimple
144 translate_isl_ast_to_gimple (sese_info_p r
)
145 : region (r
), codegen_error (false)
148 /* Translates an isl AST node NODE to GCC representation in the
149 context of a SESE. */
150 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
151 edge next_e
, ivs_params
&ip
);
153 /* Translates an isl_ast_node_for to Gimple. */
154 edge
translate_isl_ast_node_for (loop_p context_loop
,
155 __isl_keep isl_ast_node
*node
,
156 edge next_e
, ivs_params
&ip
);
158 /* Create the loop for a isl_ast_node_for.
160 - NEXT_E is the edge where new generated code should be attached. */
161 edge
translate_isl_ast_for_loop (loop_p context_loop
,
162 __isl_keep isl_ast_node
*node_for
,
164 tree type
, tree lb
, tree ub
,
167 /* Translates an isl_ast_node_if to Gimple. */
168 edge
translate_isl_ast_node_if (loop_p context_loop
,
169 __isl_keep isl_ast_node
*node
,
170 edge next_e
, ivs_params
&ip
);
172 /* Translates an isl_ast_node_user to Gimple.
174 FIXME: We should remove iv_map.create (loop->num + 1), if it is
176 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
177 edge next_e
, ivs_params
&ip
);
179 /* Translates an isl_ast_node_block to Gimple. */
180 edge
translate_isl_ast_node_block (loop_p context_loop
,
181 __isl_keep isl_ast_node
*node
,
182 edge next_e
, ivs_params
&ip
);
184 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
186 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
189 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
191 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
194 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
196 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
199 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
200 to a GCC expression tree of type TYPE. */
201 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
204 /* Converts an isl AST expression E back to a GCC expression tree of
206 tree
gcc_expression_from_isl_expression (tree type
,
207 __isl_take isl_ast_expr
*,
210 /* Return the tree variable that corresponds to the given isl ast identifier
211 expression (an isl_ast_expr of type isl_ast_expr_id).
213 FIXME: We should replace blind conversation of id's type with derivation
214 of the optimal type when we get the corresponding isl support. Blindly
215 converting type sizes may be problematic when we switch to smaller
217 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
218 __isl_keep isl_ast_expr
*expr_id
,
221 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
223 tree
gcc_expression_from_isl_expr_int (tree type
,
224 __isl_take isl_ast_expr
*expr
);
226 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
228 tree
gcc_expression_from_isl_expr_op (tree type
,
229 __isl_take isl_ast_expr
*expr
,
232 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
233 induction variable for the new LOOP. New LOOP is attached to CFG
234 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
235 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
236 isl's scattering name to the induction variable created for the
237 loop of STMT. The new induction variable is inserted in the NEWIVS
238 vector and is of type TYPE. */
239 struct loop
*graphite_create_new_loop (edge entry_edge
,
240 __isl_keep isl_ast_node
*node_for
,
241 loop_p outer
, tree type
,
242 tree lb
, tree ub
, ivs_params
&ip
);
244 /* All loops generated by create_empty_loop_on_edge have the form of
251 } while (lower bound < upper bound);
253 We create a new if region protecting the loop to be executed, if
254 the execution count is zero (lower bound > upper bound). */
255 edge
graphite_create_new_loop_guard (edge entry_edge
,
256 __isl_keep isl_ast_node
*node_for
,
258 tree
*lb
, tree
*ub
, ivs_params
&ip
);
260 /* Creates a new if region corresponding to isl's cond. */
261 edge
graphite_create_new_guard (edge entry_edge
,
262 __isl_take isl_ast_expr
*if_cond
,
265 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
266 variables of the loops around GBB in SESE.
268 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
269 chrec, we could consider using a map<int, tree> that maps loop ids to the
270 corresponding tree expressions. */
271 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
272 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
275 /* Patch the missing arguments of the phi nodes. */
277 void translate_pending_phi_nodes (void);
279 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
281 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
283 /* Get the maximal number of schedule dimensions in the scop SCOP. */
285 int get_max_schedule_dimensions (scop_p scop
);
287 /* Generates a build, which specifies the constraints on the parameters. */
289 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
291 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
293 For schedules with different dimensionality, the isl AST generator can not
294 define an order and will just randomly choose an order. The solution to
295 this problem is to extend all schedules to the maximal number of schedule
296 dimensions (using '0's for the remaining values). */
298 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
299 int nb_schedule_dims
);
301 /* Generates a schedule, which specifies an order used to
302 visit elements in a domain. */
304 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
306 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
307 /* Set the "separate" option for all schedules. This helps reducing control
310 __isl_give isl_schedule
*
311 set_options_for_schedule_tree (__isl_take isl_schedule
*schedule
);
314 /* Set the separate option for all dimensions.
315 This helps to reduce control overhead. */
317 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
318 __isl_keep isl_union_map
*schedule
);
320 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
323 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
326 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
327 definition should flow into use, and the use should respect the loop-closed
330 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
331 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
333 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
334 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
335 within a loop PHI instruction. */
337 tree
get_rename (basic_block new_bb
, tree old_name
,
338 basic_block old_bb
, bool loop_phi
) const;
340 /* For ops which are scev_analyzeable, we can regenerate a new name from
341 its scalar evolution around LOOP. */
343 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
344 basic_block new_bb
, basic_block old_bb
,
347 /* Returns a basic block that could correspond to where a constant was defined
348 in the original code. In the original code OLD_BB had the definition, we
349 need to find which basic block out of the copies of old_bb, in the new
350 region, should a definition correspond to if it has to reach BB. */
352 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
354 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
355 true when we want to rename an OP within a loop PHI instruction. */
357 tree
get_new_name (basic_block new_bb
, tree op
,
358 basic_block old_bb
, bool loop_phi
) const;
360 /* Collect all the operands of NEW_EXPR by recursively visiting each
363 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
365 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
366 NEW_PHI must be found unless they can be POSTPONEd for later. */
368 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
369 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
372 /* Copy loop phi nodes from BB to NEW_BB. */
374 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
376 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
377 the close phi node PHI. */
379 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
382 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
383 gimple
*old_close_phi
);
385 /* Copy all the loop-close phi args from BB to NEW_BB. */
387 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
390 /* Copy loop close phi nodes from BB to NEW_BB. */
392 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
394 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
395 region. If postpone is true and it isn't possible to copy any arg of PHI,
396 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
397 Returns false if the copying was unsuccessful. */
399 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
402 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
403 containing phi nodes coming from two predecessors, and none of them are back
406 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
409 /* Duplicates the statements of basic block BB into basic block NEW_BB
410 and compute the new induction variables according to the IV_MAP.
411 CODEGEN_ERROR is set when the code generation cannot continue. */
413 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
416 /* Copies BB and includes in the copied BB all the statements that can
417 be reached following the use-def chains from the memory accesses,
418 and returns the next edge following this new block. codegen_error is
419 set when the code generation cannot continue. */
421 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
424 /* Given a basic block containing close-phi it returns the new basic block
425 where to insert a copy of the close-phi nodes. All the uses in close phis
426 should come from a single loop otherwise it returns NULL. */
427 edge
edge_for_new_close_phis (basic_block bb
);
429 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
430 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
431 the other pred of OLD_BB as well. If no such basic block exists then it is
432 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
435 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
436 versa. In this case DOMINATING_PRED = NULL.
438 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
440 Returns true on successful copy of the args, false otherwise. */
442 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
443 edge old_bb_dominating_edge
,
444 edge old_bb_non_dominating_edge
,
445 gphi
*phi
, gphi
*new_phi
,
448 /* Renames the scalar uses of the statement COPY, using the substitution map
449 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
450 translation REGION, with the original copied statement in LOOP, and using
451 the induction variable renaming map IV_MAP. Returns true when something
452 has been renamed. codegen_error is set when the code generation cannot
455 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
456 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
458 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
459 When OLD_NAME and EXPR are the same we assert. */
461 void set_rename (tree old_name
, tree expr
);
463 /* Create new names for all the definitions created by COPY and add
464 replacement mappings for each new name. */
466 void set_rename_for_each_def (gimple
*stmt
);
468 /* Insert each statement from SEQ at its earliest insertion p. */
470 void gsi_insert_earliest (gimple_seq seq
);
472 /* Rename all the operands of NEW_EXPR by recursively visiting each
475 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
477 bool codegen_error_p () const
478 { return codegen_error
; }
480 /* Prints NODE to FILE. */
482 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
483 __isl_keep isl_ctx
*ctx
) const;
485 /* Return true when OP is a constant tree. */
487 bool is_constant (tree op
) const
489 return TREE_CODE (op
) == INTEGER_CST
490 || TREE_CODE (op
) == REAL_CST
491 || TREE_CODE (op
) == COMPLEX_CST
492 || TREE_CODE (op
) == VECTOR_CST
;
496 /* The region to be translated. */
499 /* This flag is set when an error occurred during the translation of isl AST
503 /* A vector of all the edges at if_condition merge points. */
504 auto_vec
<edge
, 2> merge_points
;
507 /* Return the tree variable that corresponds to the given isl ast identifier
508 expression (an isl_ast_expr of type isl_ast_expr_id).
510 FIXME: We should replace blind conversation of id's type with derivation
511 of the optimal type when we get the corresponding isl support. Blindly
512 converting type sizes may be problematic when we switch to smaller
516 translate_isl_ast_to_gimple::
517 gcc_expression_from_isl_ast_expr_id (tree type
,
518 __isl_take isl_ast_expr
*expr_id
,
521 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
522 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
523 std::map
<isl_id
*, tree
>::iterator res
;
524 res
= ip
.find (tmp_isl_id
);
525 isl_id_free (tmp_isl_id
);
526 gcc_assert (res
!= ip
.end () &&
527 "Could not map isl_id to tree expression");
528 isl_ast_expr_free (expr_id
);
529 tree t
= res
->second
;
530 return fold_convert (type
, t
);
533 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
537 translate_isl_ast_to_gimple::
538 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
540 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
541 isl_val
*val
= isl_ast_expr_get_val (expr
);
543 mpz_init (val_mpz_t
);
545 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
548 res
= gmp_cst_to_tree (type
, val_mpz_t
);
550 isl_ast_expr_free (expr
);
551 mpz_clear (val_mpz_t
);
555 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
559 translate_isl_ast_to_gimple::
560 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
562 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
563 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
564 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
565 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
567 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
568 isl_ast_expr_free (expr
);
576 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
579 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
582 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
585 /* As isl operates on arbitrary precision numbers, we may end up with
586 division by 2^64 that is folded to 0. */
587 if (integer_zerop (tree_rhs_expr
))
589 codegen_error
= true;
592 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
594 case isl_ast_op_pdiv_q
:
595 /* As isl operates on arbitrary precision numbers, we may end up with
596 division by 2^64 that is folded to 0. */
597 if (integer_zerop (tree_rhs_expr
))
599 codegen_error
= true;
602 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
604 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
605 /* isl 0.15 or later. */
606 case isl_ast_op_zdiv_r
:
608 case isl_ast_op_pdiv_r
:
609 /* As isl operates on arbitrary precision numbers, we may end up with
610 division by 2^64 that is folded to 0. */
611 if (integer_zerop (tree_rhs_expr
))
613 codegen_error
= true;
616 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
618 case isl_ast_op_fdiv_q
:
619 /* As isl operates on arbitrary precision numbers, we may end up with
620 division by 2^64 that is folded to 0. */
621 if (integer_zerop (tree_rhs_expr
))
623 codegen_error
= true;
626 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
629 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
630 tree_lhs_expr
, tree_rhs_expr
);
633 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
636 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
639 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
642 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
645 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
648 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
655 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
659 translate_isl_ast_to_gimple::
660 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
662 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
663 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
665 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
666 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
667 tree tree_second_expr
668 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
669 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
671 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
672 isl_ast_expr_free (expr
);
676 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
677 tree_second_expr
, tree_third_expr
);
680 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
684 translate_isl_ast_to_gimple::
685 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
687 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
688 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
689 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
690 isl_ast_expr_free (expr
);
691 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
694 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
695 to a GCC expression tree of type TYPE. */
698 translate_isl_ast_to_gimple::
699 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
701 enum tree_code op_code
;
702 switch (isl_ast_expr_get_op_type (expr
))
715 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
716 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
720 isl_ast_expr_free (expr
);
725 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
727 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
728 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
732 isl_ast_expr_free (expr
);
736 res
= fold_build2 (op_code
, type
, res
, t
);
738 isl_ast_expr_free (expr
);
742 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
746 translate_isl_ast_to_gimple::
747 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
752 isl_ast_expr_free (expr
);
756 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
757 switch (isl_ast_expr_get_op_type (expr
))
759 /* These isl ast expressions are not supported yet. */
760 case isl_ast_op_error
:
761 case isl_ast_op_call
:
762 case isl_ast_op_and_then
:
763 case isl_ast_op_or_else
:
764 case isl_ast_op_select
:
769 return nary_op_to_tree (type
, expr
, ip
);
775 case isl_ast_op_pdiv_q
:
776 case isl_ast_op_pdiv_r
:
777 case isl_ast_op_fdiv_q
:
778 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
779 /* isl 0.15 or later. */
780 case isl_ast_op_zdiv_r
:
789 return binary_op_to_tree (type
, expr
, ip
);
791 case isl_ast_op_minus
:
792 return unary_op_to_tree (type
, expr
, ip
);
794 case isl_ast_op_cond
:
795 return ternary_op_to_tree (type
, expr
, ip
);
804 /* Converts an isl AST expression E back to a GCC expression tree of
808 translate_isl_ast_to_gimple::
809 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
814 isl_ast_expr_free (expr
);
818 switch (isl_ast_expr_get_type (expr
))
820 case isl_ast_expr_id
:
821 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
823 case isl_ast_expr_int
:
824 return gcc_expression_from_isl_expr_int (type
, expr
);
826 case isl_ast_expr_op
:
827 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
836 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
837 induction variable for the new LOOP. New LOOP is attached to CFG
838 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
839 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
840 isl's scattering name to the induction variable created for the
841 loop of STMT. The new induction variable is inserted in the NEWIVS
842 vector and is of type TYPE. */
845 translate_isl_ast_to_gimple::
846 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
847 loop_p outer
, tree type
, tree lb
, tree ub
,
850 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
851 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
853 /* To fail code generation, we generate wrong code until we discard it. */
855 stride
= integer_zero_node
;
857 tree ivvar
= create_tmp_var (type
, "graphite_IV");
858 tree iv
, iv_after_increment
;
859 loop_p loop
= create_empty_loop_on_edge
860 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
861 outer
? outer
: entry_edge
->src
->loop_father
);
863 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
864 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
865 std::map
<isl_id
*, tree
>::iterator res
;
868 isl_id_free (res
->first
);
870 isl_ast_expr_free (for_iterator
);
874 /* Create the loop for a isl_ast_node_for.
876 - NEXT_E is the edge where new generated code should be attached. */
879 translate_isl_ast_to_gimple::
880 translate_isl_ast_for_loop (loop_p context_loop
,
881 __isl_keep isl_ast_node
*node_for
, edge next_e
,
882 tree type
, tree lb
, tree ub
,
885 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
886 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
888 edge last_e
= single_exit (loop
);
889 edge to_body
= single_succ_edge (loop
->header
);
890 basic_block after
= to_body
->dest
;
892 /* Translate the body of the loop. */
893 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
894 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
895 isl_ast_node_free (for_body
);
897 /* Early return if we failed to translate loop body. */
898 if (!next_e
|| codegen_error_p ())
901 if (next_e
->dest
!= after
)
902 redirect_edge_succ_nodup (next_e
, after
);
903 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
905 if (flag_loop_parallelize_all
)
907 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
909 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
910 loop
->can_be_parallel
= for_info
->is_parallelizable
;
918 /* We use this function to get the upper bound because of the form,
919 which is used by isl to represent loops:
921 for (iterator = init; cond; iterator += inc)
929 The loop condition is an arbitrary expression, which contains the
930 current loop iterator.
932 (e.g. iterator + 3 < B && C > iterator + A)
934 We have to know the upper bound of the iterator to generate a loop
935 in Gimple form. It can be obtained from the special representation
936 of the loop condition, which is generated by isl,
937 if the ast_build_atomic_upper_bound option is set. In this case,
938 isl generates a loop condition that consists of the current loop
939 iterator, + an operator (< or <=) and an expression not involving
940 the iterator, which is processed and returned by this function.
942 (e.g iterator <= upper-bound-expression-without-iterator) */
944 static __isl_give isl_ast_expr
*
945 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
947 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
948 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
949 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
951 switch (isl_ast_expr_get_op_type (for_cond
))
954 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
959 /* (iterator < ub) => (iterator <= ub - 1). */
961 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
962 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
963 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
970 isl_ast_expr_free (for_cond
);
974 /* All loops generated by create_empty_loop_on_edge have the form of
981 } while (lower bound < upper bound);
983 We create a new if region protecting the loop to be executed, if
984 the execution count is zero (lower bound > upper bound). */
987 translate_isl_ast_to_gimple::
988 graphite_create_new_loop_guard (edge entry_edge
,
989 __isl_keep isl_ast_node
*node_for
, tree
*type
,
990 tree
*lb
, tree
*ub
, ivs_params
&ip
)
992 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
997 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
998 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
999 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
1000 /* To fail code generation, we generate wrong code until we discard it. */
1002 *lb
= integer_zero_node
;
1003 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
1004 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
1005 /* To fail code generation, we generate wrong code until we discard it. */
1007 *ub
= integer_zero_node
;
1009 /* When ub is simply a constant or a parameter, use lb <= ub. */
1010 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
1011 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
1014 tree one
= (POINTER_TYPE_P (*type
)
1015 ? convert_to_ptrofftype (integer_one_node
)
1016 : fold_convert (*type
, integer_one_node
));
1017 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1018 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1019 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1020 is true, even if we do not want this. However lb < ub + 1 is false,
1022 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1023 : PLUS_EXPR
, *type
, *ub
, one
);
1025 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1028 if (integer_onep (cond_expr
))
1029 exit_edge
= entry_edge
;
1031 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1036 /* Translates an isl_ast_node_for to Gimple. */
1039 translate_isl_ast_to_gimple::
1040 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1041 edge next_e
, ivs_params
&ip
)
1043 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1045 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1048 if (last_e
== next_e
)
1050 /* There was no guard generated. */
1051 last_e
= single_succ_edge (split_edge (last_e
));
1053 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1058 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1059 merge_points
.safe_push (last_e
);
1061 last_e
= single_succ_edge (split_edge (last_e
));
1062 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1067 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1068 variables of the loops around GBB in SESE.
1070 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1071 chrec, we could consider using a map<int, tree> that maps loop ids to the
1072 corresponding tree expressions. */
1075 translate_isl_ast_to_gimple::
1076 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1077 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1080 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1081 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1083 isl_ast_expr
*arg_expr
;
1084 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1086 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1088 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1089 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1090 /* To fail code generation, we generate wrong code until we discard it. */
1092 t
= integer_zero_node
;
1094 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1095 iv_map
[old_loop
->num
] = t
;
1099 /* Translates an isl_ast_node_user to Gimple.
1101 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1104 translate_isl_ast_to_gimple::
1105 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1106 edge next_e
, ivs_params
&ip
)
1108 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1110 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1111 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1112 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1114 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1115 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1118 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1120 isl_ast_expr_free (name_expr
);
1121 isl_id_free (name_id
);
1123 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1124 "The entry block should not even appear within a scop");
1126 const int nb_loops
= number_of_loops (cfun
);
1128 iv_map
.create (nb_loops
);
1129 iv_map
.safe_grow_cleared (nb_loops
);
1131 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1132 isl_ast_expr_free (user_expr
);
1134 basic_block old_bb
= GBB_BB (gbb
);
1138 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1139 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1140 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1144 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1148 if (codegen_error_p ())
1153 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1154 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1160 /* Translates an isl_ast_node_block to Gimple. */
1163 translate_isl_ast_to_gimple::
1164 translate_isl_ast_node_block (loop_p context_loop
,
1165 __isl_keep isl_ast_node
*node
,
1166 edge next_e
, ivs_params
&ip
)
1168 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1169 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1171 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1173 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1174 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1175 isl_ast_node_free (tmp_node
);
1177 isl_ast_node_list_free (node_list
);
1181 /* Creates a new if region corresponding to isl's cond. */
1184 translate_isl_ast_to_gimple::
1185 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1189 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1190 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1191 /* To fail code generation, we generate wrong code until we discard it. */
1193 cond_expr
= integer_zero_node
;
1195 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1199 /* Translates an isl_ast_node_if to Gimple. */
1202 translate_isl_ast_to_gimple::
1203 translate_isl_ast_node_if (loop_p context_loop
,
1204 __isl_keep isl_ast_node
*node
,
1205 edge next_e
, ivs_params
&ip
)
1207 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1208 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1209 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1210 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1211 merge_points
.safe_push (last_e
);
1213 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1214 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1215 isl_ast_node_free (then_node
);
1217 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1218 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1219 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1220 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1222 isl_ast_node_free (else_node
);
1226 /* Translates an isl AST node NODE to GCC representation in the
1227 context of a SESE. */
1230 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1231 __isl_keep isl_ast_node
*node
,
1232 edge next_e
, ivs_params
&ip
)
1234 if (codegen_error_p ())
1237 switch (isl_ast_node_get_type (node
))
1239 case isl_ast_node_error
:
1242 case isl_ast_node_for
:
1243 return translate_isl_ast_node_for (context_loop
, node
,
1246 case isl_ast_node_if
:
1247 return translate_isl_ast_node_if (context_loop
, node
,
1250 case isl_ast_node_user
:
1251 return translate_isl_ast_node_user (node
, next_e
, ip
);
1253 case isl_ast_node_block
:
1254 return translate_isl_ast_node_block (context_loop
, node
,
1257 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1258 case isl_ast_node_mark
:
1260 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1261 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1262 isl_ast_node_free (n
);
1272 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1273 at the exit of loop which takes one argument that is the last value of the
1274 variable being used out of the loop. */
1277 bb_contains_loop_close_phi_nodes (basic_block bb
)
1279 return single_pred_p (bb
)
1280 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1283 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1284 header containing phi nodes which has one init-edge and one back-edge. */
1287 bb_contains_loop_phi_nodes (basic_block bb
)
1289 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1291 if (bb
->preds
->length () == 1)
1294 unsigned depth
= loop_depth (bb
->loop_father
);
1296 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1298 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1299 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1302 /* When one of the edges correspond to the same loop father and other
1304 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1305 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1308 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1309 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1315 /* Check if USE is defined in a basic block from where the definition of USE can
1316 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1319 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1321 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1324 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1325 if (bb_contains_loop_close_phi_nodes (bb
))
1328 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1329 basic_block def_bb
= gimple_bb (def
);
1331 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1334 /* Return the number of phi nodes in BB. */
1337 number_of_phi_nodes (basic_block bb
)
1340 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1346 /* Returns true if BB uses name in one of its PHIs. */
1349 phi_uses_name (basic_block bb
, tree name
)
1351 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1354 gphi
*phi
= psi
.phi ();
1355 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1357 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1358 if (use_arg
== name
)
1365 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1366 definition should flow into use, and the use should respect the loop-closed
1370 translate_isl_ast_to_gimple::
1371 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1372 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1374 /* The def of the rename must either dominate the uses or come from a
1375 back-edge. Also the def must respect the loop closed ssa form. */
1376 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1380 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1381 print_generic_expr (dump_file
, rename
, 0);
1382 fprintf (dump_file
, "\n");
1387 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1390 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1392 /* The loop-header dominates the loop-body. */
1393 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1396 /* RENAME would be used in loop-phi. */
1397 gcc_assert (number_of_phi_nodes (use_bb
));
1399 /* For definitions coming from back edges, we should check that
1400 old_name is used in a loop PHI node.
1401 FIXME: Verify if this is true. */
1402 if (phi_uses_name (old_bb
, old_name
))
1408 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1409 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1410 within a loop PHI instruction. */
1413 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1416 bool loop_phi
) const
1418 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1419 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1421 if (!renames
|| renames
->is_empty ())
1424 if (1 == renames
->length ())
1426 tree rename
= (*renames
)[0];
1427 if (TREE_CODE (rename
) == SSA_NAME
)
1429 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1430 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1435 if (is_constant (rename
))
1441 /* More than one renames corresponding to the old_name. Find the rename for
1442 which the definition flows into usage at new_bb. */
1444 tree t1
= NULL_TREE
, t2
;
1445 basic_block t1_bb
= NULL
;
1446 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1448 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1450 /* Defined in the same basic block as used. */
1451 if (t2_bb
== new_bb
)
1454 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1455 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1458 /* Compute the nearest dominator. */
1459 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1469 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1470 When OLD_NAME and EXPR are the same we assert. */
1473 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1477 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1478 print_generic_expr (dump_file
, old_name
, 0);
1479 fprintf (dump_file
, ", new_name = ");
1480 print_generic_expr (dump_file
, expr
, 0);
1481 fprintf (dump_file
, "\n");
1484 if (old_name
== expr
)
1487 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1490 renames
->safe_push (expr
);
1496 region
->rename_map
->put (old_name
, r
);
1500 /* Return an iterator to the instructions comes last in the execution order.
1501 Either GSI1 and GSI2 should belong to the same basic block or one of their
1502 respective basic blocks should dominate the other. */
1504 gimple_stmt_iterator
1505 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1507 basic_block bb1
= gsi_bb (gsi1
);
1508 basic_block bb2
= gsi_bb (gsi2
);
1510 /* Find the iterator which is the latest. */
1513 /* For empty basic blocks gsis point to the end of the sequence. Since
1514 there is no operator== defined for gimple_stmt_iterator and for gsis
1515 not pointing to a valid statement gsi_next would assert. */
1516 gimple_stmt_iterator gsi
= gsi1
;
1518 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1521 } while (!gsi_end_p (gsi
));
1526 /* Find the basic block closest to the basic block which defines stmt. */
1527 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1530 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1534 /* Insert each statement from SEQ at its earliest insertion p. */
1537 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1539 update_modified_stmts (seq
);
1540 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1541 basic_block begin_bb
= get_entry_bb (codegen_region
);
1543 /* Inserting the gimple statements in a vector because gimple_seq behave
1544 in strage ways when inserting the stmts from it into different basic
1545 blocks one at a time. */
1546 auto_vec
<gimple
*, 3> stmts
;
1547 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1549 stmts
.safe_push (gsi_stmt (gsi
));
1553 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1555 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1556 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1558 use_operand_p use_p
;
1559 ssa_op_iter op_iter
;
1560 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1562 /* Iterator to the current def of use_p. For function parameters or
1563 anything where def is not found, insert at the beginning of the
1564 generated region. */
1565 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1567 tree op
= USE_FROM_PTR (use_p
);
1568 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1569 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1570 gsi_stmt
= gsi_for_stmt (stmt
);
1572 /* For region parameters, insert at the beginning of the generated
1574 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1575 gsi_stmt
= gsi_def_stmt
;
1577 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1580 if (!gsi_stmt (gsi_def_stmt
))
1582 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1583 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1585 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1587 gimple_stmt_iterator bsi
1588 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1589 /* Insert right after the PHI statements. */
1590 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1593 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1597 fprintf (dump_file
, "[codegen] inserting statement: ");
1598 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1599 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1604 /* Collect all the operands of NEW_EXPR by recursively visiting each
1608 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1612 /* Rename all uses in new_expr. */
1613 if (TREE_CODE (new_expr
) == SSA_NAME
)
1615 vec_ssa
->safe_push (new_expr
);
1619 /* Iterate over SSA_NAMES in NEW_EXPR. */
1620 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1622 tree op
= TREE_OPERAND (new_expr
, i
);
1623 collect_all_ssa_names (op
, vec_ssa
);
1627 /* This is abridged version of the function copied from:
1628 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1631 substitute_ssa_name (tree exp
, tree f
, tree r
)
1633 enum tree_code code
= TREE_CODE (exp
);
1634 tree op0
, op1
, op2
, op3
;
1637 /* We handle TREE_LIST and COMPONENT_REF separately. */
1638 if (code
== TREE_LIST
)
1640 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1641 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1642 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1645 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1647 else if (code
== COMPONENT_REF
)
1651 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1652 and it is the right field, replace it with R. */
1653 for (inner
= TREE_OPERAND (exp
, 0);
1654 REFERENCE_CLASS_P (inner
);
1655 inner
= TREE_OPERAND (inner
, 0))
1659 op1
= TREE_OPERAND (exp
, 1);
1661 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1664 /* If this expression hasn't been completed let, leave it alone. */
1665 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1668 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1669 if (op0
== TREE_OPERAND (exp
, 0))
1673 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1676 switch (TREE_CODE_CLASS (code
))
1681 case tcc_declaration
:
1687 case tcc_expression
:
1691 /* Fall through... */
1693 case tcc_exceptional
:
1696 case tcc_comparison
:
1698 switch (TREE_CODE_LENGTH (code
))
1706 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1707 if (op0
== TREE_OPERAND (exp
, 0))
1710 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1714 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1715 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1717 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1720 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1724 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1725 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1726 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1728 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1729 && op2
== TREE_OPERAND (exp
, 2))
1732 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1736 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1737 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1738 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1739 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1741 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1742 && op2
== TREE_OPERAND (exp
, 2)
1743 && op3
== TREE_OPERAND (exp
, 3))
1747 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1760 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1762 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1763 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1768 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1771 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1774 auto_vec
<tree
, 2> ssa_names
;
1775 collect_all_ssa_names (new_expr
, &ssa_names
);
1778 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1779 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1780 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1785 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1786 scalar evolution around LOOP. */
1789 translate_isl_ast_to_gimple::
1790 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1791 basic_block new_bb
, basic_block old_bb
,
1794 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1796 /* At this point we should know the exact scev for each
1797 scalar SSA_NAME used in the scop: all the other scalar
1798 SSA_NAMEs should have been translated out of SSA using
1799 arrays with one element. */
1801 if (chrec_contains_undetermined (scev
))
1803 codegen_error
= true;
1804 return build_zero_cst (TREE_TYPE (old_name
));
1807 new_expr
= chrec_apply_map (scev
, iv_map
);
1809 /* The apply should produce an expression tree containing
1810 the uses of the new induction variables. We should be
1811 able to use new_expr instead of the old_name in the newly
1812 generated loop nest. */
1813 if (chrec_contains_undetermined (new_expr
)
1814 || tree_contains_chrecs (new_expr
, NULL
))
1816 codegen_error
= true;
1817 return build_zero_cst (TREE_TYPE (old_name
));
1820 /* We should check all the operands and all of them should dominate the use at
1822 if (TREE_CODE (new_expr
) == SSA_NAME
)
1824 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1825 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1827 codegen_error
= true;
1828 return build_zero_cst (TREE_TYPE (old_name
));
1832 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1834 /* We check all the operands and all of them should dominate the use at
1836 auto_vec
<tree
, 2> new_ssa_names
;
1837 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1840 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1842 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1844 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1845 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1847 codegen_error
= true;
1848 return build_zero_cst (TREE_TYPE (old_name
));
1853 /* Replace the old_name with the new_expr. */
1854 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1858 /* Renames the scalar uses of the statement COPY, using the
1859 substitution map RENAME_MAP, inserting the gimplification code at
1860 GSI_TGT, for the translation REGION, with the original copied
1861 statement in LOOP, and using the induction variable renaming map
1862 IV_MAP. Returns true when something has been renamed. codegen_error
1863 is set when the code generation cannot continue. */
1866 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1867 gimple_stmt_iterator
*gsi_tgt
,
1869 loop_p loop
, vec
<tree
> iv_map
)
1871 bool changed
= false;
1873 if (is_gimple_debug (copy
))
1875 if (gimple_debug_bind_p (copy
))
1876 gimple_debug_bind_reset_value (copy
);
1877 else if (gimple_debug_source_bind_p (copy
))
1887 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1888 print_gimple_stmt (dump_file
, copy
, 0, 0);
1891 use_operand_p use_p
;
1892 ssa_op_iter op_iter
;
1893 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1895 tree old_name
= USE_FROM_PTR (use_p
);
1899 fprintf (dump_file
, "[codegen] renaming old_name = ");
1900 print_generic_expr (dump_file
, old_name
, 0);
1901 fprintf (dump_file
, "\n");
1904 if (TREE_CODE (old_name
) != SSA_NAME
1905 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1909 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1914 tree type_old_name
= TREE_TYPE (old_name
);
1915 tree type_new_expr
= TREE_TYPE (new_expr
);
1919 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1920 print_generic_expr (dump_file
, new_expr
, 0);
1921 fprintf (dump_file
, "\n");
1924 if (type_old_name
!= type_new_expr
1925 || TREE_CODE (new_expr
) != SSA_NAME
)
1927 tree var
= create_tmp_var (type_old_name
, "var");
1929 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1930 new_expr
= fold_convert (type_old_name
, new_expr
);
1933 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1934 gsi_insert_earliest (stmts
);
1937 replace_exp (use_p
, new_expr
);
1942 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1944 if (!new_expr
|| codegen_error_p ())
1949 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1950 print_generic_expr (dump_file
, new_expr
, 0);
1951 fprintf (dump_file
, "\n");
1954 gsi_insert_earliest (stmts
);
1955 replace_exp (use_p
, new_expr
);
1957 if (TREE_CODE (new_expr
) == INTEGER_CST
1958 && is_gimple_assign (copy
))
1960 tree rhs
= gimple_assign_rhs1 (copy
);
1962 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1963 recompute_tree_invariant_for_addr_expr (rhs
);
1966 set_rename (old_name
, new_expr
);
1972 /* Returns a basic block that could correspond to where a constant was defined
1973 in the original code. In the original code OLD_BB had the definition, we
1974 need to find which basic block out of the copies of old_bb, in the new
1975 region, should a definition correspond to if it has to reach BB. */
1978 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1979 basic_block old_bb
) const
1981 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1983 if (!bbs
|| bbs
->is_empty ())
1986 if (1 == bbs
->length ())
1990 basic_block b1
= NULL
, b2
;
1991 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1996 /* BB and B2 are in two unrelated if-clauses. */
1997 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
2000 /* Compute the nearest dominator. */
2001 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
2009 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
2010 when we want to rename an OP within a loop PHI instruction. */
2013 translate_isl_ast_to_gimple::
2014 get_new_name (basic_block new_bb
, tree op
,
2015 basic_block old_bb
, bool loop_phi
) const
2017 /* For constants the names are the same. */
2018 if (is_constant (op
))
2021 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
2024 /* Return a debug location for OP. */
2029 location_t loc
= UNKNOWN_LOCATION
;
2031 if (TREE_CODE (op
) == SSA_NAME
)
2032 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2036 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2037 the init edge (from outside the loop) and the second one is the back edge
2038 from the same loop. */
2040 std::pair
<edge
, edge
>
2041 get_edges (basic_block bb
)
2043 std::pair
<edge
, edge
> edges
;
2046 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2047 if (bb
->loop_father
!= e
->src
->loop_father
)
2054 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2055 must be found unless they can be POSTPONEd for later. */
2058 translate_isl_ast_to_gimple::
2059 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2060 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2063 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2065 basic_block new_bb
= gimple_bb (new_phi
);
2066 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2069 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2070 e
= ibp_new_bb
.first
;
2072 e
= ibp_new_bb
.second
;
2074 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2075 tree new_name
= get_new_name (new_bb
, old_name
,
2076 gimple_bb (old_phi
), true);
2079 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2083 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2084 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2085 /* If the phi arg was a function arg, or wasn't defined, just use the
2087 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2090 /* Postpone code gen for later for those back-edges we don't have the
2092 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2094 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2097 /* Either we should add the arg to phi or, we should postpone. */
2103 /* Copy loop phi nodes from BB to NEW_BB. */
2106 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2110 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2113 /* Loop phi nodes should have only two arguments. */
2114 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2116 /* First edge is the init edge and second is the back edge. */
2117 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2119 /* First edge is the init edge and second is the back edge. */
2120 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2122 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2125 gphi
*phi
= psi
.phi ();
2126 tree res
= gimple_phi_result (phi
);
2127 if (virtual_operand_p (res
))
2129 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2132 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2133 tree new_res
= create_new_def_for (res
, new_phi
,
2134 gimple_phi_result_ptr (new_phi
));
2135 set_rename (res
, new_res
);
2136 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2138 update_stmt (new_phi
);
2142 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2143 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2150 /* Return the init value of PHI, the value coming from outside the loop. */
2153 get_loop_init_value (gphi
*phi
)
2156 loop_p loop
= gimple_bb (phi
)->loop_father
;
2160 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2161 if (e
->src
->loop_father
!= loop
)
2162 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2167 /* Find the init value (the value which comes from outside the loop), of one of
2168 the operands of DEF which is defined by a loop phi. */
2171 find_init_value (gimple
*def
)
2173 if (gimple_code (def
) == GIMPLE_PHI
)
2174 return get_loop_init_value (as_a
<gphi
*> (def
));
2176 if (gimple_vuse (def
))
2180 use_operand_p use_p
;
2181 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2183 tree use
= USE_FROM_PTR (use_p
);
2184 if (TREE_CODE (use
) == SSA_NAME
)
2186 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2194 /* Return the init value, the value coming from outside the loop. */
2197 find_init_value_close_phi (gphi
*phi
)
2199 gcc_assert (gimple_phi_num_args (phi
) == 1);
2200 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2201 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2202 return find_init_value (def
);
2206 tree
translate_isl_ast_to_gimple::
2207 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2208 gimple
*old_close_phi
)
2210 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2211 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2212 basic_block bb
= gimple_bb (stmt
);
2213 if (!bb_in_sese_p (bb
, codegen_region
))
2214 return last_merge_name
;
2216 loop_p loop
= bb
->loop_father
;
2217 if (!loop_in_sese_p (loop
, codegen_region
))
2218 return last_merge_name
;
2220 edge e
= single_exit (loop
);
2222 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2223 return last_merge_name
;
2225 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2226 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2229 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2230 bb
= split_edge (e
);
2232 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2233 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2234 gimple_phi_result_ptr (close_phi
));
2235 set_rename (old_close_phi_name
, res
);
2236 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2237 last_merge_name
= res
;
2239 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2242 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2243 the close phi node PHI. */
2245 bool translate_isl_ast_to_gimple::
2246 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2249 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2250 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2251 if (SSA_NAME
== TREE_CODE (default_value
))
2253 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2254 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2256 default_value_bb
= gimple_bb (stmt
);
2259 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2261 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2262 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2263 tree last_merge_name
= new_close_phi_name
;
2264 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2268 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2270 basic_block new_merge_bb
= merge_e
->src
;
2271 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2274 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2277 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2278 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2279 gimple_phi_result_ptr (merge_phi
));
2280 set_rename (old_close_phi_name
, merge_res
);
2282 edge from_loop
= NULL
, from_default_value
= NULL
;
2285 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2286 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2289 from_default_value
= e
;
2291 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2292 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2293 is contained in another condition. */
2294 if (!from_default_value
|| !from_loop
)
2297 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2298 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2302 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2303 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2306 update_stmt (merge_phi
);
2307 last_merge_name
= merge_res
;
2313 /* Copy all the loop-close phi args from BB to NEW_BB. */
2316 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2320 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2323 gphi
*old_close_phi
= psi
.phi ();
2324 tree res
= gimple_phi_result (old_close_phi
);
2325 if (virtual_operand_p (res
))
2328 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2329 /* Loop close phi nodes should not be scev_analyzable_p. */
2332 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2333 tree new_res
= create_new_def_for (res
, new_close_phi
,
2334 gimple_phi_result_ptr (new_close_phi
));
2335 set_rename (res
, new_res
);
2337 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2338 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2340 /* Predecessor basic blocks of a loop close phi should have been code
2341 generated before. FIXME: This is fixable by merging PHIs from inner
2342 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2346 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2347 get_loc (old_name
));
2350 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2351 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2354 update_stmt (new_close_phi
);
2356 /* When there is no loop guard around this codegenerated loop, there is no
2357 need to collect the close-phi arg. */
2358 if (merge_points
.is_empty ())
2361 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2362 tree default_value
= find_init_value_close_phi (new_close_phi
);
2364 /* A close phi must come from a loop-phi having a default value. */
2370 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2374 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2375 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2380 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2388 /* Copy loop close phi nodes from BB to NEW_BB. */
2391 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2395 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2397 /* Loop close phi nodes should have only one argument. */
2398 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2400 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2404 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2405 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2406 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2407 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2410 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2411 In this case DOMINATING_PRED = NULL.
2413 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2415 Returns true on successful copy of the args, false otherwise. */
2418 translate_isl_ast_to_gimple::
2419 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2420 edge old_bb_dominating_edge
,
2421 edge old_bb_non_dominating_edge
,
2422 gphi
*phi
, gphi
*new_phi
,
2425 basic_block def_pred
[2] = { NULL
, NULL
};
2426 int not_found_bb_index
= -1;
2427 for (int i
= 0; i
< 2; i
++)
2429 /* If the corresponding def_bb could not be found the entry will be
2431 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2432 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2433 gimple_phi_arg_edge (phi
, i
)->src
);
2434 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2435 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2439 /* When non are available bail out. */
2440 if (not_found_bb_index
!= -1)
2442 not_found_bb_index
= i
;
2446 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2447 if (old_bb_dominating_edge
)
2449 if (not_found_bb_index
!= -1)
2452 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2453 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2454 vec
<basic_block
> *bbs
2455 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2457 /* Could not find a mapping. */
2461 basic_block new_pred
= NULL
;
2464 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2466 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2468 /* FIXME: If we have already found new_pred then we have to
2469 disambiguate, bail out for now. */
2472 new_pred
= new_pred1
;
2474 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2476 /* FIXME: If we have already found new_pred then we have to either
2477 it dominates both or we have to disambiguate, bail out. */
2480 new_pred
= new_pred2
;
2487 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2488 gcc_assert (new_non_dominating_edge
);
2489 /* FIXME: Validate each args just like in loop-phis. */
2490 /* By the process of elimination we first insert insert phi-edge for
2491 non-dominating pred which is computed above and then we insert the
2493 int inserted_edge
= 0;
2494 for (; inserted_edge
< 2; inserted_edge
++)
2496 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2497 if (new_non_dominating_edge
== new_bb_pred_edge
)
2499 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2500 new_non_dominating_edge
,
2501 get_loc (old_phi_args
[inserted_edge
]));
2505 if (inserted_edge
== 2)
2508 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2510 edge new_dominating_edge
= NULL
;
2511 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2513 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2514 if (e
!= new_non_dominating_edge
)
2516 new_dominating_edge
= e
;
2517 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2518 new_dominating_edge
,
2519 get_loc (old_phi_args
[inserted_edge
]));
2523 gcc_assert (new_dominating_edge
);
2527 /* Classic diamond structure: both edges are non-dominating. We need to
2528 find one unique edge then the other can be found be elimination. If
2529 any definition (def_pred) dominates both the preds of new_bb then we
2530 bail out. Entries of def_pred maybe NULL, in that case we must
2531 uniquely find pred with help of only one entry. */
2532 edge new_e
[2] = { NULL
, NULL
};
2533 for (int i
= 0; i
< 2; i
++)
2537 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2539 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2542 /* We do not know how to handle the case when def_pred
2543 dominates more than a predecessor. */
2549 gcc_assert (new_e
[0] || new_e
[1]);
2551 /* Find the other edge by process of elimination. */
2552 if (not_found_bb_index
!= -1)
2554 gcc_assert (!new_e
[not_found_bb_index
]);
2555 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2558 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2560 if (new_e
[found_bb_index
] == e
)
2562 new_e
[not_found_bb_index
] = e
;
2566 /* Add edges to phi args. */
2567 for (int i
= 0; i
< 2; i
++)
2568 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2569 get_loc (old_phi_args
[i
]));
2575 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2576 region. If postpone is true and it isn't possible to copy any arg of PHI,
2577 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2578 Returns false if the copying was unsuccessful. */
2581 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2586 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2587 gcc_assert (2 == gimple_phi_num_args (phi
));
2589 basic_block new_bb
= gimple_bb (new_phi
);
2590 loop_p loop
= gimple_bb (phi
)->loop_father
;
2592 basic_block old_bb
= gimple_bb (phi
);
2593 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2597 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2598 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2599 old_bb_non_dominating_edge
= e
;
2601 old_bb_dominating_edge
= e
;
2603 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2604 old_bb_non_dominating_edge
->src
));
2606 tree new_phi_args
[2];
2607 tree old_phi_args
[2];
2609 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2611 tree old_name
= gimple_phi_arg_def (phi
, i
);
2612 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2613 old_phi_args
[i
] = old_name
;
2616 new_phi_args
[i
] = new_name
;
2620 /* If the phi-arg was a parameter. */
2621 if (vec_find (region
->params
, old_name
) != -1)
2623 new_phi_args
[i
] = old_name
;
2627 "[codegen] parameter argument to phi, new_expr: ");
2628 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2629 fprintf (dump_file
, "\n");
2634 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2635 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2636 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2642 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2643 if (is_gimple_reg (old_name
)
2644 && scev_analyzable_p (old_name
, region
->region
))
2647 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2648 new_bb
, old_bb
, iv_map
);
2649 if (codegen_error_p ())
2652 gcc_assert (new_expr
);
2656 "[codegen] scev analyzeable, new_expr: ");
2657 print_generic_expr (dump_file
, new_expr
, 0);
2658 fprintf (dump_file
, "\n");
2660 gsi_insert_earliest (stmts
);
2661 new_phi_args
[i
] = new_name
;
2665 /* Postpone code gen for later for back-edges. */
2666 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2670 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2671 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2674 new_phi_args
[i
] = NULL_TREE
;
2678 /* Either we should add the arg to phi or, we should postpone. */
2682 /* If none of the args have been determined in the first stage then wait until
2684 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2687 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2688 old_bb_dominating_edge
,
2689 old_bb_non_dominating_edge
,
2690 phi
, new_phi
, new_bb
);
2693 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2694 containing phi nodes coming from two predecessors, and none of them are back
2698 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2703 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2706 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2709 /* Cond phi nodes should have exactly two arguments. */
2710 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2712 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2715 gphi
*phi
= psi
.phi ();
2716 tree res
= gimple_phi_result (phi
);
2717 if (virtual_operand_p (res
))
2719 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2720 /* Cond phi nodes should not be scev_analyzable_p. */
2723 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2724 tree new_res
= create_new_def_for (res
, new_phi
,
2725 gimple_phi_result_ptr (new_phi
));
2726 set_rename (res
, new_res
);
2728 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2731 update_stmt (new_phi
);
2737 /* Return true if STMT should be copied from region to the new code-generated
2738 region. LABELs, CONDITIONS, induction-variables and region parameters need
2742 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2744 /* Do not copy labels or conditions. */
2745 if (gimple_code (stmt
) == GIMPLE_LABEL
2746 || gimple_code (stmt
) == GIMPLE_COND
)
2750 /* Do not copy induction variables. */
2751 if (is_gimple_assign (stmt
)
2752 && (lhs
= gimple_assign_lhs (stmt
))
2753 && TREE_CODE (lhs
) == SSA_NAME
2754 && is_gimple_reg (lhs
)
2755 && scev_analyzable_p (lhs
, region
->region
))
2761 /* Create new names for all the definitions created by COPY and add replacement
2762 mappings for each new name. */
2765 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2767 def_operand_p def_p
;
2768 ssa_op_iter op_iter
;
2769 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2771 tree old_name
= DEF_FROM_PTR (def_p
);
2772 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2773 set_rename (old_name
, new_name
);
2777 /* Duplicates the statements of basic block BB into basic block NEW_BB
2778 and compute the new induction variables according to the IV_MAP.
2779 CODEGEN_ERROR is set when the code generation cannot continue. */
2782 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2786 /* Iterator poining to the place where new statement (s) will be inserted. */
2787 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2789 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2792 gimple
*stmt
= gsi_stmt (gsi
);
2793 if (!should_copy_to_new_region (stmt
, region
))
2796 /* Create a new copy of STMT and duplicate STMT's virtual
2798 gimple
*copy
= gimple_copy (stmt
);
2799 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2803 fprintf (dump_file
, "[codegen] inserting statement: ");
2804 print_gimple_stmt (dump_file
, copy
, 0, 0);
2807 maybe_duplicate_eh_stmt (copy
, stmt
);
2808 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2810 /* Crete new names for each def in the copied stmt. */
2811 set_rename_for_each_def (copy
);
2813 loop_p loop
= bb
->loop_father
;
2814 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2816 fold_stmt_inplace (&gsi_tgt
);
2817 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2820 if (codegen_error_p ())
2830 /* Given a basic block containing close-phi it returns the new basic block where
2831 to insert a copy of the close-phi nodes. All the uses in close phis should
2832 come from a single loop otherwise it returns NULL. */
2835 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2837 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2838 of close phi in the original code and then find the mapping of basic block
2839 defining that variable. If there are multiple close-phis and they are
2840 defined in different loops (in the original or in the new code) because of
2841 loop splitting, then we bail out. */
2842 loop_p new_loop
= NULL
;
2843 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2846 gphi
*phi
= psi
.phi ();
2847 tree name
= gimple_phi_arg_def (phi
, 0);
2848 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2850 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2851 if (!bbs
|| bbs
->length () != 1)
2852 /* This is one of the places which shows preserving original structure
2853 is not always possible, as we may need to insert close PHI for a loop
2854 where the latch does not have any mapping, or the mapping is
2859 new_loop
= (*bbs
)[0]->loop_father
;
2860 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2867 return single_exit (new_loop
);
2870 /* Copies BB and includes in the copied BB all the statements that can
2871 be reached following the use-def chains from the memory accesses,
2872 and returns the next edge following this new block. codegen_error is
2873 set when the code generation cannot continue. */
2876 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2880 int num_phis
= number_of_phi_nodes (bb
);
2882 if (region
->copied_bb_map
->get (bb
))
2884 /* FIXME: we should be able to handle phi nodes with args coming from
2885 outside the region. */
2888 codegen_error
= true;
2893 basic_block new_bb
= NULL
;
2894 if (bb_contains_loop_close_phi_nodes (bb
))
2897 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2900 edge e
= edge_for_new_close_phis (bb
);
2903 codegen_error
= true;
2907 basic_block phi_bb
= e
->dest
;
2909 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2910 phi_bb
= split_edge (e
);
2912 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2913 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2915 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2917 codegen_error
= true;
2924 new_bb
= split_edge (next_e
);
2928 new_bb
= split_edge (next_e
);
2929 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2931 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2933 /* At this point we are unable to codegenerate by still preserving the SSA
2934 structure because maybe the loop is completely unrolled and the PHIs
2935 and cross-bb scalar dependencies are untrackable w.r.t. the original
2936 code. See gfortran.dg/graphite/pr29832.f90. */
2937 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2939 codegen_error
= true;
2943 /* In case isl did some loop peeling, like this:
2946 for (int c1 = 1; c1 <= 5; c1 += 1) {
2951 there should be no loop-phi nodes in S_8(0).
2953 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2954 values of all scalar variables: for the moment we instantiate only
2955 SCEV analyzable expressions on the iteration domain, and we need to
2956 extend that to reductions that cannot be analyzed by SCEV. */
2957 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2959 codegen_error
= true;
2964 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2966 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2968 codegen_error
= true;
2972 else if (num_phis
> 0)
2975 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2978 basic_block phi_bb
= single_pred (new_bb
);
2979 loop_p loop_father
= new_bb
->loop_father
;
2981 /* Move back until we find the block with two predecessors. */
2982 while (single_pred_p (phi_bb
))
2983 phi_bb
= single_pred_edge (phi_bb
)->src
;
2985 /* If a corresponding merge-point was not found, then abort codegen. */
2986 if (phi_bb
->loop_father
!= loop_father
2987 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2988 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2990 codegen_error
= true;
2997 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2998 bb
->index
, new_bb
->index
);
3000 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
3002 copied_bbs
->safe_push (new_bb
);
3005 vec
<basic_block
> bbs
;
3007 bbs
.safe_push (new_bb
);
3008 region
->copied_bb_map
->put (bb
, bbs
);
3011 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3013 codegen_error
= true;
3017 return single_succ_edge (new_bb
);
3020 /* Patch the missing arguments of the phi nodes. */
3023 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3027 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3029 gphi
*old_phi
= rename
->first
;
3030 gphi
*new_phi
= rename
->second
;
3031 basic_block old_bb
= gimple_bb (old_phi
);
3032 basic_block new_bb
= gimple_bb (new_phi
);
3034 /* First edge is the init edge and second is the back edge. */
3035 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3036 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3040 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3041 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3044 auto_vec
<tree
, 1> iv_map
;
3045 if (bb_contains_loop_phi_nodes (new_bb
))
3046 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3048 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3049 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3051 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3055 fprintf (dump_file
, "[codegen] to new-phi: ");
3056 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3063 /* Prints NODE to FILE. */
3066 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3067 __isl_keep isl_ast_node
*node
,
3068 __isl_keep isl_ctx
*ctx
) const
3070 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3071 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3072 prn
= isl_printer_print_ast_node (prn
, node
);
3073 prn
= isl_printer_print_str (prn
, "\n");
3074 isl_printer_free (prn
);
3077 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
3080 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3083 sese_info_p region
= scop
->scop_info
;
3084 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3085 gcc_assert (nb_parameters
== region
->params
.length ());
3087 for (i
= 0; i
< nb_parameters
; i
++)
3089 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3091 ip
[tmp_id
] = region
->params
[i
];
3096 /* Generates a build, which specifies the constraints on the parameters. */
3098 __isl_give isl_ast_build
*
3099 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3101 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3102 return isl_ast_build_from_context (context_isl
);
3105 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3108 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3112 int schedule_dims
= 0;
3114 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3116 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3117 if (pbb_schedule_dims
> schedule_dims
)
3118 schedule_dims
= pbb_schedule_dims
;
3121 return schedule_dims
;
3124 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3126 For schedules with different dimensionality, the isl AST generator can not
3127 define an order and will just randomly choose an order. The solution to this
3128 problem is to extend all schedules to the maximal number of schedule
3129 dimensions (using '0's for the remaining values). */
3131 __isl_give isl_map
*
3132 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3133 int nb_schedule_dims
)
3135 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3137 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3139 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3141 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3144 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3146 isl_val_free (zero
);
3150 /* Generates a schedule, which specifies an order used to
3151 visit elements in a domain. */
3153 __isl_give isl_union_map
*
3154 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3156 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3159 isl_union_map
*schedule_isl
=
3160 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3162 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3164 /* Dead code elimination: when the domain of a PBB is empty,
3165 don't generate code for the PBB. */
3166 if (isl_set_is_empty (pbb
->domain
))
3169 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3170 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3171 isl_set_copy (pbb
->domain
));
3172 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3173 bb_schedule
= isl_map_coalesce (bb_schedule
);
3175 = isl_union_map_union (schedule_isl
,
3176 isl_union_map_from_map (bb_schedule
));
3177 schedule_isl
= isl_union_map_coalesce (schedule_isl
);
3179 return schedule_isl
;
3182 /* This method is executed before the construction of a for node. */
3184 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3186 isl_union_map
*dependences
= (isl_union_map
*) user
;
3187 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3188 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3189 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3190 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3191 for_info
->is_parallelizable
=
3192 !carries_deps (schedule
, dependences
, dimension
);
3193 isl_union_map_free (schedule
);
3194 isl_space_free (schedule_space
);
3195 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3199 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3200 /* Set the separate option for all schedules. This helps reducing control
3203 __isl_give isl_schedule
*
3204 translate_isl_ast_to_gimple::set_options_for_schedule_tree
3205 (__isl_take isl_schedule
*schedule
)
3207 return isl_schedule_map_schedule_node_bottom_up
3208 (schedule
, set_separate_option
, NULL
);
3212 /* Set the separate option for all dimensions.
3213 This helps to reduce control overhead. */
3215 __isl_give isl_ast_build
*
3216 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3217 __isl_keep isl_union_map
*schedule
)
3219 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3220 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3222 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3223 isl_union_set
*range
=
3224 isl_union_set_from_set (isl_set_universe (range_space
));
3225 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3226 domain
= isl_union_set_universe (domain
);
3227 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3228 return isl_ast_build_set_options (control
, options
);
3231 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3233 __isl_give isl_ast_node
*
3234 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3236 isl_ast_node
*ast_isl
= NULL
;
3237 /* Generate loop upper bounds that consist of the current loop iterator, an
3238 operator (< or <=) and an expression not involving the iterator. If this
3239 option is not set, then the current loop iterator may appear several times
3240 in the upper bound. See the isl manual for more details. */
3241 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3243 add_parameters_to_ivs_params (scop
, ip
);
3244 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3245 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3246 context_isl
= set_options (context_isl
, schedule_isl
);
3247 if (flag_loop_parallelize_all
)
3249 isl_union_map
*dependence
= scop_get_dependences (scop
);
3251 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3255 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3258 scop
->schedule
= set_options_for_schedule_tree (scop
->schedule
);
3259 ast_isl
= isl_ast_build_node_from_schedule (context_isl
, scop
->schedule
);
3260 isl_union_map_free(schedule_isl
);
3263 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3265 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3266 isl_schedule_free (scop
->schedule
);
3269 isl_ast_build_free (context_isl
);
3273 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3274 the given SCOP. Return true if code generation succeeded.
3276 FIXME: This is not yet a full implementation of the code generator
3277 with isl ASTs. Generation of GIMPLE code has to be completed. */
3280 graphite_regenerate_ast_isl (scop_p scop
)
3282 sese_info_p region
= scop
->scop_info
;
3283 translate_isl_ast_to_gimple
t (region
);
3285 ifsese if_region
= NULL
;
3286 isl_ast_node
*root_node
;
3289 timevar_push (TV_GRAPHITE_CODE_GEN
);
3290 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3294 fprintf (dump_file
, "AST generated by isl: \n");
3295 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3298 recompute_all_dominators ();
3301 if_region
= move_sese_in_condition (region
);
3302 region
->if_region
= if_region
;
3303 recompute_all_dominators ();
3305 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3307 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3308 basic_block bb
= split_edge (e
);
3310 /* Update the true_region exit edge. */
3311 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3313 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3314 if (t
.codegen_error_p ())
3317 fprintf (dump_file
, "[codegen] unsuccessful,"
3318 " reverting back to the original code.\n");
3319 set_ifsese_condition (if_region
, integer_zero_node
);
3323 t
.translate_pending_phi_nodes ();
3324 if (!t
.codegen_error_p ())
3326 sese_insert_phis_for_liveouts (region
,
3327 if_region
->region
->region
.exit
->src
,
3328 if_region
->false_region
->region
.exit
,
3329 if_region
->true_region
->region
.exit
);
3330 mark_virtual_operands_for_renaming (cfun
);
3331 update_ssa (TODO_update_ssa
);
3336 recompute_all_dominators ();
3342 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3343 " pending phis, reverting back to the original code.\n");
3344 set_ifsese_condition (if_region
, integer_zero_node
);
3348 free (if_region
->true_region
);
3349 free (if_region
->region
);
3352 ivs_params_clear (ip
);
3353 isl_ast_node_free (root_node
);
3354 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3359 int num_no_dependency
= 0;
3361 FOR_EACH_LOOP (loop
, 0)
3362 if (loop
->can_be_parallel
)
3363 num_no_dependency
++;
3365 fprintf (dump_file
, "%d loops carried no dependency.\n",
3369 return !t
.codegen_error_p ();
3372 #endif /* HAVE_isl */