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 static 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_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
);
140 /* Print SCHEDULE under an AST form on file F. */
143 print_schedule_ast (FILE *f
, __isl_keep isl_schedule
*schedule
, scop_p scop
)
145 isl_set
*set
= isl_set_params (isl_set_copy (scop
->param_context
));
146 isl_ast_build
*context
= isl_ast_build_from_context (set
);
148 = isl_ast_build_node_from_schedule (context
, isl_schedule_copy (schedule
));
149 isl_ast_build_free (context
);
150 print_isl_ast (f
, ast
);
151 isl_ast_node_free (ast
);
155 debug_schedule_ast (__isl_keep isl_schedule
*s
, scop_p scop
)
157 print_schedule_ast (stderr
, s
, scop
);
170 class translate_isl_ast_to_gimple
173 translate_isl_ast_to_gimple (sese_info_p r
)
174 : region (r
), codegen_error (false)
177 /* Translates an isl AST node NODE to GCC representation in the
178 context of a SESE. */
179 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
180 edge next_e
, ivs_params
&ip
);
182 /* Translates an isl_ast_node_for to Gimple. */
183 edge
translate_isl_ast_node_for (loop_p context_loop
,
184 __isl_keep isl_ast_node
*node
,
185 edge next_e
, ivs_params
&ip
);
187 /* Create the loop for a isl_ast_node_for.
189 - NEXT_E is the edge where new generated code should be attached. */
190 edge
translate_isl_ast_for_loop (loop_p context_loop
,
191 __isl_keep isl_ast_node
*node_for
,
193 tree type
, tree lb
, tree ub
,
196 /* Translates an isl_ast_node_if to Gimple. */
197 edge
translate_isl_ast_node_if (loop_p context_loop
,
198 __isl_keep isl_ast_node
*node
,
199 edge next_e
, ivs_params
&ip
);
201 /* Translates an isl_ast_node_user to Gimple.
203 FIXME: We should remove iv_map.create (loop->num + 1), if it is
205 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
206 edge next_e
, ivs_params
&ip
);
208 /* Translates an isl_ast_node_block to Gimple. */
209 edge
translate_isl_ast_node_block (loop_p context_loop
,
210 __isl_keep isl_ast_node
*node
,
211 edge next_e
, ivs_params
&ip
);
213 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
215 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
218 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
220 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
223 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
225 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
228 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
229 to a GCC expression tree of type TYPE. */
230 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
233 /* Converts an isl AST expression E back to a GCC expression tree of
235 tree
gcc_expression_from_isl_expression (tree type
,
236 __isl_take isl_ast_expr
*,
239 /* Return the tree variable that corresponds to the given isl ast identifier
240 expression (an isl_ast_expr of type isl_ast_expr_id).
242 FIXME: We should replace blind conversation of id's type with derivation
243 of the optimal type when we get the corresponding isl support. Blindly
244 converting type sizes may be problematic when we switch to smaller
246 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
247 __isl_keep isl_ast_expr
*expr_id
,
250 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
252 tree
gcc_expression_from_isl_expr_int (tree type
,
253 __isl_take isl_ast_expr
*expr
);
255 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
257 tree
gcc_expression_from_isl_expr_op (tree type
,
258 __isl_take isl_ast_expr
*expr
,
261 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
262 induction variable for the new LOOP. New LOOP is attached to CFG
263 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
264 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
265 isl's scattering name to the induction variable created for the
266 loop of STMT. The new induction variable is inserted in the NEWIVS
267 vector and is of type TYPE. */
268 struct loop
*graphite_create_new_loop (edge entry_edge
,
269 __isl_keep isl_ast_node
*node_for
,
270 loop_p outer
, tree type
,
271 tree lb
, tree ub
, ivs_params
&ip
);
273 /* All loops generated by create_empty_loop_on_edge have the form of
280 } while (lower bound < upper bound);
282 We create a new if region protecting the loop to be executed, if
283 the execution count is zero (lower bound > upper bound). */
284 edge
graphite_create_new_loop_guard (edge entry_edge
,
285 __isl_keep isl_ast_node
*node_for
,
287 tree
*lb
, tree
*ub
, ivs_params
&ip
);
289 /* Creates a new if region corresponding to isl's cond. */
290 edge
graphite_create_new_guard (edge entry_edge
,
291 __isl_take isl_ast_expr
*if_cond
,
294 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
295 variables of the loops around GBB in SESE.
297 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
298 chrec, we could consider using a map<int, tree> that maps loop ids to the
299 corresponding tree expressions. */
300 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
301 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
304 /* Patch the missing arguments of the phi nodes. */
306 void translate_pending_phi_nodes (void);
308 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
310 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
312 /* Generates a build, which specifies the constraints on the parameters. */
314 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
316 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
317 /* Generate isl AST from schedule of SCOP. */
318 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
);
320 /* Get the maximal number of schedule dimensions in the scop SCOP. */
321 int get_max_schedule_dimensions (scop_p scop
);
323 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
325 For schedules with different dimensionality, the isl AST generator can not
326 define an order and will just randomly choose an order. The solution to
327 this problem is to extend all schedules to the maximal number of schedule
328 dimensions (using '0's for the remaining values). */
329 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
330 int nb_schedule_dims
);
332 /* Generates a schedule, which specifies an order used to
333 visit elements in a domain. */
334 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
336 /* Set the separate option for all dimensions.
337 This helps to reduce control overhead. */
338 __isl_give isl_ast_build
*set_options (__isl_take isl_ast_build
*control
,
339 __isl_keep isl_union_map
*schedule
);
341 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
343 __isl_give isl_ast_node
*scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
345 /* Prints NODE to FILE. */
346 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
347 __isl_keep isl_ctx
*ctx
) const
349 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
350 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
351 prn
= isl_printer_print_ast_node (prn
, node
);
352 prn
= isl_printer_print_str (prn
, "\n");
353 isl_printer_free (prn
);
357 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
358 definition should flow into use, and the use should respect the loop-closed
361 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
362 phi_node_kind
, tree old_name
, basic_block old_bb
) const;
364 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
365 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
366 within a loop PHI instruction. */
368 tree
get_rename (basic_block new_bb
, tree old_name
,
369 basic_block old_bb
, phi_node_kind
) const;
371 /* For ops which are scev_analyzeable, we can regenerate a new name from
372 its scalar evolution around LOOP. */
374 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
375 basic_block new_bb
, basic_block old_bb
,
378 /* Returns a basic block that could correspond to where a constant was defined
379 in the original code. In the original code OLD_BB had the definition, we
380 need to find which basic block out of the copies of old_bb, in the new
381 region, should a definition correspond to if it has to reach BB. */
383 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
385 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
386 true when we want to rename an OP within a loop PHI instruction. */
388 tree
get_new_name (basic_block new_bb
, tree op
,
389 basic_block old_bb
, phi_node_kind
) const;
391 /* Collect all the operands of NEW_EXPR by recursively visiting each
394 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
396 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
397 NEW_PHI must be found unless they can be POSTPONEd for later. */
399 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
400 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
403 /* Copy loop phi nodes from BB to NEW_BB. */
405 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
407 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
408 the close phi node PHI. */
410 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
413 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
414 gimple
*old_close_phi
);
416 /* Copy all the loop-close phi args from BB to NEW_BB. */
418 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
421 /* Copy loop close phi nodes from BB to NEW_BB. */
423 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
425 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
426 region. If postpone is true and it isn't possible to copy any arg of PHI,
427 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
428 Returns false if the copying was unsuccessful. */
430 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
433 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
434 containing phi nodes coming from two predecessors, and none of them are back
437 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
440 /* Duplicates the statements of basic block BB into basic block NEW_BB
441 and compute the new induction variables according to the IV_MAP.
442 CODEGEN_ERROR is set when the code generation cannot continue. */
444 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
447 /* Copies BB and includes in the copied BB all the statements that can
448 be reached following the use-def chains from the memory accesses,
449 and returns the next edge following this new block. codegen_error is
450 set when the code generation cannot continue. */
452 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
455 /* Given a basic block containing close-phi it returns the new basic block
456 where to insert a copy of the close-phi nodes. All the uses in close phis
457 should come from a single loop otherwise it returns NULL. */
458 edge
edge_for_new_close_phis (basic_block bb
);
460 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
461 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
462 the other pred of OLD_BB as well. If no such basic block exists then it is
463 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
466 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
467 versa. In this case DOMINATING_PRED = NULL.
469 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
471 Returns true on successful copy of the args, false otherwise. */
473 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
474 edge old_bb_dominating_edge
,
475 edge old_bb_non_dominating_edge
,
476 gphi
*phi
, gphi
*new_phi
,
479 /* Renames the scalar uses of the statement COPY, using the substitution map
480 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
481 translation REGION, with the original copied statement in LOOP, and using
482 the induction variable renaming map IV_MAP. Returns true when something
483 has been renamed. codegen_error is set when the code generation cannot
486 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
487 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
489 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
490 When OLD_NAME and EXPR are the same we assert. */
492 void set_rename (tree old_name
, tree expr
);
494 /* Create new names for all the definitions created by COPY and add
495 replacement mappings for each new name. */
497 void set_rename_for_each_def (gimple
*stmt
);
499 /* Insert each statement from SEQ at its earliest insertion p. */
501 void gsi_insert_earliest (gimple_seq seq
);
503 /* Rename all the operands of NEW_EXPR by recursively visiting each
506 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
508 bool codegen_error_p () const
509 { return codegen_error
; }
511 /* Return true when OP is a constant tree. */
513 bool is_constant (tree op
) const
515 return TREE_CODE (op
) == INTEGER_CST
516 || TREE_CODE (op
) == REAL_CST
517 || TREE_CODE (op
) == COMPLEX_CST
518 || TREE_CODE (op
) == VECTOR_CST
;
522 /* The region to be translated. */
525 /* This flag is set when an error occurred during the translation of isl AST
529 /* A vector of all the edges at if_condition merge points. */
530 auto_vec
<edge
, 2> merge_points
;
533 /* Return the tree variable that corresponds to the given isl ast identifier
534 expression (an isl_ast_expr of type isl_ast_expr_id).
536 FIXME: We should replace blind conversion of id's type with derivation
537 of the optimal type when we get the corresponding isl support. Blindly
538 converting type sizes may be problematic when we switch to smaller
542 translate_isl_ast_to_gimple::
543 gcc_expression_from_isl_ast_expr_id (tree type
,
544 __isl_take isl_ast_expr
*expr_id
,
547 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
548 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
549 std::map
<isl_id
*, tree
>::iterator res
;
550 res
= ip
.find (tmp_isl_id
);
551 isl_id_free (tmp_isl_id
);
552 gcc_assert (res
!= ip
.end () &&
553 "Could not map isl_id to tree expression");
554 isl_ast_expr_free (expr_id
);
555 tree t
= res
->second
;
556 tree
*val
= region
->parameter_rename_map
->get(t
);
560 return fold_convert (type
, *val
);
563 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
567 translate_isl_ast_to_gimple::
568 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
570 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
571 isl_val
*val
= isl_ast_expr_get_val (expr
);
573 mpz_init (val_mpz_t
);
575 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
578 res
= gmp_cst_to_tree (type
, val_mpz_t
);
580 isl_ast_expr_free (expr
);
581 mpz_clear (val_mpz_t
);
585 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
589 translate_isl_ast_to_gimple::
590 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
592 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
593 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
594 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
595 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
597 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
598 isl_ast_expr_free (expr
);
606 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
609 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
612 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
615 /* As isl operates on arbitrary precision numbers, we may end up with
616 division by 2^64 that is folded to 0. */
617 if (integer_zerop (tree_rhs_expr
))
619 codegen_error
= true;
622 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
624 case isl_ast_op_pdiv_q
:
625 /* As isl operates on arbitrary precision numbers, we may end up with
626 division by 2^64 that is folded to 0. */
627 if (integer_zerop (tree_rhs_expr
))
629 codegen_error
= true;
632 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
634 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
635 /* isl 0.15 or later. */
636 case isl_ast_op_zdiv_r
:
638 case isl_ast_op_pdiv_r
:
639 /* As isl operates on arbitrary precision numbers, we may end up with
640 division by 2^64 that is folded to 0. */
641 if (integer_zerop (tree_rhs_expr
))
643 codegen_error
= true;
646 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
648 case isl_ast_op_fdiv_q
:
649 /* As isl operates on arbitrary precision numbers, we may end up with
650 division by 2^64 that is folded to 0. */
651 if (integer_zerop (tree_rhs_expr
))
653 codegen_error
= true;
656 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
659 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
660 tree_lhs_expr
, tree_rhs_expr
);
663 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
666 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
669 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
672 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
675 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
678 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
685 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
689 translate_isl_ast_to_gimple::
690 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
692 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
693 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
695 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
696 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
697 tree tree_second_expr
698 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
699 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
701 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
702 isl_ast_expr_free (expr
);
706 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
707 tree_second_expr
, tree_third_expr
);
710 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
714 translate_isl_ast_to_gimple::
715 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
717 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
718 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
719 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
720 isl_ast_expr_free (expr
);
721 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
724 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
725 to a GCC expression tree of type TYPE. */
728 translate_isl_ast_to_gimple::
729 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
731 enum tree_code op_code
;
732 switch (isl_ast_expr_get_op_type (expr
))
745 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
746 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
750 isl_ast_expr_free (expr
);
755 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
757 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
758 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
762 isl_ast_expr_free (expr
);
766 res
= fold_build2 (op_code
, type
, res
, t
);
768 isl_ast_expr_free (expr
);
772 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
776 translate_isl_ast_to_gimple::
777 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
782 isl_ast_expr_free (expr
);
786 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
787 switch (isl_ast_expr_get_op_type (expr
))
789 /* These isl ast expressions are not supported yet. */
790 case isl_ast_op_error
:
791 case isl_ast_op_call
:
792 case isl_ast_op_and_then
:
793 case isl_ast_op_or_else
:
794 case isl_ast_op_select
:
799 return nary_op_to_tree (type
, expr
, ip
);
805 case isl_ast_op_pdiv_q
:
806 case isl_ast_op_pdiv_r
:
807 case isl_ast_op_fdiv_q
:
808 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
809 /* isl 0.15 or later. */
810 case isl_ast_op_zdiv_r
:
819 return binary_op_to_tree (type
, expr
, ip
);
821 case isl_ast_op_minus
:
822 return unary_op_to_tree (type
, expr
, ip
);
824 case isl_ast_op_cond
:
825 return ternary_op_to_tree (type
, expr
, ip
);
834 /* Converts an isl AST expression E back to a GCC expression tree of
838 translate_isl_ast_to_gimple::
839 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
844 isl_ast_expr_free (expr
);
848 switch (isl_ast_expr_get_type (expr
))
850 case isl_ast_expr_id
:
851 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
853 case isl_ast_expr_int
:
854 return gcc_expression_from_isl_expr_int (type
, expr
);
856 case isl_ast_expr_op
:
857 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
866 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
867 induction variable for the new LOOP. New LOOP is attached to CFG
868 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
869 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
870 isl's scattering name to the induction variable created for the
871 loop of STMT. The new induction variable is inserted in the NEWIVS
872 vector and is of type TYPE. */
875 translate_isl_ast_to_gimple::
876 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
877 loop_p outer
, tree type
, tree lb
, tree ub
,
880 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
881 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
883 /* To fail code generation, we generate wrong code until we discard it. */
885 stride
= integer_zero_node
;
887 tree ivvar
= create_tmp_var (type
, "graphite_IV");
888 tree iv
, iv_after_increment
;
889 loop_p loop
= create_empty_loop_on_edge
890 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
891 outer
? outer
: entry_edge
->src
->loop_father
);
893 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
894 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
895 std::map
<isl_id
*, tree
>::iterator res
;
898 isl_id_free (res
->first
);
900 isl_ast_expr_free (for_iterator
);
904 /* Create the loop for a isl_ast_node_for.
906 - NEXT_E is the edge where new generated code should be attached. */
909 translate_isl_ast_to_gimple::
910 translate_isl_ast_for_loop (loop_p context_loop
,
911 __isl_keep isl_ast_node
*node_for
, edge next_e
,
912 tree type
, tree lb
, tree ub
,
915 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
916 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
918 edge last_e
= single_exit (loop
);
919 edge to_body
= single_succ_edge (loop
->header
);
920 basic_block after
= to_body
->dest
;
922 /* Translate the body of the loop. */
923 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
924 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
925 isl_ast_node_free (for_body
);
927 /* Early return if we failed to translate loop body. */
928 if (!next_e
|| codegen_error_p ())
931 if (next_e
->dest
!= after
)
932 redirect_edge_succ_nodup (next_e
, after
);
933 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
935 if (flag_loop_parallelize_all
)
937 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
939 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
940 loop
->can_be_parallel
= for_info
->is_parallelizable
;
948 /* We use this function to get the upper bound because of the form,
949 which is used by isl to represent loops:
951 for (iterator = init; cond; iterator += inc)
959 The loop condition is an arbitrary expression, which contains the
960 current loop iterator.
962 (e.g. iterator + 3 < B && C > iterator + A)
964 We have to know the upper bound of the iterator to generate a loop
965 in Gimple form. It can be obtained from the special representation
966 of the loop condition, which is generated by isl,
967 if the ast_build_atomic_upper_bound option is set. In this case,
968 isl generates a loop condition that consists of the current loop
969 iterator, + an operator (< or <=) and an expression not involving
970 the iterator, which is processed and returned by this function.
972 (e.g iterator <= upper-bound-expression-without-iterator) */
974 static __isl_give isl_ast_expr
*
975 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
977 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
978 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
979 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
981 switch (isl_ast_expr_get_op_type (for_cond
))
984 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
989 /* (iterator < ub) => (iterator <= ub - 1). */
991 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
992 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
993 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
1000 isl_ast_expr_free (for_cond
);
1004 /* All loops generated by create_empty_loop_on_edge have the form of
1011 } while (lower bound < upper bound);
1013 We create a new if region protecting the loop to be executed, if
1014 the execution count is zero (lower bound > upper bound). */
1017 translate_isl_ast_to_gimple::
1018 graphite_create_new_loop_guard (edge entry_edge
,
1019 __isl_keep isl_ast_node
*node_for
, tree
*type
,
1020 tree
*lb
, tree
*ub
, ivs_params
&ip
)
1022 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
1027 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1028 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
1029 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
1030 /* To fail code generation, we generate wrong code until we discard it. */
1032 *lb
= integer_zero_node
;
1033 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
1034 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
1035 /* To fail code generation, we generate wrong code until we discard it. */
1037 *ub
= integer_zero_node
;
1039 /* When ub is simply a constant or a parameter, use lb <= ub. */
1040 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
1041 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
1044 tree one
= (POINTER_TYPE_P (*type
)
1045 ? convert_to_ptrofftype (integer_one_node
)
1046 : fold_convert (*type
, integer_one_node
));
1047 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1048 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1049 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1050 is true, even if we do not want this. However lb < ub + 1 is false,
1052 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1053 : PLUS_EXPR
, *type
, *ub
, one
);
1055 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1058 if (integer_onep (cond_expr
))
1059 exit_edge
= entry_edge
;
1061 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1066 /* Translates an isl_ast_node_for to Gimple. */
1069 translate_isl_ast_to_gimple::
1070 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1071 edge next_e
, ivs_params
&ip
)
1073 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1075 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1078 if (last_e
== next_e
)
1080 /* There was no guard generated. */
1081 last_e
= single_succ_edge (split_edge (last_e
));
1083 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1088 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1089 merge_points
.safe_push (last_e
);
1091 last_e
= single_succ_edge (split_edge (last_e
));
1092 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1097 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1098 variables of the loops around GBB in SESE.
1100 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1101 chrec, we could consider using a map<int, tree> that maps loop ids to the
1102 corresponding tree expressions. */
1105 translate_isl_ast_to_gimple::
1106 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1107 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1110 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1111 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1113 isl_ast_expr
*arg_expr
;
1114 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1116 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1118 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1119 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1120 /* To fail code generation, we generate wrong code until we discard it. */
1122 t
= integer_zero_node
;
1124 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1125 iv_map
[old_loop
->num
] = t
;
1129 /* Translates an isl_ast_node_user to Gimple.
1131 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1134 translate_isl_ast_to_gimple::
1135 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1136 edge next_e
, ivs_params
&ip
)
1138 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1140 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1141 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1142 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1144 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1145 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1148 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1150 isl_ast_expr_free (name_expr
);
1151 isl_id_free (name_id
);
1153 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1154 "The entry block should not even appear within a scop");
1156 const int nb_loops
= number_of_loops (cfun
);
1158 iv_map
.create (nb_loops
);
1159 iv_map
.safe_grow_cleared (nb_loops
);
1161 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1162 isl_ast_expr_free (user_expr
);
1164 basic_block old_bb
= GBB_BB (gbb
);
1168 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1169 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1170 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1174 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1178 if (codegen_error_p ())
1183 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1184 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1190 /* Translates an isl_ast_node_block to Gimple. */
1193 translate_isl_ast_to_gimple::
1194 translate_isl_ast_node_block (loop_p context_loop
,
1195 __isl_keep isl_ast_node
*node
,
1196 edge next_e
, ivs_params
&ip
)
1198 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1199 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1201 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1203 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1204 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1205 isl_ast_node_free (tmp_node
);
1207 isl_ast_node_list_free (node_list
);
1211 /* Creates a new if region corresponding to isl's cond. */
1214 translate_isl_ast_to_gimple::
1215 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1219 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1220 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1221 /* To fail code generation, we generate wrong code until we discard it. */
1223 cond_expr
= integer_zero_node
;
1225 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1229 /* Translates an isl_ast_node_if to Gimple. */
1232 translate_isl_ast_to_gimple::
1233 translate_isl_ast_node_if (loop_p context_loop
,
1234 __isl_keep isl_ast_node
*node
,
1235 edge next_e
, ivs_params
&ip
)
1237 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1238 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1239 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1240 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1241 merge_points
.safe_push (last_e
);
1243 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1244 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1245 isl_ast_node_free (then_node
);
1247 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1248 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1249 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1250 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1252 isl_ast_node_free (else_node
);
1256 /* Translates an isl AST node NODE to GCC representation in the
1257 context of a SESE. */
1260 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1261 __isl_keep isl_ast_node
*node
,
1262 edge next_e
, ivs_params
&ip
)
1264 if (codegen_error_p ())
1267 switch (isl_ast_node_get_type (node
))
1269 case isl_ast_node_error
:
1272 case isl_ast_node_for
:
1273 return translate_isl_ast_node_for (context_loop
, node
,
1276 case isl_ast_node_if
:
1277 return translate_isl_ast_node_if (context_loop
, node
,
1280 case isl_ast_node_user
:
1281 return translate_isl_ast_node_user (node
, next_e
, ip
);
1283 case isl_ast_node_block
:
1284 return translate_isl_ast_node_block (context_loop
, node
,
1287 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1288 case isl_ast_node_mark
:
1290 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1291 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1292 isl_ast_node_free (n
);
1302 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1303 at the exit of loop which takes one argument that is the last value of the
1304 variable being used out of the loop. */
1307 bb_contains_loop_close_phi_nodes (basic_block bb
)
1309 return single_pred_p (bb
)
1310 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1313 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1314 header containing phi nodes which has one init-edge and one back-edge. */
1317 bb_contains_loop_phi_nodes (basic_block bb
)
1319 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1321 if (bb
->preds
->length () == 1)
1324 unsigned depth
= loop_depth (bb
->loop_father
);
1326 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1328 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1329 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1332 /* When one of the edges correspond to the same loop father and other
1334 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1335 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1338 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1339 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1345 /* Check if USE is defined in a basic block from where the definition of USE can
1346 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1349 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1351 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1354 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1355 if (bb_contains_loop_close_phi_nodes (bb
))
1358 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1359 basic_block def_bb
= gimple_bb (def
);
1361 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1364 /* Return the number of phi nodes in BB. */
1367 number_of_phi_nodes (basic_block bb
)
1370 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1376 /* Returns true if BB uses name in one of its PHIs. */
1379 phi_uses_name (basic_block bb
, tree name
)
1381 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1384 gphi
*phi
= psi
.phi ();
1385 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1387 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1388 if (use_arg
== name
)
1395 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1396 definition should flow into use, and the use should respect the loop-closed
1400 translate_isl_ast_to_gimple::
1401 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1402 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1404 /* The def of the rename must either dominate the uses or come from a
1405 back-edge. Also the def must respect the loop closed ssa form. */
1406 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1410 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1411 print_generic_expr (dump_file
, rename
, 0);
1412 fprintf (dump_file
, "\n");
1417 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1420 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1422 /* The loop-header dominates the loop-body. */
1423 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1426 /* RENAME would be used in loop-phi. */
1427 gcc_assert (number_of_phi_nodes (use_bb
));
1429 /* For definitions coming from back edges, we should check that
1430 old_name is used in a loop PHI node.
1431 FIXME: Verify if this is true. */
1432 if (phi_uses_name (old_bb
, old_name
))
1438 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1439 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1442 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1445 phi_node_kind phi_kind
) const
1447 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1448 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1450 if (!renames
|| renames
->is_empty ())
1453 if (1 == renames
->length ())
1455 tree rename
= (*renames
)[0];
1456 if (TREE_CODE (rename
) == SSA_NAME
)
1458 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1459 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1460 && (phi_kind
== close_phi
1461 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1466 if (is_constant (rename
))
1472 /* More than one renames corresponding to the old_name. Find the rename for
1473 which the definition flows into usage at new_bb. */
1475 tree t1
= NULL_TREE
, t2
;
1476 basic_block t1_bb
= NULL
;
1477 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1479 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1481 /* Defined in the same basic block as used. */
1482 if (t2_bb
== new_bb
)
1485 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1486 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1489 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1492 /* Compute the nearest dominator. */
1493 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1503 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1504 When OLD_NAME and EXPR are the same we assert. */
1507 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1511 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1512 print_generic_expr (dump_file
, old_name
, 0);
1513 fprintf (dump_file
, ", new_name = ");
1514 print_generic_expr (dump_file
, expr
, 0);
1515 fprintf (dump_file
, "\n");
1518 if (old_name
== expr
)
1521 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1524 renames
->safe_push (expr
);
1530 region
->rename_map
->put (old_name
, r
);
1535 /* For a parameter of a scop we don't want to rename it. */
1536 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1538 region
->parameter_rename_map
->put(old_name
, expr
);
1541 /* Return an iterator to the instructions comes last in the execution order.
1542 Either GSI1 and GSI2 should belong to the same basic block or one of their
1543 respective basic blocks should dominate the other. */
1545 gimple_stmt_iterator
1546 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1548 basic_block bb1
= gsi_bb (gsi1
);
1549 basic_block bb2
= gsi_bb (gsi2
);
1551 /* Find the iterator which is the latest. */
1554 /* For empty basic blocks gsis point to the end of the sequence. Since
1555 there is no operator== defined for gimple_stmt_iterator and for gsis
1556 not pointing to a valid statement gsi_next would assert. */
1557 gimple_stmt_iterator gsi
= gsi1
;
1559 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1562 } while (!gsi_end_p (gsi
));
1567 /* Find the basic block closest to the basic block which defines stmt. */
1568 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1571 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1575 /* Insert each statement from SEQ at its earliest insertion p. */
1578 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1580 update_modified_stmts (seq
);
1581 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1582 basic_block begin_bb
= get_entry_bb (codegen_region
);
1584 /* Inserting the gimple statements in a vector because gimple_seq behave
1585 in strage ways when inserting the stmts from it into different basic
1586 blocks one at a time. */
1587 auto_vec
<gimple
*, 3> stmts
;
1588 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1590 stmts
.safe_push (gsi_stmt (gsi
));
1594 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1596 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1597 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1599 use_operand_p use_p
;
1600 ssa_op_iter op_iter
;
1601 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1603 /* Iterator to the current def of use_p. For function parameters or
1604 anything where def is not found, insert at the beginning of the
1605 generated region. */
1606 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1608 tree op
= USE_FROM_PTR (use_p
);
1609 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1610 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1611 gsi_stmt
= gsi_for_stmt (stmt
);
1613 /* For region parameters, insert at the beginning of the generated
1615 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1616 gsi_stmt
= gsi_def_stmt
;
1618 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1621 if (!gsi_stmt (gsi_def_stmt
))
1623 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1624 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1626 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1628 gimple_stmt_iterator bsi
1629 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1630 /* Insert right after the PHI statements. */
1631 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1634 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1638 fprintf (dump_file
, "[codegen] inserting statement: ");
1639 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1640 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1645 /* Collect all the operands of NEW_EXPR by recursively visiting each
1649 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1653 /* Rename all uses in new_expr. */
1654 if (TREE_CODE (new_expr
) == SSA_NAME
)
1656 vec_ssa
->safe_push (new_expr
);
1660 /* Iterate over SSA_NAMES in NEW_EXPR. */
1661 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1663 tree op
= TREE_OPERAND (new_expr
, i
);
1664 collect_all_ssa_names (op
, vec_ssa
);
1668 /* This is abridged version of the function copied from:
1669 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1672 substitute_ssa_name (tree exp
, tree f
, tree r
)
1674 enum tree_code code
= TREE_CODE (exp
);
1675 tree op0
, op1
, op2
, op3
;
1678 /* We handle TREE_LIST and COMPONENT_REF separately. */
1679 if (code
== TREE_LIST
)
1681 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1682 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1683 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1686 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1688 else if (code
== COMPONENT_REF
)
1692 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1693 and it is the right field, replace it with R. */
1694 for (inner
= TREE_OPERAND (exp
, 0);
1695 REFERENCE_CLASS_P (inner
);
1696 inner
= TREE_OPERAND (inner
, 0))
1700 op1
= TREE_OPERAND (exp
, 1);
1702 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1705 /* If this expression hasn't been completed let, leave it alone. */
1706 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1709 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1710 if (op0
== TREE_OPERAND (exp
, 0))
1714 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1717 switch (TREE_CODE_CLASS (code
))
1722 case tcc_declaration
:
1728 case tcc_expression
:
1732 /* Fall through... */
1734 case tcc_exceptional
:
1737 case tcc_comparison
:
1739 switch (TREE_CODE_LENGTH (code
))
1747 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1748 if (op0
== TREE_OPERAND (exp
, 0))
1751 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1755 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1756 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1758 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1761 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1765 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1766 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1767 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1769 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1770 && op2
== TREE_OPERAND (exp
, 2))
1773 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1777 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1778 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1779 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1780 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1782 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1783 && op2
== TREE_OPERAND (exp
, 2)
1784 && op3
== TREE_OPERAND (exp
, 3))
1788 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1801 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1803 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1804 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1809 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1812 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1815 auto_vec
<tree
, 2> ssa_names
;
1816 collect_all_ssa_names (new_expr
, &ssa_names
);
1819 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1820 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1821 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1826 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1827 scalar evolution around LOOP. */
1830 translate_isl_ast_to_gimple::
1831 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1832 basic_block new_bb
, basic_block old_bb
,
1835 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1837 /* At this point we should know the exact scev for each
1838 scalar SSA_NAME used in the scop: all the other scalar
1839 SSA_NAMEs should have been translated out of SSA using
1840 arrays with one element. */
1842 if (chrec_contains_undetermined (scev
))
1844 codegen_error
= true;
1845 return build_zero_cst (TREE_TYPE (old_name
));
1848 new_expr
= chrec_apply_map (scev
, iv_map
);
1850 /* The apply should produce an expression tree containing
1851 the uses of the new induction variables. We should be
1852 able to use new_expr instead of the old_name in the newly
1853 generated loop nest. */
1854 if (chrec_contains_undetermined (new_expr
)
1855 || tree_contains_chrecs (new_expr
, NULL
))
1857 codegen_error
= true;
1858 return build_zero_cst (TREE_TYPE (old_name
));
1861 /* We should check all the operands and all of them should dominate the use at
1863 if (TREE_CODE (new_expr
) == SSA_NAME
)
1865 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1866 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1868 codegen_error
= true;
1869 return build_zero_cst (TREE_TYPE (old_name
));
1873 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1875 /* We check all the operands and all of them should dominate the use at
1877 auto_vec
<tree
, 2> new_ssa_names
;
1878 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1881 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1883 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1885 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1886 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1888 codegen_error
= true;
1889 return build_zero_cst (TREE_TYPE (old_name
));
1894 /* Replace the old_name with the new_expr. */
1895 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1899 /* Renames the scalar uses of the statement COPY, using the
1900 substitution map RENAME_MAP, inserting the gimplification code at
1901 GSI_TGT, for the translation REGION, with the original copied
1902 statement in LOOP, and using the induction variable renaming map
1903 IV_MAP. Returns true when something has been renamed. codegen_error
1904 is set when the code generation cannot continue. */
1907 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1908 gimple_stmt_iterator
*gsi_tgt
,
1910 loop_p loop
, vec
<tree
> iv_map
)
1912 bool changed
= false;
1914 if (is_gimple_debug (copy
))
1916 if (gimple_debug_bind_p (copy
))
1917 gimple_debug_bind_reset_value (copy
);
1918 else if (gimple_debug_source_bind_p (copy
))
1928 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1929 print_gimple_stmt (dump_file
, copy
, 0, 0);
1932 use_operand_p use_p
;
1933 ssa_op_iter op_iter
;
1934 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1936 tree old_name
= USE_FROM_PTR (use_p
);
1940 fprintf (dump_file
, "[codegen] renaming old_name = ");
1941 print_generic_expr (dump_file
, old_name
, 0);
1942 fprintf (dump_file
, "\n");
1945 if (TREE_CODE (old_name
) != SSA_NAME
1946 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1950 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1951 old_bb
, unknown_phi
);
1955 tree type_old_name
= TREE_TYPE (old_name
);
1956 tree type_new_expr
= TREE_TYPE (new_expr
);
1960 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1961 print_generic_expr (dump_file
, new_expr
, 0);
1962 fprintf (dump_file
, "\n");
1965 if (type_old_name
!= type_new_expr
1966 || TREE_CODE (new_expr
) != SSA_NAME
)
1968 tree var
= create_tmp_var (type_old_name
, "var");
1970 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1971 new_expr
= fold_convert (type_old_name
, new_expr
);
1974 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1975 gsi_insert_earliest (stmts
);
1978 replace_exp (use_p
, new_expr
);
1983 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1985 if (!new_expr
|| codegen_error_p ())
1990 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1991 print_generic_expr (dump_file
, new_expr
, 0);
1992 fprintf (dump_file
, "\n");
1995 gsi_insert_earliest (stmts
);
1996 replace_exp (use_p
, new_expr
);
1998 if (TREE_CODE (new_expr
) == INTEGER_CST
1999 && is_gimple_assign (copy
))
2001 tree rhs
= gimple_assign_rhs1 (copy
);
2003 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2004 recompute_tree_invariant_for_addr_expr (rhs
);
2007 set_rename (old_name
, new_expr
);
2013 /* Returns a basic block that could correspond to where a constant was defined
2014 in the original code. In the original code OLD_BB had the definition, we
2015 need to find which basic block out of the copies of old_bb, in the new
2016 region, should a definition correspond to if it has to reach BB. */
2019 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
2020 basic_block old_bb
) const
2022 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
2024 if (!bbs
|| bbs
->is_empty ())
2027 if (1 == bbs
->length ())
2031 basic_block b1
= NULL
, b2
;
2032 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
2037 /* BB and B2 are in two unrelated if-clauses. */
2038 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
2041 /* Compute the nearest dominator. */
2042 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
2050 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
2051 determines the kind of phi node. */
2054 translate_isl_ast_to_gimple::
2055 get_new_name (basic_block new_bb
, tree op
,
2056 basic_block old_bb
, phi_node_kind phi_kind
) const
2058 /* For constants the names are the same. */
2059 if (is_constant (op
))
2062 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
2065 /* Return a debug location for OP. */
2070 location_t loc
= UNKNOWN_LOCATION
;
2072 if (TREE_CODE (op
) == SSA_NAME
)
2073 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2077 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2078 the init edge (from outside the loop) and the second one is the back edge
2079 from the same loop. */
2081 std::pair
<edge
, edge
>
2082 get_edges (basic_block bb
)
2084 std::pair
<edge
, edge
> edges
;
2087 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2088 if (bb
->loop_father
!= e
->src
->loop_father
)
2095 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2096 must be found unless they can be POSTPONEd for later. */
2099 translate_isl_ast_to_gimple::
2100 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2101 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2104 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2106 basic_block new_bb
= gimple_bb (new_phi
);
2107 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2110 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2111 e
= ibp_new_bb
.first
;
2113 e
= ibp_new_bb
.second
;
2115 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2116 tree new_name
= get_new_name (new_bb
, old_name
,
2117 gimple_bb (old_phi
), loop_phi
);
2120 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2124 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2125 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2126 /* If the phi arg was a function arg, or wasn't defined, just use the
2128 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2131 /* Postpone code gen for later for those back-edges we don't have the
2133 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2135 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2138 /* Either we should add the arg to phi or, we should postpone. */
2144 /* Copy loop phi nodes from BB to NEW_BB. */
2147 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2151 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2154 /* Loop phi nodes should have only two arguments. */
2155 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2157 /* First edge is the init edge and second is the back edge. */
2158 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2160 /* First edge is the init edge and second is the back edge. */
2161 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2163 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2166 gphi
*phi
= psi
.phi ();
2167 tree res
= gimple_phi_result (phi
);
2168 if (virtual_operand_p (res
))
2170 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2173 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2174 tree new_res
= create_new_def_for (res
, new_phi
,
2175 gimple_phi_result_ptr (new_phi
));
2176 set_rename (res
, new_res
);
2177 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2179 update_stmt (new_phi
);
2183 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2184 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2191 /* Return the init value of PHI, the value coming from outside the loop. */
2194 get_loop_init_value (gphi
*phi
)
2197 loop_p loop
= gimple_bb (phi
)->loop_father
;
2201 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2202 if (e
->src
->loop_father
!= loop
)
2203 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2208 /* Find the init value (the value which comes from outside the loop), of one of
2209 the operands of DEF which is defined by a loop phi. */
2212 find_init_value (gimple
*def
)
2214 if (gimple_code (def
) == GIMPLE_PHI
)
2215 return get_loop_init_value (as_a
<gphi
*> (def
));
2217 if (gimple_vuse (def
))
2221 use_operand_p use_p
;
2222 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2224 tree use
= USE_FROM_PTR (use_p
);
2225 if (TREE_CODE (use
) == SSA_NAME
)
2227 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2235 /* Return the init value, the value coming from outside the loop. */
2238 find_init_value_close_phi (gphi
*phi
)
2240 gcc_assert (gimple_phi_num_args (phi
) == 1);
2241 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2242 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2243 return find_init_value (def
);
2247 tree
translate_isl_ast_to_gimple::
2248 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2249 gimple
*old_close_phi
)
2251 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2252 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2253 basic_block bb
= gimple_bb (stmt
);
2254 if (!bb_in_sese_p (bb
, codegen_region
))
2255 return last_merge_name
;
2257 loop_p loop
= bb
->loop_father
;
2258 if (!loop_in_sese_p (loop
, codegen_region
))
2259 return last_merge_name
;
2261 edge e
= single_exit (loop
);
2263 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2264 return last_merge_name
;
2266 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2267 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2270 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2271 bb
= split_edge (e
);
2273 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2274 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2275 gimple_phi_result_ptr (close_phi
));
2276 set_rename (old_close_phi_name
, res
);
2277 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2278 last_merge_name
= res
;
2280 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2283 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2284 the close phi node PHI. */
2286 bool translate_isl_ast_to_gimple::
2287 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2290 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2291 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2292 if (SSA_NAME
== TREE_CODE (default_value
))
2294 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2295 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2297 default_value_bb
= gimple_bb (stmt
);
2300 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2302 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2303 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2304 tree last_merge_name
= new_close_phi_name
;
2305 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2309 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2311 basic_block new_merge_bb
= merge_e
->src
;
2312 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2315 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2318 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2319 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2320 gimple_phi_result_ptr (merge_phi
));
2321 set_rename (old_close_phi_name
, merge_res
);
2323 edge from_loop
= NULL
, from_default_value
= NULL
;
2326 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2327 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2330 from_default_value
= e
;
2332 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2333 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2334 is contained in another condition. */
2335 if (!from_default_value
|| !from_loop
)
2338 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2339 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2343 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2344 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2347 update_stmt (merge_phi
);
2348 last_merge_name
= merge_res
;
2354 /* Copy all the loop-close phi args from BB to NEW_BB. */
2357 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2361 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2364 gphi
*old_close_phi
= psi
.phi ();
2365 tree res
= gimple_phi_result (old_close_phi
);
2366 if (virtual_operand_p (res
))
2369 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2370 /* Loop close phi nodes should not be scev_analyzable_p. */
2373 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2374 tree new_res
= create_new_def_for (res
, new_close_phi
,
2375 gimple_phi_result_ptr (new_close_phi
));
2376 set_rename (res
, new_res
);
2378 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2379 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2381 /* Predecessor basic blocks of a loop close phi should have been code
2382 generated before. FIXME: This is fixable by merging PHIs from inner
2383 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2387 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2388 get_loc (old_name
));
2391 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2392 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2395 update_stmt (new_close_phi
);
2397 /* When there is no loop guard around this codegenerated loop, there is no
2398 need to collect the close-phi arg. */
2399 if (merge_points
.is_empty ())
2402 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2403 tree default_value
= find_init_value_close_phi (new_close_phi
);
2405 /* A close phi must come from a loop-phi having a default value. */
2411 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2415 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2416 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2421 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2429 /* Copy loop close phi nodes from BB to NEW_BB. */
2432 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2436 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2438 /* Loop close phi nodes should have only one argument. */
2439 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2441 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2445 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2446 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2447 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2448 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2451 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2452 In this case DOMINATING_PRED = NULL.
2454 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2456 Returns true on successful copy of the args, false otherwise. */
2459 translate_isl_ast_to_gimple::
2460 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2461 edge old_bb_dominating_edge
,
2462 edge old_bb_non_dominating_edge
,
2463 gphi
*phi
, gphi
*new_phi
,
2466 basic_block def_pred
[2] = { NULL
, NULL
};
2467 int not_found_bb_index
= -1;
2468 for (int i
= 0; i
< 2; i
++)
2470 /* If the corresponding def_bb could not be found the entry will be
2472 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2473 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2474 gimple_phi_arg_edge (phi
, i
)->src
);
2475 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2476 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2480 /* When non are available bail out. */
2481 if (not_found_bb_index
!= -1)
2483 not_found_bb_index
= i
;
2487 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2488 if (old_bb_dominating_edge
)
2490 if (not_found_bb_index
!= -1)
2493 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2494 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2495 vec
<basic_block
> *bbs
2496 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2498 /* Could not find a mapping. */
2502 basic_block new_pred
= NULL
;
2505 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2507 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2509 /* FIXME: If we have already found new_pred then we have to
2510 disambiguate, bail out for now. */
2513 new_pred
= new_pred1
;
2515 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2517 /* FIXME: If we have already found new_pred then we have to either
2518 it dominates both or we have to disambiguate, bail out. */
2521 new_pred
= new_pred2
;
2528 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2529 gcc_assert (new_non_dominating_edge
);
2530 /* FIXME: Validate each args just like in loop-phis. */
2531 /* By the process of elimination we first insert insert phi-edge for
2532 non-dominating pred which is computed above and then we insert the
2534 int inserted_edge
= 0;
2535 for (; inserted_edge
< 2; inserted_edge
++)
2537 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2538 if (new_non_dominating_edge
== new_bb_pred_edge
)
2540 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2541 new_non_dominating_edge
,
2542 get_loc (old_phi_args
[inserted_edge
]));
2546 if (inserted_edge
== 2)
2549 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2551 edge new_dominating_edge
= NULL
;
2552 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2554 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2555 if (e
!= new_non_dominating_edge
)
2557 new_dominating_edge
= e
;
2558 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2559 new_dominating_edge
,
2560 get_loc (old_phi_args
[inserted_edge
]));
2564 gcc_assert (new_dominating_edge
);
2568 /* Classic diamond structure: both edges are non-dominating. We need to
2569 find one unique edge then the other can be found be elimination. If
2570 any definition (def_pred) dominates both the preds of new_bb then we
2571 bail out. Entries of def_pred maybe NULL, in that case we must
2572 uniquely find pred with help of only one entry. */
2573 edge new_e
[2] = { NULL
, NULL
};
2574 for (int i
= 0; i
< 2; i
++)
2578 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2580 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2583 /* We do not know how to handle the case when def_pred
2584 dominates more than a predecessor. */
2590 gcc_assert (new_e
[0] || new_e
[1]);
2592 /* Find the other edge by process of elimination. */
2593 if (not_found_bb_index
!= -1)
2595 gcc_assert (!new_e
[not_found_bb_index
]);
2596 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2599 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2601 if (new_e
[found_bb_index
] == e
)
2603 new_e
[not_found_bb_index
] = e
;
2607 /* Add edges to phi args. */
2608 for (int i
= 0; i
< 2; i
++)
2609 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2610 get_loc (old_phi_args
[i
]));
2616 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2617 region. If postpone is true and it isn't possible to copy any arg of PHI,
2618 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2619 Returns false if the copying was unsuccessful. */
2622 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2627 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2628 gcc_assert (2 == gimple_phi_num_args (phi
));
2630 basic_block new_bb
= gimple_bb (new_phi
);
2631 loop_p loop
= gimple_bb (phi
)->loop_father
;
2633 basic_block old_bb
= gimple_bb (phi
);
2634 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2638 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2639 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2640 old_bb_non_dominating_edge
= e
;
2642 old_bb_dominating_edge
= e
;
2644 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2645 old_bb_non_dominating_edge
->src
));
2647 tree new_phi_args
[2];
2648 tree old_phi_args
[2];
2650 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2652 tree old_name
= gimple_phi_arg_def (phi
, i
);
2653 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2654 old_phi_args
[i
] = old_name
;
2657 new_phi_args
[i
] = new_name
;
2661 /* If the phi-arg was a parameter. */
2662 if (vec_find (region
->params
, old_name
) != -1)
2664 new_phi_args
[i
] = old_name
;
2668 "[codegen] parameter argument to phi, new_expr: ");
2669 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2670 fprintf (dump_file
, "\n");
2675 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2676 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2677 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2683 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2684 if (is_gimple_reg (old_name
)
2685 && scev_analyzable_p (old_name
, region
->region
))
2688 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2689 new_bb
, old_bb
, iv_map
);
2690 if (codegen_error_p ())
2693 gcc_assert (new_expr
);
2697 "[codegen] scev analyzeable, new_expr: ");
2698 print_generic_expr (dump_file
, new_expr
, 0);
2699 fprintf (dump_file
, "\n");
2701 gsi_insert_earliest (stmts
);
2702 new_phi_args
[i
] = new_name
;
2706 /* Postpone code gen for later for back-edges. */
2707 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2711 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2712 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2715 new_phi_args
[i
] = NULL_TREE
;
2719 /* Either we should add the arg to phi or, we should postpone. */
2723 /* If none of the args have been determined in the first stage then wait until
2725 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2728 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2729 old_bb_dominating_edge
,
2730 old_bb_non_dominating_edge
,
2731 phi
, new_phi
, new_bb
);
2734 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2735 containing phi nodes coming from two predecessors, and none of them are back
2739 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2744 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2747 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2750 /* Cond phi nodes should have exactly two arguments. */
2751 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2753 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2756 gphi
*phi
= psi
.phi ();
2757 tree res
= gimple_phi_result (phi
);
2758 if (virtual_operand_p (res
))
2760 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2761 /* Cond phi nodes should not be scev_analyzable_p. */
2764 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2765 tree new_res
= create_new_def_for (res
, new_phi
,
2766 gimple_phi_result_ptr (new_phi
));
2767 set_rename (res
, new_res
);
2769 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2772 update_stmt (new_phi
);
2778 /* Return true if STMT should be copied from region to the new code-generated
2779 region. LABELs, CONDITIONS, induction-variables and region parameters need
2783 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2785 /* Do not copy labels or conditions. */
2786 if (gimple_code (stmt
) == GIMPLE_LABEL
2787 || gimple_code (stmt
) == GIMPLE_COND
)
2791 /* Do not copy induction variables. */
2792 if (is_gimple_assign (stmt
)
2793 && (lhs
= gimple_assign_lhs (stmt
))
2794 && TREE_CODE (lhs
) == SSA_NAME
2795 && is_gimple_reg (lhs
)
2796 && scev_analyzable_p (lhs
, region
->region
))
2799 /* Do not copy parameters that have been generated in the header of the
2801 if (is_gimple_assign (stmt
)
2802 && (lhs
= gimple_assign_lhs (stmt
))
2803 && TREE_CODE (lhs
) == SSA_NAME
2804 && region
->parameter_rename_map
->get(lhs
))
2810 /* Create new names for all the definitions created by COPY and add replacement
2811 mappings for each new name. */
2814 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2816 def_operand_p def_p
;
2817 ssa_op_iter op_iter
;
2818 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2820 tree old_name
= DEF_FROM_PTR (def_p
);
2821 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2822 set_rename (old_name
, new_name
);
2826 /* Duplicates the statements of basic block BB into basic block NEW_BB
2827 and compute the new induction variables according to the IV_MAP.
2828 CODEGEN_ERROR is set when the code generation cannot continue. */
2831 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2835 /* Iterator poining to the place where new statement (s) will be inserted. */
2836 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2838 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2841 gimple
*stmt
= gsi_stmt (gsi
);
2842 if (!should_copy_to_new_region (stmt
, region
))
2845 /* Create a new copy of STMT and duplicate STMT's virtual
2847 gimple
*copy
= gimple_copy (stmt
);
2848 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2852 fprintf (dump_file
, "[codegen] inserting statement: ");
2853 print_gimple_stmt (dump_file
, copy
, 0, 0);
2856 maybe_duplicate_eh_stmt (copy
, stmt
);
2857 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2859 /* Crete new names for each def in the copied stmt. */
2860 set_rename_for_each_def (copy
);
2862 loop_p loop
= bb
->loop_father
;
2863 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2865 fold_stmt_inplace (&gsi_tgt
);
2866 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2869 if (codegen_error_p ())
2872 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2874 use_operand_p use_p
;
2875 if (!is_gimple_debug (copy
))
2876 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2878 tree old_name
= USE_FROM_PTR (use_p
);
2880 if (TREE_CODE (old_name
) != SSA_NAME
2881 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2884 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2888 replace_exp (use_p
, *new_expr
);
2898 /* Given a basic block containing close-phi it returns the new basic block where
2899 to insert a copy of the close-phi nodes. All the uses in close phis should
2900 come from a single loop otherwise it returns NULL. */
2903 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2905 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2906 of close phi in the original code and then find the mapping of basic block
2907 defining that variable. If there are multiple close-phis and they are
2908 defined in different loops (in the original or in the new code) because of
2909 loop splitting, then we bail out. */
2910 loop_p new_loop
= NULL
;
2911 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2914 gphi
*phi
= psi
.phi ();
2915 tree name
= gimple_phi_arg_def (phi
, 0);
2916 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2918 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2919 if (!bbs
|| bbs
->length () != 1)
2920 /* This is one of the places which shows preserving original structure
2921 is not always possible, as we may need to insert close PHI for a loop
2922 where the latch does not have any mapping, or the mapping is
2927 new_loop
= (*bbs
)[0]->loop_father
;
2928 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2935 return single_exit (new_loop
);
2938 /* Copies BB and includes in the copied BB all the statements that can
2939 be reached following the use-def chains from the memory accesses,
2940 and returns the next edge following this new block. codegen_error is
2941 set when the code generation cannot continue. */
2944 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2948 int num_phis
= number_of_phi_nodes (bb
);
2950 if (region
->copied_bb_map
->get (bb
))
2952 /* FIXME: we should be able to handle phi nodes with args coming from
2953 outside the region. */
2956 codegen_error
= true;
2961 basic_block new_bb
= NULL
;
2962 if (bb_contains_loop_close_phi_nodes (bb
))
2965 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2968 edge e
= edge_for_new_close_phis (bb
);
2971 codegen_error
= true;
2975 basic_block phi_bb
= e
->dest
;
2977 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2978 phi_bb
= split_edge (e
);
2980 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2981 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2983 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2985 codegen_error
= true;
2992 new_bb
= split_edge (next_e
);
2996 new_bb
= split_edge (next_e
);
2997 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2999 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
3001 /* At this point we are unable to codegenerate by still preserving the SSA
3002 structure because maybe the loop is completely unrolled and the PHIs
3003 and cross-bb scalar dependencies are untrackable w.r.t. the original
3004 code. See gfortran.dg/graphite/pr29832.f90. */
3005 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
3007 codegen_error
= true;
3011 /* In case isl did some loop peeling, like this:
3014 for (int c1 = 1; c1 <= 5; c1 += 1) {
3019 there should be no loop-phi nodes in S_8(0).
3021 FIXME: We need to reason about dynamic instances of S_8, i.e., the
3022 values of all scalar variables: for the moment we instantiate only
3023 SCEV analyzable expressions on the iteration domain, and we need to
3024 extend that to reductions that cannot be analyzed by SCEV. */
3025 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
3027 codegen_error
= true;
3032 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
3034 if (!copy_loop_phi_nodes (bb
, phi_bb
))
3036 codegen_error
= true;
3040 else if (num_phis
> 0)
3043 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
3046 basic_block phi_bb
= single_pred (new_bb
);
3047 loop_p loop_father
= new_bb
->loop_father
;
3049 /* Move back until we find the block with two predecessors. */
3050 while (single_pred_p (phi_bb
))
3051 phi_bb
= single_pred_edge (phi_bb
)->src
;
3053 /* If a corresponding merge-point was not found, then abort codegen. */
3054 if (phi_bb
->loop_father
!= loop_father
3055 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
3056 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
3058 codegen_error
= true;
3065 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
3066 bb
->index
, new_bb
->index
);
3068 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
3070 copied_bbs
->safe_push (new_bb
);
3073 vec
<basic_block
> bbs
;
3075 bbs
.safe_push (new_bb
);
3076 region
->copied_bb_map
->put (bb
, bbs
);
3079 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3081 codegen_error
= true;
3085 return single_succ_edge (new_bb
);
3088 /* Patch the missing arguments of the phi nodes. */
3091 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3095 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3097 gphi
*old_phi
= rename
->first
;
3098 gphi
*new_phi
= rename
->second
;
3099 basic_block old_bb
= gimple_bb (old_phi
);
3100 basic_block new_bb
= gimple_bb (new_phi
);
3102 /* First edge is the init edge and second is the back edge. */
3103 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3104 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3108 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3109 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3112 auto_vec
<tree
, 1> iv_map
;
3113 if (bb_contains_loop_phi_nodes (new_bb
))
3114 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3116 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3117 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3119 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3123 fprintf (dump_file
, "[codegen] to new-phi: ");
3124 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3131 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
3134 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3137 sese_info_p region
= scop
->scop_info
;
3138 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3139 gcc_assert (nb_parameters
== region
->params
.length ());
3141 for (i
= 0; i
< nb_parameters
; i
++)
3143 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3145 ip
[tmp_id
] = region
->params
[i
];
3150 /* Generates a build, which specifies the constraints on the parameters. */
3152 __isl_give isl_ast_build
*
3153 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3155 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3156 return isl_ast_build_from_context (context_isl
);
3159 /* This method is executed before the construction of a for node. */
3161 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3163 isl_union_map
*dependences
= (isl_union_map
*) user
;
3164 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3165 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3166 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3167 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3168 for_info
->is_parallelizable
=
3169 !carries_deps (schedule
, dependences
, dimension
);
3170 isl_union_map_free (schedule
);
3171 isl_space_free (schedule_space
);
3172 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3176 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3178 /* Generate isl AST from schedule of SCOP. */
3180 __isl_give isl_ast_node
*
3181 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
)
3183 gcc_assert (scop
->transformed_schedule
);
3185 /* Set the separate option to reduce control flow overhead. */
3186 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
3187 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
3188 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3190 if (flag_loop_parallelize_all
)
3192 scop_get_dependences (scop
);
3194 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3198 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
3199 (context_isl
, schedule
);
3200 isl_ast_build_free (context_isl
);
3205 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3208 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3212 int schedule_dims
= 0;
3214 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3216 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3217 if (pbb_schedule_dims
> schedule_dims
)
3218 schedule_dims
= pbb_schedule_dims
;
3221 return schedule_dims
;
3224 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3226 For schedules with different dimensionality, the isl AST generator can not
3227 define an order and will just randomly choose an order. The solution to this
3228 problem is to extend all schedules to the maximal number of schedule
3229 dimensions (using '0's for the remaining values). */
3231 __isl_give isl_map
*
3232 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3233 int nb_schedule_dims
)
3235 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3237 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3239 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3241 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3244 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3246 isl_val_free (zero
);
3250 /* Generates a schedule, which specifies an order used to
3251 visit elements in a domain. */
3253 __isl_give isl_union_map
*
3254 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3256 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3259 isl_union_map
*schedule_isl
=
3260 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3262 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3264 /* Dead code elimination: when the domain of a PBB is empty,
3265 don't generate code for the PBB. */
3266 if (isl_set_is_empty (pbb
->domain
))
3269 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3270 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3271 isl_set_copy (pbb
->domain
));
3272 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3273 bb_schedule
= isl_map_coalesce (bb_schedule
);
3275 = isl_union_map_union (schedule_isl
,
3276 isl_union_map_from_map (bb_schedule
));
3277 schedule_isl
= isl_union_map_coalesce (schedule_isl
);
3279 return schedule_isl
;
3282 /* Set the separate option for all dimensions.
3283 This helps to reduce control overhead. */
3285 __isl_give isl_ast_build
*
3286 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3287 __isl_keep isl_union_map
*schedule
)
3289 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3290 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3292 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3293 isl_union_set
*range
=
3294 isl_union_set_from_set (isl_set_universe (range_space
));
3295 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3296 domain
= isl_union_set_universe (domain
);
3297 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3298 return isl_ast_build_set_options (control
, options
);
3301 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3303 __isl_give isl_ast_node
*
3304 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3306 /* Generate loop upper bounds that consist of the current loop iterator, an
3307 operator (< or <=) and an expression not involving the iterator. If this
3308 option is not set, then the current loop iterator may appear several times
3309 in the upper bound. See the isl manual for more details. */
3310 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3312 add_parameters_to_ivs_params (scop
, ip
);
3313 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3314 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3315 context_isl
= set_options (context_isl
, schedule_isl
);
3316 if (flag_loop_parallelize_all
)
3318 isl_union_map
*dependence
= scop_get_dependences (scop
);
3320 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3324 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3328 isl_schedule_free (scop
->schedule
);
3329 scop
->schedule
= NULL
;
3332 isl_ast_build_free (context_isl
);
3337 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
3338 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
3341 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
3342 gimple_stmt_iterator
*gsi
)
3344 if (!defined_in_sese_p (tr
, region
->region
))
3348 use_operand_p use_p
;
3349 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
3351 tree use_tr
= USE_FROM_PTR (use_p
);
3353 /* Do not copy parameters that have been generated in the header of the
3355 if (region
->parameter_rename_map
->get(use_tr
))
3358 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
3362 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
3365 gimple
*copy
= gimple_copy (def_stmt
);
3366 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
3368 /* Create new names for all the definitions created by COPY and
3369 add replacement mappings for each new name. */
3370 def_operand_p def_p
;
3371 ssa_op_iter op_iter
;
3372 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
3374 tree old_name
= DEF_FROM_PTR (def_p
);
3375 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
3376 region
->parameter_rename_map
->put(old_name
, new_name
);
3383 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
3385 /* For all the parameters which definitino is in the if_region->false_region,
3386 insert code on true_region (if_region->true_region->entry). */
3390 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
3392 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
3394 // If def is not in region.
3395 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
3397 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
3401 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3402 the given SCOP. Return true if code generation succeeded.
3404 FIXME: This is not yet a full implementation of the code generator
3405 with isl ASTs. Generation of GIMPLE code has to be completed. */
3408 graphite_regenerate_ast_isl (scop_p scop
)
3410 sese_info_p region
= scop
->scop_info
;
3411 translate_isl_ast_to_gimple
t (region
);
3413 ifsese if_region
= NULL
;
3414 isl_ast_node
*root_node
;
3417 timevar_push (TV_GRAPHITE_CODE_GEN
);
3418 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3419 t
.add_parameters_to_ivs_params (scop
, ip
);
3420 root_node
= t
.scop_to_isl_ast (scop
);
3422 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3427 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3428 fprintf (dump_file
, "[scheduler] original schedule:\n");
3429 print_isl_schedule (dump_file
, scop
->original_schedule
);
3430 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
3431 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
3433 fprintf (dump_file
, "[scheduler] original ast:\n");
3434 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
3436 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
3437 print_isl_ast (dump_file
, root_node
);
3440 recompute_all_dominators ();
3443 if_region
= move_sese_in_condition (region
);
3444 region
->if_region
= if_region
;
3445 recompute_all_dominators ();
3447 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3449 /* Copy all the parameters which are defined in the region. */
3450 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3452 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3453 basic_block bb
= split_edge (e
);
3455 /* Update the true_region exit edge. */
3456 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3458 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3459 if (t
.codegen_error_p ())
3462 fprintf (dump_file
, "codegen error: "
3463 "reverting back to the original code.\n");
3464 set_ifsese_condition (if_region
, integer_zero_node
);
3468 t
.translate_pending_phi_nodes ();
3469 if (!t
.codegen_error_p ())
3471 sese_insert_phis_for_liveouts (region
,
3472 if_region
->region
->region
.exit
->src
,
3473 if_region
->false_region
->region
.exit
,
3474 if_region
->true_region
->region
.exit
);
3475 mark_virtual_operands_for_renaming (cfun
);
3476 update_ssa (TODO_update_ssa
);
3481 recompute_all_dominators ();
3485 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
3490 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3491 " pending phis, reverting back to the original code.\n");
3492 set_ifsese_condition (if_region
, integer_zero_node
);
3496 free (if_region
->true_region
);
3497 free (if_region
->region
);
3500 ivs_params_clear (ip
);
3501 isl_ast_node_free (root_node
);
3502 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3504 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3507 int num_no_dependency
= 0;
3509 FOR_EACH_LOOP (loop
, 0)
3510 if (loop
->can_be_parallel
)
3511 num_no_dependency
++;
3513 fprintf (dump_file
, "%d loops carried no dependency.\n",
3517 return !t
.codegen_error_p ();
3520 #endif /* HAVE_isl */