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_zdiv_r
:
592 case isl_ast_op_pdiv_r
:
593 /* As ISL operates on arbitrary precision numbers, we may end up with
594 division by 2^64 that is folded to 0. */
595 if (integer_zerop (tree_rhs_expr
))
597 codegen_error
= true;
600 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
602 case isl_ast_op_fdiv_q
:
603 /* As ISL operates on arbitrary precision numbers, we may end up with
604 division by 2^64 that is folded to 0. */
605 if (integer_zerop (tree_rhs_expr
))
607 codegen_error
= true;
610 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
613 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
614 tree_lhs_expr
, tree_rhs_expr
);
617 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
620 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
623 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
626 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
629 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
632 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
639 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
643 translate_isl_ast_to_gimple::
644 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
646 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
647 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
649 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
650 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
651 tree tree_second_expr
652 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
653 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
655 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
656 isl_ast_expr_free (expr
);
660 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
661 tree_second_expr
, tree_third_expr
);
664 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
668 translate_isl_ast_to_gimple::
669 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
671 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
672 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
673 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
674 isl_ast_expr_free (expr
);
675 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
678 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
679 to a GCC expression tree of type TYPE. */
682 translate_isl_ast_to_gimple::
683 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
685 enum tree_code op_code
;
686 switch (isl_ast_expr_get_op_type (expr
))
699 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
700 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
704 isl_ast_expr_free (expr
);
709 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
711 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
712 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
716 isl_ast_expr_free (expr
);
720 res
= fold_build2 (op_code
, type
, res
, t
);
722 isl_ast_expr_free (expr
);
726 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
730 translate_isl_ast_to_gimple::
731 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
736 isl_ast_expr_free (expr
);
740 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
741 switch (isl_ast_expr_get_op_type (expr
))
743 /* These isl ast expressions are not supported yet. */
744 case isl_ast_op_error
:
745 case isl_ast_op_call
:
746 case isl_ast_op_and_then
:
747 case isl_ast_op_or_else
:
748 case isl_ast_op_select
:
753 return nary_op_to_tree (type
, expr
, ip
);
759 case isl_ast_op_pdiv_q
:
760 case isl_ast_op_pdiv_r
:
761 case isl_ast_op_fdiv_q
:
762 case isl_ast_op_zdiv_r
:
770 return binary_op_to_tree (type
, expr
, ip
);
772 case isl_ast_op_minus
:
773 return unary_op_to_tree (type
, expr
, ip
);
775 case isl_ast_op_cond
:
776 return ternary_op_to_tree (type
, expr
, ip
);
785 /* Converts an ISL AST expression E back to a GCC expression tree of
789 translate_isl_ast_to_gimple::
790 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
795 isl_ast_expr_free (expr
);
799 switch (isl_ast_expr_get_type (expr
))
801 case isl_ast_expr_id
:
802 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
804 case isl_ast_expr_int
:
805 return gcc_expression_from_isl_expr_int (type
, expr
);
807 case isl_ast_expr_op
:
808 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
817 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
818 induction variable for the new LOOP. New LOOP is attached to CFG
819 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
820 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
821 ISL's scattering name to the induction variable created for the
822 loop of STMT. The new induction variable is inserted in the NEWIVS
823 vector and is of type TYPE. */
826 translate_isl_ast_to_gimple::
827 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
828 loop_p outer
, tree type
, tree lb
, tree ub
,
831 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
832 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
834 /* To fail code generation, we generate wrong code until we discard it. */
836 stride
= integer_zero_node
;
838 tree ivvar
= create_tmp_var (type
, "graphite_IV");
839 tree iv
, iv_after_increment
;
840 loop_p loop
= create_empty_loop_on_edge
841 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
842 outer
? outer
: entry_edge
->src
->loop_father
);
844 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
845 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
846 std::map
<isl_id
*, tree
>::iterator res
;
849 isl_id_free (res
->first
);
851 isl_ast_expr_free (for_iterator
);
855 /* Create the loop for a isl_ast_node_for.
857 - NEXT_E is the edge where new generated code should be attached. */
860 translate_isl_ast_to_gimple::
861 translate_isl_ast_for_loop (loop_p context_loop
,
862 __isl_keep isl_ast_node
*node_for
, edge next_e
,
863 tree type
, tree lb
, tree ub
,
866 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
867 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
869 edge last_e
= single_exit (loop
);
870 edge to_body
= single_succ_edge (loop
->header
);
871 basic_block after
= to_body
->dest
;
873 /* Translate the body of the loop. */
874 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
875 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
876 isl_ast_node_free (for_body
);
878 /* Early return if we failed to translate loop body. */
879 if (!next_e
|| codegen_error_p ())
882 if (next_e
->dest
!= after
)
883 redirect_edge_succ_nodup (next_e
, after
);
884 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
886 if (flag_loop_parallelize_all
)
888 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
890 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
891 loop
->can_be_parallel
= for_info
->is_parallelizable
;
899 /* We use this function to get the upper bound because of the form,
900 which is used by isl to represent loops:
902 for (iterator = init; cond; iterator += inc)
910 The loop condition is an arbitrary expression, which contains the
911 current loop iterator.
913 (e.g. iterator + 3 < B && C > iterator + A)
915 We have to know the upper bound of the iterator to generate a loop
916 in Gimple form. It can be obtained from the special representation
917 of the loop condition, which is generated by isl,
918 if the ast_build_atomic_upper_bound option is set. In this case,
919 isl generates a loop condition that consists of the current loop
920 iterator, + an operator (< or <=) and an expression not involving
921 the iterator, which is processed and returned by this function.
923 (e.g iterator <= upper-bound-expression-without-iterator) */
925 static __isl_give isl_ast_expr
*
926 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
928 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
929 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
930 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
932 switch (isl_ast_expr_get_op_type (for_cond
))
935 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
940 /* (iterator < ub) => (iterator <= ub - 1). */
942 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
943 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
944 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
951 isl_ast_expr_free (for_cond
);
955 /* All loops generated by create_empty_loop_on_edge have the form of
962 } while (lower bound < upper bound);
964 We create a new if region protecting the loop to be executed, if
965 the execution count is zero (lower bound > upper bound). */
968 translate_isl_ast_to_gimple::
969 graphite_create_new_loop_guard (edge entry_edge
,
970 __isl_keep isl_ast_node
*node_for
, tree
*type
,
971 tree
*lb
, tree
*ub
, ivs_params
&ip
)
973 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
978 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
979 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
980 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
981 /* To fail code generation, we generate wrong code until we discard it. */
983 *lb
= integer_zero_node
;
984 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
985 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
986 /* To fail code generation, we generate wrong code until we discard it. */
988 *ub
= integer_zero_node
;
990 /* When ub is simply a constant or a parameter, use lb <= ub. */
991 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
992 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
995 tree one
= (POINTER_TYPE_P (*type
)
996 ? convert_to_ptrofftype (integer_one_node
)
997 : fold_convert (*type
, integer_one_node
));
998 /* Adding +1 and using LT_EXPR helps with loop latches that have a
999 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1000 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1001 is true, even if we do not want this. However lb < ub + 1 is false,
1003 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1004 : PLUS_EXPR
, *type
, *ub
, one
);
1006 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1009 if (integer_onep (cond_expr
))
1010 exit_edge
= entry_edge
;
1012 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1017 /* Translates an isl_ast_node_for to Gimple. */
1020 translate_isl_ast_to_gimple::
1021 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1022 edge next_e
, ivs_params
&ip
)
1024 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1026 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1029 if (last_e
== next_e
)
1031 /* There was no guard generated. */
1032 last_e
= single_succ_edge (split_edge (last_e
));
1034 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1039 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1040 merge_points
.safe_push (last_e
);
1042 last_e
= single_succ_edge (split_edge (last_e
));
1043 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1048 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1049 variables of the loops around GBB in SESE.
1051 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1052 chrec, we could consider using a map<int, tree> that maps loop ids to the
1053 corresponding tree expressions. */
1056 translate_isl_ast_to_gimple::
1057 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1058 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1061 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1062 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1064 isl_ast_expr
*arg_expr
;
1065 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1067 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1069 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1070 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1071 /* To fail code generation, we generate wrong code until we discard it. */
1073 t
= integer_zero_node
;
1075 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1076 iv_map
[old_loop
->num
] = t
;
1080 /* Translates an isl_ast_node_user to Gimple.
1082 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1085 translate_isl_ast_to_gimple::
1086 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1087 edge next_e
, ivs_params
&ip
)
1089 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1091 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1092 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1093 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1095 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1096 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1099 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1101 isl_ast_expr_free (name_expr
);
1102 isl_id_free (name_id
);
1104 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1105 "The entry block should not even appear within a scop");
1107 const int nb_loops
= number_of_loops (cfun
);
1109 iv_map
.create (nb_loops
);
1110 iv_map
.safe_grow_cleared (nb_loops
);
1112 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1113 isl_ast_expr_free (user_expr
);
1117 fprintf (dump_file
, "[codegen] copying from basic block\n");
1118 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1119 fprintf (dump_file
, "[codegen] to new basic block\n");
1120 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1123 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1128 if (codegen_error_p ())
1133 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1134 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1140 /* Translates an isl_ast_node_block to Gimple. */
1143 translate_isl_ast_to_gimple::
1144 translate_isl_ast_node_block (loop_p context_loop
,
1145 __isl_keep isl_ast_node
*node
,
1146 edge next_e
, ivs_params
&ip
)
1148 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1149 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1151 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1153 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1154 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1155 isl_ast_node_free (tmp_node
);
1157 isl_ast_node_list_free (node_list
);
1161 /* Creates a new if region corresponding to ISL's cond. */
1164 translate_isl_ast_to_gimple::
1165 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1169 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1170 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1171 /* To fail code generation, we generate wrong code until we discard it. */
1173 cond_expr
= integer_zero_node
;
1175 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1179 /* Translates an isl_ast_node_if to Gimple. */
1182 translate_isl_ast_to_gimple::
1183 translate_isl_ast_node_if (loop_p context_loop
,
1184 __isl_keep isl_ast_node
*node
,
1185 edge next_e
, ivs_params
&ip
)
1187 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1188 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1189 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1190 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1191 merge_points
.safe_push (last_e
);
1193 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1194 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1195 isl_ast_node_free (then_node
);
1197 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1198 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1199 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1200 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1202 isl_ast_node_free (else_node
);
1206 /* Translates an ISL AST node NODE to GCC representation in the
1207 context of a SESE. */
1210 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1211 __isl_keep isl_ast_node
*node
,
1212 edge next_e
, ivs_params
&ip
)
1214 if (codegen_error_p ())
1217 switch (isl_ast_node_get_type (node
))
1219 case isl_ast_node_error
:
1222 case isl_ast_node_for
:
1223 return translate_isl_ast_node_for (context_loop
, node
,
1226 case isl_ast_node_if
:
1227 return translate_isl_ast_node_if (context_loop
, node
,
1230 case isl_ast_node_user
:
1231 return translate_isl_ast_node_user (node
, next_e
, ip
);
1233 case isl_ast_node_block
:
1234 return translate_isl_ast_node_block (context_loop
, node
,
1242 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1243 at the exit of loop which takes one argument that is the last value of the
1244 variable being used out of the loop. */
1247 bb_contains_loop_close_phi_nodes (basic_block bb
)
1249 return single_pred_p (bb
)
1250 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1253 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1254 header containing phi nodes which has one init-edge and one back-edge. */
1257 bb_contains_loop_phi_nodes (basic_block bb
)
1259 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1261 if (bb
->preds
->length () == 1)
1264 unsigned depth
= loop_depth (bb
->loop_father
);
1266 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1268 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1269 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1272 /* When one of the edges correspond to the same loop father and other
1274 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1275 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1278 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1279 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1285 /* Check if USE is defined in a basic block from where the definition of USE can
1286 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1289 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1291 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1294 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1295 if (bb_contains_loop_close_phi_nodes (bb
))
1298 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1299 basic_block def_bb
= gimple_bb (def
);
1301 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1304 /* Return the number of phi nodes in BB. */
1307 number_of_phi_nodes (basic_block bb
)
1310 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1316 /* Returns true if BB uses name in one of its PHIs. */
1319 phi_uses_name (basic_block bb
, tree name
)
1321 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1324 gphi
*phi
= psi
.phi ();
1325 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1327 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1328 if (use_arg
== name
)
1335 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1336 definition should flow into use, and the use should respect the loop-closed
1340 translate_isl_ast_to_gimple::
1341 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1342 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1344 /* The def of the rename must either dominate the uses or come from a
1345 back-edge. Also the def must respect the loop closed ssa form. */
1346 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1350 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1351 print_generic_expr (dump_file
, rename
, 0);
1352 fprintf (dump_file
, "\n");
1357 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1360 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1362 /* The loop-header dominates the loop-body. */
1363 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1366 /* RENAME would be used in loop-phi. */
1367 gcc_assert (number_of_phi_nodes (use_bb
));
1369 /* For definitions coming from back edges, we should check that
1370 old_name is used in a loop PHI node.
1371 FIXME: Verify if this is true. */
1372 if (phi_uses_name (old_bb
, old_name
))
1378 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1379 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1380 within a loop PHI instruction. */
1383 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1386 bool loop_phi
) const
1388 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1389 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1391 if (!renames
|| renames
->is_empty ())
1394 if (1 == renames
->length ())
1396 tree rename
= (*renames
)[0];
1397 if (TREE_CODE (rename
) == SSA_NAME
)
1399 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1400 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1405 if (is_constant (rename
))
1411 /* More than one renames corresponding to the old_name. Find the rename for
1412 which the definition flows into usage at new_bb. */
1414 tree t1
= NULL_TREE
, t2
;
1415 basic_block t1_bb
= NULL
;
1416 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1418 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1420 /* Defined in the same basic block as used. */
1421 if (t2_bb
== new_bb
)
1424 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1425 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1428 /* Compute the nearest dominator. */
1429 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1439 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1440 When OLD_NAME and EXPR are the same we assert. */
1443 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1447 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1448 print_generic_expr (dump_file
, old_name
, 0);
1449 fprintf (dump_file
, ", new_name = ");
1450 print_generic_expr (dump_file
, expr
, 0);
1451 fprintf (dump_file
, "\n");
1454 if (old_name
== expr
)
1457 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1460 renames
->safe_push (expr
);
1466 region
->rename_map
->put (old_name
, r
);
1470 /* Return an iterator to the instructions comes last in the execution order.
1471 Either GSI1 and GSI2 should belong to the same basic block or one of their
1472 respective basic blocks should dominate the other. */
1474 gimple_stmt_iterator
1475 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1477 basic_block bb1
= gsi_bb (gsi1
);
1478 basic_block bb2
= gsi_bb (gsi2
);
1480 /* Find the iterator which is the latest. */
1483 /* For empty basic blocks gsis point to the end of the sequence. Since
1484 there is no operator== defined for gimple_stmt_iterator and for gsis
1485 not pointing to a valid statement gsi_next would assert. */
1486 gimple_stmt_iterator gsi
= gsi1
;
1488 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1491 } while (!gsi_end_p (gsi
));
1496 /* Find the basic block closest to the basic block which defines stmt. */
1497 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1500 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1504 /* Insert each statement from SEQ at its earliest insertion p. */
1507 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1509 update_modified_stmts (seq
);
1510 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1511 basic_block begin_bb
= get_entry_bb (codegen_region
);
1513 /* Inserting the gimple statements in a vector because gimple_seq behave
1514 in strage ways when inserting the stmts from it into different basic
1515 blocks one at a time. */
1516 auto_vec
<gimple
*, 3> stmts
;
1517 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1519 stmts
.safe_push (gsi_stmt (gsi
));
1523 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1525 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1526 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1528 use_operand_p use_p
;
1529 ssa_op_iter op_iter
;
1530 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1532 /* Iterator to the current def of use_p. For function parameters or
1533 anything where def is not found, insert at the beginning of the
1534 generated region. */
1535 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1537 tree op
= USE_FROM_PTR (use_p
);
1538 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1539 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1540 gsi_stmt
= gsi_for_stmt (stmt
);
1542 /* For region parameters, insert at the beginning of the generated
1544 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1545 gsi_stmt
= gsi_def_stmt
;
1547 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1550 if (!gsi_stmt (gsi_def_stmt
))
1552 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1553 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1555 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1557 gimple_stmt_iterator bsi
1558 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1559 /* Insert right after the PHI statements. */
1560 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1563 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1567 fprintf (dump_file
, "[codegen] inserting statement: ");
1568 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1569 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1574 /* Collect all the operands of NEW_EXPR by recursively visiting each
1578 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1582 /* Rename all uses in new_expr. */
1583 if (TREE_CODE (new_expr
) == SSA_NAME
)
1585 vec_ssa
->safe_push (new_expr
);
1589 /* Iterate over SSA_NAMES in NEW_EXPR. */
1590 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1592 tree op
= TREE_OPERAND (new_expr
, i
);
1593 collect_all_ssa_names (op
, vec_ssa
);
1597 /* This is abridged version of the function:
1598 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1601 substitute_ssa_name (tree exp
, tree f
, tree r
)
1603 enum tree_code code
= TREE_CODE (exp
);
1604 tree op0
, op1
, op2
, op3
;
1607 /* We handle TREE_LIST and COMPONENT_REF separately. */
1608 if (code
== TREE_LIST
)
1610 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1611 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1612 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1615 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1617 else if (code
== COMPONENT_REF
)
1621 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1622 and it is the right field, replace it with R. */
1623 for (inner
= TREE_OPERAND (exp
, 0);
1624 REFERENCE_CLASS_P (inner
);
1625 inner
= TREE_OPERAND (inner
, 0))
1629 op1
= TREE_OPERAND (exp
, 1);
1631 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1634 /* If this expression hasn't been completed let, leave it alone. */
1635 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1638 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1639 if (op0
== TREE_OPERAND (exp
, 0))
1643 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1646 switch (TREE_CODE_CLASS (code
))
1651 case tcc_declaration
:
1657 case tcc_expression
:
1661 /* Fall through... */
1663 case tcc_exceptional
:
1666 case tcc_comparison
:
1668 switch (TREE_CODE_LENGTH (code
))
1676 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1677 if (op0
== TREE_OPERAND (exp
, 0))
1680 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1684 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1685 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1687 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1690 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1694 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1695 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1696 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1698 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1699 && op2
== TREE_OPERAND (exp
, 2))
1702 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1706 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1707 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1708 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1709 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1711 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1712 && op2
== TREE_OPERAND (exp
, 2)
1713 && op3
== TREE_OPERAND (exp
, 3))
1717 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1730 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1732 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1733 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1738 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1741 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1744 auto_vec
<tree
, 2> ssa_names
;
1745 collect_all_ssa_names (new_expr
, &ssa_names
);
1748 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1749 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1750 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1755 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1756 scalar evolution around LOOP. */
1759 translate_isl_ast_to_gimple::
1760 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1761 basic_block new_bb
, basic_block old_bb
,
1764 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1766 /* At this point we should know the exact scev for each
1767 scalar SSA_NAME used in the scop: all the other scalar
1768 SSA_NAMEs should have been translated out of SSA using
1769 arrays with one element. */
1771 if (chrec_contains_undetermined (scev
))
1773 codegen_error
= true;
1774 return build_zero_cst (TREE_TYPE (old_name
));
1777 new_expr
= chrec_apply_map (scev
, iv_map
);
1779 /* The apply should produce an expression tree containing
1780 the uses of the new induction variables. We should be
1781 able to use new_expr instead of the old_name in the newly
1782 generated loop nest. */
1783 if (chrec_contains_undetermined (new_expr
)
1784 || tree_contains_chrecs (new_expr
, NULL
))
1786 codegen_error
= true;
1787 return build_zero_cst (TREE_TYPE (old_name
));
1790 /* We should check all the operands and all of them should dominate the use at
1792 if (TREE_CODE (new_expr
) == SSA_NAME
)
1794 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1795 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1797 codegen_error
= true;
1798 return build_zero_cst (TREE_TYPE (old_name
));
1802 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1803 /* We should check all the operands and all of them should dominate the use at
1805 if (TREE_CODE (new_expr
) == SSA_NAME
)
1807 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1808 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1810 codegen_error
= true;
1811 return build_zero_cst (TREE_TYPE (old_name
));
1815 /* Replace the old_name with the new_expr. */
1816 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1820 /* Renames the scalar uses of the statement COPY, using the
1821 substitution map RENAME_MAP, inserting the gimplification code at
1822 GSI_TGT, for the translation REGION, with the original copied
1823 statement in LOOP, and using the induction variable renaming map
1824 IV_MAP. Returns true when something has been renamed. codegen_error
1825 is set when the code generation cannot continue. */
1828 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1829 gimple_stmt_iterator
*gsi_tgt
,
1831 loop_p loop
, vec
<tree
> iv_map
)
1833 bool changed
= false;
1835 if (is_gimple_debug (copy
))
1837 if (gimple_debug_bind_p (copy
))
1838 gimple_debug_bind_reset_value (copy
);
1839 else if (gimple_debug_source_bind_p (copy
))
1849 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1850 print_gimple_stmt (dump_file
, copy
, 0, 0);
1853 use_operand_p use_p
;
1854 ssa_op_iter op_iter
;
1855 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1857 tree old_name
= USE_FROM_PTR (use_p
);
1861 fprintf (dump_file
, "[codegen] renaming old_name = ");
1862 print_generic_expr (dump_file
, old_name
, 0);
1863 fprintf (dump_file
, "\n");
1866 if (TREE_CODE (old_name
) != SSA_NAME
1867 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1871 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1876 tree type_old_name
= TREE_TYPE (old_name
);
1877 tree type_new_expr
= TREE_TYPE (new_expr
);
1881 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1882 print_generic_expr (dump_file
, new_expr
, 0);
1883 fprintf (dump_file
, "\n");
1886 if (type_old_name
!= type_new_expr
1887 || TREE_CODE (new_expr
) != SSA_NAME
)
1889 tree var
= create_tmp_var (type_old_name
, "var");
1891 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1892 new_expr
= fold_convert (type_old_name
, new_expr
);
1895 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1896 gsi_insert_earliest (stmts
);
1899 replace_exp (use_p
, new_expr
);
1904 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1906 if (!new_expr
|| codegen_error_p ())
1911 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1912 print_generic_expr (dump_file
, new_expr
, 0);
1913 fprintf (dump_file
, "\n");
1916 gsi_insert_earliest (stmts
);
1917 replace_exp (use_p
, new_expr
);
1919 if (TREE_CODE (new_expr
) == INTEGER_CST
1920 && is_gimple_assign (copy
))
1922 tree rhs
= gimple_assign_rhs1 (copy
);
1924 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1925 recompute_tree_invariant_for_addr_expr (rhs
);
1928 set_rename (old_name
, new_expr
);
1934 /* Returns a basic block that could correspond to where a constant was defined
1935 in the original code. In the original code OLD_BB had the definition, we
1936 need to find which basic block out of the copies of old_bb, in the new
1937 region, should a definition correspond to if it has to reach BB. */
1940 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1941 basic_block old_bb
) const
1943 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1945 if (!bbs
|| bbs
->is_empty ())
1948 if (1 == bbs
->length ())
1952 basic_block b1
= NULL
, b2
;
1953 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1958 /* BB and B2 are in two unrelated if-clauses. */
1959 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1962 /* Compute the nearest dominator. */
1963 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1971 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1972 when we want to rename an OP within a loop PHI instruction. */
1975 translate_isl_ast_to_gimple::
1976 get_new_name (basic_block new_bb
, tree op
,
1977 basic_block old_bb
, bool loop_phi
) const
1979 /* For constants the names are the same. */
1980 if (is_constant (op
))
1983 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1986 /* Return a debug location for OP. */
1991 location_t loc
= UNKNOWN_LOCATION
;
1993 if (TREE_CODE (op
) == SSA_NAME
)
1994 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1998 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1999 the init edge (from outside the loop) and the second one is the back edge
2000 from the same loop. */
2002 std::pair
<edge
, edge
>
2003 get_edges (basic_block bb
)
2005 std::pair
<edge
, edge
> edges
;
2008 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2009 if (bb
->loop_father
!= e
->src
->loop_father
)
2016 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2017 must be found unless they can be POSTPONEd for later. */
2020 translate_isl_ast_to_gimple::
2021 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2022 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2025 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2027 basic_block new_bb
= gimple_bb (new_phi
);
2028 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2031 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2032 e
= ibp_new_bb
.first
;
2034 e
= ibp_new_bb
.second
;
2036 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2037 tree new_name
= get_new_name (new_bb
, old_name
,
2038 gimple_bb (old_phi
), true);
2041 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2045 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2046 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2047 /* If the phi arg was a function arg, or wasn't defined, just use the
2049 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2052 /* Postpone code gen for later for those back-edges we don't have the
2054 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2056 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2059 /* Either we should add the arg to phi or, we should postpone. */
2065 /* Copy loop phi nodes from BB to NEW_BB. */
2068 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2072 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2075 /* Loop phi nodes should have only two arguments. */
2076 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2078 /* First edge is the init edge and second is the back edge. */
2079 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2081 /* First edge is the init edge and second is the back edge. */
2082 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2084 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2087 gphi
*phi
= psi
.phi ();
2088 tree res
= gimple_phi_result (phi
);
2089 if (virtual_operand_p (res
))
2091 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2094 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2095 tree new_res
= create_new_def_for (res
, new_phi
,
2096 gimple_phi_result_ptr (new_phi
));
2097 set_rename (res
, new_res
);
2098 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2100 update_stmt (new_phi
);
2104 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2105 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2112 /* Return the init value of PHI, the value coming from outside the loop. */
2115 get_loop_init_value (gphi
*phi
)
2118 loop_p loop
= gimple_bb (phi
)->loop_father
;
2122 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2123 if (e
->src
->loop_father
!= loop
)
2124 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2129 /* Find the init value (the value which comes from outside the loop), of one of
2130 the operands of DEF which is defined by a loop phi. */
2133 find_init_value (gimple
*def
)
2135 if (gimple_code (def
) == GIMPLE_PHI
)
2136 return get_loop_init_value (as_a
<gphi
*> (def
));
2138 if (gimple_vuse (def
))
2142 use_operand_p use_p
;
2143 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2145 tree use
= USE_FROM_PTR (use_p
);
2146 if (TREE_CODE (use
) == SSA_NAME
)
2148 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2156 /* Return the init value, the value coming from outside the loop. */
2159 find_init_value_close_phi (gphi
*phi
)
2161 gcc_assert (gimple_phi_num_args (phi
) == 1);
2162 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2163 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2164 return find_init_value (def
);
2168 tree
translate_isl_ast_to_gimple::
2169 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2170 gimple
*old_close_phi
)
2172 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2173 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2174 basic_block bb
= gimple_bb (stmt
);
2175 if (!bb_in_sese_p (bb
, codegen_region
))
2176 return last_merge_name
;
2178 loop_p loop
= bb
->loop_father
;
2179 if (!loop_in_sese_p (loop
, codegen_region
))
2180 return last_merge_name
;
2182 edge e
= single_exit (loop
);
2184 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2185 return last_merge_name
;
2187 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2188 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2191 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2192 bb
= split_edge (e
);
2194 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2195 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2196 gimple_phi_result_ptr (close_phi
));
2197 set_rename (old_close_phi_name
, res
);
2198 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2199 last_merge_name
= res
;
2201 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2204 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2205 the close phi node PHI. */
2207 bool translate_isl_ast_to_gimple::
2208 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2211 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2212 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2213 if (SSA_NAME
== TREE_CODE (default_value
))
2215 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2216 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2218 default_value_bb
= gimple_bb (stmt
);
2221 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2223 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2224 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2225 tree last_merge_name
= new_close_phi_name
;
2226 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2230 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2232 basic_block new_merge_bb
= merge_e
->src
;
2233 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2236 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2239 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2240 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2241 gimple_phi_result_ptr (merge_phi
));
2242 set_rename (old_close_phi_name
, merge_res
);
2244 edge from_loop
= NULL
, from_default_value
= NULL
;
2247 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2248 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2251 from_default_value
= e
;
2253 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2254 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2255 is contained in another condition. */
2256 if (!from_default_value
|| !from_loop
)
2259 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2260 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2264 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2265 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2268 update_stmt (merge_phi
);
2269 last_merge_name
= merge_res
;
2275 /* Copy all the loop-close phi args from BB to NEW_BB. */
2278 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2282 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2285 gphi
*old_close_phi
= psi
.phi ();
2286 tree res
= gimple_phi_result (old_close_phi
);
2287 if (virtual_operand_p (res
))
2290 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2291 /* Loop close phi nodes should not be scev_analyzable_p. */
2294 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2295 tree new_res
= create_new_def_for (res
, new_close_phi
,
2296 gimple_phi_result_ptr (new_close_phi
));
2297 set_rename (res
, new_res
);
2299 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2300 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2302 /* Predecessor basic blocks of a loop close phi should have been code
2303 generated before. FIXME: This is fixable by merging PHIs from inner
2304 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2308 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2309 get_loc (old_name
));
2312 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2313 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2316 update_stmt (new_close_phi
);
2318 /* When there is no loop guard around this codegenerated loop, there is no
2319 need to collect the close-phi arg. */
2320 if (merge_points
.is_empty ())
2323 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2324 tree default_value
= find_init_value_close_phi (new_close_phi
);
2326 /* A close phi must come from a loop-phi having a default value. */
2332 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2336 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2337 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2342 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2350 /* Copy loop close phi nodes from BB to NEW_BB. */
2353 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2357 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2359 /* Loop close phi nodes should have only one argument. */
2360 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2362 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2366 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2367 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2368 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2369 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2372 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2373 In this case DOMINATING_PRED = NULL.
2375 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2377 Returns true on successful copy of the args, false otherwise. */
2380 translate_isl_ast_to_gimple::
2381 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2382 edge old_bb_dominating_edge
,
2383 edge old_bb_non_dominating_edge
,
2384 gphi
*phi
, gphi
*new_phi
,
2387 basic_block def_pred
[2] = { NULL
, NULL
};
2388 int not_found_bb_index
= -1;
2389 for (int i
= 0; i
< 2; i
++)
2391 /* If the corresponding def_bb could not be found the entry will be
2393 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2394 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2395 gimple_phi_arg_edge (phi
, i
)->src
);
2396 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2397 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2401 /* When non are available bail out. */
2402 if (not_found_bb_index
!= -1)
2404 not_found_bb_index
= i
;
2408 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2409 if (old_bb_dominating_edge
)
2411 if (not_found_bb_index
!= -1)
2414 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2415 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2416 vec
<basic_block
> *bbs
2417 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2419 /* Could not find a mapping. */
2423 basic_block new_pred
= NULL
;
2426 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2428 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2430 /* FIXME: If we have already found new_pred then we have to
2431 disambiguate, bail out for now. */
2434 new_pred
= new_pred1
;
2436 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2438 /* FIXME: If we have already found new_pred then we have to either
2439 it dominates both or we have to disambiguate, bail out. */
2442 new_pred
= new_pred2
;
2449 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2450 gcc_assert (new_non_dominating_edge
);
2451 /* FIXME: Validate each args just like in loop-phis. */
2452 /* By the process of elimination we first insert insert phi-edge for
2453 non-dominating pred which is computed above and then we insert the
2455 int inserted_edge
= 0;
2456 for (; inserted_edge
< 2; inserted_edge
++)
2458 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2459 if (new_non_dominating_edge
== new_bb_pred_edge
)
2461 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2462 new_non_dominating_edge
,
2463 get_loc (old_phi_args
[inserted_edge
]));
2467 if (inserted_edge
== 2)
2470 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2472 edge new_dominating_edge
= NULL
;
2473 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2475 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2476 if (e
!= new_non_dominating_edge
)
2478 new_dominating_edge
= e
;
2479 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2480 new_dominating_edge
,
2481 get_loc (old_phi_args
[inserted_edge
]));
2485 gcc_assert (new_dominating_edge
);
2489 /* Classic diamond structure: both edges are non-dominating. We need to
2490 find one unique edge then the other can be found be elimination. If
2491 any definition (def_pred) dominates both the preds of new_bb then we
2492 bail out. Entries of def_pred maybe NULL, in that case we must
2493 uniquely find pred with help of only one entry. */
2494 edge new_e
[2] = { NULL
, NULL
};
2495 for (int i
= 0; i
< 2; i
++)
2499 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2501 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2504 /* We do not know how to handle the case when def_pred
2505 dominates more than a predecessor. */
2511 gcc_assert (new_e
[0] || new_e
[1]);
2513 /* Find the other edge by process of elimination. */
2514 if (not_found_bb_index
!= -1)
2516 gcc_assert (!new_e
[not_found_bb_index
]);
2517 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2520 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2522 if (new_e
[found_bb_index
] == e
)
2524 new_e
[not_found_bb_index
] = e
;
2528 /* Add edges to phi args. */
2529 for (int i
= 0; i
< 2; i
++)
2530 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2531 get_loc (old_phi_args
[i
]));
2537 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2538 region. If postpone is true and it isn't possible to copy any arg of PHI,
2539 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2540 Returns false if the copying was unsuccessful. */
2543 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2548 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2549 gcc_assert (2 == gimple_phi_num_args (phi
));
2551 basic_block new_bb
= gimple_bb (new_phi
);
2552 loop_p loop
= gimple_bb (phi
)->loop_father
;
2554 basic_block old_bb
= gimple_bb (phi
);
2555 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2559 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2560 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2561 old_bb_non_dominating_edge
= e
;
2563 old_bb_dominating_edge
= e
;
2565 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2566 old_bb_non_dominating_edge
->src
));
2568 tree new_phi_args
[2];
2569 tree old_phi_args
[2];
2571 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2573 tree old_name
= gimple_phi_arg_def (phi
, i
);
2574 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2575 old_phi_args
[i
] = old_name
;
2578 new_phi_args
[i
] = new_name
;
2582 /* If the phi-arg was a parameter. */
2583 if (vec_find (region
->params
, old_name
) != -1)
2585 new_phi_args
[i
] = old_name
;
2589 "[codegen] parameter argument to phi, new_expr: ");
2590 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2591 fprintf (dump_file
, "\n");
2596 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2597 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2598 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2604 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2605 if (is_gimple_reg (old_name
)
2606 && scev_analyzable_p (old_name
, region
->region
))
2609 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2610 new_bb
, old_bb
, iv_map
);
2611 if (codegen_error_p ())
2614 gcc_assert (new_expr
);
2618 "[codegen] scev analyzeable, new_expr: ");
2619 print_generic_expr (dump_file
, new_expr
, 0);
2620 fprintf (dump_file
, "\n");
2622 gsi_insert_earliest (stmts
);
2623 new_phi_args
[i
] = new_name
;
2627 /* Postpone code gen for later for back-edges. */
2628 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2632 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2633 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2636 new_phi_args
[i
] = NULL_TREE
;
2640 /* Either we should add the arg to phi or, we should postpone. */
2644 /* If none of the args have been determined in the first stage then wait until
2646 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2649 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2650 old_bb_dominating_edge
,
2651 old_bb_non_dominating_edge
,
2652 phi
, new_phi
, new_bb
);
2655 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2656 containing phi nodes coming from two predecessors, and none of them are back
2660 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2665 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2668 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2671 /* Cond phi nodes should have exactly two arguments. */
2672 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2674 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2677 gphi
*phi
= psi
.phi ();
2678 tree res
= gimple_phi_result (phi
);
2679 if (virtual_operand_p (res
))
2681 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2682 /* Cond phi nodes should not be scev_analyzable_p. */
2685 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2686 tree new_res
= create_new_def_for (res
, new_phi
,
2687 gimple_phi_result_ptr (new_phi
));
2688 set_rename (res
, new_res
);
2690 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2693 update_stmt (new_phi
);
2699 /* Return true if STMT should be copied from region to the new code-generated
2700 region. LABELs, CONDITIONS, induction-variables and region parameters need
2704 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2706 /* Do not copy labels or conditions. */
2707 if (gimple_code (stmt
) == GIMPLE_LABEL
2708 || gimple_code (stmt
) == GIMPLE_COND
)
2712 /* Do not copy induction variables. */
2713 if (is_gimple_assign (stmt
)
2714 && (lhs
= gimple_assign_lhs (stmt
))
2715 && TREE_CODE (lhs
) == SSA_NAME
2716 && is_gimple_reg (lhs
)
2717 && scev_analyzable_p (lhs
, region
->region
))
2723 /* Create new names for all the definitions created by COPY and add replacement
2724 mappings for each new name. */
2727 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2729 def_operand_p def_p
;
2730 ssa_op_iter op_iter
;
2731 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2733 tree old_name
= DEF_FROM_PTR (def_p
);
2734 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2735 set_rename (old_name
, new_name
);
2739 /* Duplicates the statements of basic block BB into basic block NEW_BB
2740 and compute the new induction variables according to the IV_MAP.
2741 CODEGEN_ERROR is set when the code generation cannot continue. */
2744 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2748 /* Iterator poining to the place where new statement (s) will be inserted. */
2749 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2751 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2754 gimple
*stmt
= gsi_stmt (gsi
);
2755 if (!should_copy_to_new_region (stmt
, region
))
2758 /* Create a new copy of STMT and duplicate STMT's virtual
2760 gimple
*copy
= gimple_copy (stmt
);
2761 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2765 fprintf (dump_file
, "[codegen] inserting statement: ");
2766 print_gimple_stmt (dump_file
, copy
, 0, 0);
2769 maybe_duplicate_eh_stmt (copy
, stmt
);
2770 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2772 /* Crete new names for each def in the copied stmt. */
2773 set_rename_for_each_def (copy
);
2775 loop_p loop
= bb
->loop_father
;
2776 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2778 fold_stmt_inplace (&gsi_tgt
);
2779 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2782 if (codegen_error_p ())
2792 /* Given a basic block containing close-phi it returns the new basic block where
2793 to insert a copy of the close-phi nodes. All the uses in close phis should
2794 come from a single loop otherwise it returns NULL. */
2797 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2799 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2800 of close phi in the original code and then find the mapping of basic block
2801 defining that variable. If there are multiple close-phis and they are
2802 defined in different loops (in the original or in the new code) because of
2803 loop splitting, then we bail out. */
2804 loop_p new_loop
= NULL
;
2805 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2808 gphi
*phi
= psi
.phi ();
2809 tree name
= gimple_phi_arg_def (phi
, 0);
2810 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2812 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2813 if (!bbs
|| bbs
->length () != 1)
2814 /* This is one of the places which shows preserving original structure
2815 is not always possible, as we may need to insert close PHI for a loop
2816 where the latch does not have any mapping, or the mapping is
2821 new_loop
= (*bbs
)[0]->loop_father
;
2822 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2829 return single_exit (new_loop
);
2832 /* Copies BB and includes in the copied BB all the statements that can
2833 be reached following the use-def chains from the memory accesses,
2834 and returns the next edge following this new block. codegen_error is
2835 set when the code generation cannot continue. */
2838 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2842 int num_phis
= number_of_phi_nodes (bb
);
2844 if (region
->copied_bb_map
->get (bb
))
2846 /* FIXME: we should be able to handle phi nodes with args coming from
2847 outside the region. */
2850 codegen_error
= true;
2855 basic_block new_bb
= NULL
;
2856 if (bb_contains_loop_close_phi_nodes (bb
))
2859 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2862 edge e
= edge_for_new_close_phis (bb
);
2865 codegen_error
= true;
2869 basic_block phi_bb
= e
->dest
;
2871 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2872 phi_bb
= split_edge (e
);
2874 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2875 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2877 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2879 codegen_error
= true;
2886 new_bb
= split_edge (next_e
);
2890 new_bb
= split_edge (next_e
);
2891 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2893 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2895 /* At this point we are unable to codegenerate by still preserving the SSA
2896 structure because maybe the loop is completely unrolled and the PHIs
2897 and cross-bb scalar dependencies are untrackable w.r.t. the original
2898 code. See gfortran.dg/graphite/pr29832.f90. */
2899 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2901 codegen_error
= true;
2905 /* In case ISL did some loop peeling, like this:
2908 for (int c1 = 1; c1 <= 5; c1 += 1) {
2913 there should be no loop-phi nodes in S_8(0).
2915 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2916 values of all scalar variables: for the moment we instantiate only
2917 SCEV analyzable expressions on the iteration domain, and we need to
2918 extend that to reductions that cannot be analyzed by SCEV. */
2919 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2921 codegen_error
= true;
2926 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2928 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2930 codegen_error
= true;
2934 else if (num_phis
> 0)
2937 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2940 basic_block phi_bb
= single_pred (new_bb
);
2941 loop_p loop_father
= new_bb
->loop_father
;
2943 /* Move back until we find the block with two predecessors. */
2944 while (single_pred_p (phi_bb
))
2945 phi_bb
= single_pred_edge (phi_bb
)->src
;
2947 /* If a corresponding merge-point was not found, then abort codegen. */
2948 if (phi_bb
->loop_father
!= loop_father
2949 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2950 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2952 codegen_error
= true;
2959 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2960 bb
->index
, new_bb
->index
);
2962 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2964 copied_bbs
->safe_push (new_bb
);
2967 vec
<basic_block
> bbs
;
2969 bbs
.safe_push (new_bb
);
2970 region
->copied_bb_map
->put (bb
, bbs
);
2973 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2975 codegen_error
= true;
2979 return single_succ_edge (new_bb
);
2982 /* Patch the missing arguments of the phi nodes. */
2985 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2989 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2991 gphi
*old_phi
= rename
->first
;
2992 gphi
*new_phi
= rename
->second
;
2993 basic_block old_bb
= gimple_bb (old_phi
);
2994 basic_block new_bb
= gimple_bb (new_phi
);
2996 /* First edge is the init edge and second is the back edge. */
2997 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2998 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3002 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3003 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3006 auto_vec
<tree
, 1> iv_map
;
3007 if (bb_contains_loop_phi_nodes (new_bb
))
3008 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3010 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3011 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3013 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3017 fprintf (dump_file
, "[codegen] to new-phi: ");
3018 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3025 /* Prints NODE to FILE. */
3028 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3029 __isl_keep isl_ast_node
*node
,
3030 __isl_keep isl_ctx
*ctx
) const
3032 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3033 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3034 prn
= isl_printer_print_ast_node (prn
, node
);
3035 prn
= isl_printer_print_str (prn
, "\n");
3036 isl_printer_free (prn
);
3039 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
3042 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3045 sese_info_p region
= scop
->scop_info
;
3046 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3047 gcc_assert (nb_parameters
== region
->params
.length ());
3049 for (i
= 0; i
< nb_parameters
; i
++)
3051 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3053 ip
[tmp_id
] = region
->params
[i
];
3058 /* Generates a build, which specifies the constraints on the parameters. */
3060 __isl_give isl_ast_build
*
3061 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3063 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3064 return isl_ast_build_from_context (context_isl
);
3067 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3070 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3074 int schedule_dims
= 0;
3076 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3078 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3079 if (pbb_schedule_dims
> schedule_dims
)
3080 schedule_dims
= pbb_schedule_dims
;
3083 return schedule_dims
;
3086 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3088 For schedules with different dimensionality, the isl AST generator can not
3089 define an order and will just randomly choose an order. The solution to this
3090 problem is to extend all schedules to the maximal number of schedule
3091 dimensions (using '0's for the remaining values). */
3093 __isl_give isl_map
*
3094 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3095 int nb_schedule_dims
)
3097 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3099 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3101 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3103 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3106 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3108 isl_val_free (zero
);
3112 /* Generates a schedule, which specifies an order used to
3113 visit elements in a domain. */
3115 __isl_give isl_union_map
*
3116 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3118 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3121 isl_union_map
*schedule_isl
=
3122 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3124 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3126 /* Dead code elimination: when the domain of a PBB is empty,
3127 don't generate code for the PBB. */
3128 if (isl_set_is_empty (pbb
->domain
))
3131 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3132 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3133 isl_set_copy (pbb
->domain
));
3134 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3136 = isl_union_map_union (schedule_isl
,
3137 isl_union_map_from_map (bb_schedule
));
3139 return schedule_isl
;
3142 /* This method is executed before the construction of a for node. */
3144 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3146 isl_union_map
*dependences
= (isl_union_map
*) user
;
3147 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3148 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3149 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3150 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3151 for_info
->is_parallelizable
=
3152 !carries_deps (schedule
, dependences
, dimension
);
3153 isl_union_map_free (schedule
);
3154 isl_space_free (schedule_space
);
3155 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3159 /* Set the separate option for all dimensions.
3160 This helps to reduce control overhead. */
3162 __isl_give isl_ast_build
*
3163 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3164 __isl_keep isl_union_map
*schedule
)
3166 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3167 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3169 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3170 isl_union_set
*range
=
3171 isl_union_set_from_set (isl_set_universe (range_space
));
3172 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3173 domain
= isl_union_set_universe (domain
);
3174 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3175 return isl_ast_build_set_options (control
, options
);
3178 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3180 __isl_give isl_ast_node
*
3181 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3183 /* Generate loop upper bounds that consist of the current loop iterator, an
3184 operator (< or <=) and an expression not involving the iterator. If this
3185 option is not set, then the current loop iterator may appear several times
3186 in the upper bound. See the isl manual for more details. */
3187 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3189 add_parameters_to_ivs_params (scop
, ip
);
3190 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3191 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3192 context_isl
= set_options (context_isl
, schedule_isl
);
3193 isl_union_map
*dependences
= NULL
;
3194 if (flag_loop_parallelize_all
)
3196 dependences
= scop_get_dependences (scop
);
3198 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3201 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3204 isl_union_map_free (dependences
);
3205 isl_ast_build_free (context_isl
);
3209 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3210 the given SCOP. Return true if code generation succeeded.
3212 FIXME: This is not yet a full implementation of the code generator
3213 with ISL ASTs. Generation of GIMPLE code has to be completed. */
3216 graphite_regenerate_ast_isl (scop_p scop
)
3218 sese_info_p region
= scop
->scop_info
;
3219 translate_isl_ast_to_gimple
t (region
);
3221 ifsese if_region
= NULL
;
3222 isl_ast_node
*root_node
;
3225 timevar_push (TV_GRAPHITE_CODE_GEN
);
3226 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3228 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3230 fprintf (dump_file
, "ISL AST generated by ISL: \n");
3231 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3234 recompute_all_dominators ();
3237 if_region
= move_sese_in_condition (region
);
3238 region
->if_region
= if_region
;
3239 recompute_all_dominators ();
3241 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3243 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3244 basic_block bb
= split_edge (e
);
3246 /* Update the true_region exit edge. */
3247 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3249 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3250 if (t
.codegen_error_p ())
3253 fprintf (dump_file
, "[codegen] unsuccessful,"
3254 " reverting back to the original code.\n");
3255 set_ifsese_condition (if_region
, integer_zero_node
);
3259 t
.translate_pending_phi_nodes ();
3260 if (!t
.codegen_error_p ())
3262 sese_insert_phis_for_liveouts (region
,
3263 if_region
->region
->region
.exit
->src
,
3264 if_region
->false_region
->region
.exit
,
3265 if_region
->true_region
->region
.exit
);
3266 mark_virtual_operands_for_renaming (cfun
);
3267 update_ssa (TODO_update_ssa
);
3272 recompute_all_dominators ();
3278 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3279 " pending phis, reverting back to the original code.\n");
3280 set_ifsese_condition (if_region
, integer_zero_node
);
3284 free (if_region
->true_region
);
3285 free (if_region
->region
);
3288 ivs_params_clear (ip
);
3289 isl_ast_node_free (root_node
);
3290 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3295 int num_no_dependency
= 0;
3297 FOR_EACH_LOOP (loop
, 0)
3298 if (loop
->can_be_parallel
)
3299 num_no_dependency
++;
3301 fprintf (dump_file
, "%d loops carried no dependency.\n",
3305 return !t
.codegen_error_p ();
3308 #endif /* HAVE_isl */