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 case isl_ast_op_pdiv_r
:
592 /* As ISL operates on arbitrary precision numbers, we may end up with
593 division by 2^64 that is folded to 0. */
594 if (integer_zerop (tree_rhs_expr
))
596 codegen_error
= true;
599 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
601 case isl_ast_op_fdiv_q
:
602 /* As ISL operates on arbitrary precision numbers, we may end up with
603 division by 2^64 that is folded to 0. */
604 if (integer_zerop (tree_rhs_expr
))
606 codegen_error
= true;
609 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
612 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
613 tree_lhs_expr
, tree_rhs_expr
);
616 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
619 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
622 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
625 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
628 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
631 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
638 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
642 translate_isl_ast_to_gimple::
643 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
645 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
646 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
648 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
649 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
650 tree tree_second_expr
651 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
652 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
654 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
655 isl_ast_expr_free (expr
);
659 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
660 tree_second_expr
, tree_third_expr
);
663 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
667 translate_isl_ast_to_gimple::
668 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
670 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
671 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
672 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
673 isl_ast_expr_free (expr
);
674 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
677 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
678 to a GCC expression tree of type TYPE. */
681 translate_isl_ast_to_gimple::
682 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
684 enum tree_code op_code
;
685 switch (isl_ast_expr_get_op_type (expr
))
698 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
699 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
703 isl_ast_expr_free (expr
);
708 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
710 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
711 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
715 isl_ast_expr_free (expr
);
719 res
= fold_build2 (op_code
, type
, res
, t
);
721 isl_ast_expr_free (expr
);
725 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
729 translate_isl_ast_to_gimple::
730 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
735 isl_ast_expr_free (expr
);
739 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
740 switch (isl_ast_expr_get_op_type (expr
))
742 /* These isl ast expressions are not supported yet. */
743 case isl_ast_op_error
:
744 case isl_ast_op_call
:
745 case isl_ast_op_and_then
:
746 case isl_ast_op_or_else
:
747 case isl_ast_op_select
:
752 return nary_op_to_tree (type
, expr
, ip
);
758 case isl_ast_op_pdiv_q
:
759 case isl_ast_op_pdiv_r
:
760 case isl_ast_op_fdiv_q
:
768 return binary_op_to_tree (type
, expr
, ip
);
770 case isl_ast_op_minus
:
771 return unary_op_to_tree (type
, expr
, ip
);
773 case isl_ast_op_cond
:
774 return ternary_op_to_tree (type
, expr
, ip
);
783 /* Converts an ISL AST expression E back to a GCC expression tree of
787 translate_isl_ast_to_gimple::
788 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
793 isl_ast_expr_free (expr
);
797 switch (isl_ast_expr_get_type (expr
))
799 case isl_ast_expr_id
:
800 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
802 case isl_ast_expr_int
:
803 return gcc_expression_from_isl_expr_int (type
, expr
);
805 case isl_ast_expr_op
:
806 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
815 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
816 induction variable for the new LOOP. New LOOP is attached to CFG
817 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
818 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
819 ISL's scattering name to the induction variable created for the
820 loop of STMT. The new induction variable is inserted in the NEWIVS
821 vector and is of type TYPE. */
824 translate_isl_ast_to_gimple::
825 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
826 loop_p outer
, tree type
, tree lb
, tree ub
,
829 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
830 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
832 /* To fail code generation, we generate wrong code until we discard it. */
834 stride
= integer_zero_node
;
836 tree ivvar
= create_tmp_var (type
, "graphite_IV");
837 tree iv
, iv_after_increment
;
838 loop_p loop
= create_empty_loop_on_edge
839 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
840 outer
? outer
: entry_edge
->src
->loop_father
);
842 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
843 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
844 std::map
<isl_id
*, tree
>::iterator res
;
847 isl_id_free (res
->first
);
849 isl_ast_expr_free (for_iterator
);
853 /* Create the loop for a isl_ast_node_for.
855 - NEXT_E is the edge where new generated code should be attached. */
858 translate_isl_ast_to_gimple::
859 translate_isl_ast_for_loop (loop_p context_loop
,
860 __isl_keep isl_ast_node
*node_for
, edge next_e
,
861 tree type
, tree lb
, tree ub
,
864 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
865 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
867 edge last_e
= single_exit (loop
);
868 edge to_body
= single_succ_edge (loop
->header
);
869 basic_block after
= to_body
->dest
;
871 /* Translate the body of the loop. */
872 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
873 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
874 isl_ast_node_free (for_body
);
876 /* Early return if we failed to translate loop body. */
877 if (!next_e
|| codegen_error_p ())
880 if (next_e
->dest
!= after
)
881 redirect_edge_succ_nodup (next_e
, after
);
882 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
884 if (flag_loop_parallelize_all
)
886 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
888 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
889 loop
->can_be_parallel
= for_info
->is_parallelizable
;
897 /* We use this function to get the upper bound because of the form,
898 which is used by isl to represent loops:
900 for (iterator = init; cond; iterator += inc)
908 The loop condition is an arbitrary expression, which contains the
909 current loop iterator.
911 (e.g. iterator + 3 < B && C > iterator + A)
913 We have to know the upper bound of the iterator to generate a loop
914 in Gimple form. It can be obtained from the special representation
915 of the loop condition, which is generated by isl,
916 if the ast_build_atomic_upper_bound option is set. In this case,
917 isl generates a loop condition that consists of the current loop
918 iterator, + an operator (< or <=) and an expression not involving
919 the iterator, which is processed and returned by this function.
921 (e.g iterator <= upper-bound-expression-without-iterator) */
923 static __isl_give isl_ast_expr
*
924 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
926 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
927 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
928 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
930 switch (isl_ast_expr_get_op_type (for_cond
))
933 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
938 /* (iterator < ub) => (iterator <= ub - 1). */
940 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
941 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
942 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
949 isl_ast_expr_free (for_cond
);
953 /* All loops generated by create_empty_loop_on_edge have the form of
960 } while (lower bound < upper bound);
962 We create a new if region protecting the loop to be executed, if
963 the execution count is zero (lower bound > upper bound). */
966 translate_isl_ast_to_gimple::
967 graphite_create_new_loop_guard (edge entry_edge
,
968 __isl_keep isl_ast_node
*node_for
, tree
*type
,
969 tree
*lb
, tree
*ub
, ivs_params
&ip
)
971 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
976 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
977 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
978 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
979 /* To fail code generation, we generate wrong code until we discard it. */
981 *lb
= integer_zero_node
;
982 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
983 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
984 /* To fail code generation, we generate wrong code until we discard it. */
986 *ub
= integer_zero_node
;
988 /* When ub is simply a constant or a parameter, use lb <= ub. */
989 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
990 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
993 tree one
= (POINTER_TYPE_P (*type
)
994 ? convert_to_ptrofftype (integer_one_node
)
995 : fold_convert (*type
, integer_one_node
));
996 /* Adding +1 and using LT_EXPR helps with loop latches that have a
997 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
998 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
999 is true, even if we do not want this. However lb < ub + 1 is false,
1001 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1002 : PLUS_EXPR
, *type
, *ub
, one
);
1004 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1007 if (integer_onep (cond_expr
))
1008 exit_edge
= entry_edge
;
1010 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1015 /* Translates an isl_ast_node_for to Gimple. */
1018 translate_isl_ast_to_gimple::
1019 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1020 edge next_e
, ivs_params
&ip
)
1022 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1024 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1027 if (last_e
== next_e
)
1029 /* There was no guard generated. */
1030 last_e
= single_succ_edge (split_edge (last_e
));
1032 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1037 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1038 merge_points
.safe_push (last_e
);
1040 last_e
= single_succ_edge (split_edge (last_e
));
1041 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1046 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1047 variables of the loops around GBB in SESE.
1049 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1050 chrec, we could consider using a map<int, tree> that maps loop ids to the
1051 corresponding tree expressions. */
1054 translate_isl_ast_to_gimple::
1055 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1056 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1059 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1060 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1062 isl_ast_expr
*arg_expr
;
1063 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1065 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1067 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1068 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1069 /* To fail code generation, we generate wrong code until we discard it. */
1071 t
= integer_zero_node
;
1073 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1074 iv_map
[old_loop
->num
] = t
;
1078 /* Translates an isl_ast_node_user to Gimple.
1080 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1083 translate_isl_ast_to_gimple::
1084 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1085 edge next_e
, ivs_params
&ip
)
1087 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1089 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1090 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1091 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1093 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1094 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1097 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1099 isl_ast_expr_free (name_expr
);
1100 isl_id_free (name_id
);
1102 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1103 "The entry block should not even appear within a scop");
1105 const int nb_loops
= number_of_loops (cfun
);
1107 iv_map
.create (nb_loops
);
1108 iv_map
.safe_grow_cleared (nb_loops
);
1110 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1111 isl_ast_expr_free (user_expr
);
1115 fprintf (dump_file
, "[codegen] copying from basic block\n");
1116 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1117 fprintf (dump_file
, "[codegen] to new basic block\n");
1118 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1121 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1126 if (codegen_error_p ())
1131 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1132 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1138 /* Translates an isl_ast_node_block to Gimple. */
1141 translate_isl_ast_to_gimple::
1142 translate_isl_ast_node_block (loop_p context_loop
,
1143 __isl_keep isl_ast_node
*node
,
1144 edge next_e
, ivs_params
&ip
)
1146 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1147 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1149 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1151 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1152 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1153 isl_ast_node_free (tmp_node
);
1155 isl_ast_node_list_free (node_list
);
1159 /* Creates a new if region corresponding to ISL's cond. */
1162 translate_isl_ast_to_gimple::
1163 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1167 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1168 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1169 /* To fail code generation, we generate wrong code until we discard it. */
1171 cond_expr
= integer_zero_node
;
1173 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1177 /* Translates an isl_ast_node_if to Gimple. */
1180 translate_isl_ast_to_gimple::
1181 translate_isl_ast_node_if (loop_p context_loop
,
1182 __isl_keep isl_ast_node
*node
,
1183 edge next_e
, ivs_params
&ip
)
1185 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1186 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1187 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1188 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1189 merge_points
.safe_push (last_e
);
1191 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1192 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1193 isl_ast_node_free (then_node
);
1195 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1196 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1197 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1198 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1200 isl_ast_node_free (else_node
);
1204 /* Translates an ISL AST node NODE to GCC representation in the
1205 context of a SESE. */
1208 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1209 __isl_keep isl_ast_node
*node
,
1210 edge next_e
, ivs_params
&ip
)
1212 if (codegen_error_p ())
1215 switch (isl_ast_node_get_type (node
))
1217 case isl_ast_node_error
:
1220 case isl_ast_node_for
:
1221 return translate_isl_ast_node_for (context_loop
, node
,
1224 case isl_ast_node_if
:
1225 return translate_isl_ast_node_if (context_loop
, node
,
1228 case isl_ast_node_user
:
1229 return translate_isl_ast_node_user (node
, next_e
, ip
);
1231 case isl_ast_node_block
:
1232 return translate_isl_ast_node_block (context_loop
, node
,
1240 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1241 at the exit of loop which takes one argument that is the last value of the
1242 variable being used out of the loop. */
1245 bb_contains_loop_close_phi_nodes (basic_block bb
)
1247 return single_pred_p (bb
)
1248 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1251 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1252 header containing phi nodes which has one init-edge and one back-edge. */
1255 bb_contains_loop_phi_nodes (basic_block bb
)
1257 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1259 if (bb
->preds
->length () == 1)
1262 unsigned depth
= loop_depth (bb
->loop_father
);
1264 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1266 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1267 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1270 /* When one of the edges correspond to the same loop father and other
1272 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1273 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1276 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1277 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1283 /* Check if USE is defined in a basic block from where the definition of USE can
1284 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1287 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1289 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1292 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1293 if (bb_contains_loop_close_phi_nodes (bb
))
1296 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1297 basic_block def_bb
= gimple_bb (def
);
1299 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1302 /* Return the number of phi nodes in BB. */
1305 number_of_phi_nodes (basic_block bb
)
1308 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1314 /* Returns true if BB uses name in one of its PHIs. */
1317 phi_uses_name (basic_block bb
, tree name
)
1319 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1322 gphi
*phi
= psi
.phi ();
1323 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1325 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1326 if (use_arg
== name
)
1333 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1334 definition should flow into use, and the use should respect the loop-closed
1338 translate_isl_ast_to_gimple::
1339 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1340 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1342 /* The def of the rename must either dominate the uses or come from a
1343 back-edge. Also the def must respect the loop closed ssa form. */
1344 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1348 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1349 print_generic_expr (dump_file
, rename
, 0);
1350 fprintf (dump_file
, "\n");
1355 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1358 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1360 /* The loop-header dominates the loop-body. */
1361 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1364 /* RENAME would be used in loop-phi. */
1365 gcc_assert (number_of_phi_nodes (use_bb
));
1367 /* For definitions coming from back edges, we should check that
1368 old_name is used in a loop PHI node.
1369 FIXME: Verify if this is true. */
1370 if (phi_uses_name (old_bb
, old_name
))
1376 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1377 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1378 within a loop PHI instruction. */
1381 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1384 bool loop_phi
) const
1386 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1387 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1389 if (!renames
|| renames
->is_empty ())
1392 if (1 == renames
->length ())
1394 tree rename
= (*renames
)[0];
1395 if (TREE_CODE (rename
) == SSA_NAME
)
1397 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1398 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1403 if (is_constant (rename
))
1409 /* More than one renames corresponding to the old_name. Find the rename for
1410 which the definition flows into usage at new_bb. */
1412 tree t1
= NULL_TREE
, t2
;
1413 basic_block t1_bb
= NULL
;
1414 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1416 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1418 /* Defined in the same basic block as used. */
1419 if (t2_bb
== new_bb
)
1422 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1423 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1426 /* Compute the nearest dominator. */
1427 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1437 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1438 When OLD_NAME and EXPR are the same we assert. */
1441 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1445 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1446 print_generic_expr (dump_file
, old_name
, 0);
1447 fprintf (dump_file
, ", new_name = ");
1448 print_generic_expr (dump_file
, expr
, 0);
1449 fprintf (dump_file
, "\n");
1452 if (old_name
== expr
)
1455 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1458 renames
->safe_push (expr
);
1464 region
->rename_map
->put (old_name
, r
);
1468 /* Return an iterator to the instructions comes last in the execution order.
1469 Either GSI1 and GSI2 should belong to the same basic block or one of their
1470 respective basic blocks should dominate the other. */
1472 gimple_stmt_iterator
1473 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1475 basic_block bb1
= gsi_bb (gsi1
);
1476 basic_block bb2
= gsi_bb (gsi2
);
1478 /* Find the iterator which is the latest. */
1481 /* For empty basic blocks gsis point to the end of the sequence. Since
1482 there is no operator== defined for gimple_stmt_iterator and for gsis
1483 not pointing to a valid statement gsi_next would assert. */
1484 gimple_stmt_iterator gsi
= gsi1
;
1486 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1489 } while (!gsi_end_p (gsi
));
1494 /* Find the basic block closest to the basic block which defines stmt. */
1495 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1498 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1502 /* Insert each statement from SEQ at its earliest insertion p. */
1505 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1507 update_modified_stmts (seq
);
1508 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1509 basic_block begin_bb
= get_entry_bb (codegen_region
);
1511 /* Inserting the gimple statements in a vector because gimple_seq behave
1512 in strage ways when inserting the stmts from it into different basic
1513 blocks one at a time. */
1514 auto_vec
<gimple
*, 3> stmts
;
1515 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1517 stmts
.safe_push (gsi_stmt (gsi
));
1521 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1523 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1524 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1526 use_operand_p use_p
;
1527 ssa_op_iter op_iter
;
1528 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1530 /* Iterator to the current def of use_p. For function parameters or
1531 anything where def is not found, insert at the beginning of the
1532 generated region. */
1533 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1535 tree op
= USE_FROM_PTR (use_p
);
1536 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1537 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1538 gsi_stmt
= gsi_for_stmt (stmt
);
1540 /* For region parameters, insert at the beginning of the generated
1542 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1543 gsi_stmt
= gsi_def_stmt
;
1545 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1548 if (!gsi_stmt (gsi_def_stmt
))
1550 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1551 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1553 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1555 gimple_stmt_iterator bsi
1556 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1557 /* Insert right after the PHI statements. */
1558 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1561 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1565 fprintf (dump_file
, "[codegen] inserting statement: ");
1566 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1567 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1572 /* Collect all the operands of NEW_EXPR by recursively visiting each
1576 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1580 /* Rename all uses in new_expr. */
1581 if (TREE_CODE (new_expr
) == SSA_NAME
)
1583 vec_ssa
->safe_push (new_expr
);
1587 /* Iterate over SSA_NAMES in NEW_EXPR. */
1588 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1590 tree op
= TREE_OPERAND (new_expr
, i
);
1591 collect_all_ssa_names (op
, vec_ssa
);
1595 /* This is abridged version of the function:
1596 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1599 substitute_ssa_name (tree exp
, tree f
, tree r
)
1601 enum tree_code code
= TREE_CODE (exp
);
1602 tree op0
, op1
, op2
, op3
;
1605 /* We handle TREE_LIST and COMPONENT_REF separately. */
1606 if (code
== TREE_LIST
)
1608 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1609 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1610 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1613 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1615 else if (code
== COMPONENT_REF
)
1619 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1620 and it is the right field, replace it with R. */
1621 for (inner
= TREE_OPERAND (exp
, 0);
1622 REFERENCE_CLASS_P (inner
);
1623 inner
= TREE_OPERAND (inner
, 0))
1627 op1
= TREE_OPERAND (exp
, 1);
1629 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1632 /* If this expression hasn't been completed let, leave it alone. */
1633 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1636 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1637 if (op0
== TREE_OPERAND (exp
, 0))
1641 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1644 switch (TREE_CODE_CLASS (code
))
1649 case tcc_declaration
:
1655 case tcc_expression
:
1659 /* Fall through... */
1661 case tcc_exceptional
:
1664 case tcc_comparison
:
1666 switch (TREE_CODE_LENGTH (code
))
1674 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1675 if (op0
== TREE_OPERAND (exp
, 0))
1678 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1682 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1683 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1685 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1688 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1692 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1693 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1694 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1696 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1697 && op2
== TREE_OPERAND (exp
, 2))
1700 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1704 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1705 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1706 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1707 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1709 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1710 && op2
== TREE_OPERAND (exp
, 2)
1711 && op3
== TREE_OPERAND (exp
, 3))
1715 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1728 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1730 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1731 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1736 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1739 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1742 auto_vec
<tree
, 2> ssa_names
;
1743 collect_all_ssa_names (new_expr
, &ssa_names
);
1746 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1747 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1748 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1753 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1754 scalar evolution around LOOP. */
1757 translate_isl_ast_to_gimple::
1758 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1759 basic_block new_bb
, basic_block old_bb
,
1762 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1764 /* At this point we should know the exact scev for each
1765 scalar SSA_NAME used in the scop: all the other scalar
1766 SSA_NAMEs should have been translated out of SSA using
1767 arrays with one element. */
1769 if (chrec_contains_undetermined (scev
))
1771 codegen_error
= true;
1772 return build_zero_cst (TREE_TYPE (old_name
));
1775 new_expr
= chrec_apply_map (scev
, iv_map
);
1777 /* The apply should produce an expression tree containing
1778 the uses of the new induction variables. We should be
1779 able to use new_expr instead of the old_name in the newly
1780 generated loop nest. */
1781 if (chrec_contains_undetermined (new_expr
)
1782 || tree_contains_chrecs (new_expr
, NULL
))
1784 codegen_error
= true;
1785 return build_zero_cst (TREE_TYPE (old_name
));
1788 /* We should check all the operands and all of them should dominate the use at
1790 if (TREE_CODE (new_expr
) == SSA_NAME
)
1792 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1793 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1795 codegen_error
= true;
1796 return build_zero_cst (TREE_TYPE (old_name
));
1800 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1801 /* We should check all the operands and all of them should dominate the use at
1803 if (TREE_CODE (new_expr
) == SSA_NAME
)
1805 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1806 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1808 codegen_error
= true;
1809 return build_zero_cst (TREE_TYPE (old_name
));
1813 /* Replace the old_name with the new_expr. */
1814 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1818 /* Renames the scalar uses of the statement COPY, using the
1819 substitution map RENAME_MAP, inserting the gimplification code at
1820 GSI_TGT, for the translation REGION, with the original copied
1821 statement in LOOP, and using the induction variable renaming map
1822 IV_MAP. Returns true when something has been renamed. codegen_error
1823 is set when the code generation cannot continue. */
1826 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1827 gimple_stmt_iterator
*gsi_tgt
,
1829 loop_p loop
, vec
<tree
> iv_map
)
1831 bool changed
= false;
1833 if (is_gimple_debug (copy
))
1835 if (gimple_debug_bind_p (copy
))
1836 gimple_debug_bind_reset_value (copy
);
1837 else if (gimple_debug_source_bind_p (copy
))
1847 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1848 print_gimple_stmt (dump_file
, copy
, 0, 0);
1851 use_operand_p use_p
;
1852 ssa_op_iter op_iter
;
1853 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1855 tree old_name
= USE_FROM_PTR (use_p
);
1859 fprintf (dump_file
, "[codegen] renaming old_name = ");
1860 print_generic_expr (dump_file
, old_name
, 0);
1861 fprintf (dump_file
, "\n");
1864 if (TREE_CODE (old_name
) != SSA_NAME
1865 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1869 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1874 tree type_old_name
= TREE_TYPE (old_name
);
1875 tree type_new_expr
= TREE_TYPE (new_expr
);
1879 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1880 print_generic_expr (dump_file
, new_expr
, 0);
1881 fprintf (dump_file
, "\n");
1884 if (type_old_name
!= type_new_expr
1885 || TREE_CODE (new_expr
) != SSA_NAME
)
1887 tree var
= create_tmp_var (type_old_name
, "var");
1889 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1890 new_expr
= fold_convert (type_old_name
, new_expr
);
1893 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1894 gsi_insert_earliest (stmts
);
1897 replace_exp (use_p
, new_expr
);
1902 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1904 if (!new_expr
|| codegen_error_p ())
1909 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1910 print_generic_expr (dump_file
, new_expr
, 0);
1911 fprintf (dump_file
, "\n");
1914 gsi_insert_earliest (stmts
);
1915 replace_exp (use_p
, new_expr
);
1917 if (TREE_CODE (new_expr
) == INTEGER_CST
1918 && is_gimple_assign (copy
))
1920 tree rhs
= gimple_assign_rhs1 (copy
);
1922 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1923 recompute_tree_invariant_for_addr_expr (rhs
);
1926 set_rename (old_name
, new_expr
);
1932 /* Returns a basic block that could correspond to where a constant was defined
1933 in the original code. In the original code OLD_BB had the definition, we
1934 need to find which basic block out of the copies of old_bb, in the new
1935 region, should a definition correspond to if it has to reach BB. */
1938 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1939 basic_block old_bb
) const
1941 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1943 if (!bbs
|| bbs
->is_empty ())
1946 if (1 == bbs
->length ())
1950 basic_block b1
= NULL
, b2
;
1951 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1956 /* BB and B2 are in two unrelated if-clauses. */
1957 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1960 /* Compute the nearest dominator. */
1961 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1969 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1970 when we want to rename an OP within a loop PHI instruction. */
1973 translate_isl_ast_to_gimple::
1974 get_new_name (basic_block new_bb
, tree op
,
1975 basic_block old_bb
, bool loop_phi
) const
1977 /* For constants the names are the same. */
1978 if (is_constant (op
))
1981 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1984 /* Return a debug location for OP. */
1989 location_t loc
= UNKNOWN_LOCATION
;
1991 if (TREE_CODE (op
) == SSA_NAME
)
1992 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1996 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1997 the init edge (from outside the loop) and the second one is the back edge
1998 from the same loop. */
2000 std::pair
<edge
, edge
>
2001 get_edges (basic_block bb
)
2003 std::pair
<edge
, edge
> edges
;
2006 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2007 if (bb
->loop_father
!= e
->src
->loop_father
)
2014 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2015 must be found unless they can be POSTPONEd for later. */
2018 translate_isl_ast_to_gimple::
2019 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2020 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2023 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2025 basic_block new_bb
= gimple_bb (new_phi
);
2026 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2029 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2030 e
= ibp_new_bb
.first
;
2032 e
= ibp_new_bb
.second
;
2034 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2035 tree new_name
= get_new_name (new_bb
, old_name
,
2036 gimple_bb (old_phi
), true);
2039 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2043 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2044 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2045 /* If the phi arg was a function arg, or wasn't defined, just use the
2047 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2050 /* Postpone code gen for later for those back-edges we don't have the
2052 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2054 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2057 /* Either we should add the arg to phi or, we should postpone. */
2063 /* Copy loop phi nodes from BB to NEW_BB. */
2066 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2070 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2073 /* Loop phi nodes should have only two arguments. */
2074 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2076 /* First edge is the init edge and second is the back edge. */
2077 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2079 /* First edge is the init edge and second is the back edge. */
2080 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2082 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2085 gphi
*phi
= psi
.phi ();
2086 tree res
= gimple_phi_result (phi
);
2087 if (virtual_operand_p (res
))
2089 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2092 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2093 tree new_res
= create_new_def_for (res
, new_phi
,
2094 gimple_phi_result_ptr (new_phi
));
2095 set_rename (res
, new_res
);
2096 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2098 update_stmt (new_phi
);
2104 /* Return the init value of PHI, the value coming from outside the loop. */
2107 get_loop_init_value (gphi
*phi
)
2110 loop_p loop
= gimple_bb (phi
)->loop_father
;
2114 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2115 if (e
->src
->loop_father
!= loop
)
2116 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2121 /* Find the init value (the value which comes from outside the loop), of one of
2122 the operands of DEF which is defined by a loop phi. */
2125 find_init_value (gimple
*def
)
2127 if (gimple_code (def
) == GIMPLE_PHI
)
2128 return get_loop_init_value (as_a
<gphi
*> (def
));
2130 if (gimple_vuse (def
))
2134 use_operand_p use_p
;
2135 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2137 tree use
= USE_FROM_PTR (use_p
);
2138 if (TREE_CODE (use
) == SSA_NAME
)
2140 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2148 /* Return the init value, the value coming from outside the loop. */
2151 find_init_value_close_phi (gphi
*phi
)
2153 gcc_assert (gimple_phi_num_args (phi
) == 1);
2154 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2155 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2156 return find_init_value (def
);
2160 tree
translate_isl_ast_to_gimple::
2161 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2162 gimple
*old_close_phi
)
2164 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2165 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2166 basic_block bb
= gimple_bb (stmt
);
2167 if (!bb_in_sese_p (bb
, codegen_region
))
2168 return last_merge_name
;
2170 loop_p loop
= bb
->loop_father
;
2171 if (!loop_in_sese_p (loop
, codegen_region
))
2172 return last_merge_name
;
2174 edge e
= single_exit (loop
);
2176 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2177 return last_merge_name
;
2179 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2180 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2183 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2184 bb
= split_edge (e
);
2186 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2187 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2188 gimple_phi_result_ptr (close_phi
));
2189 set_rename (old_close_phi_name
, res
);
2190 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2191 last_merge_name
= res
;
2193 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2196 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2197 the close phi node PHI. */
2199 bool translate_isl_ast_to_gimple::
2200 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2203 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2204 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2205 if (SSA_NAME
== TREE_CODE (default_value
))
2207 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2208 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2210 default_value_bb
= gimple_bb (stmt
);
2213 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2215 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2216 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2217 tree last_merge_name
= new_close_phi_name
;
2218 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2222 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2224 basic_block new_merge_bb
= merge_e
->src
;
2225 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2228 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2231 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2232 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2233 gimple_phi_result_ptr (merge_phi
));
2234 set_rename (old_close_phi_name
, merge_res
);
2236 edge from_loop
= NULL
, from_default_value
= NULL
;
2239 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2240 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2243 from_default_value
= e
;
2245 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2246 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2247 is contained in another condition. */
2248 if (!from_default_value
|| !from_loop
)
2251 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2252 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2256 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2257 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2260 update_stmt (merge_phi
);
2261 last_merge_name
= merge_res
;
2267 /* Copy all the loop-close phi args from BB to NEW_BB. */
2270 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2274 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2277 gphi
*old_close_phi
= psi
.phi ();
2278 tree res
= gimple_phi_result (old_close_phi
);
2279 if (virtual_operand_p (res
))
2282 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2283 /* Loop close phi nodes should not be scev_analyzable_p. */
2286 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2287 tree new_res
= create_new_def_for (res
, new_close_phi
,
2288 gimple_phi_result_ptr (new_close_phi
));
2289 set_rename (res
, new_res
);
2291 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2292 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2294 /* Predecessor basic blocks of a loop close phi should have been code
2295 generated before. FIXME: This is fixable by merging PHIs from inner
2296 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2300 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2301 get_loc (old_name
));
2304 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2305 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2308 update_stmt (new_close_phi
);
2310 /* When there is no loop guard around this codegenerated loop, there is no
2311 need to collect the close-phi arg. */
2312 if (merge_points
.is_empty ())
2315 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2316 tree default_value
= find_init_value_close_phi (new_close_phi
);
2318 /* A close phi must come from a loop-phi having a default value. */
2324 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2328 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2329 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2334 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2342 /* Copy loop close phi nodes from BB to NEW_BB. */
2345 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2349 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2351 /* Loop close phi nodes should have only one argument. */
2352 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2354 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2358 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2359 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2360 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2361 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2364 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2365 In this case DOMINATING_PRED = NULL.
2367 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2369 Returns true on successful copy of the args, false otherwise. */
2372 translate_isl_ast_to_gimple::
2373 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2374 edge old_bb_dominating_edge
,
2375 edge old_bb_non_dominating_edge
,
2376 gphi
*phi
, gphi
*new_phi
,
2379 basic_block def_pred
[2] = { NULL
, NULL
};
2380 int not_found_bb_index
= -1;
2381 for (int i
= 0; i
< 2; i
++)
2383 /* If the corresponding def_bb could not be found the entry will be
2385 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2386 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2387 gimple_phi_arg_edge (phi
, i
)->src
);
2388 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2389 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2393 /* When non are available bail out. */
2394 if (not_found_bb_index
!= -1)
2396 not_found_bb_index
= i
;
2400 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2401 if (old_bb_dominating_edge
)
2403 if (not_found_bb_index
!= -1)
2406 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2407 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2408 vec
<basic_block
> *bbs
2409 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2411 /* Could not find a mapping. */
2415 basic_block new_pred
= NULL
;
2418 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2420 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2422 /* FIXME: If we have already found new_pred then we have to
2423 disambiguate, bail out for now. */
2426 new_pred
= new_pred1
;
2428 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2430 /* FIXME: If we have already found new_pred then we have to either
2431 it dominates both or we have to disambiguate, bail out. */
2434 new_pred
= new_pred2
;
2441 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2442 gcc_assert (new_non_dominating_edge
);
2443 /* FIXME: Validate each args just like in loop-phis. */
2444 /* By the process of elimination we first insert insert phi-edge for
2445 non-dominating pred which is computed above and then we insert the
2447 int inserted_edge
= 0;
2448 for (; inserted_edge
< 2; inserted_edge
++)
2450 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2451 if (new_non_dominating_edge
== new_bb_pred_edge
)
2453 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2454 new_non_dominating_edge
,
2455 get_loc (old_phi_args
[inserted_edge
]));
2459 if (inserted_edge
== 2)
2462 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2464 edge new_dominating_edge
= NULL
;
2465 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2467 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2468 if (e
!= new_non_dominating_edge
)
2470 new_dominating_edge
= e
;
2471 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2472 new_dominating_edge
,
2473 get_loc (old_phi_args
[inserted_edge
]));
2477 gcc_assert (new_dominating_edge
);
2481 /* Classic diamond structure: both edges are non-dominating. We need to
2482 find one unique edge then the other can be found be elimination. If
2483 any definition (def_pred) dominates both the preds of new_bb then we
2484 bail out. Entries of def_pred maybe NULL, in that case we must
2485 uniquely find pred with help of only one entry. */
2486 edge new_e
[2] = { NULL
, NULL
};
2487 for (int i
= 0; i
< 2; i
++)
2491 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2493 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2496 /* We do not know how to handle the case when def_pred
2497 dominates more than a predecessor. */
2503 gcc_assert (new_e
[0] || new_e
[1]);
2505 /* Find the other edge by process of elimination. */
2506 if (not_found_bb_index
!= -1)
2508 gcc_assert (!new_e
[not_found_bb_index
]);
2509 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2512 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2514 if (new_e
[found_bb_index
] == e
)
2516 new_e
[not_found_bb_index
] = e
;
2520 /* Add edges to phi args. */
2521 for (int i
= 0; i
< 2; i
++)
2522 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2523 get_loc (old_phi_args
[i
]));
2529 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2530 region. If postpone is true and it isn't possible to copy any arg of PHI,
2531 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2532 Returns false if the copying was unsuccessful. */
2535 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2540 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2541 gcc_assert (2 == gimple_phi_num_args (phi
));
2543 basic_block new_bb
= gimple_bb (new_phi
);
2544 loop_p loop
= gimple_bb (phi
)->loop_father
;
2546 basic_block old_bb
= gimple_bb (phi
);
2547 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2551 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2552 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2553 old_bb_non_dominating_edge
= e
;
2555 old_bb_dominating_edge
= e
;
2557 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2558 old_bb_non_dominating_edge
->src
));
2560 tree new_phi_args
[2];
2561 tree old_phi_args
[2];
2563 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2565 tree old_name
= gimple_phi_arg_def (phi
, i
);
2566 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2567 old_phi_args
[i
] = old_name
;
2570 new_phi_args
[i
] = new_name
;
2574 /* If the phi-arg was a parameter. */
2575 if (vec_find (region
->params
, old_name
) != -1)
2577 new_phi_args
[i
] = old_name
;
2581 "[codegen] parameter argument to phi, new_expr: ");
2582 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2583 fprintf (dump_file
, "\n");
2588 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2589 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2590 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2596 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2597 if (is_gimple_reg (old_name
)
2598 && scev_analyzable_p (old_name
, region
->region
))
2601 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2602 new_bb
, old_bb
, iv_map
);
2603 if (codegen_error_p ())
2606 gcc_assert (new_expr
);
2610 "[codegen] scev analyzeable, new_expr: ");
2611 print_generic_expr (dump_file
, new_expr
, 0);
2612 fprintf (dump_file
, "\n");
2614 gsi_insert_earliest (stmts
);
2615 new_phi_args
[i
] = new_name
;
2619 /* Postpone code gen for later for back-edges. */
2620 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2624 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2625 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2628 new_phi_args
[i
] = NULL_TREE
;
2632 /* Either we should add the arg to phi or, we should postpone. */
2636 /* If none of the args have been determined in the first stage then wait until
2638 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2641 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2642 old_bb_dominating_edge
,
2643 old_bb_non_dominating_edge
,
2644 phi
, new_phi
, new_bb
);
2647 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2648 containing phi nodes coming from two predecessors, and none of them are back
2652 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2657 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2660 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2663 /* Cond phi nodes should have exactly two arguments. */
2664 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2666 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2669 gphi
*phi
= psi
.phi ();
2670 tree res
= gimple_phi_result (phi
);
2671 if (virtual_operand_p (res
))
2673 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2674 /* Cond phi nodes should not be scev_analyzable_p. */
2677 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2678 tree new_res
= create_new_def_for (res
, new_phi
,
2679 gimple_phi_result_ptr (new_phi
));
2680 set_rename (res
, new_res
);
2682 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2685 update_stmt (new_phi
);
2691 /* Return true if STMT should be copied from region to the new code-generated
2692 region. LABELs, CONDITIONS, induction-variables and region parameters need
2696 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2698 /* Do not copy labels or conditions. */
2699 if (gimple_code (stmt
) == GIMPLE_LABEL
2700 || gimple_code (stmt
) == GIMPLE_COND
)
2704 /* Do not copy induction variables. */
2705 if (is_gimple_assign (stmt
)
2706 && (lhs
= gimple_assign_lhs (stmt
))
2707 && TREE_CODE (lhs
) == SSA_NAME
2708 && is_gimple_reg (lhs
)
2709 && scev_analyzable_p (lhs
, region
->region
))
2715 /* Create new names for all the definitions created by COPY and add replacement
2716 mappings for each new name. */
2719 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2721 def_operand_p def_p
;
2722 ssa_op_iter op_iter
;
2723 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2725 tree old_name
= DEF_FROM_PTR (def_p
);
2726 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2727 set_rename (old_name
, new_name
);
2731 /* Duplicates the statements of basic block BB into basic block NEW_BB
2732 and compute the new induction variables according to the IV_MAP.
2733 CODEGEN_ERROR is set when the code generation cannot continue. */
2736 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2740 /* Iterator poining to the place where new statement (s) will be inserted. */
2741 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2743 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2746 gimple
*stmt
= gsi_stmt (gsi
);
2747 if (!should_copy_to_new_region (stmt
, region
))
2750 /* Create a new copy of STMT and duplicate STMT's virtual
2752 gimple
*copy
= gimple_copy (stmt
);
2753 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2757 fprintf (dump_file
, "[codegen] inserting statement: ");
2758 print_gimple_stmt (dump_file
, copy
, 0, 0);
2761 maybe_duplicate_eh_stmt (copy
, stmt
);
2762 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2764 /* Crete new names for each def in the copied stmt. */
2765 set_rename_for_each_def (copy
);
2767 loop_p loop
= bb
->loop_father
;
2768 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2770 fold_stmt_inplace (&gsi_tgt
);
2771 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2774 if (codegen_error_p ())
2784 /* Given a basic block containing close-phi it returns the new basic block where
2785 to insert a copy of the close-phi nodes. All the uses in close phis should
2786 come from a single loop otherwise it returns NULL. */
2789 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2791 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2792 of close phi in the original code and then find the mapping of basic block
2793 defining that variable. If there are multiple close-phis and they are
2794 defined in different loops (in the original or in the new code) because of
2795 loop splitting, then we bail out. */
2796 loop_p new_loop
= NULL
;
2797 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2800 gphi
*phi
= psi
.phi ();
2801 tree name
= gimple_phi_arg_def (phi
, 0);
2802 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2804 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2805 if (!bbs
|| bbs
->length () != 1)
2806 /* This is one of the places which shows preserving original structure
2807 is not always possible, as we may need to insert close PHI for a loop
2808 where the latch does not have any mapping, or the mapping is
2813 new_loop
= (*bbs
)[0]->loop_father
;
2814 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2821 return single_exit (new_loop
);
2824 /* Copies BB and includes in the copied BB all the statements that can
2825 be reached following the use-def chains from the memory accesses,
2826 and returns the next edge following this new block. codegen_error is
2827 set when the code generation cannot continue. */
2830 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2834 int num_phis
= number_of_phi_nodes (bb
);
2836 if (region
->copied_bb_map
->get (bb
))
2838 /* FIXME: we should be able to handle phi nodes with args coming from
2839 outside the region. */
2842 codegen_error
= true;
2847 basic_block new_bb
= NULL
;
2848 if (bb_contains_loop_close_phi_nodes (bb
))
2851 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2854 edge e
= edge_for_new_close_phis (bb
);
2857 codegen_error
= true;
2861 basic_block phi_bb
= e
->dest
;
2863 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2864 phi_bb
= split_edge (e
);
2866 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2867 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2869 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2871 codegen_error
= true;
2878 new_bb
= split_edge (next_e
);
2882 new_bb
= split_edge (next_e
);
2883 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2885 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2887 /* At this point we are unable to codegenerate by still preserving the SSA
2888 structure because maybe the loop is completely unrolled and the PHIs
2889 and cross-bb scalar dependencies are untrackable w.r.t. the original
2890 code. See gfortran.dg/graphite/pr29832.f90. */
2891 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2893 codegen_error
= true;
2898 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2900 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2902 codegen_error
= true;
2906 else if (num_phis
> 0)
2909 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2912 basic_block phi_bb
= single_pred (new_bb
);
2913 loop_p loop_father
= new_bb
->loop_father
;
2915 /* Move back until we find the block with two predecessors. */
2916 while (single_pred_p (phi_bb
))
2917 phi_bb
= single_pred_edge (phi_bb
)->src
;
2919 /* If a corresponding merge-point was not found, then abort codegen. */
2920 if (phi_bb
->loop_father
!= loop_father
2921 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2923 codegen_error
= true;
2930 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2931 bb
->index
, new_bb
->index
);
2933 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2935 copied_bbs
->safe_push (new_bb
);
2938 vec
<basic_block
> bbs
;
2940 bbs
.safe_push (new_bb
);
2941 region
->copied_bb_map
->put (bb
, bbs
);
2944 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2946 codegen_error
= true;
2950 return single_succ_edge (new_bb
);
2953 /* Patch the missing arguments of the phi nodes. */
2956 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2960 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2962 gphi
*old_phi
= rename
->first
;
2963 gphi
*new_phi
= rename
->second
;
2964 basic_block old_bb
= gimple_bb (old_phi
);
2965 basic_block new_bb
= gimple_bb (new_phi
);
2967 /* First edge is the init edge and second is the back edge. */
2968 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2969 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2973 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2974 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2977 auto_vec
<tree
, 1> iv_map
;
2978 if (bb_contains_loop_phi_nodes (new_bb
))
2979 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2981 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2982 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2984 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2988 fprintf (dump_file
, "[codegen] to new-phi: ");
2989 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2996 /* Prints NODE to FILE. */
2999 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3000 __isl_keep isl_ast_node
*node
,
3001 __isl_keep isl_ctx
*ctx
) const
3003 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3004 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3005 prn
= isl_printer_print_ast_node (prn
, node
);
3006 prn
= isl_printer_print_str (prn
, "\n");
3007 isl_printer_free (prn
);
3010 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
3013 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3016 sese_info_p region
= scop
->scop_info
;
3017 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3018 gcc_assert (nb_parameters
== region
->params
.length ());
3020 for (i
= 0; i
< nb_parameters
; i
++)
3022 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3024 ip
[tmp_id
] = region
->params
[i
];
3029 /* Generates a build, which specifies the constraints on the parameters. */
3031 __isl_give isl_ast_build
*
3032 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3034 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3035 return isl_ast_build_from_context (context_isl
);
3038 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3041 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3045 int schedule_dims
= 0;
3047 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3049 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3050 if (pbb_schedule_dims
> schedule_dims
)
3051 schedule_dims
= pbb_schedule_dims
;
3054 return schedule_dims
;
3057 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3059 For schedules with different dimensionality, the isl AST generator can not
3060 define an order and will just randomly choose an order. The solution to this
3061 problem is to extend all schedules to the maximal number of schedule
3062 dimensions (using '0's for the remaining values). */
3064 __isl_give isl_map
*
3065 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3066 int nb_schedule_dims
)
3068 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3070 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3072 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3074 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3077 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3079 isl_val_free (zero
);
3083 /* Generates a schedule, which specifies an order used to
3084 visit elements in a domain. */
3086 __isl_give isl_union_map
*
3087 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3089 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3092 isl_union_map
*schedule_isl
=
3093 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3095 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3097 /* Dead code elimination: when the domain of a PBB is empty,
3098 don't generate code for the PBB. */
3099 if (isl_set_is_empty (pbb
->domain
))
3102 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3103 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3104 isl_set_copy (pbb
->domain
));
3105 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3107 = isl_union_map_union (schedule_isl
,
3108 isl_union_map_from_map (bb_schedule
));
3110 return schedule_isl
;
3113 /* This method is executed before the construction of a for node. */
3115 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3117 isl_union_map
*dependences
= (isl_union_map
*) user
;
3118 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3119 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3120 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3121 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3122 for_info
->is_parallelizable
=
3123 !carries_deps (schedule
, dependences
, dimension
);
3124 isl_union_map_free (schedule
);
3125 isl_space_free (schedule_space
);
3126 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3130 /* Set the separate option for all dimensions.
3131 This helps to reduce control overhead. */
3133 __isl_give isl_ast_build
*
3134 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3135 __isl_keep isl_union_map
*schedule
)
3137 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3138 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3140 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3141 isl_union_set
*range
=
3142 isl_union_set_from_set (isl_set_universe (range_space
));
3143 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3144 domain
= isl_union_set_universe (domain
);
3145 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3146 return isl_ast_build_set_options (control
, options
);
3149 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3151 __isl_give isl_ast_node
*
3152 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3154 /* Generate loop upper bounds that consist of the current loop iterator, an
3155 operator (< or <=) and an expression not involving the iterator. If this
3156 option is not set, then the current loop iterator may appear several times
3157 in the upper bound. See the isl manual for more details. */
3158 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3160 add_parameters_to_ivs_params (scop
, ip
);
3161 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3162 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3163 context_isl
= set_options (context_isl
, schedule_isl
);
3164 isl_union_map
*dependences
= NULL
;
3165 if (flag_loop_parallelize_all
)
3167 dependences
= scop_get_dependences (scop
);
3169 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3172 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3175 isl_union_map_free (dependences
);
3176 isl_ast_build_free (context_isl
);
3180 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3181 the given SCOP. Return true if code generation succeeded.
3183 FIXME: This is not yet a full implementation of the code generator
3184 with ISL ASTs. Generation of GIMPLE code has to be completed. */
3187 graphite_regenerate_ast_isl (scop_p scop
)
3189 sese_info_p region
= scop
->scop_info
;
3190 translate_isl_ast_to_gimple
t (region
);
3192 ifsese if_region
= NULL
;
3193 isl_ast_node
*root_node
;
3196 timevar_push (TV_GRAPHITE_CODE_GEN
);
3197 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3201 fprintf (dump_file
, "ISL AST generated by ISL: \n");
3202 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3205 recompute_all_dominators ();
3208 if_region
= move_sese_in_condition (region
);
3209 region
->if_region
= if_region
;
3210 recompute_all_dominators ();
3212 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3214 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3215 basic_block bb
= split_edge (e
);
3217 /* Update the true_region exit edge. */
3218 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3220 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3221 if (t
.codegen_error_p ())
3224 fprintf (dump_file
, "[codegen] unsuccessful,"
3225 " reverting back to the original code.\n");
3226 set_ifsese_condition (if_region
, integer_zero_node
);
3230 t
.translate_pending_phi_nodes ();
3231 if (!t
.codegen_error_p ())
3233 sese_insert_phis_for_liveouts (region
,
3234 if_region
->region
->region
.exit
->src
,
3235 if_region
->false_region
->region
.exit
,
3236 if_region
->true_region
->region
.exit
);
3237 mark_virtual_operands_for_renaming (cfun
);
3238 update_ssa (TODO_update_ssa
);
3243 recompute_all_dominators ();
3249 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3250 " pending phis, reverting back to the original code.\n");
3251 set_ifsese_condition (if_region
, integer_zero_node
);
3255 free (if_region
->true_region
);
3256 free (if_region
->region
);
3259 ivs_params_clear (ip
);
3260 isl_ast_node_free (root_node
);
3261 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3266 int num_no_dependency
= 0;
3268 FOR_EACH_LOOP (loop
, 0)
3269 if (loop
->can_be_parallel
)
3270 num_no_dependency
++;
3272 fprintf (dump_file
, "%d loops carried no dependency.\n",
3276 return !t
.codegen_error_p ();
3279 #endif /* HAVE_isl */