1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 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"
60 /* We always try to use signed 128 bit types, but fall back to smaller types
61 in case a platform does not provide types of these sizes. In the future we
62 should use isl to derive the optimal type for each subexpression. */
64 static int max_mode_int_precision
=
65 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
66 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
67 128 : max_mode_int_precision
;
72 : is_parallelizable(false)
74 bool is_parallelizable
;
77 /* Converts a GMP constant VAL to a tree and returns it. */
80 gmp_cst_to_tree (tree type
, mpz_t val
)
82 tree t
= type
? type
: integer_type_node
;
87 wide_int wi
= wi::from_mpz (t
, tmp
, true);
90 return wide_int_to_tree (t
, wi
);
93 /* Verifies properties that GRAPHITE should maintain during translation. */
96 graphite_verify (void)
98 checking_verify_loop_structure ();
99 checking_verify_loop_closed_ssa (true);
102 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
103 to corresponding trees. */
105 typedef std::map
<isl_id
*, tree
> ivs_params
;
107 /* Free all memory allocated for ISL's identifiers. */
109 void ivs_params_clear (ivs_params
&ip
)
111 std::map
<isl_id
*, tree
>::iterator it
;
112 for (it
= ip
.begin ();
113 it
!= ip
.end (); it
++)
115 isl_id_free (it
->first
);
119 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
121 /* Set the "separate" option for the schedule node. */
123 static __isl_give isl_schedule_node
*
124 set_separate_option (__isl_take isl_schedule_node
*node
, void *user
)
129 if (isl_schedule_node_get_type (node
) != isl_schedule_node_band
)
132 /* Set the "separate" option unless it is set earlier to another option. */
133 if (isl_schedule_node_band_member_get_ast_loop_type (node
, 0)
134 == isl_ast_loop_default
)
135 return isl_schedule_node_band_member_set_ast_loop_type
136 (node
, 0, isl_ast_loop_separate
);
142 class translate_isl_ast_to_gimple
145 translate_isl_ast_to_gimple (sese_info_p r
)
146 : region (r
), codegen_error (false)
149 /* Translates an ISL AST node NODE to GCC representation in the
150 context of a SESE. */
151 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
152 edge next_e
, ivs_params
&ip
);
154 /* Translates an isl_ast_node_for to Gimple. */
155 edge
translate_isl_ast_node_for (loop_p context_loop
,
156 __isl_keep isl_ast_node
*node
,
157 edge next_e
, ivs_params
&ip
);
159 /* Create the loop for a isl_ast_node_for.
161 - NEXT_E is the edge where new generated code should be attached. */
162 edge
translate_isl_ast_for_loop (loop_p context_loop
,
163 __isl_keep isl_ast_node
*node_for
,
165 tree type
, tree lb
, tree ub
,
168 /* Translates an isl_ast_node_if to Gimple. */
169 edge
translate_isl_ast_node_if (loop_p context_loop
,
170 __isl_keep isl_ast_node
*node
,
171 edge next_e
, ivs_params
&ip
);
173 /* Translates an isl_ast_node_user to Gimple.
175 FIXME: We should remove iv_map.create (loop->num + 1), if it is
177 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
178 edge next_e
, ivs_params
&ip
);
180 /* Translates an isl_ast_node_block to Gimple. */
181 edge
translate_isl_ast_node_block (loop_p context_loop
,
182 __isl_keep isl_ast_node
*node
,
183 edge next_e
, ivs_params
&ip
);
185 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
187 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
190 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
192 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
195 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
197 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
200 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
201 to a GCC expression tree of type TYPE. */
202 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
205 /* Converts an ISL AST expression E back to a GCC expression tree of
207 tree
gcc_expression_from_isl_expression (tree type
,
208 __isl_take isl_ast_expr
*,
211 /* Return the tree variable that corresponds to the given isl ast identifier
212 expression (an isl_ast_expr of type isl_ast_expr_id).
214 FIXME: We should replace blind conversation of id's type with derivation
215 of the optimal type when we get the corresponding isl support. Blindly
216 converting type sizes may be problematic when we switch to smaller
218 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
219 __isl_keep isl_ast_expr
*expr_id
,
222 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
224 tree
gcc_expression_from_isl_expr_int (tree type
,
225 __isl_take isl_ast_expr
*expr
);
227 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
229 tree
gcc_expression_from_isl_expr_op (tree type
,
230 __isl_take isl_ast_expr
*expr
,
233 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
234 induction variable for the new LOOP. New LOOP is attached to CFG
235 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
236 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
237 ISL's scattering name to the induction variable created for the
238 loop of STMT. The new induction variable is inserted in the NEWIVS
239 vector and is of type TYPE. */
240 struct loop
*graphite_create_new_loop (edge entry_edge
,
241 __isl_keep isl_ast_node
*node_for
,
242 loop_p outer
, tree type
,
243 tree lb
, tree ub
, ivs_params
&ip
);
245 /* All loops generated by create_empty_loop_on_edge have the form of
252 } while (lower bound < upper bound);
254 We create a new if region protecting the loop to be executed, if
255 the execution count is zero (lower bound > upper bound). */
256 edge
graphite_create_new_loop_guard (edge entry_edge
,
257 __isl_keep isl_ast_node
*node_for
,
259 tree
*lb
, tree
*ub
, ivs_params
&ip
);
261 /* Creates a new if region corresponding to ISL's cond. */
262 edge
graphite_create_new_guard (edge entry_edge
,
263 __isl_take isl_ast_expr
*if_cond
,
266 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
267 variables of the loops around GBB in SESE.
269 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
270 chrec, we could consider using a map<int, tree> that maps loop ids to the
271 corresponding tree expressions. */
272 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
273 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
276 /* Patch the missing arguments of the phi nodes. */
278 void translate_pending_phi_nodes (void);
280 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
282 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
284 /* Get the maximal number of schedule dimensions in the scop SCOP. */
286 int get_max_schedule_dimensions (scop_p scop
);
288 /* Generates a build, which specifies the constraints on the parameters. */
290 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
292 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
294 For schedules with different dimensionality, the isl AST generator can not
295 define an order and will just randomly choose an order. The solution to
296 this problem is to extend all schedules to the maximal number of schedule
297 dimensions (using '0's for the remaining values). */
299 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
300 int nb_schedule_dims
);
302 /* Generates a schedule, which specifies an order used to
303 visit elements in a domain. */
305 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
307 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
308 /* Set the "separate" option for all schedules. This helps reducing control
311 __isl_give isl_schedule
*
312 set_options_for_schedule_tree (__isl_take isl_schedule
*schedule
);
315 /* Set the separate option for all dimensions.
316 This helps to reduce control overhead. */
318 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
319 __isl_keep isl_union_map
*schedule
);
321 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
324 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
327 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
328 definition should flow into use, and the use should respect the loop-closed
331 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
332 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
334 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
335 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
336 within a loop PHI instruction. */
338 tree
get_rename (basic_block new_bb
, tree old_name
,
339 basic_block old_bb
, bool loop_phi
) const;
341 /* For ops which are scev_analyzeable, we can regenerate a new name from
342 its scalar evolution around LOOP. */
344 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
345 basic_block new_bb
, basic_block old_bb
,
348 /* Returns a basic block that could correspond to where a constant was defined
349 in the original code. In the original code OLD_BB had the definition, we
350 need to find which basic block out of the copies of old_bb, in the new
351 region, should a definition correspond to if it has to reach BB. */
353 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
355 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
356 true when we want to rename an OP within a loop PHI instruction. */
358 tree
get_new_name (basic_block new_bb
, tree op
,
359 basic_block old_bb
, bool loop_phi
) const;
361 /* Collect all the operands of NEW_EXPR by recursively visiting each
364 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
366 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
367 NEW_PHI must be found unless they can be POSTPONEd for later. */
369 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
370 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
373 /* Copy loop phi nodes from BB to NEW_BB. */
375 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
377 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
378 the close phi node PHI. */
380 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
383 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
384 gimple
*old_close_phi
);
386 /* Copy all the loop-close phi args from BB to NEW_BB. */
388 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
391 /* Copy loop close phi nodes from BB to NEW_BB. */
393 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
395 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
396 region. If postpone is true and it isn't possible to copy any arg of PHI,
397 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
398 Returns false if the copying was unsuccessful. */
400 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
403 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
404 containing phi nodes coming from two predecessors, and none of them are back
407 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
410 /* Duplicates the statements of basic block BB into basic block NEW_BB
411 and compute the new induction variables according to the IV_MAP.
412 CODEGEN_ERROR is set when the code generation cannot continue. */
414 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
417 /* Copies BB and includes in the copied BB all the statements that can
418 be reached following the use-def chains from the memory accesses,
419 and returns the next edge following this new block. codegen_error is
420 set when the code generation cannot continue. */
422 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
425 /* Given a basic block containing close-phi it returns the new basic block
426 where to insert a copy of the close-phi nodes. All the uses in close phis
427 should come from a single loop otherwise it returns NULL. */
428 edge
edge_for_new_close_phis (basic_block bb
);
430 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
431 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
432 the other pred of OLD_BB as well. If no such basic block exists then it is
433 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
436 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
437 versa. In this case DOMINATING_PRED = NULL.
439 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
441 Returns true on successful copy of the args, false otherwise. */
443 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
444 edge old_bb_dominating_edge
,
445 edge old_bb_non_dominating_edge
,
446 gphi
*phi
, gphi
*new_phi
,
449 /* Renames the scalar uses of the statement COPY, using the substitution map
450 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
451 translation REGION, with the original copied statement in LOOP, and using
452 the induction variable renaming map IV_MAP. Returns true when something
453 has been renamed. codegen_error is set when the code generation cannot
456 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
457 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
459 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
460 When OLD_NAME and EXPR are the same we assert. */
462 void set_rename (tree old_name
, tree expr
);
464 /* Create new names for all the definitions created by COPY and add
465 replacement mappings for each new name. */
467 void set_rename_for_each_def (gimple
*stmt
);
469 /* Insert each statement from SEQ at its earliest insertion p. */
471 void gsi_insert_earliest (gimple_seq seq
);
473 /* Rename all the operands of NEW_EXPR by recursively visiting each
476 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
478 bool codegen_error_p () const
479 { return codegen_error
; }
481 /* Prints NODE to FILE. */
483 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
484 __isl_keep isl_ctx
*ctx
) const;
486 /* Return true when OP is a constant tree. */
488 bool is_constant (tree op
) const
490 return TREE_CODE (op
) == INTEGER_CST
491 || TREE_CODE (op
) == REAL_CST
492 || TREE_CODE (op
) == COMPLEX_CST
493 || TREE_CODE (op
) == VECTOR_CST
;
497 /* The region to be translated. */
500 /* This flag is set when an error occurred during the translation of ISL AST
504 /* A vector of all the edges at if_condition merge points. */
505 auto_vec
<edge
, 2> merge_points
;
508 /* Return the tree variable that corresponds to the given isl ast identifier
509 expression (an isl_ast_expr of type isl_ast_expr_id).
511 FIXME: We should replace blind conversation of id's type with derivation
512 of the optimal type when we get the corresponding isl support. Blindly
513 converting type sizes may be problematic when we switch to smaller
517 translate_isl_ast_to_gimple::
518 gcc_expression_from_isl_ast_expr_id (tree type
,
519 __isl_take isl_ast_expr
*expr_id
,
522 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
523 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
524 std::map
<isl_id
*, tree
>::iterator res
;
525 res
= ip
.find (tmp_isl_id
);
526 isl_id_free (tmp_isl_id
);
527 gcc_assert (res
!= ip
.end () &&
528 "Could not map isl_id to tree expression");
529 isl_ast_expr_free (expr_id
);
530 tree t
= res
->second
;
531 return fold_convert (type
, t
);
534 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
538 translate_isl_ast_to_gimple::
539 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
541 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
542 isl_val
*val
= isl_ast_expr_get_val (expr
);
544 mpz_init (val_mpz_t
);
546 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
549 res
= gmp_cst_to_tree (type
, val_mpz_t
);
551 isl_ast_expr_free (expr
);
552 mpz_clear (val_mpz_t
);
556 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
560 translate_isl_ast_to_gimple::
561 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
563 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
564 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
565 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
566 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
568 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
569 isl_ast_expr_free (expr
);
577 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
580 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
583 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
586 /* As ISL operates on arbitrary precision numbers, we may end up with
587 division by 2^64 that is folded to 0. */
588 if (integer_zerop (tree_rhs_expr
))
590 codegen_error
= true;
593 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
595 case isl_ast_op_pdiv_q
:
596 /* As ISL operates on arbitrary precision numbers, we may end up with
597 division by 2^64 that is folded to 0. */
598 if (integer_zerop (tree_rhs_expr
))
600 codegen_error
= true;
603 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
605 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
606 /* ISL-0.15 or later. */
607 case isl_ast_op_zdiv_r
:
609 case isl_ast_op_pdiv_r
:
610 /* As ISL operates on arbitrary precision numbers, we may end up with
611 division by 2^64 that is folded to 0. */
612 if (integer_zerop (tree_rhs_expr
))
614 codegen_error
= true;
617 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
619 case isl_ast_op_fdiv_q
:
620 /* As ISL operates on arbitrary precision numbers, we may end up with
621 division by 2^64 that is folded to 0. */
622 if (integer_zerop (tree_rhs_expr
))
624 codegen_error
= true;
627 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
630 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
631 tree_lhs_expr
, tree_rhs_expr
);
634 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
637 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
640 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
643 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
646 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
649 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
656 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
660 translate_isl_ast_to_gimple::
661 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
663 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
664 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
666 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
667 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
668 tree tree_second_expr
669 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
670 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
672 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
673 isl_ast_expr_free (expr
);
677 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
678 tree_second_expr
, tree_third_expr
);
681 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
685 translate_isl_ast_to_gimple::
686 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
688 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
689 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
690 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
691 isl_ast_expr_free (expr
);
692 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
695 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
696 to a GCC expression tree of type TYPE. */
699 translate_isl_ast_to_gimple::
700 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
702 enum tree_code op_code
;
703 switch (isl_ast_expr_get_op_type (expr
))
716 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
717 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
721 isl_ast_expr_free (expr
);
726 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
728 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
729 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
733 isl_ast_expr_free (expr
);
737 res
= fold_build2 (op_code
, type
, res
, t
);
739 isl_ast_expr_free (expr
);
743 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
747 translate_isl_ast_to_gimple::
748 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
753 isl_ast_expr_free (expr
);
757 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
758 switch (isl_ast_expr_get_op_type (expr
))
760 /* These isl ast expressions are not supported yet. */
761 case isl_ast_op_error
:
762 case isl_ast_op_call
:
763 case isl_ast_op_and_then
:
764 case isl_ast_op_or_else
:
765 case isl_ast_op_select
:
770 return nary_op_to_tree (type
, expr
, ip
);
776 case isl_ast_op_pdiv_q
:
777 case isl_ast_op_pdiv_r
:
778 case isl_ast_op_fdiv_q
:
779 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
780 /* ISL-0.15 or later. */
781 case isl_ast_op_zdiv_r
:
790 return binary_op_to_tree (type
, expr
, ip
);
792 case isl_ast_op_minus
:
793 return unary_op_to_tree (type
, expr
, ip
);
795 case isl_ast_op_cond
:
796 return ternary_op_to_tree (type
, expr
, ip
);
805 /* Converts an ISL AST expression E back to a GCC expression tree of
809 translate_isl_ast_to_gimple::
810 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
815 isl_ast_expr_free (expr
);
819 switch (isl_ast_expr_get_type (expr
))
821 case isl_ast_expr_id
:
822 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
824 case isl_ast_expr_int
:
825 return gcc_expression_from_isl_expr_int (type
, expr
);
827 case isl_ast_expr_op
:
828 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
837 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
838 induction variable for the new LOOP. New LOOP is attached to CFG
839 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
840 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
841 ISL's scattering name to the induction variable created for the
842 loop of STMT. The new induction variable is inserted in the NEWIVS
843 vector and is of type TYPE. */
846 translate_isl_ast_to_gimple::
847 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
848 loop_p outer
, tree type
, tree lb
, tree ub
,
851 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
852 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
854 /* To fail code generation, we generate wrong code until we discard it. */
856 stride
= integer_zero_node
;
858 tree ivvar
= create_tmp_var (type
, "graphite_IV");
859 tree iv
, iv_after_increment
;
860 loop_p loop
= create_empty_loop_on_edge
861 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
862 outer
? outer
: entry_edge
->src
->loop_father
);
864 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
865 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
866 std::map
<isl_id
*, tree
>::iterator res
;
869 isl_id_free (res
->first
);
871 isl_ast_expr_free (for_iterator
);
875 /* Create the loop for a isl_ast_node_for.
877 - NEXT_E is the edge where new generated code should be attached. */
880 translate_isl_ast_to_gimple::
881 translate_isl_ast_for_loop (loop_p context_loop
,
882 __isl_keep isl_ast_node
*node_for
, edge next_e
,
883 tree type
, tree lb
, tree ub
,
886 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
887 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
889 edge last_e
= single_exit (loop
);
890 edge to_body
= single_succ_edge (loop
->header
);
891 basic_block after
= to_body
->dest
;
893 /* Translate the body of the loop. */
894 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
895 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
896 isl_ast_node_free (for_body
);
898 /* Early return if we failed to translate loop body. */
899 if (!next_e
|| codegen_error_p ())
902 if (next_e
->dest
!= after
)
903 redirect_edge_succ_nodup (next_e
, after
);
904 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
906 if (flag_loop_parallelize_all
)
908 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
910 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
911 loop
->can_be_parallel
= for_info
->is_parallelizable
;
919 /* We use this function to get the upper bound because of the form,
920 which is used by isl to represent loops:
922 for (iterator = init; cond; iterator += inc)
930 The loop condition is an arbitrary expression, which contains the
931 current loop iterator.
933 (e.g. iterator + 3 < B && C > iterator + A)
935 We have to know the upper bound of the iterator to generate a loop
936 in Gimple form. It can be obtained from the special representation
937 of the loop condition, which is generated by isl,
938 if the ast_build_atomic_upper_bound option is set. In this case,
939 isl generates a loop condition that consists of the current loop
940 iterator, + an operator (< or <=) and an expression not involving
941 the iterator, which is processed and returned by this function.
943 (e.g iterator <= upper-bound-expression-without-iterator) */
945 static __isl_give isl_ast_expr
*
946 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
948 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
949 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
950 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
952 switch (isl_ast_expr_get_op_type (for_cond
))
955 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
960 /* (iterator < ub) => (iterator <= ub - 1). */
962 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
963 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
964 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
971 isl_ast_expr_free (for_cond
);
975 /* All loops generated by create_empty_loop_on_edge have the form of
982 } while (lower bound < upper bound);
984 We create a new if region protecting the loop to be executed, if
985 the execution count is zero (lower bound > upper bound). */
988 translate_isl_ast_to_gimple::
989 graphite_create_new_loop_guard (edge entry_edge
,
990 __isl_keep isl_ast_node
*node_for
, tree
*type
,
991 tree
*lb
, tree
*ub
, ivs_params
&ip
)
993 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
998 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
999 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
1000 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
1001 /* To fail code generation, we generate wrong code until we discard it. */
1003 *lb
= integer_zero_node
;
1004 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
1005 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
1006 /* To fail code generation, we generate wrong code until we discard it. */
1008 *ub
= integer_zero_node
;
1010 /* When ub is simply a constant or a parameter, use lb <= ub. */
1011 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
1012 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
1015 tree one
= (POINTER_TYPE_P (*type
)
1016 ? convert_to_ptrofftype (integer_one_node
)
1017 : fold_convert (*type
, integer_one_node
));
1018 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1019 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1020 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1021 is true, even if we do not want this. However lb < ub + 1 is false,
1023 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1024 : PLUS_EXPR
, *type
, *ub
, one
);
1026 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1029 if (integer_onep (cond_expr
))
1030 exit_edge
= entry_edge
;
1032 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1037 /* Translates an isl_ast_node_for to Gimple. */
1040 translate_isl_ast_to_gimple::
1041 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1042 edge next_e
, ivs_params
&ip
)
1044 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1046 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1049 if (last_e
== next_e
)
1051 /* There was no guard generated. */
1052 last_e
= single_succ_edge (split_edge (last_e
));
1054 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1059 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1060 merge_points
.safe_push (last_e
);
1062 last_e
= single_succ_edge (split_edge (last_e
));
1063 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1068 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1069 variables of the loops around GBB in SESE.
1071 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1072 chrec, we could consider using a map<int, tree> that maps loop ids to the
1073 corresponding tree expressions. */
1076 translate_isl_ast_to_gimple::
1077 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1078 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1081 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1082 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1084 isl_ast_expr
*arg_expr
;
1085 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1087 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1089 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1090 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1091 /* To fail code generation, we generate wrong code until we discard it. */
1093 t
= integer_zero_node
;
1095 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1096 iv_map
[old_loop
->num
] = t
;
1100 /* Translates an isl_ast_node_user to Gimple.
1102 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1105 translate_isl_ast_to_gimple::
1106 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1107 edge next_e
, ivs_params
&ip
)
1109 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1111 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1112 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1113 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1115 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1116 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1119 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1121 isl_ast_expr_free (name_expr
);
1122 isl_id_free (name_id
);
1124 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1125 "The entry block should not even appear within a scop");
1127 const int nb_loops
= number_of_loops (cfun
);
1129 iv_map
.create (nb_loops
);
1130 iv_map
.safe_grow_cleared (nb_loops
);
1132 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1133 isl_ast_expr_free (user_expr
);
1135 basic_block old_bb
= GBB_BB (gbb
);
1139 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1140 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1141 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1145 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1149 if (codegen_error_p ())
1154 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1155 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1161 /* Translates an isl_ast_node_block to Gimple. */
1164 translate_isl_ast_to_gimple::
1165 translate_isl_ast_node_block (loop_p context_loop
,
1166 __isl_keep isl_ast_node
*node
,
1167 edge next_e
, ivs_params
&ip
)
1169 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1170 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1172 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1174 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1175 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1176 isl_ast_node_free (tmp_node
);
1178 isl_ast_node_list_free (node_list
);
1182 /* Creates a new if region corresponding to ISL's cond. */
1185 translate_isl_ast_to_gimple::
1186 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1190 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1191 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1192 /* To fail code generation, we generate wrong code until we discard it. */
1194 cond_expr
= integer_zero_node
;
1196 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1200 /* Translates an isl_ast_node_if to Gimple. */
1203 translate_isl_ast_to_gimple::
1204 translate_isl_ast_node_if (loop_p context_loop
,
1205 __isl_keep isl_ast_node
*node
,
1206 edge next_e
, ivs_params
&ip
)
1208 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1209 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1210 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1211 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1212 merge_points
.safe_push (last_e
);
1214 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1215 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1216 isl_ast_node_free (then_node
);
1218 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1219 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1220 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1221 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1223 isl_ast_node_free (else_node
);
1227 /* Translates an ISL AST node NODE to GCC representation in the
1228 context of a SESE. */
1231 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1232 __isl_keep isl_ast_node
*node
,
1233 edge next_e
, ivs_params
&ip
)
1235 if (codegen_error_p ())
1238 switch (isl_ast_node_get_type (node
))
1240 case isl_ast_node_error
:
1243 case isl_ast_node_for
:
1244 return translate_isl_ast_node_for (context_loop
, node
,
1247 case isl_ast_node_if
:
1248 return translate_isl_ast_node_if (context_loop
, node
,
1251 case isl_ast_node_user
:
1252 return translate_isl_ast_node_user (node
, next_e
, ip
);
1254 case isl_ast_node_block
:
1255 return translate_isl_ast_node_block (context_loop
, node
,
1263 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1264 at the exit of loop which takes one argument that is the last value of the
1265 variable being used out of the loop. */
1268 bb_contains_loop_close_phi_nodes (basic_block bb
)
1270 return single_pred_p (bb
)
1271 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1274 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1275 header containing phi nodes which has one init-edge and one back-edge. */
1278 bb_contains_loop_phi_nodes (basic_block bb
)
1280 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1282 if (bb
->preds
->length () == 1)
1285 unsigned depth
= loop_depth (bb
->loop_father
);
1287 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1289 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1290 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1293 /* When one of the edges correspond to the same loop father and other
1295 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1296 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1299 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1300 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1306 /* Check if USE is defined in a basic block from where the definition of USE can
1307 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1310 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1312 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1315 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1316 if (bb_contains_loop_close_phi_nodes (bb
))
1319 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1320 basic_block def_bb
= gimple_bb (def
);
1322 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1325 /* Return the number of phi nodes in BB. */
1328 number_of_phi_nodes (basic_block bb
)
1331 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1337 /* Returns true if BB uses name in one of its PHIs. */
1340 phi_uses_name (basic_block bb
, tree name
)
1342 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1345 gphi
*phi
= psi
.phi ();
1346 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1348 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1349 if (use_arg
== name
)
1356 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1357 definition should flow into use, and the use should respect the loop-closed
1361 translate_isl_ast_to_gimple::
1362 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1363 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1365 /* The def of the rename must either dominate the uses or come from a
1366 back-edge. Also the def must respect the loop closed ssa form. */
1367 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1371 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1372 print_generic_expr (dump_file
, rename
, 0);
1373 fprintf (dump_file
, "\n");
1378 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1381 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1383 /* The loop-header dominates the loop-body. */
1384 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1387 /* RENAME would be used in loop-phi. */
1388 gcc_assert (number_of_phi_nodes (use_bb
));
1390 /* For definitions coming from back edges, we should check that
1391 old_name is used in a loop PHI node.
1392 FIXME: Verify if this is true. */
1393 if (phi_uses_name (old_bb
, old_name
))
1399 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1400 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1401 within a loop PHI instruction. */
1404 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1407 bool loop_phi
) const
1409 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1410 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1412 if (!renames
|| renames
->is_empty ())
1415 if (1 == renames
->length ())
1417 tree rename
= (*renames
)[0];
1418 if (TREE_CODE (rename
) == SSA_NAME
)
1420 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1421 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1426 if (is_constant (rename
))
1432 /* More than one renames corresponding to the old_name. Find the rename for
1433 which the definition flows into usage at new_bb. */
1435 tree t1
= NULL_TREE
, t2
;
1436 basic_block t1_bb
= NULL
;
1437 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1439 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1441 /* Defined in the same basic block as used. */
1442 if (t2_bb
== new_bb
)
1445 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1446 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1449 /* Compute the nearest dominator. */
1450 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1460 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1461 When OLD_NAME and EXPR are the same we assert. */
1464 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1468 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1469 print_generic_expr (dump_file
, old_name
, 0);
1470 fprintf (dump_file
, ", new_name = ");
1471 print_generic_expr (dump_file
, expr
, 0);
1472 fprintf (dump_file
, "\n");
1475 if (old_name
== expr
)
1478 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1481 renames
->safe_push (expr
);
1487 region
->rename_map
->put (old_name
, r
);
1491 /* Return an iterator to the instructions comes last in the execution order.
1492 Either GSI1 and GSI2 should belong to the same basic block or one of their
1493 respective basic blocks should dominate the other. */
1495 gimple_stmt_iterator
1496 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1498 basic_block bb1
= gsi_bb (gsi1
);
1499 basic_block bb2
= gsi_bb (gsi2
);
1501 /* Find the iterator which is the latest. */
1504 /* For empty basic blocks gsis point to the end of the sequence. Since
1505 there is no operator== defined for gimple_stmt_iterator and for gsis
1506 not pointing to a valid statement gsi_next would assert. */
1507 gimple_stmt_iterator gsi
= gsi1
;
1509 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1512 } while (!gsi_end_p (gsi
));
1517 /* Find the basic block closest to the basic block which defines stmt. */
1518 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1521 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1525 /* Insert each statement from SEQ at its earliest insertion p. */
1528 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1530 update_modified_stmts (seq
);
1531 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1532 basic_block begin_bb
= get_entry_bb (codegen_region
);
1534 /* Inserting the gimple statements in a vector because gimple_seq behave
1535 in strage ways when inserting the stmts from it into different basic
1536 blocks one at a time. */
1537 auto_vec
<gimple
*, 3> stmts
;
1538 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1540 stmts
.safe_push (gsi_stmt (gsi
));
1544 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1546 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1547 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1549 use_operand_p use_p
;
1550 ssa_op_iter op_iter
;
1551 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1553 /* Iterator to the current def of use_p. For function parameters or
1554 anything where def is not found, insert at the beginning of the
1555 generated region. */
1556 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1558 tree op
= USE_FROM_PTR (use_p
);
1559 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1560 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1561 gsi_stmt
= gsi_for_stmt (stmt
);
1563 /* For region parameters, insert at the beginning of the generated
1565 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1566 gsi_stmt
= gsi_def_stmt
;
1568 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1571 if (!gsi_stmt (gsi_def_stmt
))
1573 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1574 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1576 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1578 gimple_stmt_iterator bsi
1579 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1580 /* Insert right after the PHI statements. */
1581 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1584 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1588 fprintf (dump_file
, "[codegen] inserting statement: ");
1589 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1590 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1595 /* Collect all the operands of NEW_EXPR by recursively visiting each
1599 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1603 /* Rename all uses in new_expr. */
1604 if (TREE_CODE (new_expr
) == SSA_NAME
)
1606 vec_ssa
->safe_push (new_expr
);
1610 /* Iterate over SSA_NAMES in NEW_EXPR. */
1611 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1613 tree op
= TREE_OPERAND (new_expr
, i
);
1614 collect_all_ssa_names (op
, vec_ssa
);
1618 /* This is abridged version of the function copied from:
1619 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1622 substitute_ssa_name (tree exp
, tree f
, tree r
)
1624 enum tree_code code
= TREE_CODE (exp
);
1625 tree op0
, op1
, op2
, op3
;
1628 /* We handle TREE_LIST and COMPONENT_REF separately. */
1629 if (code
== TREE_LIST
)
1631 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1632 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1633 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1636 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1638 else if (code
== COMPONENT_REF
)
1642 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1643 and it is the right field, replace it with R. */
1644 for (inner
= TREE_OPERAND (exp
, 0);
1645 REFERENCE_CLASS_P (inner
);
1646 inner
= TREE_OPERAND (inner
, 0))
1650 op1
= TREE_OPERAND (exp
, 1);
1652 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1655 /* If this expression hasn't been completed let, leave it alone. */
1656 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1659 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1660 if (op0
== TREE_OPERAND (exp
, 0))
1664 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1667 switch (TREE_CODE_CLASS (code
))
1672 case tcc_declaration
:
1678 case tcc_expression
:
1682 /* Fall through... */
1684 case tcc_exceptional
:
1687 case tcc_comparison
:
1689 switch (TREE_CODE_LENGTH (code
))
1697 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1698 if (op0
== TREE_OPERAND (exp
, 0))
1701 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1705 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1706 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1708 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1711 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1715 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1716 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1717 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1719 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1720 && op2
== TREE_OPERAND (exp
, 2))
1723 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1727 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1728 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1729 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1730 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1732 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1733 && op2
== TREE_OPERAND (exp
, 2)
1734 && op3
== TREE_OPERAND (exp
, 3))
1738 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1751 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1753 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1754 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1759 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1762 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1765 auto_vec
<tree
, 2> ssa_names
;
1766 collect_all_ssa_names (new_expr
, &ssa_names
);
1769 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1770 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1771 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1776 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1777 scalar evolution around LOOP. */
1780 translate_isl_ast_to_gimple::
1781 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1782 basic_block new_bb
, basic_block old_bb
,
1785 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1787 /* At this point we should know the exact scev for each
1788 scalar SSA_NAME used in the scop: all the other scalar
1789 SSA_NAMEs should have been translated out of SSA using
1790 arrays with one element. */
1792 if (chrec_contains_undetermined (scev
))
1794 codegen_error
= true;
1795 return build_zero_cst (TREE_TYPE (old_name
));
1798 new_expr
= chrec_apply_map (scev
, iv_map
);
1800 /* The apply should produce an expression tree containing
1801 the uses of the new induction variables. We should be
1802 able to use new_expr instead of the old_name in the newly
1803 generated loop nest. */
1804 if (chrec_contains_undetermined (new_expr
)
1805 || tree_contains_chrecs (new_expr
, NULL
))
1807 codegen_error
= true;
1808 return build_zero_cst (TREE_TYPE (old_name
));
1811 /* We should check all the operands and all of them should dominate the use at
1813 if (TREE_CODE (new_expr
) == SSA_NAME
)
1815 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1816 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1818 codegen_error
= true;
1819 return build_zero_cst (TREE_TYPE (old_name
));
1823 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1825 /* We check all the operands and all of them should dominate the use at
1827 auto_vec
<tree
, 2> new_ssa_names
;
1828 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1831 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1833 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1835 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1836 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1838 codegen_error
= true;
1839 return build_zero_cst (TREE_TYPE (old_name
));
1844 /* Replace the old_name with the new_expr. */
1845 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1849 /* Renames the scalar uses of the statement COPY, using the
1850 substitution map RENAME_MAP, inserting the gimplification code at
1851 GSI_TGT, for the translation REGION, with the original copied
1852 statement in LOOP, and using the induction variable renaming map
1853 IV_MAP. Returns true when something has been renamed. codegen_error
1854 is set when the code generation cannot continue. */
1857 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1858 gimple_stmt_iterator
*gsi_tgt
,
1860 loop_p loop
, vec
<tree
> iv_map
)
1862 bool changed
= false;
1864 if (is_gimple_debug (copy
))
1866 if (gimple_debug_bind_p (copy
))
1867 gimple_debug_bind_reset_value (copy
);
1868 else if (gimple_debug_source_bind_p (copy
))
1878 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1879 print_gimple_stmt (dump_file
, copy
, 0, 0);
1882 use_operand_p use_p
;
1883 ssa_op_iter op_iter
;
1884 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1886 tree old_name
= USE_FROM_PTR (use_p
);
1890 fprintf (dump_file
, "[codegen] renaming old_name = ");
1891 print_generic_expr (dump_file
, old_name
, 0);
1892 fprintf (dump_file
, "\n");
1895 if (TREE_CODE (old_name
) != SSA_NAME
1896 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1900 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1905 tree type_old_name
= TREE_TYPE (old_name
);
1906 tree type_new_expr
= TREE_TYPE (new_expr
);
1910 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1911 print_generic_expr (dump_file
, new_expr
, 0);
1912 fprintf (dump_file
, "\n");
1915 if (type_old_name
!= type_new_expr
1916 || TREE_CODE (new_expr
) != SSA_NAME
)
1918 tree var
= create_tmp_var (type_old_name
, "var");
1920 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1921 new_expr
= fold_convert (type_old_name
, new_expr
);
1924 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1925 gsi_insert_earliest (stmts
);
1928 replace_exp (use_p
, new_expr
);
1933 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1935 if (!new_expr
|| codegen_error_p ())
1940 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1941 print_generic_expr (dump_file
, new_expr
, 0);
1942 fprintf (dump_file
, "\n");
1945 gsi_insert_earliest (stmts
);
1946 replace_exp (use_p
, new_expr
);
1948 if (TREE_CODE (new_expr
) == INTEGER_CST
1949 && is_gimple_assign (copy
))
1951 tree rhs
= gimple_assign_rhs1 (copy
);
1953 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1954 recompute_tree_invariant_for_addr_expr (rhs
);
1957 set_rename (old_name
, new_expr
);
1963 /* Returns a basic block that could correspond to where a constant was defined
1964 in the original code. In the original code OLD_BB had the definition, we
1965 need to find which basic block out of the copies of old_bb, in the new
1966 region, should a definition correspond to if it has to reach BB. */
1969 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1970 basic_block old_bb
) const
1972 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1974 if (!bbs
|| bbs
->is_empty ())
1977 if (1 == bbs
->length ())
1981 basic_block b1
= NULL
, b2
;
1982 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1987 /* BB and B2 are in two unrelated if-clauses. */
1988 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1991 /* Compute the nearest dominator. */
1992 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
2000 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
2001 when we want to rename an OP within a loop PHI instruction. */
2004 translate_isl_ast_to_gimple::
2005 get_new_name (basic_block new_bb
, tree op
,
2006 basic_block old_bb
, bool loop_phi
) const
2008 /* For constants the names are the same. */
2009 if (is_constant (op
))
2012 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
2015 /* Return a debug location for OP. */
2020 location_t loc
= UNKNOWN_LOCATION
;
2022 if (TREE_CODE (op
) == SSA_NAME
)
2023 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2027 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2028 the init edge (from outside the loop) and the second one is the back edge
2029 from the same loop. */
2031 std::pair
<edge
, edge
>
2032 get_edges (basic_block bb
)
2034 std::pair
<edge
, edge
> edges
;
2037 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2038 if (bb
->loop_father
!= e
->src
->loop_father
)
2045 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2046 must be found unless they can be POSTPONEd for later. */
2049 translate_isl_ast_to_gimple::
2050 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2051 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2054 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2056 basic_block new_bb
= gimple_bb (new_phi
);
2057 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2060 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2061 e
= ibp_new_bb
.first
;
2063 e
= ibp_new_bb
.second
;
2065 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2066 tree new_name
= get_new_name (new_bb
, old_name
,
2067 gimple_bb (old_phi
), true);
2070 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2074 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2075 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2076 /* If the phi arg was a function arg, or wasn't defined, just use the
2078 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2081 /* Postpone code gen for later for those back-edges we don't have the
2083 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2085 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2088 /* Either we should add the arg to phi or, we should postpone. */
2094 /* Copy loop phi nodes from BB to NEW_BB. */
2097 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2101 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2104 /* Loop phi nodes should have only two arguments. */
2105 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2107 /* First edge is the init edge and second is the back edge. */
2108 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2110 /* First edge is the init edge and second is the back edge. */
2111 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2113 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2116 gphi
*phi
= psi
.phi ();
2117 tree res
= gimple_phi_result (phi
);
2118 if (virtual_operand_p (res
))
2120 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2123 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2124 tree new_res
= create_new_def_for (res
, new_phi
,
2125 gimple_phi_result_ptr (new_phi
));
2126 set_rename (res
, new_res
);
2127 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2129 update_stmt (new_phi
);
2133 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2134 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2141 /* Return the init value of PHI, the value coming from outside the loop. */
2144 get_loop_init_value (gphi
*phi
)
2147 loop_p loop
= gimple_bb (phi
)->loop_father
;
2151 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2152 if (e
->src
->loop_father
!= loop
)
2153 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2158 /* Find the init value (the value which comes from outside the loop), of one of
2159 the operands of DEF which is defined by a loop phi. */
2162 find_init_value (gimple
*def
)
2164 if (gimple_code (def
) == GIMPLE_PHI
)
2165 return get_loop_init_value (as_a
<gphi
*> (def
));
2167 if (gimple_vuse (def
))
2171 use_operand_p use_p
;
2172 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2174 tree use
= USE_FROM_PTR (use_p
);
2175 if (TREE_CODE (use
) == SSA_NAME
)
2177 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2185 /* Return the init value, the value coming from outside the loop. */
2188 find_init_value_close_phi (gphi
*phi
)
2190 gcc_assert (gimple_phi_num_args (phi
) == 1);
2191 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2192 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2193 return find_init_value (def
);
2197 tree
translate_isl_ast_to_gimple::
2198 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2199 gimple
*old_close_phi
)
2201 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2202 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2203 basic_block bb
= gimple_bb (stmt
);
2204 if (!bb_in_sese_p (bb
, codegen_region
))
2205 return last_merge_name
;
2207 loop_p loop
= bb
->loop_father
;
2208 if (!loop_in_sese_p (loop
, codegen_region
))
2209 return last_merge_name
;
2211 edge e
= single_exit (loop
);
2213 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2214 return last_merge_name
;
2216 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2217 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2220 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2221 bb
= split_edge (e
);
2223 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2224 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2225 gimple_phi_result_ptr (close_phi
));
2226 set_rename (old_close_phi_name
, res
);
2227 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2228 last_merge_name
= res
;
2230 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2233 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2234 the close phi node PHI. */
2236 bool translate_isl_ast_to_gimple::
2237 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2240 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2241 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2242 if (SSA_NAME
== TREE_CODE (default_value
))
2244 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2245 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2247 default_value_bb
= gimple_bb (stmt
);
2250 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2252 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2253 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2254 tree last_merge_name
= new_close_phi_name
;
2255 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2259 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2261 basic_block new_merge_bb
= merge_e
->src
;
2262 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2265 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2268 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2269 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2270 gimple_phi_result_ptr (merge_phi
));
2271 set_rename (old_close_phi_name
, merge_res
);
2273 edge from_loop
= NULL
, from_default_value
= NULL
;
2276 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2277 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2280 from_default_value
= e
;
2282 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2283 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2284 is contained in another condition. */
2285 if (!from_default_value
|| !from_loop
)
2288 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2289 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2293 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2294 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2297 update_stmt (merge_phi
);
2298 last_merge_name
= merge_res
;
2304 /* Copy all the loop-close phi args from BB to NEW_BB. */
2307 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2311 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2314 gphi
*old_close_phi
= psi
.phi ();
2315 tree res
= gimple_phi_result (old_close_phi
);
2316 if (virtual_operand_p (res
))
2319 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2320 /* Loop close phi nodes should not be scev_analyzable_p. */
2323 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2324 tree new_res
= create_new_def_for (res
, new_close_phi
,
2325 gimple_phi_result_ptr (new_close_phi
));
2326 set_rename (res
, new_res
);
2328 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2329 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2331 /* Predecessor basic blocks of a loop close phi should have been code
2332 generated before. FIXME: This is fixable by merging PHIs from inner
2333 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2337 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2338 get_loc (old_name
));
2341 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2342 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2345 update_stmt (new_close_phi
);
2347 /* When there is no loop guard around this codegenerated loop, there is no
2348 need to collect the close-phi arg. */
2349 if (merge_points
.is_empty ())
2352 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2353 tree default_value
= find_init_value_close_phi (new_close_phi
);
2355 /* A close phi must come from a loop-phi having a default value. */
2361 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2365 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2366 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2371 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2379 /* Copy loop close phi nodes from BB to NEW_BB. */
2382 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2386 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2388 /* Loop close phi nodes should have only one argument. */
2389 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2391 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2395 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2396 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2397 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2398 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2401 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2402 In this case DOMINATING_PRED = NULL.
2404 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2406 Returns true on successful copy of the args, false otherwise. */
2409 translate_isl_ast_to_gimple::
2410 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2411 edge old_bb_dominating_edge
,
2412 edge old_bb_non_dominating_edge
,
2413 gphi
*phi
, gphi
*new_phi
,
2416 basic_block def_pred
[2] = { NULL
, NULL
};
2417 int not_found_bb_index
= -1;
2418 for (int i
= 0; i
< 2; i
++)
2420 /* If the corresponding def_bb could not be found the entry will be
2422 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2423 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2424 gimple_phi_arg_edge (phi
, i
)->src
);
2425 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2426 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2430 /* When non are available bail out. */
2431 if (not_found_bb_index
!= -1)
2433 not_found_bb_index
= i
;
2437 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2438 if (old_bb_dominating_edge
)
2440 if (not_found_bb_index
!= -1)
2443 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2444 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2445 vec
<basic_block
> *bbs
2446 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2448 /* Could not find a mapping. */
2452 basic_block new_pred
= NULL
;
2455 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2457 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2459 /* FIXME: If we have already found new_pred then we have to
2460 disambiguate, bail out for now. */
2463 new_pred
= new_pred1
;
2465 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2467 /* FIXME: If we have already found new_pred then we have to either
2468 it dominates both or we have to disambiguate, bail out. */
2471 new_pred
= new_pred2
;
2478 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2479 gcc_assert (new_non_dominating_edge
);
2480 /* FIXME: Validate each args just like in loop-phis. */
2481 /* By the process of elimination we first insert insert phi-edge for
2482 non-dominating pred which is computed above and then we insert the
2484 int inserted_edge
= 0;
2485 for (; inserted_edge
< 2; inserted_edge
++)
2487 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2488 if (new_non_dominating_edge
== new_bb_pred_edge
)
2490 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2491 new_non_dominating_edge
,
2492 get_loc (old_phi_args
[inserted_edge
]));
2496 if (inserted_edge
== 2)
2499 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2501 edge new_dominating_edge
= NULL
;
2502 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2504 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2505 if (e
!= new_non_dominating_edge
)
2507 new_dominating_edge
= e
;
2508 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2509 new_dominating_edge
,
2510 get_loc (old_phi_args
[inserted_edge
]));
2514 gcc_assert (new_dominating_edge
);
2518 /* Classic diamond structure: both edges are non-dominating. We need to
2519 find one unique edge then the other can be found be elimination. If
2520 any definition (def_pred) dominates both the preds of new_bb then we
2521 bail out. Entries of def_pred maybe NULL, in that case we must
2522 uniquely find pred with help of only one entry. */
2523 edge new_e
[2] = { NULL
, NULL
};
2524 for (int i
= 0; i
< 2; i
++)
2528 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2530 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2533 /* We do not know how to handle the case when def_pred
2534 dominates more than a predecessor. */
2540 gcc_assert (new_e
[0] || new_e
[1]);
2542 /* Find the other edge by process of elimination. */
2543 if (not_found_bb_index
!= -1)
2545 gcc_assert (!new_e
[not_found_bb_index
]);
2546 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2549 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2551 if (new_e
[found_bb_index
] == e
)
2553 new_e
[not_found_bb_index
] = e
;
2557 /* Add edges to phi args. */
2558 for (int i
= 0; i
< 2; i
++)
2559 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2560 get_loc (old_phi_args
[i
]));
2566 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2567 region. If postpone is true and it isn't possible to copy any arg of PHI,
2568 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2569 Returns false if the copying was unsuccessful. */
2572 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2577 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2578 gcc_assert (2 == gimple_phi_num_args (phi
));
2580 basic_block new_bb
= gimple_bb (new_phi
);
2581 loop_p loop
= gimple_bb (phi
)->loop_father
;
2583 basic_block old_bb
= gimple_bb (phi
);
2584 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2588 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2589 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2590 old_bb_non_dominating_edge
= e
;
2592 old_bb_dominating_edge
= e
;
2594 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2595 old_bb_non_dominating_edge
->src
));
2597 tree new_phi_args
[2];
2598 tree old_phi_args
[2];
2600 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2602 tree old_name
= gimple_phi_arg_def (phi
, i
);
2603 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2604 old_phi_args
[i
] = old_name
;
2607 new_phi_args
[i
] = new_name
;
2611 /* If the phi-arg was a parameter. */
2612 if (vec_find (region
->params
, old_name
) != -1)
2614 new_phi_args
[i
] = old_name
;
2618 "[codegen] parameter argument to phi, new_expr: ");
2619 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2620 fprintf (dump_file
, "\n");
2625 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2626 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2627 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2633 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2634 if (is_gimple_reg (old_name
)
2635 && scev_analyzable_p (old_name
, region
->region
))
2638 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2639 new_bb
, old_bb
, iv_map
);
2640 if (codegen_error_p ())
2643 gcc_assert (new_expr
);
2647 "[codegen] scev analyzeable, new_expr: ");
2648 print_generic_expr (dump_file
, new_expr
, 0);
2649 fprintf (dump_file
, "\n");
2651 gsi_insert_earliest (stmts
);
2652 new_phi_args
[i
] = new_name
;
2656 /* Postpone code gen for later for back-edges. */
2657 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2661 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2662 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2665 new_phi_args
[i
] = NULL_TREE
;
2669 /* Either we should add the arg to phi or, we should postpone. */
2673 /* If none of the args have been determined in the first stage then wait until
2675 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2678 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2679 old_bb_dominating_edge
,
2680 old_bb_non_dominating_edge
,
2681 phi
, new_phi
, new_bb
);
2684 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2685 containing phi nodes coming from two predecessors, and none of them are back
2689 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2694 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2697 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2700 /* Cond phi nodes should have exactly two arguments. */
2701 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2703 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2706 gphi
*phi
= psi
.phi ();
2707 tree res
= gimple_phi_result (phi
);
2708 if (virtual_operand_p (res
))
2710 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2711 /* Cond phi nodes should not be scev_analyzable_p. */
2714 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2715 tree new_res
= create_new_def_for (res
, new_phi
,
2716 gimple_phi_result_ptr (new_phi
));
2717 set_rename (res
, new_res
);
2719 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2722 update_stmt (new_phi
);
2728 /* Return true if STMT should be copied from region to the new code-generated
2729 region. LABELs, CONDITIONS, induction-variables and region parameters need
2733 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2735 /* Do not copy labels or conditions. */
2736 if (gimple_code (stmt
) == GIMPLE_LABEL
2737 || gimple_code (stmt
) == GIMPLE_COND
)
2741 /* Do not copy induction variables. */
2742 if (is_gimple_assign (stmt
)
2743 && (lhs
= gimple_assign_lhs (stmt
))
2744 && TREE_CODE (lhs
) == SSA_NAME
2745 && is_gimple_reg (lhs
)
2746 && scev_analyzable_p (lhs
, region
->region
))
2752 /* Create new names for all the definitions created by COPY and add replacement
2753 mappings for each new name. */
2756 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2758 def_operand_p def_p
;
2759 ssa_op_iter op_iter
;
2760 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2762 tree old_name
= DEF_FROM_PTR (def_p
);
2763 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2764 set_rename (old_name
, new_name
);
2768 /* Duplicates the statements of basic block BB into basic block NEW_BB
2769 and compute the new induction variables according to the IV_MAP.
2770 CODEGEN_ERROR is set when the code generation cannot continue. */
2773 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2777 /* Iterator poining to the place where new statement (s) will be inserted. */
2778 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2780 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2783 gimple
*stmt
= gsi_stmt (gsi
);
2784 if (!should_copy_to_new_region (stmt
, region
))
2787 /* Create a new copy of STMT and duplicate STMT's virtual
2789 gimple
*copy
= gimple_copy (stmt
);
2790 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2794 fprintf (dump_file
, "[codegen] inserting statement: ");
2795 print_gimple_stmt (dump_file
, copy
, 0, 0);
2798 maybe_duplicate_eh_stmt (copy
, stmt
);
2799 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2801 /* Crete new names for each def in the copied stmt. */
2802 set_rename_for_each_def (copy
);
2804 loop_p loop
= bb
->loop_father
;
2805 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2807 fold_stmt_inplace (&gsi_tgt
);
2808 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2811 if (codegen_error_p ())
2821 /* Given a basic block containing close-phi it returns the new basic block where
2822 to insert a copy of the close-phi nodes. All the uses in close phis should
2823 come from a single loop otherwise it returns NULL. */
2826 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2828 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2829 of close phi in the original code and then find the mapping of basic block
2830 defining that variable. If there are multiple close-phis and they are
2831 defined in different loops (in the original or in the new code) because of
2832 loop splitting, then we bail out. */
2833 loop_p new_loop
= NULL
;
2834 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2837 gphi
*phi
= psi
.phi ();
2838 tree name
= gimple_phi_arg_def (phi
, 0);
2839 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2841 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2842 if (!bbs
|| bbs
->length () != 1)
2843 /* This is one of the places which shows preserving original structure
2844 is not always possible, as we may need to insert close PHI for a loop
2845 where the latch does not have any mapping, or the mapping is
2850 new_loop
= (*bbs
)[0]->loop_father
;
2851 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2858 return single_exit (new_loop
);
2861 /* Copies BB and includes in the copied BB all the statements that can
2862 be reached following the use-def chains from the memory accesses,
2863 and returns the next edge following this new block. codegen_error is
2864 set when the code generation cannot continue. */
2867 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2871 int num_phis
= number_of_phi_nodes (bb
);
2873 if (region
->copied_bb_map
->get (bb
))
2875 /* FIXME: we should be able to handle phi nodes with args coming from
2876 outside the region. */
2879 codegen_error
= true;
2884 basic_block new_bb
= NULL
;
2885 if (bb_contains_loop_close_phi_nodes (bb
))
2888 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2891 edge e
= edge_for_new_close_phis (bb
);
2894 codegen_error
= true;
2898 basic_block phi_bb
= e
->dest
;
2900 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2901 phi_bb
= split_edge (e
);
2903 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2904 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2906 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2908 codegen_error
= true;
2915 new_bb
= split_edge (next_e
);
2919 new_bb
= split_edge (next_e
);
2920 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2922 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2924 /* At this point we are unable to codegenerate by still preserving the SSA
2925 structure because maybe the loop is completely unrolled and the PHIs
2926 and cross-bb scalar dependencies are untrackable w.r.t. the original
2927 code. See gfortran.dg/graphite/pr29832.f90. */
2928 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2930 codegen_error
= true;
2934 /* In case ISL did some loop peeling, like this:
2937 for (int c1 = 1; c1 <= 5; c1 += 1) {
2942 there should be no loop-phi nodes in S_8(0).
2944 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2945 values of all scalar variables: for the moment we instantiate only
2946 SCEV analyzable expressions on the iteration domain, and we need to
2947 extend that to reductions that cannot be analyzed by SCEV. */
2948 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2950 codegen_error
= true;
2955 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2957 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2959 codegen_error
= true;
2963 else if (num_phis
> 0)
2966 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2969 basic_block phi_bb
= single_pred (new_bb
);
2970 loop_p loop_father
= new_bb
->loop_father
;
2972 /* Move back until we find the block with two predecessors. */
2973 while (single_pred_p (phi_bb
))
2974 phi_bb
= single_pred_edge (phi_bb
)->src
;
2976 /* If a corresponding merge-point was not found, then abort codegen. */
2977 if (phi_bb
->loop_father
!= loop_father
2978 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2979 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2981 codegen_error
= true;
2988 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2989 bb
->index
, new_bb
->index
);
2991 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2993 copied_bbs
->safe_push (new_bb
);
2996 vec
<basic_block
> bbs
;
2998 bbs
.safe_push (new_bb
);
2999 region
->copied_bb_map
->put (bb
, bbs
);
3002 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
3004 codegen_error
= true;
3008 return single_succ_edge (new_bb
);
3011 /* Patch the missing arguments of the phi nodes. */
3014 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3018 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3020 gphi
*old_phi
= rename
->first
;
3021 gphi
*new_phi
= rename
->second
;
3022 basic_block old_bb
= gimple_bb (old_phi
);
3023 basic_block new_bb
= gimple_bb (new_phi
);
3025 /* First edge is the init edge and second is the back edge. */
3026 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3027 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3031 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3032 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3035 auto_vec
<tree
, 1> iv_map
;
3036 if (bb_contains_loop_phi_nodes (new_bb
))
3037 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3039 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3040 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3042 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3046 fprintf (dump_file
, "[codegen] to new-phi: ");
3047 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3054 /* Prints NODE to FILE. */
3057 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3058 __isl_keep isl_ast_node
*node
,
3059 __isl_keep isl_ctx
*ctx
) const
3061 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3062 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3063 prn
= isl_printer_print_ast_node (prn
, node
);
3064 prn
= isl_printer_print_str (prn
, "\n");
3065 isl_printer_free (prn
);
3068 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
3071 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3074 sese_info_p region
= scop
->scop_info
;
3075 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3076 gcc_assert (nb_parameters
== region
->params
.length ());
3078 for (i
= 0; i
< nb_parameters
; i
++)
3080 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3082 ip
[tmp_id
] = region
->params
[i
];
3087 /* Generates a build, which specifies the constraints on the parameters. */
3089 __isl_give isl_ast_build
*
3090 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3092 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3093 return isl_ast_build_from_context (context_isl
);
3096 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3099 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3103 int schedule_dims
= 0;
3105 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3107 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3108 if (pbb_schedule_dims
> schedule_dims
)
3109 schedule_dims
= pbb_schedule_dims
;
3112 return schedule_dims
;
3115 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3117 For schedules with different dimensionality, the isl AST generator can not
3118 define an order and will just randomly choose an order. The solution to this
3119 problem is to extend all schedules to the maximal number of schedule
3120 dimensions (using '0's for the remaining values). */
3122 __isl_give isl_map
*
3123 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3124 int nb_schedule_dims
)
3126 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3128 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3130 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3132 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3135 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3137 isl_val_free (zero
);
3141 /* Generates a schedule, which specifies an order used to
3142 visit elements in a domain. */
3144 __isl_give isl_union_map
*
3145 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3147 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3150 isl_union_map
*schedule_isl
=
3151 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3153 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3155 /* Dead code elimination: when the domain of a PBB is empty,
3156 don't generate code for the PBB. */
3157 if (isl_set_is_empty (pbb
->domain
))
3160 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3161 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3162 isl_set_copy (pbb
->domain
));
3163 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3165 = isl_union_map_union (schedule_isl
,
3166 isl_union_map_from_map (bb_schedule
));
3168 return schedule_isl
;
3171 /* This method is executed before the construction of a for node. */
3173 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3175 isl_union_map
*dependences
= (isl_union_map
*) user
;
3176 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3177 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3178 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3179 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3180 for_info
->is_parallelizable
=
3181 !carries_deps (schedule
, dependences
, dimension
);
3182 isl_union_map_free (schedule
);
3183 isl_space_free (schedule_space
);
3184 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3188 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3189 /* Set the separate option for all schedules. This helps reducing control
3192 __isl_give isl_schedule
*
3193 translate_isl_ast_to_gimple::set_options_for_schedule_tree
3194 (__isl_take isl_schedule
*schedule
)
3196 return isl_schedule_map_schedule_node_bottom_up
3197 (schedule
, set_separate_option
, NULL
);
3201 /* Set the separate option for all dimensions.
3202 This helps to reduce control overhead. */
3204 __isl_give isl_ast_build
*
3205 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3206 __isl_keep isl_union_map
*schedule
)
3208 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3209 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3211 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3212 isl_union_set
*range
=
3213 isl_union_set_from_set (isl_set_universe (range_space
));
3214 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3215 domain
= isl_union_set_universe (domain
);
3216 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3217 return isl_ast_build_set_options (control
, options
);
3220 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3222 __isl_give isl_ast_node
*
3223 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3225 isl_ast_node
*ast_isl
= NULL
;
3226 /* Generate loop upper bounds that consist of the current loop iterator, an
3227 operator (< or <=) and an expression not involving the iterator. If this
3228 option is not set, then the current loop iterator may appear several times
3229 in the upper bound. See the isl manual for more details. */
3230 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3232 add_parameters_to_ivs_params (scop
, ip
);
3233 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3234 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3235 context_isl
= set_options (context_isl
, schedule_isl
);
3236 if (flag_loop_parallelize_all
)
3238 isl_union_map
*dependence
= scop_get_dependences (scop
);
3240 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3244 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3247 scop
->schedule
= set_options_for_schedule_tree (scop
->schedule
);
3248 ast_isl
= isl_ast_build_node_from_schedule (context_isl
, scop
->schedule
);
3249 isl_union_map_free(schedule_isl
);
3252 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3254 ast_isl
= isl_ast_build_ast_from_schedule (context_isl
, schedule_isl
);
3255 isl_schedule_free (scop
->schedule
);
3258 isl_ast_build_free (context_isl
);
3262 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3263 the given SCOP. Return true if code generation succeeded.
3265 FIXME: This is not yet a full implementation of the code generator
3266 with ISL ASTs. Generation of GIMPLE code has to be completed. */
3269 graphite_regenerate_ast_isl (scop_p scop
)
3271 sese_info_p region
= scop
->scop_info
;
3272 translate_isl_ast_to_gimple
t (region
);
3274 ifsese if_region
= NULL
;
3275 isl_ast_node
*root_node
;
3278 timevar_push (TV_GRAPHITE_CODE_GEN
);
3279 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3283 fprintf (dump_file
, "ISL AST generated by ISL: \n");
3284 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3287 recompute_all_dominators ();
3290 if_region
= move_sese_in_condition (region
);
3291 region
->if_region
= if_region
;
3292 recompute_all_dominators ();
3294 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3296 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3297 basic_block bb
= split_edge (e
);
3299 /* Update the true_region exit edge. */
3300 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3302 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3303 if (t
.codegen_error_p ())
3306 fprintf (dump_file
, "[codegen] unsuccessful,"
3307 " reverting back to the original code.\n");
3308 set_ifsese_condition (if_region
, integer_zero_node
);
3312 t
.translate_pending_phi_nodes ();
3313 if (!t
.codegen_error_p ())
3315 sese_insert_phis_for_liveouts (region
,
3316 if_region
->region
->region
.exit
->src
,
3317 if_region
->false_region
->region
.exit
,
3318 if_region
->true_region
->region
.exit
);
3319 mark_virtual_operands_for_renaming (cfun
);
3320 update_ssa (TODO_update_ssa
);
3325 recompute_all_dominators ();
3331 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3332 " pending phis, reverting back to the original code.\n");
3333 set_ifsese_condition (if_region
, integer_zero_node
);
3337 free (if_region
->true_region
);
3338 free (if_region
->region
);
3341 ivs_params_clear (ip
);
3342 isl_ast_node_free (root_node
);
3343 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3345 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3348 int num_no_dependency
= 0;
3350 FOR_EACH_LOOP (loop
, 0)
3351 if (loop
->can_be_parallel
)
3352 num_no_dependency
++;
3354 fprintf (dump_file
, "%d loops carried no dependency.\n",
3358 return !t
.codegen_error_p ();
3361 #endif /* HAVE_isl */