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 enum isl_ast_op_type t
= isl_ast_expr_get_op_type (expr
);
693 gcc_assert (t
== isl_ast_op_cond
|| t
== isl_ast_op_select
);
694 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
695 tree a
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
696 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
697 tree b
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
698 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
699 tree c
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
700 isl_ast_expr_free (expr
);
705 return fold_build3 (COND_EXPR
, type
, a
, b
, c
);
708 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
712 translate_isl_ast_to_gimple::
713 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
715 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
716 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
717 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
718 isl_ast_expr_free (expr
);
719 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
722 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
723 to a GCC expression tree of type TYPE. */
726 translate_isl_ast_to_gimple::
727 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
729 enum tree_code op_code
;
730 switch (isl_ast_expr_get_op_type (expr
))
743 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
744 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
748 isl_ast_expr_free (expr
);
753 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
755 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
756 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
760 isl_ast_expr_free (expr
);
764 res
= fold_build2 (op_code
, type
, res
, t
);
766 isl_ast_expr_free (expr
);
770 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
774 translate_isl_ast_to_gimple::
775 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
780 isl_ast_expr_free (expr
);
784 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
785 switch (isl_ast_expr_get_op_type (expr
))
787 /* These isl ast expressions are not supported yet. */
788 case isl_ast_op_error
:
789 case isl_ast_op_call
:
790 case isl_ast_op_and_then
:
791 case isl_ast_op_or_else
:
796 return nary_op_to_tree (type
, expr
, ip
);
802 case isl_ast_op_pdiv_q
:
803 case isl_ast_op_pdiv_r
:
804 case isl_ast_op_fdiv_q
:
805 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
806 /* isl 0.15 or later. */
807 case isl_ast_op_zdiv_r
:
816 return binary_op_to_tree (type
, expr
, ip
);
818 case isl_ast_op_minus
:
819 return unary_op_to_tree (type
, expr
, ip
);
821 case isl_ast_op_cond
:
822 case isl_ast_op_select
:
823 return ternary_op_to_tree (type
, expr
, ip
);
832 /* Converts an isl AST expression E back to a GCC expression tree of
836 translate_isl_ast_to_gimple::
837 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
842 isl_ast_expr_free (expr
);
846 switch (isl_ast_expr_get_type (expr
))
848 case isl_ast_expr_id
:
849 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
851 case isl_ast_expr_int
:
852 return gcc_expression_from_isl_expr_int (type
, expr
);
854 case isl_ast_expr_op
:
855 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
864 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
865 induction variable for the new LOOP. New LOOP is attached to CFG
866 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
867 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
868 isl's scattering name to the induction variable created for the
869 loop of STMT. The new induction variable is inserted in the NEWIVS
870 vector and is of type TYPE. */
873 translate_isl_ast_to_gimple::
874 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
875 loop_p outer
, tree type
, tree lb
, tree ub
,
878 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
879 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
881 /* To fail code generation, we generate wrong code until we discard it. */
883 stride
= integer_zero_node
;
885 tree ivvar
= create_tmp_var (type
, "graphite_IV");
886 tree iv
, iv_after_increment
;
887 loop_p loop
= create_empty_loop_on_edge
888 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
889 outer
? outer
: entry_edge
->src
->loop_father
);
891 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
892 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
893 std::map
<isl_id
*, tree
>::iterator res
;
896 isl_id_free (res
->first
);
898 isl_ast_expr_free (for_iterator
);
902 /* Create the loop for a isl_ast_node_for.
904 - NEXT_E is the edge where new generated code should be attached. */
907 translate_isl_ast_to_gimple::
908 translate_isl_ast_for_loop (loop_p context_loop
,
909 __isl_keep isl_ast_node
*node_for
, edge next_e
,
910 tree type
, tree lb
, tree ub
,
913 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
914 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
916 edge last_e
= single_exit (loop
);
917 edge to_body
= single_succ_edge (loop
->header
);
918 basic_block after
= to_body
->dest
;
920 /* Translate the body of the loop. */
921 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
922 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
923 isl_ast_node_free (for_body
);
925 /* Early return if we failed to translate loop body. */
926 if (!next_e
|| codegen_error_p ())
929 if (next_e
->dest
!= after
)
930 redirect_edge_succ_nodup (next_e
, after
);
931 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
933 if (flag_loop_parallelize_all
)
935 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
937 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
938 loop
->can_be_parallel
= for_info
->is_parallelizable
;
946 /* We use this function to get the upper bound because of the form,
947 which is used by isl to represent loops:
949 for (iterator = init; cond; iterator += inc)
957 The loop condition is an arbitrary expression, which contains the
958 current loop iterator.
960 (e.g. iterator + 3 < B && C > iterator + A)
962 We have to know the upper bound of the iterator to generate a loop
963 in Gimple form. It can be obtained from the special representation
964 of the loop condition, which is generated by isl,
965 if the ast_build_atomic_upper_bound option is set. In this case,
966 isl generates a loop condition that consists of the current loop
967 iterator, + an operator (< or <=) and an expression not involving
968 the iterator, which is processed and returned by this function.
970 (e.g iterator <= upper-bound-expression-without-iterator) */
972 static __isl_give isl_ast_expr
*
973 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
975 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
976 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
977 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
979 switch (isl_ast_expr_get_op_type (for_cond
))
982 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
987 /* (iterator < ub) => (iterator <= ub - 1). */
989 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
990 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
991 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
998 isl_ast_expr_free (for_cond
);
1002 /* All loops generated by create_empty_loop_on_edge have the form of
1009 } while (lower bound < upper bound);
1011 We create a new if region protecting the loop to be executed, if
1012 the execution count is zero (lower bound > upper bound). */
1015 translate_isl_ast_to_gimple::
1016 graphite_create_new_loop_guard (edge entry_edge
,
1017 __isl_keep isl_ast_node
*node_for
, tree
*type
,
1018 tree
*lb
, tree
*ub
, ivs_params
&ip
)
1020 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
1025 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1026 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
1027 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
1028 /* To fail code generation, we generate wrong code until we discard it. */
1030 *lb
= integer_zero_node
;
1031 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
1032 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
1033 /* To fail code generation, we generate wrong code until we discard it. */
1035 *ub
= integer_zero_node
;
1037 /* When ub is simply a constant or a parameter, use lb <= ub. */
1038 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
1039 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
1042 tree one
= (POINTER_TYPE_P (*type
)
1043 ? convert_to_ptrofftype (integer_one_node
)
1044 : fold_convert (*type
, integer_one_node
));
1045 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1046 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1047 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1048 is true, even if we do not want this. However lb < ub + 1 is false,
1050 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1051 : PLUS_EXPR
, *type
, *ub
, one
);
1053 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1056 if (integer_onep (cond_expr
))
1057 exit_edge
= entry_edge
;
1059 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1064 /* Translates an isl_ast_node_for to Gimple. */
1067 translate_isl_ast_to_gimple::
1068 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1069 edge next_e
, ivs_params
&ip
)
1071 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1073 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1076 if (last_e
== next_e
)
1078 /* There was no guard generated. */
1079 last_e
= single_succ_edge (split_edge (last_e
));
1081 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1086 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1087 merge_points
.safe_push (last_e
);
1089 last_e
= single_succ_edge (split_edge (last_e
));
1090 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1095 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1096 variables of the loops around GBB in SESE.
1098 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1099 chrec, we could consider using a map<int, tree> that maps loop ids to the
1100 corresponding tree expressions. */
1103 translate_isl_ast_to_gimple::
1104 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1105 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1108 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1109 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1111 isl_ast_expr
*arg_expr
;
1112 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1114 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1116 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1117 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1118 /* To fail code generation, we generate wrong code until we discard it. */
1120 t
= integer_zero_node
;
1122 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1123 iv_map
[old_loop
->num
] = t
;
1127 /* Translates an isl_ast_node_user to Gimple.
1129 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1132 translate_isl_ast_to_gimple::
1133 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1134 edge next_e
, ivs_params
&ip
)
1136 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1138 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1139 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1140 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1142 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1143 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1146 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1148 isl_ast_expr_free (name_expr
);
1149 isl_id_free (name_id
);
1151 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1152 "The entry block should not even appear within a scop");
1154 const int nb_loops
= number_of_loops (cfun
);
1156 iv_map
.create (nb_loops
);
1157 iv_map
.safe_grow_cleared (nb_loops
);
1159 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1160 isl_ast_expr_free (user_expr
);
1162 basic_block old_bb
= GBB_BB (gbb
);
1166 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1167 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1168 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1172 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1176 if (codegen_error_p ())
1181 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1182 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1188 /* Translates an isl_ast_node_block to Gimple. */
1191 translate_isl_ast_to_gimple::
1192 translate_isl_ast_node_block (loop_p context_loop
,
1193 __isl_keep isl_ast_node
*node
,
1194 edge next_e
, ivs_params
&ip
)
1196 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1197 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1199 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1201 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1202 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1203 isl_ast_node_free (tmp_node
);
1205 isl_ast_node_list_free (node_list
);
1209 /* Creates a new if region corresponding to isl's cond. */
1212 translate_isl_ast_to_gimple::
1213 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1217 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1218 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1219 /* To fail code generation, we generate wrong code until we discard it. */
1221 cond_expr
= integer_zero_node
;
1223 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1227 /* Translates an isl_ast_node_if to Gimple. */
1230 translate_isl_ast_to_gimple::
1231 translate_isl_ast_node_if (loop_p context_loop
,
1232 __isl_keep isl_ast_node
*node
,
1233 edge next_e
, ivs_params
&ip
)
1235 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1236 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1237 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1238 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1239 merge_points
.safe_push (last_e
);
1241 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1242 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1243 isl_ast_node_free (then_node
);
1245 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1246 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1247 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1248 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1250 isl_ast_node_free (else_node
);
1254 /* Translates an isl AST node NODE to GCC representation in the
1255 context of a SESE. */
1258 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1259 __isl_keep isl_ast_node
*node
,
1260 edge next_e
, ivs_params
&ip
)
1262 if (codegen_error_p ())
1265 switch (isl_ast_node_get_type (node
))
1267 case isl_ast_node_error
:
1270 case isl_ast_node_for
:
1271 return translate_isl_ast_node_for (context_loop
, node
,
1274 case isl_ast_node_if
:
1275 return translate_isl_ast_node_if (context_loop
, node
,
1278 case isl_ast_node_user
:
1279 return translate_isl_ast_node_user (node
, next_e
, ip
);
1281 case isl_ast_node_block
:
1282 return translate_isl_ast_node_block (context_loop
, node
,
1285 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1286 case isl_ast_node_mark
:
1288 isl_ast_node
*n
= isl_ast_node_mark_get_node (node
);
1289 edge e
= translate_isl_ast (context_loop
, n
, next_e
, ip
);
1290 isl_ast_node_free (n
);
1300 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1301 at the exit of loop which takes one argument that is the last value of the
1302 variable being used out of the loop. */
1305 bb_contains_loop_close_phi_nodes (basic_block bb
)
1307 return single_pred_p (bb
)
1308 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1311 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1312 header containing phi nodes which has one init-edge and one back-edge. */
1315 bb_contains_loop_phi_nodes (basic_block bb
)
1317 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1319 if (bb
->preds
->length () == 1)
1322 unsigned depth
= loop_depth (bb
->loop_father
);
1324 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1326 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1327 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1330 /* When one of the edges correspond to the same loop father and other
1332 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1333 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1336 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1337 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1343 /* Check if USE is defined in a basic block from where the definition of USE can
1344 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1347 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1349 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1352 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1353 if (bb_contains_loop_close_phi_nodes (bb
))
1356 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1357 basic_block def_bb
= gimple_bb (def
);
1359 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1362 /* Return the number of phi nodes in BB. */
1365 number_of_phi_nodes (basic_block bb
)
1368 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1374 /* Returns true if BB uses name in one of its PHIs. */
1377 phi_uses_name (basic_block bb
, tree name
)
1379 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1382 gphi
*phi
= psi
.phi ();
1383 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1385 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1386 if (use_arg
== name
)
1393 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1394 definition should flow into use, and the use should respect the loop-closed
1398 translate_isl_ast_to_gimple::
1399 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1400 phi_node_kind phi_kind
, tree old_name
, basic_block old_bb
) const
1402 /* The def of the rename must either dominate the uses or come from a
1403 back-edge. Also the def must respect the loop closed ssa form. */
1404 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1408 fprintf (dump_file
, "[codegen] rename not in loop closed ssa: ");
1409 print_generic_expr (dump_file
, rename
, 0);
1410 fprintf (dump_file
, "\n");
1415 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1418 if (bb_contains_loop_phi_nodes (use_bb
) && phi_kind
== loop_phi
)
1420 /* The loop-header dominates the loop-body. */
1421 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1424 /* RENAME would be used in loop-phi. */
1425 gcc_assert (number_of_phi_nodes (use_bb
));
1427 /* For definitions coming from back edges, we should check that
1428 old_name is used in a loop PHI node.
1429 FIXME: Verify if this is true. */
1430 if (phi_uses_name (old_bb
, old_name
))
1436 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1437 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1440 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1443 phi_node_kind phi_kind
) const
1445 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1446 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1448 if (!renames
|| renames
->is_empty ())
1451 if (1 == renames
->length ())
1453 tree rename
= (*renames
)[0];
1454 if (TREE_CODE (rename
) == SSA_NAME
)
1456 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1457 if (is_valid_rename (rename
, bb
, new_bb
, phi_kind
, old_name
, old_bb
)
1458 && (phi_kind
== close_phi
1459 || flow_bb_inside_loop_p (bb
->loop_father
, new_bb
)))
1464 if (is_constant (rename
))
1470 /* More than one renames corresponding to the old_name. Find the rename for
1471 which the definition flows into usage at new_bb. */
1473 tree t1
= NULL_TREE
, t2
;
1474 basic_block t1_bb
= NULL
;
1475 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1477 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1479 /* Defined in the same basic block as used. */
1480 if (t2_bb
== new_bb
)
1483 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1484 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1487 if (!flow_bb_inside_loop_p (t2_bb
->loop_father
, new_bb
))
1490 /* Compute the nearest dominator. */
1491 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1501 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1502 When OLD_NAME and EXPR are the same we assert. */
1505 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1509 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1510 print_generic_expr (dump_file
, old_name
, 0);
1511 fprintf (dump_file
, ", new_name = ");
1512 print_generic_expr (dump_file
, expr
, 0);
1513 fprintf (dump_file
, "\n");
1516 if (old_name
== expr
)
1519 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1522 renames
->safe_push (expr
);
1528 region
->rename_map
->put (old_name
, r
);
1533 /* For a parameter of a scop we don't want to rename it. */
1534 FOR_EACH_VEC_ELT (region
->params
, i
, t
)
1536 region
->parameter_rename_map
->put(old_name
, expr
);
1539 /* Return an iterator to the instructions comes last in the execution order.
1540 Either GSI1 and GSI2 should belong to the same basic block or one of their
1541 respective basic blocks should dominate the other. */
1543 gimple_stmt_iterator
1544 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1546 basic_block bb1
= gsi_bb (gsi1
);
1547 basic_block bb2
= gsi_bb (gsi2
);
1549 /* Find the iterator which is the latest. */
1552 /* For empty basic blocks gsis point to the end of the sequence. Since
1553 there is no operator== defined for gimple_stmt_iterator and for gsis
1554 not pointing to a valid statement gsi_next would assert. */
1555 gimple_stmt_iterator gsi
= gsi1
;
1557 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1560 } while (!gsi_end_p (gsi
));
1565 /* Find the basic block closest to the basic block which defines stmt. */
1566 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1569 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1573 /* Insert each statement from SEQ at its earliest insertion p. */
1576 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1578 update_modified_stmts (seq
);
1579 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1580 basic_block begin_bb
= get_entry_bb (codegen_region
);
1582 /* Inserting the gimple statements in a vector because gimple_seq behave
1583 in strage ways when inserting the stmts from it into different basic
1584 blocks one at a time. */
1585 auto_vec
<gimple
*, 3> stmts
;
1586 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1588 stmts
.safe_push (gsi_stmt (gsi
));
1592 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1594 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1595 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1597 use_operand_p use_p
;
1598 ssa_op_iter op_iter
;
1599 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1601 /* Iterator to the current def of use_p. For function parameters or
1602 anything where def is not found, insert at the beginning of the
1603 generated region. */
1604 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1606 tree op
= USE_FROM_PTR (use_p
);
1607 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1608 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1609 gsi_stmt
= gsi_for_stmt (stmt
);
1611 /* For region parameters, insert at the beginning of the generated
1613 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1614 gsi_stmt
= gsi_def_stmt
;
1616 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1619 if (!gsi_stmt (gsi_def_stmt
))
1621 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1622 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1624 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1626 gimple_stmt_iterator bsi
1627 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1628 /* Insert right after the PHI statements. */
1629 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1632 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1636 fprintf (dump_file
, "[codegen] inserting statement: ");
1637 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1638 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1643 /* Collect all the operands of NEW_EXPR by recursively visiting each
1647 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1651 /* Rename all uses in new_expr. */
1652 if (TREE_CODE (new_expr
) == SSA_NAME
)
1654 vec_ssa
->safe_push (new_expr
);
1658 /* Iterate over SSA_NAMES in NEW_EXPR. */
1659 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1661 tree op
= TREE_OPERAND (new_expr
, i
);
1662 collect_all_ssa_names (op
, vec_ssa
);
1666 /* This is abridged version of the function copied from:
1667 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1670 substitute_ssa_name (tree exp
, tree f
, tree r
)
1672 enum tree_code code
= TREE_CODE (exp
);
1673 tree op0
, op1
, op2
, op3
;
1676 /* We handle TREE_LIST and COMPONENT_REF separately. */
1677 if (code
== TREE_LIST
)
1679 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1680 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1681 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1684 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1686 else if (code
== COMPONENT_REF
)
1690 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1691 and it is the right field, replace it with R. */
1692 for (inner
= TREE_OPERAND (exp
, 0);
1693 REFERENCE_CLASS_P (inner
);
1694 inner
= TREE_OPERAND (inner
, 0))
1698 op1
= TREE_OPERAND (exp
, 1);
1700 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1703 /* If this expression hasn't been completed let, leave it alone. */
1704 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1707 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1708 if (op0
== TREE_OPERAND (exp
, 0))
1712 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1715 switch (TREE_CODE_CLASS (code
))
1720 case tcc_declaration
:
1726 case tcc_expression
:
1730 /* Fall through... */
1732 case tcc_exceptional
:
1735 case tcc_comparison
:
1737 switch (TREE_CODE_LENGTH (code
))
1745 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1746 if (op0
== TREE_OPERAND (exp
, 0))
1749 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1753 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1754 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1756 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1759 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1763 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1764 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1765 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1767 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1768 && op2
== TREE_OPERAND (exp
, 2))
1771 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1775 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1776 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1777 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1778 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1780 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1781 && op2
== TREE_OPERAND (exp
, 2)
1782 && op3
== TREE_OPERAND (exp
, 3))
1786 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1799 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1801 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1802 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1807 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1810 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1813 auto_vec
<tree
, 2> ssa_names
;
1814 collect_all_ssa_names (new_expr
, &ssa_names
);
1817 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1818 if (tree r
= get_rename (new_bb
, t
, old_bb
, unknown_phi
))
1819 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1824 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1825 scalar evolution around LOOP. */
1828 translate_isl_ast_to_gimple::
1829 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1830 basic_block new_bb
, basic_block old_bb
,
1833 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1835 /* At this point we should know the exact scev for each
1836 scalar SSA_NAME used in the scop. */
1837 gcc_assert (!chrec_contains_undetermined (scev
));
1839 tree new_expr
= chrec_apply_map (scev
, iv_map
);
1841 /* The apply should produce an expression tree containing
1842 the uses of the new induction variables. We should be
1843 able to use new_expr instead of the old_name in the newly
1844 generated loop nest. */
1845 gcc_assert (!chrec_contains_undetermined (new_expr
)
1846 && !tree_contains_chrecs (new_expr
, NULL
));
1848 if (TREE_CODE (new_expr
) == SSA_NAME
)
1850 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1851 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1853 codegen_error
= true;
1854 return build_zero_cst (TREE_TYPE (old_name
));
1858 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1860 /* We check all the operands and all of them should dominate the use at
1862 auto_vec
<tree
, 2> new_ssa_names
;
1863 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1866 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1868 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1870 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1871 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1873 codegen_error
= true;
1874 return build_zero_cst (TREE_TYPE (old_name
));
1879 /* Replace the old_name with the new_expr. */
1880 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1884 /* Renames the scalar uses of the statement COPY, using the
1885 substitution map RENAME_MAP, inserting the gimplification code at
1886 GSI_TGT, for the translation REGION, with the original copied
1887 statement in LOOP, and using the induction variable renaming map
1888 IV_MAP. Returns true when something has been renamed. */
1891 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1892 gimple_stmt_iterator
*gsi_tgt
,
1894 loop_p loop
, vec
<tree
> iv_map
)
1896 bool changed
= false;
1898 if (is_gimple_debug (copy
))
1900 if (gimple_debug_bind_p (copy
))
1901 gimple_debug_bind_reset_value (copy
);
1902 else if (gimple_debug_source_bind_p (copy
))
1912 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1913 print_gimple_stmt (dump_file
, copy
, 0, 0);
1916 use_operand_p use_p
;
1917 ssa_op_iter op_iter
;
1918 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1920 tree old_name
= USE_FROM_PTR (use_p
);
1924 fprintf (dump_file
, "[codegen] renaming old_name = ");
1925 print_generic_expr (dump_file
, old_name
, 0);
1926 fprintf (dump_file
, "\n");
1929 if (TREE_CODE (old_name
) != SSA_NAME
1930 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1934 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1935 old_bb
, unknown_phi
);
1939 tree type_old_name
= TREE_TYPE (old_name
);
1940 tree type_new_expr
= TREE_TYPE (new_expr
);
1944 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1945 print_generic_expr (dump_file
, new_expr
, 0);
1946 fprintf (dump_file
, "\n");
1949 if (type_old_name
!= type_new_expr
1950 || TREE_CODE (new_expr
) != SSA_NAME
)
1952 tree var
= create_tmp_var (type_old_name
, "var");
1954 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1955 new_expr
= fold_convert (type_old_name
, new_expr
);
1958 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1959 gsi_insert_earliest (stmts
);
1962 replace_exp (use_p
, new_expr
);
1967 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1969 if (!new_expr
|| codegen_error_p ())
1974 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1975 print_generic_expr (dump_file
, new_expr
, 0);
1976 fprintf (dump_file
, "\n");
1979 gsi_insert_earliest (stmts
);
1980 replace_exp (use_p
, new_expr
);
1982 if (TREE_CODE (new_expr
) == INTEGER_CST
1983 && is_gimple_assign (copy
))
1985 tree rhs
= gimple_assign_rhs1 (copy
);
1987 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1988 recompute_tree_invariant_for_addr_expr (rhs
);
1991 set_rename (old_name
, new_expr
);
1997 /* Returns a basic block that could correspond to where a constant was defined
1998 in the original code. In the original code OLD_BB had the definition, we
1999 need to find which basic block out of the copies of old_bb, in the new
2000 region, should a definition correspond to if it has to reach BB. */
2003 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
2004 basic_block old_bb
) const
2006 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
2008 if (!bbs
|| bbs
->is_empty ())
2011 if (1 == bbs
->length ())
2015 basic_block b1
= NULL
, b2
;
2016 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
2021 /* BB and B2 are in two unrelated if-clauses. */
2022 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
2025 /* Compute the nearest dominator. */
2026 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
2034 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
2035 determines the kind of phi node. */
2038 translate_isl_ast_to_gimple::
2039 get_new_name (basic_block new_bb
, tree op
,
2040 basic_block old_bb
, phi_node_kind phi_kind
) const
2042 /* For constants the names are the same. */
2043 if (is_constant (op
))
2046 return get_rename (new_bb
, op
, old_bb
, phi_kind
);
2049 /* Return a debug location for OP. */
2054 location_t loc
= UNKNOWN_LOCATION
;
2056 if (TREE_CODE (op
) == SSA_NAME
)
2057 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2061 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2062 the init edge (from outside the loop) and the second one is the back edge
2063 from the same loop. */
2065 std::pair
<edge
, edge
>
2066 get_edges (basic_block bb
)
2068 std::pair
<edge
, edge
> edges
;
2071 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2072 if (bb
->loop_father
!= e
->src
->loop_father
)
2079 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2080 must be found unless they can be POSTPONEd for later. */
2083 translate_isl_ast_to_gimple::
2084 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2085 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2088 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2090 basic_block new_bb
= gimple_bb (new_phi
);
2091 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2094 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2095 e
= ibp_new_bb
.first
;
2097 e
= ibp_new_bb
.second
;
2099 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2100 tree new_name
= get_new_name (new_bb
, old_name
,
2101 gimple_bb (old_phi
), loop_phi
);
2104 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2108 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2109 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2110 /* If the phi arg was a function arg, or wasn't defined, just use the
2112 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2115 /* Postpone code gen for later for those back-edges we don't have the
2117 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2119 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2122 /* Either we should add the arg to phi or, we should postpone. */
2128 /* Copy loop phi nodes from BB to NEW_BB. */
2131 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2135 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2138 /* Loop phi nodes should have only two arguments. */
2139 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2141 /* First edge is the init edge and second is the back edge. */
2142 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2144 /* First edge is the init edge and second is the back edge. */
2145 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2147 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2150 gphi
*phi
= psi
.phi ();
2151 tree res
= gimple_phi_result (phi
);
2152 if (virtual_operand_p (res
))
2154 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2157 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2158 tree new_res
= create_new_def_for (res
, new_phi
,
2159 gimple_phi_result_ptr (new_phi
));
2160 set_rename (res
, new_res
);
2161 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2163 update_stmt (new_phi
);
2167 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2168 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2175 /* Return the init value of PHI, the value coming from outside the loop. */
2178 get_loop_init_value (gphi
*phi
)
2181 loop_p loop
= gimple_bb (phi
)->loop_father
;
2185 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2186 if (e
->src
->loop_father
!= loop
)
2187 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2192 /* Find the init value (the value which comes from outside the loop), of one of
2193 the operands of DEF which is defined by a loop phi. */
2196 find_init_value (gimple
*def
)
2198 if (gimple_code (def
) == GIMPLE_PHI
)
2199 return get_loop_init_value (as_a
<gphi
*> (def
));
2201 if (gimple_vuse (def
))
2205 use_operand_p use_p
;
2206 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2208 tree use
= USE_FROM_PTR (use_p
);
2209 if (TREE_CODE (use
) == SSA_NAME
)
2211 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2219 /* Return the init value, the value coming from outside the loop. */
2222 find_init_value_close_phi (gphi
*phi
)
2224 gcc_assert (gimple_phi_num_args (phi
) == 1);
2225 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2226 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2227 return find_init_value (def
);
2231 tree
translate_isl_ast_to_gimple::
2232 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2233 gimple
*old_close_phi
)
2235 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2236 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2237 basic_block bb
= gimple_bb (stmt
);
2238 if (!bb_in_sese_p (bb
, codegen_region
))
2239 return last_merge_name
;
2241 loop_p loop
= bb
->loop_father
;
2242 if (!loop_in_sese_p (loop
, codegen_region
))
2243 return last_merge_name
;
2245 edge e
= single_exit (loop
);
2247 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2248 return last_merge_name
;
2250 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2251 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2254 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2255 bb
= split_edge (e
);
2257 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2258 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2259 gimple_phi_result_ptr (close_phi
));
2260 set_rename (old_close_phi_name
, res
);
2261 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2262 last_merge_name
= res
;
2264 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2267 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2268 the close phi node PHI. */
2270 bool translate_isl_ast_to_gimple::
2271 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2274 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2275 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2276 if (SSA_NAME
== TREE_CODE (default_value
))
2278 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2279 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2281 default_value_bb
= gimple_bb (stmt
);
2284 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2286 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2287 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2288 tree last_merge_name
= new_close_phi_name
;
2289 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2293 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2295 basic_block new_merge_bb
= merge_e
->src
;
2296 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2299 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2302 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2303 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2304 gimple_phi_result_ptr (merge_phi
));
2305 set_rename (old_close_phi_name
, merge_res
);
2307 edge from_loop
= NULL
, from_default_value
= NULL
;
2310 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2311 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2314 from_default_value
= e
;
2316 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2317 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2318 is contained in another condition. */
2319 if (!from_default_value
|| !from_loop
)
2322 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2323 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2327 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2328 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2331 update_stmt (merge_phi
);
2332 last_merge_name
= merge_res
;
2338 /* Copy all the loop-close phi args from BB to NEW_BB. */
2341 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2345 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2348 gphi
*old_close_phi
= psi
.phi ();
2349 tree res
= gimple_phi_result (old_close_phi
);
2350 if (virtual_operand_p (res
))
2353 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2354 /* Loop close phi nodes should not be scev_analyzable_p. */
2357 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2358 tree new_res
= create_new_def_for (res
, new_close_phi
,
2359 gimple_phi_result_ptr (new_close_phi
));
2360 set_rename (res
, new_res
);
2362 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2363 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, close_phi
);
2365 /* Predecessor basic blocks of a loop close phi should have been code
2366 generated before. FIXME: This is fixable by merging PHIs from inner
2367 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2371 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2372 get_loc (old_name
));
2375 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2376 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2379 update_stmt (new_close_phi
);
2381 /* When there is no loop guard around this codegenerated loop, there is no
2382 need to collect the close-phi arg. */
2383 if (merge_points
.is_empty ())
2386 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2387 tree default_value
= find_init_value_close_phi (new_close_phi
);
2389 /* A close phi must come from a loop-phi having a default value. */
2395 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2399 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2400 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2405 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2413 /* Copy loop close phi nodes from BB to NEW_BB. */
2416 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2420 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2422 /* Loop close phi nodes should have only one argument. */
2423 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2425 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2429 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2430 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2431 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2432 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2435 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2436 In this case DOMINATING_PRED = NULL.
2438 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2440 Returns true on successful copy of the args, false otherwise. */
2443 translate_isl_ast_to_gimple::
2444 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2445 edge old_bb_dominating_edge
,
2446 edge old_bb_non_dominating_edge
,
2447 gphi
*phi
, gphi
*new_phi
,
2450 basic_block def_pred
[2] = { NULL
, NULL
};
2451 int not_found_bb_index
= -1;
2452 for (int i
= 0; i
< 2; i
++)
2454 /* If the corresponding def_bb could not be found the entry will be
2456 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2457 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2458 gimple_phi_arg_edge (phi
, i
)->src
);
2459 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2460 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2464 /* When non are available bail out. */
2465 if (not_found_bb_index
!= -1)
2467 not_found_bb_index
= i
;
2471 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2472 if (old_bb_dominating_edge
)
2474 if (not_found_bb_index
!= -1)
2477 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2478 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2479 vec
<basic_block
> *bbs
2480 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2482 /* Could not find a mapping. */
2486 basic_block new_pred
= NULL
;
2489 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2491 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2493 /* FIXME: If we have already found new_pred then we have to
2494 disambiguate, bail out for now. */
2497 new_pred
= new_pred1
;
2499 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2501 /* FIXME: If we have already found new_pred then we have to either
2502 it dominates both or we have to disambiguate, bail out. */
2505 new_pred
= new_pred2
;
2512 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2513 gcc_assert (new_non_dominating_edge
);
2514 /* FIXME: Validate each args just like in loop-phis. */
2515 /* By the process of elimination we first insert insert phi-edge for
2516 non-dominating pred which is computed above and then we insert the
2518 int inserted_edge
= 0;
2519 for (; inserted_edge
< 2; inserted_edge
++)
2521 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2522 if (new_non_dominating_edge
== new_bb_pred_edge
)
2524 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2525 new_non_dominating_edge
,
2526 get_loc (old_phi_args
[inserted_edge
]));
2530 if (inserted_edge
== 2)
2533 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2535 edge new_dominating_edge
= NULL
;
2536 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2538 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2539 if (e
!= new_non_dominating_edge
)
2541 new_dominating_edge
= e
;
2542 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2543 new_dominating_edge
,
2544 get_loc (old_phi_args
[inserted_edge
]));
2548 gcc_assert (new_dominating_edge
);
2552 /* Classic diamond structure: both edges are non-dominating. We need to
2553 find one unique edge then the other can be found be elimination. If
2554 any definition (def_pred) dominates both the preds of new_bb then we
2555 bail out. Entries of def_pred maybe NULL, in that case we must
2556 uniquely find pred with help of only one entry. */
2557 edge new_e
[2] = { NULL
, NULL
};
2558 for (int i
= 0; i
< 2; i
++)
2562 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2564 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2567 /* We do not know how to handle the case when def_pred
2568 dominates more than a predecessor. */
2574 gcc_assert (new_e
[0] || new_e
[1]);
2576 /* Find the other edge by process of elimination. */
2577 if (not_found_bb_index
!= -1)
2579 gcc_assert (!new_e
[not_found_bb_index
]);
2580 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2583 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2585 if (new_e
[found_bb_index
] == e
)
2587 new_e
[not_found_bb_index
] = e
;
2591 /* Add edges to phi args. */
2592 for (int i
= 0; i
< 2; i
++)
2593 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2594 get_loc (old_phi_args
[i
]));
2600 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2601 region. If postpone is true and it isn't possible to copy any arg of PHI,
2602 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2603 Returns false if the copying was unsuccessful. */
2606 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2611 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2612 gcc_assert (2 == gimple_phi_num_args (phi
));
2614 basic_block new_bb
= gimple_bb (new_phi
);
2615 loop_p loop
= gimple_bb (phi
)->loop_father
;
2617 basic_block old_bb
= gimple_bb (phi
);
2618 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2622 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2623 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2624 old_bb_non_dominating_edge
= e
;
2626 old_bb_dominating_edge
= e
;
2628 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2629 old_bb_non_dominating_edge
->src
));
2631 tree new_phi_args
[2];
2632 tree old_phi_args
[2];
2634 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2636 tree old_name
= gimple_phi_arg_def (phi
, i
);
2637 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, cond_phi
);
2638 old_phi_args
[i
] = old_name
;
2641 new_phi_args
[i
] = new_name
;
2645 /* If the phi-arg was a parameter. */
2646 if (vec_find (region
->params
, old_name
) != -1)
2648 new_phi_args
[i
] = old_name
;
2652 "[codegen] parameter argument to phi, new_expr: ");
2653 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2654 fprintf (dump_file
, "\n");
2659 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2660 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2661 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2667 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2668 if (is_gimple_reg (old_name
)
2669 && scev_analyzable_p (old_name
, region
->region
))
2672 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2673 new_bb
, old_bb
, iv_map
);
2674 if (codegen_error_p ())
2677 gcc_assert (new_expr
);
2681 "[codegen] scev analyzeable, new_expr: ");
2682 print_generic_expr (dump_file
, new_expr
, 0);
2683 fprintf (dump_file
, "\n");
2685 gsi_insert_earliest (stmts
);
2686 new_phi_args
[i
] = new_name
;
2690 /* Postpone code gen for later for back-edges. */
2691 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2695 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2696 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2699 new_phi_args
[i
] = NULL_TREE
;
2703 /* Either we should add the arg to phi or, we should postpone. */
2707 /* If none of the args have been determined in the first stage then wait until
2709 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2712 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2713 old_bb_dominating_edge
,
2714 old_bb_non_dominating_edge
,
2715 phi
, new_phi
, new_bb
);
2718 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2719 containing phi nodes coming from two predecessors, and none of them are back
2723 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2728 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2731 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2734 /* Cond phi nodes should have exactly two arguments. */
2735 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2737 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2740 gphi
*phi
= psi
.phi ();
2741 tree res
= gimple_phi_result (phi
);
2742 if (virtual_operand_p (res
))
2744 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2745 /* Cond phi nodes should not be scev_analyzable_p. */
2748 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2749 tree new_res
= create_new_def_for (res
, new_phi
,
2750 gimple_phi_result_ptr (new_phi
));
2751 set_rename (res
, new_res
);
2753 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2756 update_stmt (new_phi
);
2762 /* Return true if STMT should be copied from region to the new code-generated
2763 region. LABELs, CONDITIONS, induction-variables and region parameters need
2767 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2769 /* Do not copy labels or conditions. */
2770 if (gimple_code (stmt
) == GIMPLE_LABEL
2771 || gimple_code (stmt
) == GIMPLE_COND
)
2775 /* Do not copy induction variables. */
2776 if (is_gimple_assign (stmt
)
2777 && (lhs
= gimple_assign_lhs (stmt
))
2778 && TREE_CODE (lhs
) == SSA_NAME
2779 && is_gimple_reg (lhs
)
2780 && scev_analyzable_p (lhs
, region
->region
))
2783 /* Do not copy parameters that have been generated in the header of the
2785 if (is_gimple_assign (stmt
)
2786 && (lhs
= gimple_assign_lhs (stmt
))
2787 && TREE_CODE (lhs
) == SSA_NAME
2788 && region
->parameter_rename_map
->get(lhs
))
2794 /* Create new names for all the definitions created by COPY and add replacement
2795 mappings for each new name. */
2798 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2800 def_operand_p def_p
;
2801 ssa_op_iter op_iter
;
2802 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2804 tree old_name
= DEF_FROM_PTR (def_p
);
2805 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2806 set_rename (old_name
, new_name
);
2810 /* Duplicates the statements of basic block BB into basic block NEW_BB
2811 and compute the new induction variables according to the IV_MAP.
2812 CODEGEN_ERROR is set when the code generation cannot continue. */
2815 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2819 /* Iterator poining to the place where new statement (s) will be inserted. */
2820 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2822 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2825 gimple
*stmt
= gsi_stmt (gsi
);
2826 if (!should_copy_to_new_region (stmt
, region
))
2829 /* Create a new copy of STMT and duplicate STMT's virtual
2831 gimple
*copy
= gimple_copy (stmt
);
2832 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2836 fprintf (dump_file
, "[codegen] inserting statement: ");
2837 print_gimple_stmt (dump_file
, copy
, 0, 0);
2840 maybe_duplicate_eh_stmt (copy
, stmt
);
2841 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2843 /* Crete new names for each def in the copied stmt. */
2844 set_rename_for_each_def (copy
);
2846 loop_p loop
= bb
->loop_father
;
2847 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2849 fold_stmt_inplace (&gsi_tgt
);
2850 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2853 if (codegen_error_p ())
2856 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2858 use_operand_p use_p
;
2859 if (!is_gimple_debug (copy
))
2860 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, iter
, SSA_OP_USE
)
2862 tree old_name
= USE_FROM_PTR (use_p
);
2864 if (TREE_CODE (old_name
) != SSA_NAME
2865 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
2868 tree
*new_expr
= region
->parameter_rename_map
->get (old_name
);
2872 replace_exp (use_p
, *new_expr
);
2882 /* Given a basic block containing close-phi it returns the new basic block where
2883 to insert a copy of the close-phi nodes. All the uses in close phis should
2884 come from a single loop otherwise it returns NULL. */
2887 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2889 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2890 of close phi in the original code and then find the mapping of basic block
2891 defining that variable. If there are multiple close-phis and they are
2892 defined in different loops (in the original or in the new code) because of
2893 loop splitting, then we bail out. */
2894 loop_p new_loop
= NULL
;
2895 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2898 gphi
*phi
= psi
.phi ();
2899 tree name
= gimple_phi_arg_def (phi
, 0);
2900 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2902 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2903 if (!bbs
|| bbs
->length () != 1)
2904 /* This is one of the places which shows preserving original structure
2905 is not always possible, as we may need to insert close PHI for a loop
2906 where the latch does not have any mapping, or the mapping is
2911 new_loop
= (*bbs
)[0]->loop_father
;
2912 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2919 return single_exit (new_loop
);
2922 /* Copies BB and includes in the copied BB all the statements that can
2923 be reached following the use-def chains from the memory accesses,
2924 and returns the next edge following this new block. codegen_error is
2925 set when the code generation cannot continue. */
2928 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2932 int num_phis
= number_of_phi_nodes (bb
);
2934 if (region
->copied_bb_map
->get (bb
))
2936 /* FIXME: we should be able to handle phi nodes with args coming from
2937 outside the region. */
2940 codegen_error
= true;
2945 basic_block new_bb
= NULL
;
2946 if (bb_contains_loop_close_phi_nodes (bb
))
2949 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2952 edge e
= edge_for_new_close_phis (bb
);
2955 codegen_error
= true;
2959 basic_block phi_bb
= e
->dest
;
2961 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2962 phi_bb
= split_edge (e
);
2964 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2965 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2967 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2969 codegen_error
= true;
2976 new_bb
= split_edge (next_e
);
2980 new_bb
= split_edge (next_e
);
2981 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2983 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2985 /* At this point we are unable to codegenerate by still preserving the SSA
2986 structure because maybe the loop is completely unrolled and the PHIs
2987 and cross-bb scalar dependencies are untrackable w.r.t. the original
2988 code. See gfortran.dg/graphite/pr29832.f90. */
2989 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2991 codegen_error
= true;
2995 /* In case isl did some loop peeling, like this:
2998 for (int c1 = 1; c1 <= 5; c1 += 1) {
3003 there should be no loop-phi nodes in S_8(0).
3005 FIXME: We need to reason about dynamic instances of S_8, i.e., the
3006 values of all scalar variables: for the moment we instantiate only
3007 SCEV analyzable expressions on the iteration domain, and we need to
3008 extend that to reductions that cannot be analyzed by SCEV. */
3009 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
3011 codegen_error
= true;
3016 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
3018 if (!copy_loop_phi_nodes (bb
, phi_bb
))
3020 codegen_error
= true;
3024 else if (num_phis
> 0)
3027 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
3030 basic_block phi_bb
= single_pred (new_bb
);
3031 loop_p loop_father
= new_bb
->loop_father
;
3033 /* Move back until we find the block with two predecessors. */
3034 while (single_pred_p (phi_bb
))
3035 phi_bb
= single_pred_edge (phi_bb
)->src
;
3037 /* If a corresponding merge-point was not found, then abort codegen. */
3038 if (phi_bb
->loop_father
!= loop_father
3039 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
3040 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
3042 codegen_error
= true;
3049 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
3050 bb
->index
, new_bb
->index
);
3052 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
3054 copied_bbs
->safe_push (new_bb
);
3057 vec
<basic_block
> bbs
;
3059 bbs
.safe_push (new_bb
);
3060 region
->copied_bb_map
->put (bb
, bbs
);
3063 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3065 codegen_error
= true;
3069 return single_succ_edge (new_bb
);
3072 /* Patch the missing arguments of the phi nodes. */
3075 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3079 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3081 gphi
*old_phi
= rename
->first
;
3082 gphi
*new_phi
= rename
->second
;
3083 basic_block old_bb
= gimple_bb (old_phi
);
3084 basic_block new_bb
= gimple_bb (new_phi
);
3086 /* First edge is the init edge and second is the back edge. */
3087 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3088 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3092 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3093 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3096 auto_vec
<tree
, 1> iv_map
;
3097 if (bb_contains_loop_phi_nodes (new_bb
))
3098 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3100 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3101 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3103 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3107 fprintf (dump_file
, "[codegen] to new-phi: ");
3108 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3115 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
3118 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3121 sese_info_p region
= scop
->scop_info
;
3122 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3123 gcc_assert (nb_parameters
== region
->params
.length ());
3125 for (i
= 0; i
< nb_parameters
; i
++)
3127 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3129 ip
[tmp_id
] = region
->params
[i
];
3134 /* Generates a build, which specifies the constraints on the parameters. */
3136 __isl_give isl_ast_build
*
3137 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3139 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3140 return isl_ast_build_from_context (context_isl
);
3143 /* This method is executed before the construction of a for node. */
3145 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3147 isl_union_map
*dependences
= (isl_union_map
*) user
;
3148 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3149 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3150 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3151 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3152 for_info
->is_parallelizable
=
3153 !carries_deps (schedule
, dependences
, dimension
);
3154 isl_union_map_free (schedule
);
3155 isl_space_free (schedule_space
);
3156 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3160 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3162 /* Generate isl AST from schedule of SCOP. */
3164 __isl_give isl_ast_node
*
3165 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
)
3167 gcc_assert (scop
->transformed_schedule
);
3169 /* Set the separate option to reduce control flow overhead. */
3170 isl_schedule
*schedule
= isl_schedule_map_schedule_node_bottom_up
3171 (isl_schedule_copy (scop
->transformed_schedule
), set_separate_option
, NULL
);
3172 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3174 if (flag_loop_parallelize_all
)
3176 scop_get_dependences (scop
);
3178 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3182 isl_ast_node
*ast_isl
= isl_ast_build_node_from_schedule
3183 (context_isl
, schedule
);
3184 isl_ast_build_free (context_isl
);
3189 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3192 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3196 int schedule_dims
= 0;
3198 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3200 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3201 if (pbb_schedule_dims
> schedule_dims
)
3202 schedule_dims
= pbb_schedule_dims
;
3205 return schedule_dims
;
3208 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3210 For schedules with different dimensionality, the isl AST generator can not
3211 define an order and will just randomly choose an order. The solution to this
3212 problem is to extend all schedules to the maximal number of schedule
3213 dimensions (using '0's for the remaining values). */
3215 __isl_give isl_map
*
3216 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3217 int nb_schedule_dims
)
3219 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3221 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3223 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3225 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3228 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3230 isl_val_free (zero
);
3234 /* Generates a schedule, which specifies an order used to
3235 visit elements in a domain. */
3237 __isl_give isl_union_map
*
3238 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3240 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3243 isl_union_map
*schedule_isl
=
3244 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3246 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3248 /* Dead code elimination: when the domain of a PBB is empty,
3249 don't generate code for the PBB. */
3250 if (isl_set_is_empty (pbb
->domain
))
3253 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3254 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3255 isl_set_copy (pbb
->domain
));
3256 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3257 bb_schedule
= isl_map_coalesce (bb_schedule
);
3259 = isl_union_map_union (schedule_isl
,
3260 isl_union_map_from_map (bb_schedule
));
3261 schedule_isl
= isl_union_map_coalesce (schedule_isl
);
3263 return schedule_isl
;
3266 /* Set the separate option for all dimensions.
3267 This helps to reduce control overhead. */
3269 __isl_give isl_ast_build
*
3270 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3271 __isl_keep isl_union_map
*schedule
)
3273 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3274 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3276 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3277 isl_union_set
*range
=
3278 isl_union_set_from_set (isl_set_universe (range_space
));
3279 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3280 domain
= isl_union_set_universe (domain
);
3281 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3282 return isl_ast_build_set_options (control
, options
);
3285 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3287 __isl_give isl_ast_node
*
3288 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3290 /* Generate loop upper bounds that consist of the current loop iterator, an
3291 operator (< or <=) and an expression not involving the iterator. If this
3292 option is not set, then the current loop iterator may appear several times
3293 in the upper bound. See the isl manual for more details. */
3294 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3296 add_parameters_to_ivs_params (scop
, ip
);
3297 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3298 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3299 context_isl
= set_options (context_isl
, schedule_isl
);
3300 if (flag_loop_parallelize_all
)
3302 isl_union_map
*dependence
= scop_get_dependences (scop
);
3304 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3308 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3312 isl_schedule_free (scop
->schedule
);
3313 scop
->schedule
= NULL
;
3316 isl_ast_build_free (context_isl
);
3321 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
3322 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
3325 copy_def (tree tr
, gimple
*def_stmt
, sese_info_p region
, sese_info_p to_region
,
3326 gimple_stmt_iterator
*gsi
)
3328 if (!defined_in_sese_p (tr
, region
->region
))
3332 use_operand_p use_p
;
3333 FOR_EACH_SSA_USE_OPERAND (use_p
, def_stmt
, iter
, SSA_OP_USE
)
3335 tree use_tr
= USE_FROM_PTR (use_p
);
3337 /* Do not copy parameters that have been generated in the header of the
3339 if (region
->parameter_rename_map
->get(use_tr
))
3342 gimple
*def_of_use
= SSA_NAME_DEF_STMT (use_tr
);
3346 copy_def (use_tr
, def_of_use
, region
, to_region
, gsi
);
3349 gimple
*copy
= gimple_copy (def_stmt
);
3350 gsi_insert_after (gsi
, copy
, GSI_NEW_STMT
);
3352 /* Create new names for all the definitions created by COPY and
3353 add replacement mappings for each new name. */
3354 def_operand_p def_p
;
3355 ssa_op_iter op_iter
;
3356 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
3358 tree old_name
= DEF_FROM_PTR (def_p
);
3359 tree new_name
= create_new_def_for (old_name
, copy
, def_p
);
3360 region
->parameter_rename_map
->put(old_name
, new_name
);
3367 copy_internal_parameters (sese_info_p region
, sese_info_p to_region
)
3369 /* For all the parameters which definitino is in the if_region->false_region,
3370 insert code on true_region (if_region->true_region->entry). */
3374 gimple_stmt_iterator gsi
= gsi_start_bb(to_region
->region
.entry
->dest
);
3376 FOR_EACH_VEC_ELT (region
->params
, i
, tr
)
3378 // If def is not in region.
3379 gimple
*def_stmt
= SSA_NAME_DEF_STMT (tr
);
3381 copy_def (tr
, def_stmt
, region
, to_region
, &gsi
);
3385 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3386 the given SCOP. Return true if code generation succeeded.
3388 FIXME: This is not yet a full implementation of the code generator
3389 with isl ASTs. Generation of GIMPLE code has to be completed. */
3392 graphite_regenerate_ast_isl (scop_p scop
)
3394 sese_info_p region
= scop
->scop_info
;
3395 translate_isl_ast_to_gimple
t (region
);
3397 ifsese if_region
= NULL
;
3398 isl_ast_node
*root_node
;
3401 timevar_push (TV_GRAPHITE_CODE_GEN
);
3402 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3403 t
.add_parameters_to_ivs_params (scop
, ip
);
3404 root_node
= t
.scop_to_isl_ast (scop
);
3406 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3411 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3412 fprintf (dump_file
, "[scheduler] original schedule:\n");
3413 print_isl_schedule (dump_file
, scop
->original_schedule
);
3414 fprintf (dump_file
, "[scheduler] isl transformed schedule:\n");
3415 print_isl_schedule (dump_file
, scop
->transformed_schedule
);
3417 fprintf (dump_file
, "[scheduler] original ast:\n");
3418 print_schedule_ast (dump_file
, scop
->original_schedule
, scop
);
3420 fprintf (dump_file
, "[scheduler] AST generated by isl:\n");
3421 print_isl_ast (dump_file
, root_node
);
3424 recompute_all_dominators ();
3427 if_region
= move_sese_in_condition (region
);
3428 region
->if_region
= if_region
;
3429 recompute_all_dominators ();
3431 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3433 /* Copy all the parameters which are defined in the region. */
3434 copy_internal_parameters(if_region
->false_region
, if_region
->true_region
);
3436 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3437 basic_block bb
= split_edge (e
);
3439 /* Update the true_region exit edge. */
3440 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3442 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3443 if (t
.codegen_error_p ())
3446 fprintf (dump_file
, "codegen error: "
3447 "reverting back to the original code.\n");
3448 set_ifsese_condition (if_region
, integer_zero_node
);
3452 t
.translate_pending_phi_nodes ();
3453 if (!t
.codegen_error_p ())
3455 sese_insert_phis_for_liveouts (region
,
3456 if_region
->region
->region
.exit
->src
,
3457 if_region
->false_region
->region
.exit
,
3458 if_region
->true_region
->region
.exit
);
3459 mark_virtual_operands_for_renaming (cfun
);
3460 update_ssa (TODO_update_ssa
);
3465 recompute_all_dominators ();
3469 fprintf (dump_file
, "[codegen] isl AST to Gimple succeeded.\n");
3474 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3475 " pending phis, reverting back to the original code.\n");
3476 set_ifsese_condition (if_region
, integer_zero_node
);
3480 free (if_region
->true_region
);
3481 free (if_region
->region
);
3484 ivs_params_clear (ip
);
3485 isl_ast_node_free (root_node
);
3486 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3491 int num_no_dependency
= 0;
3493 FOR_EACH_LOOP (loop
, 0)
3494 if (loop
->can_be_parallel
)
3495 num_no_dependency
++;
3497 fprintf (dump_file
, "%d loops carried no dependency.\n",
3501 return !t
.codegen_error_p ();
3504 #endif /* HAVE_isl */