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
,
1262 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1263 at the exit of loop which takes one argument that is the last value of the
1264 variable being used out of the loop. */
1267 bb_contains_loop_close_phi_nodes (basic_block bb
)
1269 return single_pred_p (bb
)
1270 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1273 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1274 header containing phi nodes which has one init-edge and one back-edge. */
1277 bb_contains_loop_phi_nodes (basic_block bb
)
1279 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1281 if (bb
->preds
->length () == 1)
1284 unsigned depth
= loop_depth (bb
->loop_father
);
1286 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1288 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1289 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1292 /* When one of the edges correspond to the same loop father and other
1294 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1295 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1298 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1299 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1305 /* Check if USE is defined in a basic block from where the definition of USE can
1306 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1309 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1311 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1314 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1315 if (bb_contains_loop_close_phi_nodes (bb
))
1318 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1319 basic_block def_bb
= gimple_bb (def
);
1321 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1324 /* Return the number of phi nodes in BB. */
1327 number_of_phi_nodes (basic_block bb
)
1330 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1336 /* Returns true if BB uses name in one of its PHIs. */
1339 phi_uses_name (basic_block bb
, tree name
)
1341 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1344 gphi
*phi
= psi
.phi ();
1345 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1347 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1348 if (use_arg
== name
)
1355 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1356 definition should flow into use, and the use should respect the loop-closed
1360 translate_isl_ast_to_gimple::
1361 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1362 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1364 /* The def of the rename must either dominate the uses or come from a
1365 back-edge. Also the def must respect the loop closed ssa form. */
1366 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1370 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1371 print_generic_expr (dump_file
, rename
, 0);
1372 fprintf (dump_file
, "\n");
1377 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1380 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1382 /* The loop-header dominates the loop-body. */
1383 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1386 /* RENAME would be used in loop-phi. */
1387 gcc_assert (number_of_phi_nodes (use_bb
));
1389 /* For definitions coming from back edges, we should check that
1390 old_name is used in a loop PHI node.
1391 FIXME: Verify if this is true. */
1392 if (phi_uses_name (old_bb
, old_name
))
1398 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1399 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1400 within a loop PHI instruction. */
1403 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1406 bool loop_phi
) const
1408 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1409 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1411 if (!renames
|| renames
->is_empty ())
1414 if (1 == renames
->length ())
1416 tree rename
= (*renames
)[0];
1417 if (TREE_CODE (rename
) == SSA_NAME
)
1419 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1420 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1425 if (is_constant (rename
))
1431 /* More than one renames corresponding to the old_name. Find the rename for
1432 which the definition flows into usage at new_bb. */
1434 tree t1
= NULL_TREE
, t2
;
1435 basic_block t1_bb
= NULL
;
1436 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1438 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1440 /* Defined in the same basic block as used. */
1441 if (t2_bb
== new_bb
)
1444 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1445 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1448 /* Compute the nearest dominator. */
1449 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1459 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1460 When OLD_NAME and EXPR are the same we assert. */
1463 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1467 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1468 print_generic_expr (dump_file
, old_name
, 0);
1469 fprintf (dump_file
, ", new_name = ");
1470 print_generic_expr (dump_file
, expr
, 0);
1471 fprintf (dump_file
, "\n");
1474 if (old_name
== expr
)
1477 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1480 renames
->safe_push (expr
);
1486 region
->rename_map
->put (old_name
, r
);
1490 /* Return an iterator to the instructions comes last in the execution order.
1491 Either GSI1 and GSI2 should belong to the same basic block or one of their
1492 respective basic blocks should dominate the other. */
1494 gimple_stmt_iterator
1495 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1497 basic_block bb1
= gsi_bb (gsi1
);
1498 basic_block bb2
= gsi_bb (gsi2
);
1500 /* Find the iterator which is the latest. */
1503 /* For empty basic blocks gsis point to the end of the sequence. Since
1504 there is no operator== defined for gimple_stmt_iterator and for gsis
1505 not pointing to a valid statement gsi_next would assert. */
1506 gimple_stmt_iterator gsi
= gsi1
;
1508 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1511 } while (!gsi_end_p (gsi
));
1516 /* Find the basic block closest to the basic block which defines stmt. */
1517 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1520 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1524 /* Insert each statement from SEQ at its earliest insertion p. */
1527 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1529 update_modified_stmts (seq
);
1530 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1531 basic_block begin_bb
= get_entry_bb (codegen_region
);
1533 /* Inserting the gimple statements in a vector because gimple_seq behave
1534 in strage ways when inserting the stmts from it into different basic
1535 blocks one at a time. */
1536 auto_vec
<gimple
*, 3> stmts
;
1537 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1539 stmts
.safe_push (gsi_stmt (gsi
));
1543 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1545 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1546 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1548 use_operand_p use_p
;
1549 ssa_op_iter op_iter
;
1550 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1552 /* Iterator to the current def of use_p. For function parameters or
1553 anything where def is not found, insert at the beginning of the
1554 generated region. */
1555 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1557 tree op
= USE_FROM_PTR (use_p
);
1558 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1559 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1560 gsi_stmt
= gsi_for_stmt (stmt
);
1562 /* For region parameters, insert at the beginning of the generated
1564 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1565 gsi_stmt
= gsi_def_stmt
;
1567 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1570 if (!gsi_stmt (gsi_def_stmt
))
1572 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1573 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1575 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1577 gimple_stmt_iterator bsi
1578 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1579 /* Insert right after the PHI statements. */
1580 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1583 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1587 fprintf (dump_file
, "[codegen] inserting statement: ");
1588 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1589 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1594 /* Collect all the operands of NEW_EXPR by recursively visiting each
1598 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1602 /* Rename all uses in new_expr. */
1603 if (TREE_CODE (new_expr
) == SSA_NAME
)
1605 vec_ssa
->safe_push (new_expr
);
1609 /* Iterate over SSA_NAMES in NEW_EXPR. */
1610 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1612 tree op
= TREE_OPERAND (new_expr
, i
);
1613 collect_all_ssa_names (op
, vec_ssa
);
1617 /* This is abridged version of the function copied from:
1618 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1621 substitute_ssa_name (tree exp
, tree f
, tree r
)
1623 enum tree_code code
= TREE_CODE (exp
);
1624 tree op0
, op1
, op2
, op3
;
1627 /* We handle TREE_LIST and COMPONENT_REF separately. */
1628 if (code
== TREE_LIST
)
1630 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1631 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1632 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1635 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1637 else if (code
== COMPONENT_REF
)
1641 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1642 and it is the right field, replace it with R. */
1643 for (inner
= TREE_OPERAND (exp
, 0);
1644 REFERENCE_CLASS_P (inner
);
1645 inner
= TREE_OPERAND (inner
, 0))
1649 op1
= TREE_OPERAND (exp
, 1);
1651 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1654 /* If this expression hasn't been completed let, leave it alone. */
1655 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1658 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1659 if (op0
== TREE_OPERAND (exp
, 0))
1663 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1666 switch (TREE_CODE_CLASS (code
))
1671 case tcc_declaration
:
1677 case tcc_expression
:
1681 /* Fall through... */
1683 case tcc_exceptional
:
1686 case tcc_comparison
:
1688 switch (TREE_CODE_LENGTH (code
))
1696 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1697 if (op0
== TREE_OPERAND (exp
, 0))
1700 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1704 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1705 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1707 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1710 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1714 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1715 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1716 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1718 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1719 && op2
== TREE_OPERAND (exp
, 2))
1722 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1726 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1727 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1728 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1729 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1731 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1732 && op2
== TREE_OPERAND (exp
, 2)
1733 && op3
== TREE_OPERAND (exp
, 3))
1737 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1750 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1752 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1753 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1758 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1761 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1764 auto_vec
<tree
, 2> ssa_names
;
1765 collect_all_ssa_names (new_expr
, &ssa_names
);
1768 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1769 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1770 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1775 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1776 scalar evolution around LOOP. */
1779 translate_isl_ast_to_gimple::
1780 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1781 basic_block new_bb
, basic_block old_bb
,
1784 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1786 /* At this point we should know the exact scev for each
1787 scalar SSA_NAME used in the scop: all the other scalar
1788 SSA_NAMEs should have been translated out of SSA using
1789 arrays with one element. */
1791 if (chrec_contains_undetermined (scev
))
1793 codegen_error
= true;
1794 return build_zero_cst (TREE_TYPE (old_name
));
1797 new_expr
= chrec_apply_map (scev
, iv_map
);
1799 /* The apply should produce an expression tree containing
1800 the uses of the new induction variables. We should be
1801 able to use new_expr instead of the old_name in the newly
1802 generated loop nest. */
1803 if (chrec_contains_undetermined (new_expr
)
1804 || tree_contains_chrecs (new_expr
, NULL
))
1806 codegen_error
= true;
1807 return build_zero_cst (TREE_TYPE (old_name
));
1810 /* We should check all the operands and all of them should dominate the use at
1812 if (TREE_CODE (new_expr
) == SSA_NAME
)
1814 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1815 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1817 codegen_error
= true;
1818 return build_zero_cst (TREE_TYPE (old_name
));
1822 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1824 /* We check all the operands and all of them should dominate the use at
1826 auto_vec
<tree
, 2> new_ssa_names
;
1827 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1830 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1832 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1834 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1835 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1837 codegen_error
= true;
1838 return build_zero_cst (TREE_TYPE (old_name
));
1843 /* Replace the old_name with the new_expr. */
1844 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1848 /* Renames the scalar uses of the statement COPY, using the
1849 substitution map RENAME_MAP, inserting the gimplification code at
1850 GSI_TGT, for the translation REGION, with the original copied
1851 statement in LOOP, and using the induction variable renaming map
1852 IV_MAP. Returns true when something has been renamed. codegen_error
1853 is set when the code generation cannot continue. */
1856 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1857 gimple_stmt_iterator
*gsi_tgt
,
1859 loop_p loop
, vec
<tree
> iv_map
)
1861 bool changed
= false;
1863 if (is_gimple_debug (copy
))
1865 if (gimple_debug_bind_p (copy
))
1866 gimple_debug_bind_reset_value (copy
);
1867 else if (gimple_debug_source_bind_p (copy
))
1877 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1878 print_gimple_stmt (dump_file
, copy
, 0, 0);
1881 use_operand_p use_p
;
1882 ssa_op_iter op_iter
;
1883 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1885 tree old_name
= USE_FROM_PTR (use_p
);
1889 fprintf (dump_file
, "[codegen] renaming old_name = ");
1890 print_generic_expr (dump_file
, old_name
, 0);
1891 fprintf (dump_file
, "\n");
1894 if (TREE_CODE (old_name
) != SSA_NAME
1895 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1899 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1904 tree type_old_name
= TREE_TYPE (old_name
);
1905 tree type_new_expr
= TREE_TYPE (new_expr
);
1909 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1910 print_generic_expr (dump_file
, new_expr
, 0);
1911 fprintf (dump_file
, "\n");
1914 if (type_old_name
!= type_new_expr
1915 || TREE_CODE (new_expr
) != SSA_NAME
)
1917 tree var
= create_tmp_var (type_old_name
, "var");
1919 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1920 new_expr
= fold_convert (type_old_name
, new_expr
);
1923 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1924 gsi_insert_earliest (stmts
);
1927 replace_exp (use_p
, new_expr
);
1932 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1934 if (!new_expr
|| codegen_error_p ())
1939 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1940 print_generic_expr (dump_file
, new_expr
, 0);
1941 fprintf (dump_file
, "\n");
1944 gsi_insert_earliest (stmts
);
1945 replace_exp (use_p
, new_expr
);
1947 if (TREE_CODE (new_expr
) == INTEGER_CST
1948 && is_gimple_assign (copy
))
1950 tree rhs
= gimple_assign_rhs1 (copy
);
1952 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1953 recompute_tree_invariant_for_addr_expr (rhs
);
1956 set_rename (old_name
, new_expr
);
1962 /* Returns a basic block that could correspond to where a constant was defined
1963 in the original code. In the original code OLD_BB had the definition, we
1964 need to find which basic block out of the copies of old_bb, in the new
1965 region, should a definition correspond to if it has to reach BB. */
1968 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1969 basic_block old_bb
) const
1971 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1973 if (!bbs
|| bbs
->is_empty ())
1976 if (1 == bbs
->length ())
1980 basic_block b1
= NULL
, b2
;
1981 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1986 /* BB and B2 are in two unrelated if-clauses. */
1987 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1990 /* Compute the nearest dominator. */
1991 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1999 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
2000 when we want to rename an OP within a loop PHI instruction. */
2003 translate_isl_ast_to_gimple::
2004 get_new_name (basic_block new_bb
, tree op
,
2005 basic_block old_bb
, bool loop_phi
) const
2007 /* For constants the names are the same. */
2008 if (is_constant (op
))
2011 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
2014 /* Return a debug location for OP. */
2019 location_t loc
= UNKNOWN_LOCATION
;
2021 if (TREE_CODE (op
) == SSA_NAME
)
2022 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2026 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2027 the init edge (from outside the loop) and the second one is the back edge
2028 from the same loop. */
2030 std::pair
<edge
, edge
>
2031 get_edges (basic_block bb
)
2033 std::pair
<edge
, edge
> edges
;
2036 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2037 if (bb
->loop_father
!= e
->src
->loop_father
)
2044 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2045 must be found unless they can be POSTPONEd for later. */
2048 translate_isl_ast_to_gimple::
2049 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2050 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2053 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2055 basic_block new_bb
= gimple_bb (new_phi
);
2056 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2059 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2060 e
= ibp_new_bb
.first
;
2062 e
= ibp_new_bb
.second
;
2064 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2065 tree new_name
= get_new_name (new_bb
, old_name
,
2066 gimple_bb (old_phi
), true);
2069 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2073 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2074 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2075 /* If the phi arg was a function arg, or wasn't defined, just use the
2077 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2080 /* Postpone code gen for later for those back-edges we don't have the
2082 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2084 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2087 /* Either we should add the arg to phi or, we should postpone. */
2093 /* Copy loop phi nodes from BB to NEW_BB. */
2096 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2100 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2103 /* Loop phi nodes should have only two arguments. */
2104 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2106 /* First edge is the init edge and second is the back edge. */
2107 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2109 /* First edge is the init edge and second is the back edge. */
2110 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2112 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2115 gphi
*phi
= psi
.phi ();
2116 tree res
= gimple_phi_result (phi
);
2117 if (virtual_operand_p (res
))
2119 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2122 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2123 tree new_res
= create_new_def_for (res
, new_phi
,
2124 gimple_phi_result_ptr (new_phi
));
2125 set_rename (res
, new_res
);
2126 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2128 update_stmt (new_phi
);
2132 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2133 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2140 /* Return the init value of PHI, the value coming from outside the loop. */
2143 get_loop_init_value (gphi
*phi
)
2146 loop_p loop
= gimple_bb (phi
)->loop_father
;
2150 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2151 if (e
->src
->loop_father
!= loop
)
2152 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2157 /* Find the init value (the value which comes from outside the loop), of one of
2158 the operands of DEF which is defined by a loop phi. */
2161 find_init_value (gimple
*def
)
2163 if (gimple_code (def
) == GIMPLE_PHI
)
2164 return get_loop_init_value (as_a
<gphi
*> (def
));
2166 if (gimple_vuse (def
))
2170 use_operand_p use_p
;
2171 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2173 tree use
= USE_FROM_PTR (use_p
);
2174 if (TREE_CODE (use
) == SSA_NAME
)
2176 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2184 /* Return the init value, the value coming from outside the loop. */
2187 find_init_value_close_phi (gphi
*phi
)
2189 gcc_assert (gimple_phi_num_args (phi
) == 1);
2190 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2191 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2192 return find_init_value (def
);
2196 tree
translate_isl_ast_to_gimple::
2197 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2198 gimple
*old_close_phi
)
2200 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2201 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2202 basic_block bb
= gimple_bb (stmt
);
2203 if (!bb_in_sese_p (bb
, codegen_region
))
2204 return last_merge_name
;
2206 loop_p loop
= bb
->loop_father
;
2207 if (!loop_in_sese_p (loop
, codegen_region
))
2208 return last_merge_name
;
2210 edge e
= single_exit (loop
);
2212 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2213 return last_merge_name
;
2215 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2216 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2219 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2220 bb
= split_edge (e
);
2222 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2223 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2224 gimple_phi_result_ptr (close_phi
));
2225 set_rename (old_close_phi_name
, res
);
2226 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2227 last_merge_name
= res
;
2229 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2232 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2233 the close phi node PHI. */
2235 bool translate_isl_ast_to_gimple::
2236 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2239 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2240 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2241 if (SSA_NAME
== TREE_CODE (default_value
))
2243 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2244 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2246 default_value_bb
= gimple_bb (stmt
);
2249 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2251 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2252 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2253 tree last_merge_name
= new_close_phi_name
;
2254 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2258 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2260 basic_block new_merge_bb
= merge_e
->src
;
2261 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2264 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2267 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2268 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2269 gimple_phi_result_ptr (merge_phi
));
2270 set_rename (old_close_phi_name
, merge_res
);
2272 edge from_loop
= NULL
, from_default_value
= NULL
;
2275 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2276 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2279 from_default_value
= e
;
2281 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2282 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2283 is contained in another condition. */
2284 if (!from_default_value
|| !from_loop
)
2287 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2288 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2292 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2293 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2296 update_stmt (merge_phi
);
2297 last_merge_name
= merge_res
;
2303 /* Copy all the loop-close phi args from BB to NEW_BB. */
2306 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2310 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2313 gphi
*old_close_phi
= psi
.phi ();
2314 tree res
= gimple_phi_result (old_close_phi
);
2315 if (virtual_operand_p (res
))
2318 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2319 /* Loop close phi nodes should not be scev_analyzable_p. */
2322 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2323 tree new_res
= create_new_def_for (res
, new_close_phi
,
2324 gimple_phi_result_ptr (new_close_phi
));
2325 set_rename (res
, new_res
);
2327 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2328 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2330 /* Predecessor basic blocks of a loop close phi should have been code
2331 generated before. FIXME: This is fixable by merging PHIs from inner
2332 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2336 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2337 get_loc (old_name
));
2340 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2341 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2344 update_stmt (new_close_phi
);
2346 /* When there is no loop guard around this codegenerated loop, there is no
2347 need to collect the close-phi arg. */
2348 if (merge_points
.is_empty ())
2351 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2352 tree default_value
= find_init_value_close_phi (new_close_phi
);
2354 /* A close phi must come from a loop-phi having a default value. */
2360 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2364 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2365 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2370 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2378 /* Copy loop close phi nodes from BB to NEW_BB. */
2381 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2385 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2387 /* Loop close phi nodes should have only one argument. */
2388 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2390 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2394 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2395 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2396 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2397 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2400 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2401 In this case DOMINATING_PRED = NULL.
2403 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2405 Returns true on successful copy of the args, false otherwise. */
2408 translate_isl_ast_to_gimple::
2409 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2410 edge old_bb_dominating_edge
,
2411 edge old_bb_non_dominating_edge
,
2412 gphi
*phi
, gphi
*new_phi
,
2415 basic_block def_pred
[2] = { NULL
, NULL
};
2416 int not_found_bb_index
= -1;
2417 for (int i
= 0; i
< 2; i
++)
2419 /* If the corresponding def_bb could not be found the entry will be
2421 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2422 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2423 gimple_phi_arg_edge (phi
, i
)->src
);
2424 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2425 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2429 /* When non are available bail out. */
2430 if (not_found_bb_index
!= -1)
2432 not_found_bb_index
= i
;
2436 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2437 if (old_bb_dominating_edge
)
2439 if (not_found_bb_index
!= -1)
2442 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2443 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2444 vec
<basic_block
> *bbs
2445 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2447 /* Could not find a mapping. */
2451 basic_block new_pred
= NULL
;
2454 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2456 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2458 /* FIXME: If we have already found new_pred then we have to
2459 disambiguate, bail out for now. */
2462 new_pred
= new_pred1
;
2464 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2466 /* FIXME: If we have already found new_pred then we have to either
2467 it dominates both or we have to disambiguate, bail out. */
2470 new_pred
= new_pred2
;
2477 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2478 gcc_assert (new_non_dominating_edge
);
2479 /* FIXME: Validate each args just like in loop-phis. */
2480 /* By the process of elimination we first insert insert phi-edge for
2481 non-dominating pred which is computed above and then we insert the
2483 int inserted_edge
= 0;
2484 for (; inserted_edge
< 2; inserted_edge
++)
2486 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2487 if (new_non_dominating_edge
== new_bb_pred_edge
)
2489 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2490 new_non_dominating_edge
,
2491 get_loc (old_phi_args
[inserted_edge
]));
2495 if (inserted_edge
== 2)
2498 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2500 edge new_dominating_edge
= NULL
;
2501 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2503 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2504 if (e
!= new_non_dominating_edge
)
2506 new_dominating_edge
= e
;
2507 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2508 new_dominating_edge
,
2509 get_loc (old_phi_args
[inserted_edge
]));
2513 gcc_assert (new_dominating_edge
);
2517 /* Classic diamond structure: both edges are non-dominating. We need to
2518 find one unique edge then the other can be found be elimination. If
2519 any definition (def_pred) dominates both the preds of new_bb then we
2520 bail out. Entries of def_pred maybe NULL, in that case we must
2521 uniquely find pred with help of only one entry. */
2522 edge new_e
[2] = { NULL
, NULL
};
2523 for (int i
= 0; i
< 2; i
++)
2527 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2529 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2532 /* We do not know how to handle the case when def_pred
2533 dominates more than a predecessor. */
2539 gcc_assert (new_e
[0] || new_e
[1]);
2541 /* Find the other edge by process of elimination. */
2542 if (not_found_bb_index
!= -1)
2544 gcc_assert (!new_e
[not_found_bb_index
]);
2545 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2548 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2550 if (new_e
[found_bb_index
] == e
)
2552 new_e
[not_found_bb_index
] = e
;
2556 /* Add edges to phi args. */
2557 for (int i
= 0; i
< 2; i
++)
2558 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2559 get_loc (old_phi_args
[i
]));
2565 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2566 region. If postpone is true and it isn't possible to copy any arg of PHI,
2567 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2568 Returns false if the copying was unsuccessful. */
2571 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2576 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2577 gcc_assert (2 == gimple_phi_num_args (phi
));
2579 basic_block new_bb
= gimple_bb (new_phi
);
2580 loop_p loop
= gimple_bb (phi
)->loop_father
;
2582 basic_block old_bb
= gimple_bb (phi
);
2583 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2587 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2588 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2589 old_bb_non_dominating_edge
= e
;
2591 old_bb_dominating_edge
= e
;
2593 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2594 old_bb_non_dominating_edge
->src
));
2596 tree new_phi_args
[2];
2597 tree old_phi_args
[2];
2599 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2601 tree old_name
= gimple_phi_arg_def (phi
, i
);
2602 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2603 old_phi_args
[i
] = old_name
;
2606 new_phi_args
[i
] = new_name
;
2610 /* If the phi-arg was a parameter. */
2611 if (vec_find (region
->params
, old_name
) != -1)
2613 new_phi_args
[i
] = old_name
;
2617 "[codegen] parameter argument to phi, new_expr: ");
2618 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2619 fprintf (dump_file
, "\n");
2624 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2625 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2626 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2632 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2633 if (is_gimple_reg (old_name
)
2634 && scev_analyzable_p (old_name
, region
->region
))
2637 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2638 new_bb
, old_bb
, iv_map
);
2639 if (codegen_error_p ())
2642 gcc_assert (new_expr
);
2646 "[codegen] scev analyzeable, new_expr: ");
2647 print_generic_expr (dump_file
, new_expr
, 0);
2648 fprintf (dump_file
, "\n");
2650 gsi_insert_earliest (stmts
);
2651 new_phi_args
[i
] = new_name
;
2655 /* Postpone code gen for later for back-edges. */
2656 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2660 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2661 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2664 new_phi_args
[i
] = NULL_TREE
;
2668 /* Either we should add the arg to phi or, we should postpone. */
2672 /* If none of the args have been determined in the first stage then wait until
2674 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2677 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2678 old_bb_dominating_edge
,
2679 old_bb_non_dominating_edge
,
2680 phi
, new_phi
, new_bb
);
2683 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2684 containing phi nodes coming from two predecessors, and none of them are back
2688 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2693 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2696 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2699 /* Cond phi nodes should have exactly two arguments. */
2700 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2702 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2705 gphi
*phi
= psi
.phi ();
2706 tree res
= gimple_phi_result (phi
);
2707 if (virtual_operand_p (res
))
2709 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2710 /* Cond phi nodes should not be scev_analyzable_p. */
2713 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2714 tree new_res
= create_new_def_for (res
, new_phi
,
2715 gimple_phi_result_ptr (new_phi
));
2716 set_rename (res
, new_res
);
2718 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2721 update_stmt (new_phi
);
2727 /* Return true if STMT should be copied from region to the new code-generated
2728 region. LABELs, CONDITIONS, induction-variables and region parameters need
2732 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2734 /* Do not copy labels or conditions. */
2735 if (gimple_code (stmt
) == GIMPLE_LABEL
2736 || gimple_code (stmt
) == GIMPLE_COND
)
2740 /* Do not copy induction variables. */
2741 if (is_gimple_assign (stmt
)
2742 && (lhs
= gimple_assign_lhs (stmt
))
2743 && TREE_CODE (lhs
) == SSA_NAME
2744 && is_gimple_reg (lhs
)
2745 && scev_analyzable_p (lhs
, region
->region
))
2751 /* Create new names for all the definitions created by COPY and add replacement
2752 mappings for each new name. */
2755 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2757 def_operand_p def_p
;
2758 ssa_op_iter op_iter
;
2759 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2761 tree old_name
= DEF_FROM_PTR (def_p
);
2762 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2763 set_rename (old_name
, new_name
);
2767 /* Duplicates the statements of basic block BB into basic block NEW_BB
2768 and compute the new induction variables according to the IV_MAP.
2769 CODEGEN_ERROR is set when the code generation cannot continue. */
2772 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2776 /* Iterator poining to the place where new statement (s) will be inserted. */
2777 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2779 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2782 gimple
*stmt
= gsi_stmt (gsi
);
2783 if (!should_copy_to_new_region (stmt
, region
))
2786 /* Create a new copy of STMT and duplicate STMT's virtual
2788 gimple
*copy
= gimple_copy (stmt
);
2789 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2793 fprintf (dump_file
, "[codegen] inserting statement: ");
2794 print_gimple_stmt (dump_file
, copy
, 0, 0);
2797 maybe_duplicate_eh_stmt (copy
, stmt
);
2798 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2800 /* Crete new names for each def in the copied stmt. */
2801 set_rename_for_each_def (copy
);
2803 loop_p loop
= bb
->loop_father
;
2804 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2806 fold_stmt_inplace (&gsi_tgt
);
2807 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2810 if (codegen_error_p ())
2820 /* Given a basic block containing close-phi it returns the new basic block where
2821 to insert a copy of the close-phi nodes. All the uses in close phis should
2822 come from a single loop otherwise it returns NULL. */
2825 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2827 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2828 of close phi in the original code and then find the mapping of basic block
2829 defining that variable. If there are multiple close-phis and they are
2830 defined in different loops (in the original or in the new code) because of
2831 loop splitting, then we bail out. */
2832 loop_p new_loop
= NULL
;
2833 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2836 gphi
*phi
= psi
.phi ();
2837 tree name
= gimple_phi_arg_def (phi
, 0);
2838 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2840 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2841 if (!bbs
|| bbs
->length () != 1)
2842 /* This is one of the places which shows preserving original structure
2843 is not always possible, as we may need to insert close PHI for a loop
2844 where the latch does not have any mapping, or the mapping is
2849 new_loop
= (*bbs
)[0]->loop_father
;
2850 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2857 return single_exit (new_loop
);
2860 /* Copies BB and includes in the copied BB all the statements that can
2861 be reached following the use-def chains from the memory accesses,
2862 and returns the next edge following this new block. codegen_error is
2863 set when the code generation cannot continue. */
2866 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2870 int num_phis
= number_of_phi_nodes (bb
);
2872 if (region
->copied_bb_map
->get (bb
))
2874 /* FIXME: we should be able to handle phi nodes with args coming from
2875 outside the region. */
2878 codegen_error
= true;
2883 basic_block new_bb
= NULL
;
2884 if (bb_contains_loop_close_phi_nodes (bb
))
2887 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2890 edge e
= edge_for_new_close_phis (bb
);
2893 codegen_error
= true;
2897 basic_block phi_bb
= e
->dest
;
2899 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2900 phi_bb
= split_edge (e
);
2902 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2903 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2905 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2907 codegen_error
= true;
2914 new_bb
= split_edge (next_e
);
2918 new_bb
= split_edge (next_e
);
2919 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2921 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2923 /* At this point we are unable to codegenerate by still preserving the SSA
2924 structure because maybe the loop is completely unrolled and the PHIs
2925 and cross-bb scalar dependencies are untrackable w.r.t. the original
2926 code. See gfortran.dg/graphite/pr29832.f90. */
2927 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2929 codegen_error
= true;
2933 /* In case isl did some loop peeling, like this:
2936 for (int c1 = 1; c1 <= 5; c1 += 1) {
2941 there should be no loop-phi nodes in S_8(0).
2943 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2944 values of all scalar variables: for the moment we instantiate only
2945 SCEV analyzable expressions on the iteration domain, and we need to
2946 extend that to reductions that cannot be analyzed by SCEV. */
2947 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2949 codegen_error
= true;
2954 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2956 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2958 codegen_error
= true;
2962 else if (num_phis
> 0)
2965 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2968 basic_block phi_bb
= single_pred (new_bb
);
2969 loop_p loop_father
= new_bb
->loop_father
;
2971 /* Move back until we find the block with two predecessors. */
2972 while (single_pred_p (phi_bb
))
2973 phi_bb
= single_pred_edge (phi_bb
)->src
;
2975 /* If a corresponding merge-point was not found, then abort codegen. */
2976 if (phi_bb
->loop_father
!= loop_father
2977 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2978 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2980 codegen_error
= true;
2987 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2988 bb
->index
, new_bb
->index
);
2990 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2992 copied_bbs
->safe_push (new_bb
);
2995 vec
<basic_block
> bbs
;
2997 bbs
.safe_push (new_bb
);
2998 region
->copied_bb_map
->put (bb
, bbs
);
3001 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3003 codegen_error
= true;
3007 return single_succ_edge (new_bb
);
3010 /* Patch the missing arguments of the phi nodes. */
3013 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3017 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3019 gphi
*old_phi
= rename
->first
;
3020 gphi
*new_phi
= rename
->second
;
3021 basic_block old_bb
= gimple_bb (old_phi
);
3022 basic_block new_bb
= gimple_bb (new_phi
);
3024 /* First edge is the init edge and second is the back edge. */
3025 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3026 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3030 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3031 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3034 auto_vec
<tree
, 1> iv_map
;
3035 if (bb_contains_loop_phi_nodes (new_bb
))
3036 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3038 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3039 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3041 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3045 fprintf (dump_file
, "[codegen] to new-phi: ");
3046 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3053 /* Prints NODE to FILE. */
3056 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3057 __isl_keep isl_ast_node
*node
,
3058 __isl_keep isl_ctx
*ctx
) const
3060 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3061 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3062 prn
= isl_printer_print_ast_node (prn
, node
);
3063 prn
= isl_printer_print_str (prn
, "\n");
3064 isl_printer_free (prn
);
3067 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
3070 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3073 sese_info_p region
= scop
->scop_info
;
3074 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3075 gcc_assert (nb_parameters
== region
->params
.length ());
3077 for (i
= 0; i
< nb_parameters
; i
++)
3079 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3081 ip
[tmp_id
] = region
->params
[i
];
3086 /* Generates a build, which specifies the constraints on the parameters. */
3088 __isl_give isl_ast_build
*
3089 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3091 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3092 return isl_ast_build_from_context (context_isl
);
3095 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3098 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3102 int schedule_dims
= 0;
3104 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3106 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3107 if (pbb_schedule_dims
> schedule_dims
)
3108 schedule_dims
= pbb_schedule_dims
;
3111 return schedule_dims
;
3114 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3116 For schedules with different dimensionality, the isl AST generator can not
3117 define an order and will just randomly choose an order. The solution to this
3118 problem is to extend all schedules to the maximal number of schedule
3119 dimensions (using '0's for the remaining values). */
3121 __isl_give isl_map
*
3122 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3123 int nb_schedule_dims
)
3125 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3127 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3129 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3131 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3134 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3136 isl_val_free (zero
);
3140 /* Generates a schedule, which specifies an order used to
3141 visit elements in a domain. */
3143 __isl_give isl_union_map
*
3144 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3146 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3149 isl_union_map
*schedule_isl
=
3150 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3152 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3154 /* Dead code elimination: when the domain of a PBB is empty,
3155 don't generate code for the PBB. */
3156 if (isl_set_is_empty (pbb
->domain
))
3159 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3160 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3161 isl_set_copy (pbb
->domain
));
3162 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3164 = isl_union_map_union (schedule_isl
,
3165 isl_union_map_from_map (bb_schedule
));
3167 return schedule_isl
;
3170 /* This method is executed before the construction of a for node. */
3172 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3174 isl_union_map
*dependences
= (isl_union_map
*) user
;
3175 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3176 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3177 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3178 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3179 for_info
->is_parallelizable
=
3180 !carries_deps (schedule
, dependences
, dimension
);
3181 isl_union_map_free (schedule
);
3182 isl_space_free (schedule_space
);
3183 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3187 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3188 /* Set the separate option for all schedules. This helps reducing control
3191 __isl_give isl_schedule
*
3192 translate_isl_ast_to_gimple::set_options_for_schedule_tree
3193 (__isl_take isl_schedule
*schedule
)
3195 return isl_schedule_map_schedule_node_bottom_up
3196 (schedule
, set_separate_option
, NULL
);
3200 /* Set the separate option for all dimensions.
3201 This helps to reduce control overhead. */
3203 __isl_give isl_ast_build
*
3204 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3205 __isl_keep isl_union_map
*schedule
)
3207 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3208 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3210 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3211 isl_union_set
*range
=
3212 isl_union_set_from_set (isl_set_universe (range_space
));
3213 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3214 domain
= isl_union_set_universe (domain
);
3215 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3216 return isl_ast_build_set_options (control
, options
);
3219 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3221 __isl_give isl_ast_node
*
3222 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3224 isl_ast_node
*ast_isl
= NULL
;
3225 /* Generate loop upper bounds that consist of the current loop iterator, an
3226 operator (< or <=) and an expression not involving the iterator. If this
3227 option is not set, then the current loop iterator may appear several times
3228 in the upper bound. See the isl manual for more details. */
3229 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3231 add_parameters_to_ivs_params (scop
, ip
);
3232 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3233 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3234 context_isl
= set_options (context_isl
, schedule_isl
);
3235 if (flag_loop_parallelize_all
)
3237 isl_union_map
*dependence
= scop_get_dependences (scop
);
3239 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3243 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3246 scop
->schedule
= set_options_for_schedule_tree (scop
->schedule
);
3247 ast_isl
= isl_ast_build_node_from_schedule (context_isl
, scop
->schedule
);
3248 isl_union_map_free(schedule_isl
);
3251 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3253 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3254 isl_schedule_free (scop
->schedule
);
3257 isl_ast_build_free (context_isl
);
3261 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3262 the given SCOP. Return true if code generation succeeded.
3264 FIXME: This is not yet a full implementation of the code generator
3265 with isl ASTs. Generation of GIMPLE code has to be completed. */
3268 graphite_regenerate_ast_isl (scop_p scop
)
3270 sese_info_p region
= scop
->scop_info
;
3271 translate_isl_ast_to_gimple
t (region
);
3273 ifsese if_region
= NULL
;
3274 isl_ast_node
*root_node
;
3277 timevar_push (TV_GRAPHITE_CODE_GEN
);
3278 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3282 fprintf (dump_file
, "AST generated by isl: \n");
3283 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3286 recompute_all_dominators ();
3289 if_region
= move_sese_in_condition (region
);
3290 region
->if_region
= if_region
;
3291 recompute_all_dominators ();
3293 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3295 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3296 basic_block bb
= split_edge (e
);
3298 /* Update the true_region exit edge. */
3299 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3301 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3302 if (t
.codegen_error_p ())
3305 fprintf (dump_file
, "[codegen] unsuccessful,"
3306 " reverting back to the original code.\n");
3307 set_ifsese_condition (if_region
, integer_zero_node
);
3311 t
.translate_pending_phi_nodes ();
3312 if (!t
.codegen_error_p ())
3314 sese_insert_phis_for_liveouts (region
,
3315 if_region
->region
->region
.exit
->src
,
3316 if_region
->false_region
->region
.exit
,
3317 if_region
->true_region
->region
.exit
);
3318 mark_virtual_operands_for_renaming (cfun
);
3319 update_ssa (TODO_update_ssa
);
3324 recompute_all_dominators ();
3330 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3331 " pending phis, reverting back to the original code.\n");
3332 set_ifsese_condition (if_region
, integer_zero_node
);
3336 free (if_region
->true_region
);
3337 free (if_region
->region
);
3340 ivs_params_clear (ip
);
3341 isl_ast_node_free (root_node
);
3342 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3344 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3347 int num_no_dependency
= 0;
3349 FOR_EACH_LOOP (loop
, 0)
3350 if (loop
->can_be_parallel
)
3351 num_no_dependency
++;
3353 fprintf (dump_file
, "%d loops carried no dependency.\n",
3357 return !t
.codegen_error_p ();
3360 #endif /* HAVE_isl */