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"
57 #include <isl/constraint.h>
59 #include <isl/union_set.h>
61 #include <isl/union_map.h>
62 #include <isl/ast_build.h>
64 /* Since ISL-0.13, the extern is in val_gmp.h. */
65 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
68 #include <isl/val_gmp.h>
69 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
77 /* We always try to use signed 128 bit types, but fall back to smaller types
78 in case a platform does not provide types of these sizes. In the future we
79 should use isl to derive the optimal type for each subexpression. */
81 static int max_mode_int_precision
=
82 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
83 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
84 128 : max_mode_int_precision
;
89 : is_parallelizable(false)
91 bool is_parallelizable
;
94 /* Converts a GMP constant VAL to a tree and returns it. */
97 gmp_cst_to_tree (tree type
, mpz_t val
)
99 tree t
= type
? type
: integer_type_node
;
104 wide_int wi
= wi::from_mpz (t
, tmp
, true);
107 return wide_int_to_tree (t
, wi
);
110 /* Verifies properties that GRAPHITE should maintain during translation. */
113 graphite_verify (void)
115 checking_verify_loop_structure ();
116 checking_verify_loop_closed_ssa (true);
119 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
120 to corresponding trees. */
122 typedef std::map
<isl_id
*, tree
> ivs_params
;
124 /* Free all memory allocated for ISL's identifiers. */
126 void ivs_params_clear (ivs_params
&ip
)
128 std::map
<isl_id
*, tree
>::iterator it
;
129 for (it
= ip
.begin ();
130 it
!= ip
.end (); it
++)
132 isl_id_free (it
->first
);
136 class translate_isl_ast_to_gimple
139 translate_isl_ast_to_gimple (sese_info_p r
)
140 : region (r
), codegen_error (false)
143 /* Translates an ISL AST node NODE to GCC representation in the
144 context of a SESE. */
145 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
146 edge next_e
, ivs_params
&ip
);
148 /* Translates an isl_ast_node_for to Gimple. */
149 edge
translate_isl_ast_node_for (loop_p context_loop
,
150 __isl_keep isl_ast_node
*node
,
151 edge next_e
, ivs_params
&ip
);
153 /* Create the loop for a isl_ast_node_for.
155 - NEXT_E is the edge where new generated code should be attached. */
156 edge
translate_isl_ast_for_loop (loop_p context_loop
,
157 __isl_keep isl_ast_node
*node_for
,
159 tree type
, tree lb
, tree ub
,
162 /* Translates an isl_ast_node_if to Gimple. */
163 edge
translate_isl_ast_node_if (loop_p context_loop
,
164 __isl_keep isl_ast_node
*node
,
165 edge next_e
, ivs_params
&ip
);
167 /* Translates an isl_ast_node_user to Gimple.
169 FIXME: We should remove iv_map.create (loop->num + 1), if it is
171 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
174 /* Translates an isl_ast_node_block to Gimple. */
175 edge
translate_isl_ast_node_block (loop_p context_loop
,
176 __isl_keep isl_ast_node
*node
,
177 edge next_e
, ivs_params
&ip
);
179 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
181 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
184 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
186 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
189 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
191 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
194 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
195 to a GCC expression tree of type TYPE. */
196 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
199 /* Converts an ISL AST expression E back to a GCC expression tree of
201 tree
gcc_expression_from_isl_expression (tree type
,
202 __isl_take isl_ast_expr
*,
205 /* Return the tree variable that corresponds to the given isl ast identifier
206 expression (an isl_ast_expr of type isl_ast_expr_id).
208 FIXME: We should replace blind conversation of id's type with derivation
209 of the optimal type when we get the corresponding isl support. Blindly
210 converting type sizes may be problematic when we switch to smaller
212 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
213 __isl_keep isl_ast_expr
*expr_id
,
216 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
218 tree
gcc_expression_from_isl_expr_int (tree type
,
219 __isl_take isl_ast_expr
*expr
);
221 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
223 tree
gcc_expression_from_isl_expr_op (tree type
,
224 __isl_take isl_ast_expr
*expr
,
227 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
228 induction variable for the new LOOP. New LOOP is attached to CFG
229 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
230 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
231 ISL's scattering name to the induction variable created for the
232 loop of STMT. The new induction variable is inserted in the NEWIVS
233 vector and is of type TYPE. */
234 struct loop
*graphite_create_new_loop (edge entry_edge
,
235 __isl_keep isl_ast_node
*node_for
,
236 loop_p outer
, tree type
,
237 tree lb
, tree ub
, ivs_params
&ip
);
239 /* All loops generated by create_empty_loop_on_edge have the form of
246 } while (lower bound < upper bound);
248 We create a new if region protecting the loop to be executed, if
249 the execution count is zero (lower bound > upper bound). */
250 edge
graphite_create_new_loop_guard (edge entry_edge
,
251 __isl_keep isl_ast_node
*node_for
,
253 tree
*lb
, tree
*ub
, ivs_params
&ip
);
255 /* Creates a new if region corresponding to ISL's cond. */
256 edge
graphite_create_new_guard (edge entry_edge
,
257 __isl_take isl_ast_expr
*if_cond
,
260 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
261 variables of the loops around GBB in SESE.
263 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
264 chrec, we could consider using a map<int, tree> that maps loop ids to the
265 corresponding tree expressions. */
266 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
267 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
270 /* Patch the missing arguments of the phi nodes. */
272 void translate_pending_phi_nodes (void);
274 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
276 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
278 /* Get the maximal number of schedule dimensions in the scop SCOP. */
280 int get_max_schedule_dimensions (scop_p scop
);
282 /* Generates a build, which specifies the constraints on the parameters. */
284 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
286 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
288 For schedules with different dimensionality, the isl AST generator can not
289 define an order and will just randomly choose an order. The solution to
290 this problem is to extend all schedules to the maximal number of schedule
291 dimensions (using '0's for the remaining values). */
293 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
294 int nb_schedule_dims
);
296 /* Generates a schedule, which specifies an order used to
297 visit elements in a domain. */
299 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
301 /* Set the separate option for all dimensions.
302 This helps to reduce control overhead. */
304 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
305 __isl_keep isl_union_map
*schedule
);
307 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
310 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
313 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
314 definition should flow into use, and the use should respect the loop-closed
317 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
318 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
320 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
321 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
322 within a loop PHI instruction. */
324 tree
get_rename (basic_block new_bb
, tree old_name
,
325 basic_block old_bb
, bool loop_phi
) const;
327 /* For ops which are scev_analyzeable, we can regenerate a new name from
328 its scalar evolution around LOOP. */
330 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
331 basic_block new_bb
, basic_block old_bb
,
334 /* Returns a basic block that could correspond to where a constant was defined
335 in the original code. In the original code OLD_BB had the definition, we
336 need to find which basic block out of the copies of old_bb, in the new
337 region, should a definition correspond to if it has to reach BB. */
339 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
341 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
342 true when we want to rename an OP within a loop PHI instruction. */
344 tree
get_new_name (basic_block new_bb
, tree op
,
345 basic_block old_bb
, bool loop_phi
) const;
347 /* Collect all the operands of NEW_EXPR by recursively visiting each
350 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
352 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
353 NEW_PHI must be found unless they can be POSTPONEd for later. */
355 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
356 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
359 /* Copy loop phi nodes from BB to NEW_BB. */
361 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
363 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
364 the close phi node PHI. */
366 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
369 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
370 gimple
*old_close_phi
);
372 /* Copy all the loop-close phi args from BB to NEW_BB. */
374 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
377 /* Copy loop close phi nodes from BB to NEW_BB. */
379 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
381 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
382 region. If postpone is true and it isn't possible to copy any arg of PHI,
383 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
384 Returns false if the copying was unsuccessful. */
386 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
389 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
390 containing phi nodes coming from two predecessors, and none of them are back
393 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
396 /* Duplicates the statements of basic block BB into basic block NEW_BB
397 and compute the new induction variables according to the IV_MAP.
398 CODEGEN_ERROR is set when the code generation cannot continue. */
400 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
403 /* Copies BB and includes in the copied BB all the statements that can
404 be reached following the use-def chains from the memory accesses,
405 and returns the next edge following this new block. codegen_error is
406 set when the code generation cannot continue. */
408 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
411 /* Given a basic block containing close-phi it returns the new basic block
412 where to insert a copy of the close-phi nodes. All the uses in close phis
413 should come from a single loop otherwise it returns NULL. */
414 edge
edge_for_new_close_phis (basic_block bb
);
416 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
417 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
418 the other pred of OLD_BB as well. If no such basic block exists then it is
419 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
422 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
423 versa. In this case DOMINATING_PRED = NULL.
425 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
427 Returns true on successful copy of the args, false otherwise. */
429 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
430 edge old_bb_dominating_edge
,
431 edge old_bb_non_dominating_edge
,
432 gphi
*phi
, gphi
*new_phi
,
435 /* Renames the scalar uses of the statement COPY, using the substitution map
436 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
437 translation REGION, with the original copied statement in LOOP, and using
438 the induction variable renaming map IV_MAP. Returns true when something
439 has been renamed. codegen_error is set when the code generation cannot
442 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
443 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
445 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
446 When OLD_NAME and EXPR are the same we assert. */
448 void set_rename (tree old_name
, tree expr
);
450 /* Create new names for all the definitions created by COPY and add
451 replacement mappings for each new name. */
453 void set_rename_for_each_def (gimple
*stmt
);
455 /* Insert each statement from SEQ at its earliest insertion p. */
457 void gsi_insert_earliest (gimple_seq seq
);
459 /* Rename all the operands of NEW_EXPR by recursively visiting each
462 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
464 bool codegen_error_p () const
465 { return codegen_error
; }
467 /* Prints NODE to FILE. */
469 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
470 __isl_keep isl_ctx
*ctx
) const;
472 /* Return true when OP is a constant tree. */
474 bool is_constant (tree op
) const
476 return TREE_CODE (op
) == INTEGER_CST
477 || TREE_CODE (op
) == REAL_CST
478 || TREE_CODE (op
) == COMPLEX_CST
479 || TREE_CODE (op
) == VECTOR_CST
;
483 /* The region to be translated. */
486 /* This flag is set when an error occurred during the translation of ISL AST
490 /* A vector of all the edges at if_condition merge points. */
491 auto_vec
<edge
, 2> merge_points
;
494 /* Return the tree variable that corresponds to the given isl ast identifier
495 expression (an isl_ast_expr of type isl_ast_expr_id).
497 FIXME: We should replace blind conversation of id's type with derivation
498 of the optimal type when we get the corresponding isl support. Blindly
499 converting type sizes may be problematic when we switch to smaller
503 translate_isl_ast_to_gimple::
504 gcc_expression_from_isl_ast_expr_id (tree type
,
505 __isl_take isl_ast_expr
*expr_id
,
508 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
509 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
510 std::map
<isl_id
*, tree
>::iterator res
;
511 res
= ip
.find (tmp_isl_id
);
512 isl_id_free (tmp_isl_id
);
513 gcc_assert (res
!= ip
.end () &&
514 "Could not map isl_id to tree expression");
515 isl_ast_expr_free (expr_id
);
516 tree t
= res
->second
;
517 return fold_convert (type
, t
);
520 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
524 translate_isl_ast_to_gimple::
525 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
527 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
528 isl_val
*val
= isl_ast_expr_get_val (expr
);
530 mpz_init (val_mpz_t
);
532 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
535 res
= gmp_cst_to_tree (type
, val_mpz_t
);
537 isl_ast_expr_free (expr
);
538 mpz_clear (val_mpz_t
);
542 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
546 translate_isl_ast_to_gimple::
547 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
549 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
550 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
551 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
552 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
554 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
555 isl_ast_expr_free (expr
);
563 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
566 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
569 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
572 /* As ISL operates on arbitrary precision numbers, we may end up with
573 division by 2^64 that is folded to 0. */
574 if (integer_zerop (tree_rhs_expr
))
576 codegen_error
= true;
579 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
581 case isl_ast_op_pdiv_q
:
582 /* As ISL operates on arbitrary precision numbers, we may end up with
583 division by 2^64 that is folded to 0. */
584 if (integer_zerop (tree_rhs_expr
))
586 codegen_error
= true;
589 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
591 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
592 case isl_ast_op_zdiv_r
:
594 case isl_ast_op_pdiv_r
:
595 /* As ISL operates on arbitrary precision numbers, we may end up with
596 division by 2^64 that is folded to 0. */
597 if (integer_zerop (tree_rhs_expr
))
599 codegen_error
= true;
602 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
604 case isl_ast_op_fdiv_q
:
605 /* As ISL operates on arbitrary precision numbers, we may end up with
606 division by 2^64 that is folded to 0. */
607 if (integer_zerop (tree_rhs_expr
))
609 codegen_error
= true;
612 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
615 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
616 tree_lhs_expr
, tree_rhs_expr
);
619 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
622 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
625 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
628 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
631 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
634 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
641 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
645 translate_isl_ast_to_gimple::
646 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
648 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
649 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
651 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
652 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
653 tree tree_second_expr
654 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
655 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
657 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
658 isl_ast_expr_free (expr
);
662 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
663 tree_second_expr
, tree_third_expr
);
666 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
670 translate_isl_ast_to_gimple::
671 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
673 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
674 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
675 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
676 isl_ast_expr_free (expr
);
677 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
680 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
681 to a GCC expression tree of type TYPE. */
684 translate_isl_ast_to_gimple::
685 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
687 enum tree_code op_code
;
688 switch (isl_ast_expr_get_op_type (expr
))
701 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
702 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
706 isl_ast_expr_free (expr
);
711 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
713 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
714 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
718 isl_ast_expr_free (expr
);
722 res
= fold_build2 (op_code
, type
, res
, t
);
724 isl_ast_expr_free (expr
);
728 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
732 translate_isl_ast_to_gimple::
733 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
738 isl_ast_expr_free (expr
);
742 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
743 switch (isl_ast_expr_get_op_type (expr
))
745 /* These isl ast expressions are not supported yet. */
746 case isl_ast_op_error
:
747 case isl_ast_op_call
:
748 case isl_ast_op_and_then
:
749 case isl_ast_op_or_else
:
750 case isl_ast_op_select
:
755 return nary_op_to_tree (type
, expr
, ip
);
761 case isl_ast_op_pdiv_q
:
762 case isl_ast_op_pdiv_r
:
763 case isl_ast_op_fdiv_q
:
764 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
765 case isl_ast_op_zdiv_r
:
774 return binary_op_to_tree (type
, expr
, ip
);
776 case isl_ast_op_minus
:
777 return unary_op_to_tree (type
, expr
, ip
);
779 case isl_ast_op_cond
:
780 return ternary_op_to_tree (type
, expr
, ip
);
789 /* Converts an ISL AST expression E back to a GCC expression tree of
793 translate_isl_ast_to_gimple::
794 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
799 isl_ast_expr_free (expr
);
803 switch (isl_ast_expr_get_type (expr
))
805 case isl_ast_expr_id
:
806 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
808 case isl_ast_expr_int
:
809 return gcc_expression_from_isl_expr_int (type
, expr
);
811 case isl_ast_expr_op
:
812 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
821 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
822 induction variable for the new LOOP. New LOOP is attached to CFG
823 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
824 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
825 ISL's scattering name to the induction variable created for the
826 loop of STMT. The new induction variable is inserted in the NEWIVS
827 vector and is of type TYPE. */
830 translate_isl_ast_to_gimple::
831 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
832 loop_p outer
, tree type
, tree lb
, tree ub
,
835 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
836 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
838 /* To fail code generation, we generate wrong code until we discard it. */
840 stride
= integer_zero_node
;
842 tree ivvar
= create_tmp_var (type
, "graphite_IV");
843 tree iv
, iv_after_increment
;
844 loop_p loop
= create_empty_loop_on_edge
845 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
846 outer
? outer
: entry_edge
->src
->loop_father
);
848 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
849 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
850 std::map
<isl_id
*, tree
>::iterator res
;
853 isl_id_free (res
->first
);
855 isl_ast_expr_free (for_iterator
);
859 /* Create the loop for a isl_ast_node_for.
861 - NEXT_E is the edge where new generated code should be attached. */
864 translate_isl_ast_to_gimple::
865 translate_isl_ast_for_loop (loop_p context_loop
,
866 __isl_keep isl_ast_node
*node_for
, edge next_e
,
867 tree type
, tree lb
, tree ub
,
870 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
871 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
873 edge last_e
= single_exit (loop
);
874 edge to_body
= single_succ_edge (loop
->header
);
875 basic_block after
= to_body
->dest
;
877 /* Translate the body of the loop. */
878 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
879 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
880 isl_ast_node_free (for_body
);
882 /* Early return if we failed to translate loop body. */
883 if (!next_e
|| codegen_error_p ())
886 if (next_e
->dest
!= after
)
887 redirect_edge_succ_nodup (next_e
, after
);
888 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
890 if (flag_loop_parallelize_all
)
892 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
894 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
895 loop
->can_be_parallel
= for_info
->is_parallelizable
;
903 /* We use this function to get the upper bound because of the form,
904 which is used by isl to represent loops:
906 for (iterator = init; cond; iterator += inc)
914 The loop condition is an arbitrary expression, which contains the
915 current loop iterator.
917 (e.g. iterator + 3 < B && C > iterator + A)
919 We have to know the upper bound of the iterator to generate a loop
920 in Gimple form. It can be obtained from the special representation
921 of the loop condition, which is generated by isl,
922 if the ast_build_atomic_upper_bound option is set. In this case,
923 isl generates a loop condition that consists of the current loop
924 iterator, + an operator (< or <=) and an expression not involving
925 the iterator, which is processed and returned by this function.
927 (e.g iterator <= upper-bound-expression-without-iterator) */
929 static __isl_give isl_ast_expr
*
930 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
932 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
933 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
934 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
936 switch (isl_ast_expr_get_op_type (for_cond
))
939 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
944 /* (iterator < ub) => (iterator <= ub - 1). */
946 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
947 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
948 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
955 isl_ast_expr_free (for_cond
);
959 /* All loops generated by create_empty_loop_on_edge have the form of
966 } while (lower bound < upper bound);
968 We create a new if region protecting the loop to be executed, if
969 the execution count is zero (lower bound > upper bound). */
972 translate_isl_ast_to_gimple::
973 graphite_create_new_loop_guard (edge entry_edge
,
974 __isl_keep isl_ast_node
*node_for
, tree
*type
,
975 tree
*lb
, tree
*ub
, ivs_params
&ip
)
977 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
982 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
983 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
984 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
985 /* To fail code generation, we generate wrong code until we discard it. */
987 *lb
= integer_zero_node
;
988 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
989 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
990 /* To fail code generation, we generate wrong code until we discard it. */
992 *ub
= integer_zero_node
;
994 /* When ub is simply a constant or a parameter, use lb <= ub. */
995 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
996 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
999 tree one
= (POINTER_TYPE_P (*type
)
1000 ? convert_to_ptrofftype (integer_one_node
)
1001 : fold_convert (*type
, integer_one_node
));
1002 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1003 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1004 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1005 is true, even if we do not want this. However lb < ub + 1 is false,
1007 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1008 : PLUS_EXPR
, *type
, *ub
, one
);
1010 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1013 if (integer_onep (cond_expr
))
1014 exit_edge
= entry_edge
;
1016 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1021 /* Translates an isl_ast_node_for to Gimple. */
1024 translate_isl_ast_to_gimple::
1025 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1026 edge next_e
, ivs_params
&ip
)
1028 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1030 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1033 if (last_e
== next_e
)
1035 /* There was no guard generated. */
1036 last_e
= single_succ_edge (split_edge (last_e
));
1038 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1043 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1044 merge_points
.safe_push (last_e
);
1046 last_e
= single_succ_edge (split_edge (last_e
));
1047 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1052 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1053 variables of the loops around GBB in SESE.
1055 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1056 chrec, we could consider using a map<int, tree> that maps loop ids to the
1057 corresponding tree expressions. */
1060 translate_isl_ast_to_gimple::
1061 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1062 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1065 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1066 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1068 isl_ast_expr
*arg_expr
;
1069 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1071 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1073 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1074 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1075 /* To fail code generation, we generate wrong code until we discard it. */
1077 t
= integer_zero_node
;
1079 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1080 iv_map
[old_loop
->num
] = t
;
1084 /* Translates an isl_ast_node_user to Gimple.
1086 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1089 translate_isl_ast_to_gimple::
1090 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1091 edge next_e
, ivs_params
&ip
)
1093 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1095 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1096 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1097 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1099 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1100 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1103 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1105 isl_ast_expr_free (name_expr
);
1106 isl_id_free (name_id
);
1108 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1109 "The entry block should not even appear within a scop");
1111 const int nb_loops
= number_of_loops (cfun
);
1113 iv_map
.create (nb_loops
);
1114 iv_map
.safe_grow_cleared (nb_loops
);
1116 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1117 isl_ast_expr_free (user_expr
);
1119 basic_block old_bb
= GBB_BB (gbb
);
1123 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
1124 old_bb
->index
, next_e
->src
->index
, next_e
->dest
->index
);
1125 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1129 next_e
= copy_bb_and_scalar_dependences (old_bb
, next_e
, iv_map
);
1133 if (codegen_error_p ())
1138 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1139 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1145 /* Translates an isl_ast_node_block to Gimple. */
1148 translate_isl_ast_to_gimple::
1149 translate_isl_ast_node_block (loop_p context_loop
,
1150 __isl_keep isl_ast_node
*node
,
1151 edge next_e
, ivs_params
&ip
)
1153 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1154 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1156 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1158 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1159 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1160 isl_ast_node_free (tmp_node
);
1162 isl_ast_node_list_free (node_list
);
1166 /* Creates a new if region corresponding to ISL's cond. */
1169 translate_isl_ast_to_gimple::
1170 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1174 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1175 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1176 /* To fail code generation, we generate wrong code until we discard it. */
1178 cond_expr
= integer_zero_node
;
1180 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1184 /* Translates an isl_ast_node_if to Gimple. */
1187 translate_isl_ast_to_gimple::
1188 translate_isl_ast_node_if (loop_p context_loop
,
1189 __isl_keep isl_ast_node
*node
,
1190 edge next_e
, ivs_params
&ip
)
1192 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1193 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1194 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1195 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1196 merge_points
.safe_push (last_e
);
1198 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1199 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1200 isl_ast_node_free (then_node
);
1202 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1203 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1204 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1205 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1207 isl_ast_node_free (else_node
);
1211 /* Translates an ISL AST node NODE to GCC representation in the
1212 context of a SESE. */
1215 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1216 __isl_keep isl_ast_node
*node
,
1217 edge next_e
, ivs_params
&ip
)
1219 if (codegen_error_p ())
1222 switch (isl_ast_node_get_type (node
))
1224 case isl_ast_node_error
:
1227 case isl_ast_node_for
:
1228 return translate_isl_ast_node_for (context_loop
, node
,
1231 case isl_ast_node_if
:
1232 return translate_isl_ast_node_if (context_loop
, node
,
1235 case isl_ast_node_user
:
1236 return translate_isl_ast_node_user (node
, next_e
, ip
);
1238 case isl_ast_node_block
:
1239 return translate_isl_ast_node_block (context_loop
, node
,
1247 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1248 at the exit of loop which takes one argument that is the last value of the
1249 variable being used out of the loop. */
1252 bb_contains_loop_close_phi_nodes (basic_block bb
)
1254 return single_pred_p (bb
)
1255 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1258 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1259 header containing phi nodes which has one init-edge and one back-edge. */
1262 bb_contains_loop_phi_nodes (basic_block bb
)
1264 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1266 if (bb
->preds
->length () == 1)
1269 unsigned depth
= loop_depth (bb
->loop_father
);
1271 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1273 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1274 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1277 /* When one of the edges correspond to the same loop father and other
1279 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1280 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1283 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1284 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1290 /* Check if USE is defined in a basic block from where the definition of USE can
1291 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1294 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1296 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1299 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1300 if (bb_contains_loop_close_phi_nodes (bb
))
1303 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1304 basic_block def_bb
= gimple_bb (def
);
1306 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1309 /* Return the number of phi nodes in BB. */
1312 number_of_phi_nodes (basic_block bb
)
1315 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1321 /* Returns true if BB uses name in one of its PHIs. */
1324 phi_uses_name (basic_block bb
, tree name
)
1326 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1329 gphi
*phi
= psi
.phi ();
1330 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1332 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1333 if (use_arg
== name
)
1340 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1341 definition should flow into use, and the use should respect the loop-closed
1345 translate_isl_ast_to_gimple::
1346 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1347 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1349 /* The def of the rename must either dominate the uses or come from a
1350 back-edge. Also the def must respect the loop closed ssa form. */
1351 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1355 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1356 print_generic_expr (dump_file
, rename
, 0);
1357 fprintf (dump_file
, "\n");
1362 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1365 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1367 /* The loop-header dominates the loop-body. */
1368 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1371 /* RENAME would be used in loop-phi. */
1372 gcc_assert (number_of_phi_nodes (use_bb
));
1374 /* For definitions coming from back edges, we should check that
1375 old_name is used in a loop PHI node.
1376 FIXME: Verify if this is true. */
1377 if (phi_uses_name (old_bb
, old_name
))
1383 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1384 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1385 within a loop PHI instruction. */
1388 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1391 bool loop_phi
) const
1393 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1394 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1396 if (!renames
|| renames
->is_empty ())
1399 if (1 == renames
->length ())
1401 tree rename
= (*renames
)[0];
1402 if (TREE_CODE (rename
) == SSA_NAME
)
1404 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1405 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1410 if (is_constant (rename
))
1416 /* More than one renames corresponding to the old_name. Find the rename for
1417 which the definition flows into usage at new_bb. */
1419 tree t1
= NULL_TREE
, t2
;
1420 basic_block t1_bb
= NULL
;
1421 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1423 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1425 /* Defined in the same basic block as used. */
1426 if (t2_bb
== new_bb
)
1429 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1430 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1433 /* Compute the nearest dominator. */
1434 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1444 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1445 When OLD_NAME and EXPR are the same we assert. */
1448 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1452 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1453 print_generic_expr (dump_file
, old_name
, 0);
1454 fprintf (dump_file
, ", new_name = ");
1455 print_generic_expr (dump_file
, expr
, 0);
1456 fprintf (dump_file
, "\n");
1459 if (old_name
== expr
)
1462 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1465 renames
->safe_push (expr
);
1471 region
->rename_map
->put (old_name
, r
);
1475 /* Return an iterator to the instructions comes last in the execution order.
1476 Either GSI1 and GSI2 should belong to the same basic block or one of their
1477 respective basic blocks should dominate the other. */
1479 gimple_stmt_iterator
1480 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1482 basic_block bb1
= gsi_bb (gsi1
);
1483 basic_block bb2
= gsi_bb (gsi2
);
1485 /* Find the iterator which is the latest. */
1488 /* For empty basic blocks gsis point to the end of the sequence. Since
1489 there is no operator== defined for gimple_stmt_iterator and for gsis
1490 not pointing to a valid statement gsi_next would assert. */
1491 gimple_stmt_iterator gsi
= gsi1
;
1493 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1496 } while (!gsi_end_p (gsi
));
1501 /* Find the basic block closest to the basic block which defines stmt. */
1502 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1505 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1509 /* Insert each statement from SEQ at its earliest insertion p. */
1512 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1514 update_modified_stmts (seq
);
1515 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1516 basic_block begin_bb
= get_entry_bb (codegen_region
);
1518 /* Inserting the gimple statements in a vector because gimple_seq behave
1519 in strage ways when inserting the stmts from it into different basic
1520 blocks one at a time. */
1521 auto_vec
<gimple
*, 3> stmts
;
1522 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1524 stmts
.safe_push (gsi_stmt (gsi
));
1528 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1530 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1531 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1533 use_operand_p use_p
;
1534 ssa_op_iter op_iter
;
1535 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1537 /* Iterator to the current def of use_p. For function parameters or
1538 anything where def is not found, insert at the beginning of the
1539 generated region. */
1540 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1542 tree op
= USE_FROM_PTR (use_p
);
1543 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1544 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1545 gsi_stmt
= gsi_for_stmt (stmt
);
1547 /* For region parameters, insert at the beginning of the generated
1549 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1550 gsi_stmt
= gsi_def_stmt
;
1552 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1555 if (!gsi_stmt (gsi_def_stmt
))
1557 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1558 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1560 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1562 gimple_stmt_iterator bsi
1563 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1564 /* Insert right after the PHI statements. */
1565 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1568 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1572 fprintf (dump_file
, "[codegen] inserting statement: ");
1573 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1574 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1579 /* Collect all the operands of NEW_EXPR by recursively visiting each
1583 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1587 /* Rename all uses in new_expr. */
1588 if (TREE_CODE (new_expr
) == SSA_NAME
)
1590 vec_ssa
->safe_push (new_expr
);
1594 /* Iterate over SSA_NAMES in NEW_EXPR. */
1595 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1597 tree op
= TREE_OPERAND (new_expr
, i
);
1598 collect_all_ssa_names (op
, vec_ssa
);
1602 /* This is abridged version of the function copied from:
1603 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1606 substitute_ssa_name (tree exp
, tree f
, tree r
)
1608 enum tree_code code
= TREE_CODE (exp
);
1609 tree op0
, op1
, op2
, op3
;
1612 /* We handle TREE_LIST and COMPONENT_REF separately. */
1613 if (code
== TREE_LIST
)
1615 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1616 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1617 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1620 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1622 else if (code
== COMPONENT_REF
)
1626 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1627 and it is the right field, replace it with R. */
1628 for (inner
= TREE_OPERAND (exp
, 0);
1629 REFERENCE_CLASS_P (inner
);
1630 inner
= TREE_OPERAND (inner
, 0))
1634 op1
= TREE_OPERAND (exp
, 1);
1636 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1639 /* If this expression hasn't been completed let, leave it alone. */
1640 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1643 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1644 if (op0
== TREE_OPERAND (exp
, 0))
1648 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1651 switch (TREE_CODE_CLASS (code
))
1656 case tcc_declaration
:
1662 case tcc_expression
:
1666 /* Fall through... */
1668 case tcc_exceptional
:
1671 case tcc_comparison
:
1673 switch (TREE_CODE_LENGTH (code
))
1681 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1682 if (op0
== TREE_OPERAND (exp
, 0))
1685 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1689 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1690 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1692 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1695 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1699 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1700 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1701 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1703 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1704 && op2
== TREE_OPERAND (exp
, 2))
1707 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1711 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1712 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1713 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1714 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1716 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1717 && op2
== TREE_OPERAND (exp
, 2)
1718 && op3
== TREE_OPERAND (exp
, 3))
1722 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1735 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1737 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1738 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1743 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1746 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1749 auto_vec
<tree
, 2> ssa_names
;
1750 collect_all_ssa_names (new_expr
, &ssa_names
);
1753 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1754 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1755 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1760 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1761 scalar evolution around LOOP. */
1764 translate_isl_ast_to_gimple::
1765 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1766 basic_block new_bb
, basic_block old_bb
,
1769 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1771 /* At this point we should know the exact scev for each
1772 scalar SSA_NAME used in the scop: all the other scalar
1773 SSA_NAMEs should have been translated out of SSA using
1774 arrays with one element. */
1776 if (chrec_contains_undetermined (scev
))
1778 codegen_error
= true;
1779 return build_zero_cst (TREE_TYPE (old_name
));
1782 new_expr
= chrec_apply_map (scev
, iv_map
);
1784 /* The apply should produce an expression tree containing
1785 the uses of the new induction variables. We should be
1786 able to use new_expr instead of the old_name in the newly
1787 generated loop nest. */
1788 if (chrec_contains_undetermined (new_expr
)
1789 || tree_contains_chrecs (new_expr
, NULL
))
1791 codegen_error
= true;
1792 return build_zero_cst (TREE_TYPE (old_name
));
1795 /* We should check all the operands and all of them should dominate the use at
1797 if (TREE_CODE (new_expr
) == SSA_NAME
)
1799 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1800 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1802 codegen_error
= true;
1803 return build_zero_cst (TREE_TYPE (old_name
));
1807 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1809 /* We check all the operands and all of them should dominate the use at
1811 auto_vec
<tree
, 2> new_ssa_names
;
1812 collect_all_ssa_names (new_expr
, &new_ssa_names
);
1815 FOR_EACH_VEC_ELT (new_ssa_names
, i
, new_ssa_name
)
1817 if (TREE_CODE (new_ssa_name
) == SSA_NAME
)
1819 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name
));
1820 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1822 codegen_error
= true;
1823 return build_zero_cst (TREE_TYPE (old_name
));
1828 /* Replace the old_name with the new_expr. */
1829 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1833 /* Renames the scalar uses of the statement COPY, using the
1834 substitution map RENAME_MAP, inserting the gimplification code at
1835 GSI_TGT, for the translation REGION, with the original copied
1836 statement in LOOP, and using the induction variable renaming map
1837 IV_MAP. Returns true when something has been renamed. codegen_error
1838 is set when the code generation cannot continue. */
1841 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1842 gimple_stmt_iterator
*gsi_tgt
,
1844 loop_p loop
, vec
<tree
> iv_map
)
1846 bool changed
= false;
1848 if (is_gimple_debug (copy
))
1850 if (gimple_debug_bind_p (copy
))
1851 gimple_debug_bind_reset_value (copy
);
1852 else if (gimple_debug_source_bind_p (copy
))
1862 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1863 print_gimple_stmt (dump_file
, copy
, 0, 0);
1866 use_operand_p use_p
;
1867 ssa_op_iter op_iter
;
1868 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1870 tree old_name
= USE_FROM_PTR (use_p
);
1874 fprintf (dump_file
, "[codegen] renaming old_name = ");
1875 print_generic_expr (dump_file
, old_name
, 0);
1876 fprintf (dump_file
, "\n");
1879 if (TREE_CODE (old_name
) != SSA_NAME
1880 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1884 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1889 tree type_old_name
= TREE_TYPE (old_name
);
1890 tree type_new_expr
= TREE_TYPE (new_expr
);
1894 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1895 print_generic_expr (dump_file
, new_expr
, 0);
1896 fprintf (dump_file
, "\n");
1899 if (type_old_name
!= type_new_expr
1900 || TREE_CODE (new_expr
) != SSA_NAME
)
1902 tree var
= create_tmp_var (type_old_name
, "var");
1904 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1905 new_expr
= fold_convert (type_old_name
, new_expr
);
1908 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1909 gsi_insert_earliest (stmts
);
1912 replace_exp (use_p
, new_expr
);
1917 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1919 if (!new_expr
|| codegen_error_p ())
1924 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1925 print_generic_expr (dump_file
, new_expr
, 0);
1926 fprintf (dump_file
, "\n");
1929 gsi_insert_earliest (stmts
);
1930 replace_exp (use_p
, new_expr
);
1932 if (TREE_CODE (new_expr
) == INTEGER_CST
1933 && is_gimple_assign (copy
))
1935 tree rhs
= gimple_assign_rhs1 (copy
);
1937 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1938 recompute_tree_invariant_for_addr_expr (rhs
);
1941 set_rename (old_name
, new_expr
);
1947 /* Returns a basic block that could correspond to where a constant was defined
1948 in the original code. In the original code OLD_BB had the definition, we
1949 need to find which basic block out of the copies of old_bb, in the new
1950 region, should a definition correspond to if it has to reach BB. */
1953 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1954 basic_block old_bb
) const
1956 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1958 if (!bbs
|| bbs
->is_empty ())
1961 if (1 == bbs
->length ())
1965 basic_block b1
= NULL
, b2
;
1966 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1971 /* BB and B2 are in two unrelated if-clauses. */
1972 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1975 /* Compute the nearest dominator. */
1976 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1984 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1985 when we want to rename an OP within a loop PHI instruction. */
1988 translate_isl_ast_to_gimple::
1989 get_new_name (basic_block new_bb
, tree op
,
1990 basic_block old_bb
, bool loop_phi
) const
1992 /* For constants the names are the same. */
1993 if (is_constant (op
))
1996 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1999 /* Return a debug location for OP. */
2004 location_t loc
= UNKNOWN_LOCATION
;
2006 if (TREE_CODE (op
) == SSA_NAME
)
2007 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2011 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2012 the init edge (from outside the loop) and the second one is the back edge
2013 from the same loop. */
2015 std::pair
<edge
, edge
>
2016 get_edges (basic_block bb
)
2018 std::pair
<edge
, edge
> edges
;
2021 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2022 if (bb
->loop_father
!= e
->src
->loop_father
)
2029 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2030 must be found unless they can be POSTPONEd for later. */
2033 translate_isl_ast_to_gimple::
2034 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2035 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2038 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2040 basic_block new_bb
= gimple_bb (new_phi
);
2041 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2044 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2045 e
= ibp_new_bb
.first
;
2047 e
= ibp_new_bb
.second
;
2049 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2050 tree new_name
= get_new_name (new_bb
, old_name
,
2051 gimple_bb (old_phi
), true);
2054 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2058 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2059 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2060 /* If the phi arg was a function arg, or wasn't defined, just use the
2062 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2065 /* Postpone code gen for later for those back-edges we don't have the
2067 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2069 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2072 /* Either we should add the arg to phi or, we should postpone. */
2078 /* Copy loop phi nodes from BB to NEW_BB. */
2081 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2085 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2088 /* Loop phi nodes should have only two arguments. */
2089 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2091 /* First edge is the init edge and second is the back edge. */
2092 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2094 /* First edge is the init edge and second is the back edge. */
2095 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2097 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2100 gphi
*phi
= psi
.phi ();
2101 tree res
= gimple_phi_result (phi
);
2102 if (virtual_operand_p (res
))
2104 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2107 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2108 tree new_res
= create_new_def_for (res
, new_phi
,
2109 gimple_phi_result_ptr (new_phi
));
2110 set_rename (res
, new_res
);
2111 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2113 update_stmt (new_phi
);
2117 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2118 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2125 /* Return the init value of PHI, the value coming from outside the loop. */
2128 get_loop_init_value (gphi
*phi
)
2131 loop_p loop
= gimple_bb (phi
)->loop_father
;
2135 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2136 if (e
->src
->loop_father
!= loop
)
2137 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2142 /* Find the init value (the value which comes from outside the loop), of one of
2143 the operands of DEF which is defined by a loop phi. */
2146 find_init_value (gimple
*def
)
2148 if (gimple_code (def
) == GIMPLE_PHI
)
2149 return get_loop_init_value (as_a
<gphi
*> (def
));
2151 if (gimple_vuse (def
))
2155 use_operand_p use_p
;
2156 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2158 tree use
= USE_FROM_PTR (use_p
);
2159 if (TREE_CODE (use
) == SSA_NAME
)
2161 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2169 /* Return the init value, the value coming from outside the loop. */
2172 find_init_value_close_phi (gphi
*phi
)
2174 gcc_assert (gimple_phi_num_args (phi
) == 1);
2175 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2176 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2177 return find_init_value (def
);
2181 tree
translate_isl_ast_to_gimple::
2182 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2183 gimple
*old_close_phi
)
2185 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2186 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2187 basic_block bb
= gimple_bb (stmt
);
2188 if (!bb_in_sese_p (bb
, codegen_region
))
2189 return last_merge_name
;
2191 loop_p loop
= bb
->loop_father
;
2192 if (!loop_in_sese_p (loop
, codegen_region
))
2193 return last_merge_name
;
2195 edge e
= single_exit (loop
);
2197 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2198 return last_merge_name
;
2200 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2201 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2204 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2205 bb
= split_edge (e
);
2207 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2208 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2209 gimple_phi_result_ptr (close_phi
));
2210 set_rename (old_close_phi_name
, res
);
2211 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2212 last_merge_name
= res
;
2214 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2217 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2218 the close phi node PHI. */
2220 bool translate_isl_ast_to_gimple::
2221 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2224 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2225 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2226 if (SSA_NAME
== TREE_CODE (default_value
))
2228 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2229 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2231 default_value_bb
= gimple_bb (stmt
);
2234 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2236 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2237 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2238 tree last_merge_name
= new_close_phi_name
;
2239 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2243 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2245 basic_block new_merge_bb
= merge_e
->src
;
2246 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2249 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2252 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2253 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2254 gimple_phi_result_ptr (merge_phi
));
2255 set_rename (old_close_phi_name
, merge_res
);
2257 edge from_loop
= NULL
, from_default_value
= NULL
;
2260 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2261 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2264 from_default_value
= e
;
2266 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2267 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2268 is contained in another condition. */
2269 if (!from_default_value
|| !from_loop
)
2272 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2273 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2277 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2278 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2281 update_stmt (merge_phi
);
2282 last_merge_name
= merge_res
;
2288 /* Copy all the loop-close phi args from BB to NEW_BB. */
2291 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2295 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2298 gphi
*old_close_phi
= psi
.phi ();
2299 tree res
= gimple_phi_result (old_close_phi
);
2300 if (virtual_operand_p (res
))
2303 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2304 /* Loop close phi nodes should not be scev_analyzable_p. */
2307 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2308 tree new_res
= create_new_def_for (res
, new_close_phi
,
2309 gimple_phi_result_ptr (new_close_phi
));
2310 set_rename (res
, new_res
);
2312 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2313 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2315 /* Predecessor basic blocks of a loop close phi should have been code
2316 generated before. FIXME: This is fixable by merging PHIs from inner
2317 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2321 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2322 get_loc (old_name
));
2325 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2326 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2329 update_stmt (new_close_phi
);
2331 /* When there is no loop guard around this codegenerated loop, there is no
2332 need to collect the close-phi arg. */
2333 if (merge_points
.is_empty ())
2336 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2337 tree default_value
= find_init_value_close_phi (new_close_phi
);
2339 /* A close phi must come from a loop-phi having a default value. */
2345 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2349 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2350 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2355 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2363 /* Copy loop close phi nodes from BB to NEW_BB. */
2366 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2370 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2372 /* Loop close phi nodes should have only one argument. */
2373 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2375 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2379 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2380 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2381 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2382 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2385 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2386 In this case DOMINATING_PRED = NULL.
2388 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2390 Returns true on successful copy of the args, false otherwise. */
2393 translate_isl_ast_to_gimple::
2394 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2395 edge old_bb_dominating_edge
,
2396 edge old_bb_non_dominating_edge
,
2397 gphi
*phi
, gphi
*new_phi
,
2400 basic_block def_pred
[2] = { NULL
, NULL
};
2401 int not_found_bb_index
= -1;
2402 for (int i
= 0; i
< 2; i
++)
2404 /* If the corresponding def_bb could not be found the entry will be
2406 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2407 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2408 gimple_phi_arg_edge (phi
, i
)->src
);
2409 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2410 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2414 /* When non are available bail out. */
2415 if (not_found_bb_index
!= -1)
2417 not_found_bb_index
= i
;
2421 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2422 if (old_bb_dominating_edge
)
2424 if (not_found_bb_index
!= -1)
2427 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2428 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2429 vec
<basic_block
> *bbs
2430 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2432 /* Could not find a mapping. */
2436 basic_block new_pred
= NULL
;
2439 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2441 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2443 /* FIXME: If we have already found new_pred then we have to
2444 disambiguate, bail out for now. */
2447 new_pred
= new_pred1
;
2449 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2451 /* FIXME: If we have already found new_pred then we have to either
2452 it dominates both or we have to disambiguate, bail out. */
2455 new_pred
= new_pred2
;
2462 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2463 gcc_assert (new_non_dominating_edge
);
2464 /* FIXME: Validate each args just like in loop-phis. */
2465 /* By the process of elimination we first insert insert phi-edge for
2466 non-dominating pred which is computed above and then we insert the
2468 int inserted_edge
= 0;
2469 for (; inserted_edge
< 2; inserted_edge
++)
2471 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2472 if (new_non_dominating_edge
== new_bb_pred_edge
)
2474 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2475 new_non_dominating_edge
,
2476 get_loc (old_phi_args
[inserted_edge
]));
2480 if (inserted_edge
== 2)
2483 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2485 edge new_dominating_edge
= NULL
;
2486 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2488 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2489 if (e
!= new_non_dominating_edge
)
2491 new_dominating_edge
= e
;
2492 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2493 new_dominating_edge
,
2494 get_loc (old_phi_args
[inserted_edge
]));
2498 gcc_assert (new_dominating_edge
);
2502 /* Classic diamond structure: both edges are non-dominating. We need to
2503 find one unique edge then the other can be found be elimination. If
2504 any definition (def_pred) dominates both the preds of new_bb then we
2505 bail out. Entries of def_pred maybe NULL, in that case we must
2506 uniquely find pred with help of only one entry. */
2507 edge new_e
[2] = { NULL
, NULL
};
2508 for (int i
= 0; i
< 2; i
++)
2512 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2514 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2517 /* We do not know how to handle the case when def_pred
2518 dominates more than a predecessor. */
2524 gcc_assert (new_e
[0] || new_e
[1]);
2526 /* Find the other edge by process of elimination. */
2527 if (not_found_bb_index
!= -1)
2529 gcc_assert (!new_e
[not_found_bb_index
]);
2530 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2533 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2535 if (new_e
[found_bb_index
] == e
)
2537 new_e
[not_found_bb_index
] = e
;
2541 /* Add edges to phi args. */
2542 for (int i
= 0; i
< 2; i
++)
2543 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2544 get_loc (old_phi_args
[i
]));
2550 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2551 region. If postpone is true and it isn't possible to copy any arg of PHI,
2552 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2553 Returns false if the copying was unsuccessful. */
2556 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2561 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2562 gcc_assert (2 == gimple_phi_num_args (phi
));
2564 basic_block new_bb
= gimple_bb (new_phi
);
2565 loop_p loop
= gimple_bb (phi
)->loop_father
;
2567 basic_block old_bb
= gimple_bb (phi
);
2568 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2572 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2573 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2574 old_bb_non_dominating_edge
= e
;
2576 old_bb_dominating_edge
= e
;
2578 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2579 old_bb_non_dominating_edge
->src
));
2581 tree new_phi_args
[2];
2582 tree old_phi_args
[2];
2584 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2586 tree old_name
= gimple_phi_arg_def (phi
, i
);
2587 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2588 old_phi_args
[i
] = old_name
;
2591 new_phi_args
[i
] = new_name
;
2595 /* If the phi-arg was a parameter. */
2596 if (vec_find (region
->params
, old_name
) != -1)
2598 new_phi_args
[i
] = old_name
;
2602 "[codegen] parameter argument to phi, new_expr: ");
2603 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2604 fprintf (dump_file
, "\n");
2609 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2610 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2611 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2617 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2618 if (is_gimple_reg (old_name
)
2619 && scev_analyzable_p (old_name
, region
->region
))
2622 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2623 new_bb
, old_bb
, iv_map
);
2624 if (codegen_error_p ())
2627 gcc_assert (new_expr
);
2631 "[codegen] scev analyzeable, new_expr: ");
2632 print_generic_expr (dump_file
, new_expr
, 0);
2633 fprintf (dump_file
, "\n");
2635 gsi_insert_earliest (stmts
);
2636 new_phi_args
[i
] = new_name
;
2640 /* Postpone code gen for later for back-edges. */
2641 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2645 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2646 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2649 new_phi_args
[i
] = NULL_TREE
;
2653 /* Either we should add the arg to phi or, we should postpone. */
2657 /* If none of the args have been determined in the first stage then wait until
2659 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2662 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2663 old_bb_dominating_edge
,
2664 old_bb_non_dominating_edge
,
2665 phi
, new_phi
, new_bb
);
2668 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2669 containing phi nodes coming from two predecessors, and none of them are back
2673 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2678 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2681 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2684 /* Cond phi nodes should have exactly two arguments. */
2685 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2687 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2690 gphi
*phi
= psi
.phi ();
2691 tree res
= gimple_phi_result (phi
);
2692 if (virtual_operand_p (res
))
2694 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2695 /* Cond phi nodes should not be scev_analyzable_p. */
2698 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2699 tree new_res
= create_new_def_for (res
, new_phi
,
2700 gimple_phi_result_ptr (new_phi
));
2701 set_rename (res
, new_res
);
2703 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2706 update_stmt (new_phi
);
2712 /* Return true if STMT should be copied from region to the new code-generated
2713 region. LABELs, CONDITIONS, induction-variables and region parameters need
2717 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2719 /* Do not copy labels or conditions. */
2720 if (gimple_code (stmt
) == GIMPLE_LABEL
2721 || gimple_code (stmt
) == GIMPLE_COND
)
2725 /* Do not copy induction variables. */
2726 if (is_gimple_assign (stmt
)
2727 && (lhs
= gimple_assign_lhs (stmt
))
2728 && TREE_CODE (lhs
) == SSA_NAME
2729 && is_gimple_reg (lhs
)
2730 && scev_analyzable_p (lhs
, region
->region
))
2736 /* Create new names for all the definitions created by COPY and add replacement
2737 mappings for each new name. */
2740 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2742 def_operand_p def_p
;
2743 ssa_op_iter op_iter
;
2744 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2746 tree old_name
= DEF_FROM_PTR (def_p
);
2747 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2748 set_rename (old_name
, new_name
);
2752 /* Duplicates the statements of basic block BB into basic block NEW_BB
2753 and compute the new induction variables according to the IV_MAP.
2754 CODEGEN_ERROR is set when the code generation cannot continue. */
2757 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2761 /* Iterator poining to the place where new statement (s) will be inserted. */
2762 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2764 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2767 gimple
*stmt
= gsi_stmt (gsi
);
2768 if (!should_copy_to_new_region (stmt
, region
))
2771 /* Create a new copy of STMT and duplicate STMT's virtual
2773 gimple
*copy
= gimple_copy (stmt
);
2774 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2778 fprintf (dump_file
, "[codegen] inserting statement: ");
2779 print_gimple_stmt (dump_file
, copy
, 0, 0);
2782 maybe_duplicate_eh_stmt (copy
, stmt
);
2783 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2785 /* Crete new names for each def in the copied stmt. */
2786 set_rename_for_each_def (copy
);
2788 loop_p loop
= bb
->loop_father
;
2789 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2791 fold_stmt_inplace (&gsi_tgt
);
2792 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2795 if (codegen_error_p ())
2805 /* Given a basic block containing close-phi it returns the new basic block where
2806 to insert a copy of the close-phi nodes. All the uses in close phis should
2807 come from a single loop otherwise it returns NULL. */
2810 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2812 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2813 of close phi in the original code and then find the mapping of basic block
2814 defining that variable. If there are multiple close-phis and they are
2815 defined in different loops (in the original or in the new code) because of
2816 loop splitting, then we bail out. */
2817 loop_p new_loop
= NULL
;
2818 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2821 gphi
*phi
= psi
.phi ();
2822 tree name
= gimple_phi_arg_def (phi
, 0);
2823 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2825 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2826 if (!bbs
|| bbs
->length () != 1)
2827 /* This is one of the places which shows preserving original structure
2828 is not always possible, as we may need to insert close PHI for a loop
2829 where the latch does not have any mapping, or the mapping is
2834 new_loop
= (*bbs
)[0]->loop_father
;
2835 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2842 return single_exit (new_loop
);
2845 /* Copies BB and includes in the copied BB all the statements that can
2846 be reached following the use-def chains from the memory accesses,
2847 and returns the next edge following this new block. codegen_error is
2848 set when the code generation cannot continue. */
2851 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2855 int num_phis
= number_of_phi_nodes (bb
);
2857 if (region
->copied_bb_map
->get (bb
))
2859 /* FIXME: we should be able to handle phi nodes with args coming from
2860 outside the region. */
2863 codegen_error
= true;
2868 basic_block new_bb
= NULL
;
2869 if (bb_contains_loop_close_phi_nodes (bb
))
2872 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2875 edge e
= edge_for_new_close_phis (bb
);
2878 codegen_error
= true;
2882 basic_block phi_bb
= e
->dest
;
2884 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2885 phi_bb
= split_edge (e
);
2887 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2888 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2890 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2892 codegen_error
= true;
2899 new_bb
= split_edge (next_e
);
2903 new_bb
= split_edge (next_e
);
2904 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2906 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2908 /* At this point we are unable to codegenerate by still preserving the SSA
2909 structure because maybe the loop is completely unrolled and the PHIs
2910 and cross-bb scalar dependencies are untrackable w.r.t. the original
2911 code. See gfortran.dg/graphite/pr29832.f90. */
2912 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2914 codegen_error
= true;
2918 /* In case ISL did some loop peeling, like this:
2921 for (int c1 = 1; c1 <= 5; c1 += 1) {
2926 there should be no loop-phi nodes in S_8(0).
2928 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2929 values of all scalar variables: for the moment we instantiate only
2930 SCEV analyzable expressions on the iteration domain, and we need to
2931 extend that to reductions that cannot be analyzed by SCEV. */
2932 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2934 codegen_error
= true;
2939 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2941 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2943 codegen_error
= true;
2947 else if (num_phis
> 0)
2950 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2953 basic_block phi_bb
= single_pred (new_bb
);
2954 loop_p loop_father
= new_bb
->loop_father
;
2956 /* Move back until we find the block with two predecessors. */
2957 while (single_pred_p (phi_bb
))
2958 phi_bb
= single_pred_edge (phi_bb
)->src
;
2960 /* If a corresponding merge-point was not found, then abort codegen. */
2961 if (phi_bb
->loop_father
!= loop_father
2962 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2963 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2965 codegen_error
= true;
2972 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2973 bb
->index
, new_bb
->index
);
2975 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2977 copied_bbs
->safe_push (new_bb
);
2980 vec
<basic_block
> bbs
;
2982 bbs
.safe_push (new_bb
);
2983 region
->copied_bb_map
->put (bb
, bbs
);
2986 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2988 codegen_error
= true;
2992 return single_succ_edge (new_bb
);
2995 /* Patch the missing arguments of the phi nodes. */
2998 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
3002 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
3004 gphi
*old_phi
= rename
->first
;
3005 gphi
*new_phi
= rename
->second
;
3006 basic_block old_bb
= gimple_bb (old_phi
);
3007 basic_block new_bb
= gimple_bb (new_phi
);
3009 /* First edge is the init edge and second is the back edge. */
3010 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3011 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3015 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3016 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3019 auto_vec
<tree
, 1> iv_map
;
3020 if (bb_contains_loop_phi_nodes (new_bb
))
3021 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3023 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3024 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3026 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3030 fprintf (dump_file
, "[codegen] to new-phi: ");
3031 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3038 /* Prints NODE to FILE. */
3041 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3042 __isl_keep isl_ast_node
*node
,
3043 __isl_keep isl_ctx
*ctx
) const
3045 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3046 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3047 prn
= isl_printer_print_ast_node (prn
, node
);
3048 prn
= isl_printer_print_str (prn
, "\n");
3049 isl_printer_free (prn
);
3052 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
3055 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3058 sese_info_p region
= scop
->scop_info
;
3059 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3060 gcc_assert (nb_parameters
== region
->params
.length ());
3062 for (i
= 0; i
< nb_parameters
; i
++)
3064 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3066 ip
[tmp_id
] = region
->params
[i
];
3071 /* Generates a build, which specifies the constraints on the parameters. */
3073 __isl_give isl_ast_build
*
3074 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3076 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3077 return isl_ast_build_from_context (context_isl
);
3080 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3083 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3087 int schedule_dims
= 0;
3089 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3091 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3092 if (pbb_schedule_dims
> schedule_dims
)
3093 schedule_dims
= pbb_schedule_dims
;
3096 return schedule_dims
;
3099 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3101 For schedules with different dimensionality, the isl AST generator can not
3102 define an order and will just randomly choose an order. The solution to this
3103 problem is to extend all schedules to the maximal number of schedule
3104 dimensions (using '0's for the remaining values). */
3106 __isl_give isl_map
*
3107 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3108 int nb_schedule_dims
)
3110 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3112 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3114 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3116 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3119 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3121 isl_val_free (zero
);
3125 /* Generates a schedule, which specifies an order used to
3126 visit elements in a domain. */
3128 __isl_give isl_union_map
*
3129 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3131 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3134 isl_union_map
*schedule_isl
=
3135 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3137 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3139 /* Dead code elimination: when the domain of a PBB is empty,
3140 don't generate code for the PBB. */
3141 if (isl_set_is_empty (pbb
->domain
))
3144 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3145 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3146 isl_set_copy (pbb
->domain
));
3147 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3149 = isl_union_map_union (schedule_isl
,
3150 isl_union_map_from_map (bb_schedule
));
3152 return schedule_isl
;
3155 /* This method is executed before the construction of a for node. */
3157 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3159 isl_union_map
*dependences
= (isl_union_map
*) user
;
3160 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3161 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3162 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3163 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3164 for_info
->is_parallelizable
=
3165 !carries_deps (schedule
, dependences
, dimension
);
3166 isl_union_map_free (schedule
);
3167 isl_space_free (schedule_space
);
3168 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3172 /* Set the separate option for all dimensions.
3173 This helps to reduce control overhead. */
3175 __isl_give isl_ast_build
*
3176 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3177 __isl_keep isl_union_map
*schedule
)
3179 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3180 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3182 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3183 isl_union_set
*range
=
3184 isl_union_set_from_set (isl_set_universe (range_space
));
3185 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3186 domain
= isl_union_set_universe (domain
);
3187 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3188 return isl_ast_build_set_options (control
, options
);
3191 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3193 __isl_give isl_ast_node
*
3194 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3196 /* Generate loop upper bounds that consist of the current loop iterator, an
3197 operator (< or <=) and an expression not involving the iterator. If this
3198 option is not set, then the current loop iterator may appear several times
3199 in the upper bound. See the isl manual for more details. */
3200 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3202 add_parameters_to_ivs_params (scop
, ip
);
3203 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3204 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3205 context_isl
= set_options (context_isl
, schedule_isl
);
3206 isl_union_map
*dependences
= NULL
;
3207 if (flag_loop_parallelize_all
)
3209 dependences
= scop_get_dependences (scop
);
3211 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3214 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3217 isl_union_map_free (dependences
);
3218 isl_ast_build_free (context_isl
);
3222 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3223 the given SCOP. Return true if code generation succeeded.
3225 FIXME: This is not yet a full implementation of the code generator
3226 with ISL ASTs. Generation of GIMPLE code has to be completed. */
3229 graphite_regenerate_ast_isl (scop_p scop
)
3231 sese_info_p region
= scop
->scop_info
;
3232 translate_isl_ast_to_gimple
t (region
);
3234 ifsese if_region
= NULL
;
3235 isl_ast_node
*root_node
;
3238 timevar_push (TV_GRAPHITE_CODE_GEN
);
3239 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3243 fprintf (dump_file
, "ISL AST generated by ISL: \n");
3244 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3247 recompute_all_dominators ();
3250 if_region
= move_sese_in_condition (region
);
3251 region
->if_region
= if_region
;
3252 recompute_all_dominators ();
3254 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3256 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3257 basic_block bb
= split_edge (e
);
3259 /* Update the true_region exit edge. */
3260 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3262 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3263 if (t
.codegen_error_p ())
3266 fprintf (dump_file
, "[codegen] unsuccessful,"
3267 " reverting back to the original code.\n");
3268 set_ifsese_condition (if_region
, integer_zero_node
);
3272 t
.translate_pending_phi_nodes ();
3273 if (!t
.codegen_error_p ())
3275 sese_insert_phis_for_liveouts (region
,
3276 if_region
->region
->region
.exit
->src
,
3277 if_region
->false_region
->region
.exit
,
3278 if_region
->true_region
->region
.exit
);
3279 mark_virtual_operands_for_renaming (cfun
);
3280 update_ssa (TODO_update_ssa
);
3285 recompute_all_dominators ();
3291 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3292 " pending phis, reverting back to the original code.\n");
3293 set_ifsese_condition (if_region
, integer_zero_node
);
3297 free (if_region
->true_region
);
3298 free (if_region
->region
);
3301 ivs_params_clear (ip
);
3302 isl_ast_node_free (root_node
);
3303 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3308 int num_no_dependency
= 0;
3310 FOR_EACH_LOOP (loop
, 0)
3311 if (loop
->can_be_parallel
)
3312 num_no_dependency
++;
3314 fprintf (dump_file
, "%d loops carried no dependency.\n",
3318 return !t
.codegen_error_p ();
3321 #endif /* HAVE_isl */