1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
34 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
40 #include "tree-ssa-loop.h"
41 #include "tree-ssa-operands.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-pass.h"
45 #include "tree-data-ref.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-scalar-evolution.h"
48 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "tree-into-ssa.h"
51 #include "ssa-iterators.h"
53 #include "gimple-pretty-print.h"
55 #include "value-prof.h"
57 #include <isl/constraint.h>
59 #include <isl/union_set.h>
61 #include <isl/union_map.h>
62 #include <isl/ast_build.h>
64 /* Since ISL-0.13, the extern is in val_gmp.h. */
65 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
68 #include <isl/val_gmp.h>
69 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
77 /* We always try to use signed 128 bit types, but fall back to smaller types
78 in case a platform does not provide types of these sizes. In the future we
79 should use isl to derive the optimal type for each subexpression. */
81 static int max_mode_int_precision
=
82 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
83 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
84 128 : max_mode_int_precision
;
89 : is_parallelizable(false)
91 bool is_parallelizable
;
94 /* Converts a GMP constant VAL to a tree and returns it. */
97 gmp_cst_to_tree (tree type
, mpz_t val
)
99 tree t
= type
? type
: integer_type_node
;
104 wide_int wi
= wi::from_mpz (t
, tmp
, true);
107 return wide_int_to_tree (t
, wi
);
110 /* Verifies properties that GRAPHITE should maintain during translation. */
113 graphite_verify (void)
115 checking_verify_loop_structure ();
116 checking_verify_loop_closed_ssa (true);
119 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
120 to corresponding trees. */
122 typedef std::map
<isl_id
*, tree
> ivs_params
;
124 /* Free all memory allocated for ISL's identifiers. */
126 void ivs_params_clear (ivs_params
&ip
)
128 std::map
<isl_id
*, tree
>::iterator it
;
129 for (it
= ip
.begin ();
130 it
!= ip
.end (); it
++)
132 isl_id_free (it
->first
);
136 class translate_isl_ast_to_gimple
139 translate_isl_ast_to_gimple (sese_info_p r
)
140 : region (r
), codegen_error (false)
143 /* Translates an ISL AST node NODE to GCC representation in the
144 context of a SESE. */
145 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
146 edge next_e
, ivs_params
&ip
);
148 /* Translates an isl_ast_node_for to Gimple. */
149 edge
translate_isl_ast_node_for (loop_p context_loop
,
150 __isl_keep isl_ast_node
*node
,
151 edge next_e
, ivs_params
&ip
);
153 /* Create the loop for a isl_ast_node_for.
155 - NEXT_E is the edge where new generated code should be attached. */
156 edge
translate_isl_ast_for_loop (loop_p context_loop
,
157 __isl_keep isl_ast_node
*node_for
,
159 tree type
, tree lb
, tree ub
,
162 /* Translates an isl_ast_node_if to Gimple. */
163 edge
translate_isl_ast_node_if (loop_p context_loop
,
164 __isl_keep isl_ast_node
*node
,
165 edge next_e
, ivs_params
&ip
);
167 /* Translates an isl_ast_node_user to Gimple.
169 FIXME: We should remove iv_map.create (loop->num + 1), if it is
171 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
174 /* Translates an isl_ast_node_block to Gimple. */
175 edge
translate_isl_ast_node_block (loop_p context_loop
,
176 __isl_keep isl_ast_node
*node
,
177 edge next_e
, ivs_params
&ip
);
179 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
181 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
184 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
186 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
189 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
191 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
194 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
195 to a GCC expression tree of type TYPE. */
196 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
199 /* Converts an ISL AST expression E back to a GCC expression tree of
201 tree
gcc_expression_from_isl_expression (tree type
,
202 __isl_take isl_ast_expr
*,
205 /* Return the tree variable that corresponds to the given isl ast identifier
206 expression (an isl_ast_expr of type isl_ast_expr_id).
208 FIXME: We should replace blind conversation of id's type with derivation
209 of the optimal type when we get the corresponding isl support. Blindly
210 converting type sizes may be problematic when we switch to smaller
212 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
213 __isl_keep isl_ast_expr
*expr_id
,
216 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
218 tree
gcc_expression_from_isl_expr_int (tree type
,
219 __isl_take isl_ast_expr
*expr
);
221 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
223 tree
gcc_expression_from_isl_expr_op (tree type
,
224 __isl_take isl_ast_expr
*expr
,
227 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
228 induction variable for the new LOOP. New LOOP is attached to CFG
229 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
230 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
231 ISL's scattering name to the induction variable created for the
232 loop of STMT. The new induction variable is inserted in the NEWIVS
233 vector and is of type TYPE. */
234 struct loop
*graphite_create_new_loop (edge entry_edge
,
235 __isl_keep isl_ast_node
*node_for
,
236 loop_p outer
, tree type
,
237 tree lb
, tree ub
, ivs_params
&ip
);
239 /* All loops generated by create_empty_loop_on_edge have the form of
246 } while (lower bound < upper bound);
248 We create a new if region protecting the loop to be executed, if
249 the execution count is zero (lower bound > upper bound). */
250 edge
graphite_create_new_loop_guard (edge entry_edge
,
251 __isl_keep isl_ast_node
*node_for
,
253 tree
*lb
, tree
*ub
, ivs_params
&ip
);
255 /* Creates a new if region corresponding to ISL's cond. */
256 edge
graphite_create_new_guard (edge entry_edge
,
257 __isl_take isl_ast_expr
*if_cond
,
260 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
261 variables of the loops around GBB in SESE.
263 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
264 chrec, we could consider using a map<int, tree> that maps loop ids to the
265 corresponding tree expressions. */
266 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
267 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
270 /* Patch the missing arguments of the phi nodes. */
272 void translate_pending_phi_nodes (void);
274 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
276 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
278 /* Get the maximal number of schedule dimensions in the scop SCOP. */
280 int get_max_schedule_dimensions (scop_p scop
);
282 /* Generates a build, which specifies the constraints on the parameters. */
284 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
286 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
288 For schedules with different dimensionality, the isl AST generator can not
289 define an order and will just randomly choose an order. The solution to
290 this problem is to extend all schedules to the maximal number of schedule
291 dimensions (using '0's for the remaining values). */
293 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
294 int nb_schedule_dims
);
296 /* Generates a schedule, which specifies an order used to
297 visit elements in a domain. */
299 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
301 /* Set the separate option for all dimensions.
302 This helps to reduce control overhead. */
304 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
305 __isl_keep isl_union_map
*schedule
);
307 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
310 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
313 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
314 definition should flow into use, and the use should respect the loop-closed
317 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
318 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
320 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
321 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
322 within a loop PHI instruction. */
324 tree
get_rename (basic_block new_bb
, tree old_name
,
325 basic_block old_bb
, bool loop_phi
) const;
327 /* For ops which are scev_analyzeable, we can regenerate a new name from
328 its scalar evolution around LOOP. */
330 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
331 basic_block new_bb
, basic_block old_bb
,
334 /* Returns a basic block that could correspond to where a constant was defined
335 in the original code. In the original code OLD_BB had the definition, we
336 need to find which basic block out of the copies of old_bb, in the new
337 region, should a definition correspond to if it has to reach BB. */
339 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
341 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
342 true when we want to rename an OP within a loop PHI instruction. */
344 tree
get_new_name (basic_block new_bb
, tree op
,
345 basic_block old_bb
, bool loop_phi
) const;
347 /* Collect all the operands of NEW_EXPR by recursively visiting each
350 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
352 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
353 NEW_PHI must be found unless they can be POSTPONEd for later. */
355 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
356 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
359 /* Copy loop phi nodes from BB to NEW_BB. */
361 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
363 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
364 the close phi node PHI. */
366 bool add_close_phis_to_merge_points (gphi
*old_phi
, gphi
*new_phi
,
369 tree
add_close_phis_to_outer_loops (tree last_merge_name
, edge merge_e
,
370 gimple
*old_close_phi
);
372 /* Copy all the loop-close phi args from BB to NEW_BB. */
374 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
377 /* Copy loop close phi nodes from BB to NEW_BB. */
379 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
381 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
382 region. If postpone is true and it isn't possible to copy any arg of PHI,
383 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
384 Returns false if the copying was unsuccessful. */
386 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
389 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
390 containing phi nodes coming from two predecessors, and none of them are back
393 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
396 /* Duplicates the statements of basic block BB into basic block NEW_BB
397 and compute the new induction variables according to the IV_MAP.
398 CODEGEN_ERROR is set when the code generation cannot continue. */
400 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
403 /* Copies BB and includes in the copied BB all the statements that can
404 be reached following the use-def chains from the memory accesses,
405 and returns the next edge following this new block. codegen_error is
406 set when the code generation cannot continue. */
408 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
411 /* Given a basic block containing close-phi it returns the new basic block
412 where to insert a copy of the close-phi nodes. All the uses in close phis
413 should come from a single loop otherwise it returns NULL. */
414 edge
edge_for_new_close_phis (basic_block bb
);
416 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
417 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
418 the other pred of OLD_BB as well. If no such basic block exists then it is
419 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
422 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
423 versa. In this case DOMINATING_PRED = NULL.
425 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
427 Returns true on successful copy of the args, false otherwise. */
429 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
430 edge old_bb_dominating_edge
,
431 edge old_bb_non_dominating_edge
,
432 gphi
*phi
, gphi
*new_phi
,
435 /* Renames the scalar uses of the statement COPY, using the substitution map
436 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
437 translation REGION, with the original copied statement in LOOP, and using
438 the induction variable renaming map IV_MAP. Returns true when something
439 has been renamed. codegen_error is set when the code generation cannot
442 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
443 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
445 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
446 When OLD_NAME and EXPR are the same we assert. */
448 void set_rename (tree old_name
, tree expr
);
450 /* Create new names for all the definitions created by COPY and add
451 replacement mappings for each new name. */
453 void set_rename_for_each_def (gimple
*stmt
);
455 /* Insert each statement from SEQ at its earliest insertion p. */
457 void gsi_insert_earliest (gimple_seq seq
);
459 /* Rename all the operands of NEW_EXPR by recursively visiting each
462 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
464 bool codegen_error_p () const
465 { return codegen_error
; }
467 /* Prints NODE to FILE. */
469 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
470 __isl_keep isl_ctx
*ctx
) const;
472 /* Return true when OP is a constant tree. */
474 bool is_constant (tree op
) const
476 return TREE_CODE (op
) == INTEGER_CST
477 || TREE_CODE (op
) == REAL_CST
478 || TREE_CODE (op
) == COMPLEX_CST
479 || TREE_CODE (op
) == VECTOR_CST
;
483 /* The region to be translated. */
486 /* This flag is set when an error occurred during the translation of ISL AST
490 /* A vector of all the edges at if_condition merge points. */
491 auto_vec
<edge
, 2> merge_points
;
494 /* Return the tree variable that corresponds to the given isl ast identifier
495 expression (an isl_ast_expr of type isl_ast_expr_id).
497 FIXME: We should replace blind conversation of id's type with derivation
498 of the optimal type when we get the corresponding isl support. Blindly
499 converting type sizes may be problematic when we switch to smaller
503 translate_isl_ast_to_gimple::
504 gcc_expression_from_isl_ast_expr_id (tree type
,
505 __isl_take isl_ast_expr
*expr_id
,
508 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
509 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
510 std::map
<isl_id
*, tree
>::iterator res
;
511 res
= ip
.find (tmp_isl_id
);
512 isl_id_free (tmp_isl_id
);
513 gcc_assert (res
!= ip
.end () &&
514 "Could not map isl_id to tree expression");
515 isl_ast_expr_free (expr_id
);
516 tree t
= res
->second
;
517 return fold_convert (type
, t
);
520 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
524 translate_isl_ast_to_gimple::
525 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
527 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
528 isl_val
*val
= isl_ast_expr_get_val (expr
);
530 mpz_init (val_mpz_t
);
532 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
535 res
= gmp_cst_to_tree (type
, val_mpz_t
);
537 isl_ast_expr_free (expr
);
538 mpz_clear (val_mpz_t
);
542 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
546 translate_isl_ast_to_gimple::
547 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
549 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
550 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
551 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
552 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
554 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
555 isl_ast_expr_free (expr
);
563 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
566 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
569 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
572 /* As ISL operates on arbitrary precision numbers, we may end up with
573 division by 2^64 that is folded to 0. */
574 if (integer_zerop (tree_rhs_expr
))
576 codegen_error
= true;
579 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
581 case isl_ast_op_pdiv_q
:
582 /* As ISL operates on arbitrary precision numbers, we may end up with
583 division by 2^64 that is folded to 0. */
584 if (integer_zerop (tree_rhs_expr
))
586 codegen_error
= true;
589 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
591 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
592 case isl_ast_op_zdiv_r
:
594 case isl_ast_op_pdiv_r
:
595 /* As ISL operates on arbitrary precision numbers, we may end up with
596 division by 2^64 that is folded to 0. */
597 if (integer_zerop (tree_rhs_expr
))
599 codegen_error
= true;
602 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
604 case isl_ast_op_fdiv_q
:
605 /* As ISL operates on arbitrary precision numbers, we may end up with
606 division by 2^64 that is folded to 0. */
607 if (integer_zerop (tree_rhs_expr
))
609 codegen_error
= true;
612 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
615 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
616 tree_lhs_expr
, tree_rhs_expr
);
619 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
622 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
625 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
628 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
631 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
634 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
641 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
645 translate_isl_ast_to_gimple::
646 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
648 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
649 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
651 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
652 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
653 tree tree_second_expr
654 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
655 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
657 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
658 isl_ast_expr_free (expr
);
662 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
663 tree_second_expr
, tree_third_expr
);
666 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
670 translate_isl_ast_to_gimple::
671 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
673 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
674 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
675 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
676 isl_ast_expr_free (expr
);
677 return codegen_error
? NULL_TREE
: fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
680 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
681 to a GCC expression tree of type TYPE. */
684 translate_isl_ast_to_gimple::
685 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
687 enum tree_code op_code
;
688 switch (isl_ast_expr_get_op_type (expr
))
701 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
702 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
706 isl_ast_expr_free (expr
);
711 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
713 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
714 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
718 isl_ast_expr_free (expr
);
722 res
= fold_build2 (op_code
, type
, res
, t
);
724 isl_ast_expr_free (expr
);
728 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
732 translate_isl_ast_to_gimple::
733 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
738 isl_ast_expr_free (expr
);
742 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
743 switch (isl_ast_expr_get_op_type (expr
))
745 /* These isl ast expressions are not supported yet. */
746 case isl_ast_op_error
:
747 case isl_ast_op_call
:
748 case isl_ast_op_and_then
:
749 case isl_ast_op_or_else
:
750 case isl_ast_op_select
:
755 return nary_op_to_tree (type
, expr
, ip
);
761 case isl_ast_op_pdiv_q
:
762 case isl_ast_op_pdiv_r
:
763 case isl_ast_op_fdiv_q
:
764 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
765 case isl_ast_op_zdiv_r
:
774 return binary_op_to_tree (type
, expr
, ip
);
776 case isl_ast_op_minus
:
777 return unary_op_to_tree (type
, expr
, ip
);
779 case isl_ast_op_cond
:
780 return ternary_op_to_tree (type
, expr
, ip
);
789 /* Converts an ISL AST expression E back to a GCC expression tree of
793 translate_isl_ast_to_gimple::
794 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
799 isl_ast_expr_free (expr
);
803 switch (isl_ast_expr_get_type (expr
))
805 case isl_ast_expr_id
:
806 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
808 case isl_ast_expr_int
:
809 return gcc_expression_from_isl_expr_int (type
, expr
);
811 case isl_ast_expr_op
:
812 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
821 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
822 induction variable for the new LOOP. New LOOP is attached to CFG
823 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
824 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
825 ISL's scattering name to the induction variable created for the
826 loop of STMT. The new induction variable is inserted in the NEWIVS
827 vector and is of type TYPE. */
830 translate_isl_ast_to_gimple::
831 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
832 loop_p outer
, tree type
, tree lb
, tree ub
,
835 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
836 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
838 /* To fail code generation, we generate wrong code until we discard it. */
840 stride
= integer_zero_node
;
842 tree ivvar
= create_tmp_var (type
, "graphite_IV");
843 tree iv
, iv_after_increment
;
844 loop_p loop
= create_empty_loop_on_edge
845 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
846 outer
? outer
: entry_edge
->src
->loop_father
);
848 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
849 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
850 std::map
<isl_id
*, tree
>::iterator res
;
853 isl_id_free (res
->first
);
855 isl_ast_expr_free (for_iterator
);
859 /* Create the loop for a isl_ast_node_for.
861 - NEXT_E is the edge where new generated code should be attached. */
864 translate_isl_ast_to_gimple::
865 translate_isl_ast_for_loop (loop_p context_loop
,
866 __isl_keep isl_ast_node
*node_for
, edge next_e
,
867 tree type
, tree lb
, tree ub
,
870 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
871 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
873 edge last_e
= single_exit (loop
);
874 edge to_body
= single_succ_edge (loop
->header
);
875 basic_block after
= to_body
->dest
;
877 /* Translate the body of the loop. */
878 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
879 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
880 isl_ast_node_free (for_body
);
882 /* Early return if we failed to translate loop body. */
883 if (!next_e
|| codegen_error_p ())
886 if (next_e
->dest
!= after
)
887 redirect_edge_succ_nodup (next_e
, after
);
888 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
890 if (flag_loop_parallelize_all
)
892 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
894 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
895 loop
->can_be_parallel
= for_info
->is_parallelizable
;
903 /* We use this function to get the upper bound because of the form,
904 which is used by isl to represent loops:
906 for (iterator = init; cond; iterator += inc)
914 The loop condition is an arbitrary expression, which contains the
915 current loop iterator.
917 (e.g. iterator + 3 < B && C > iterator + A)
919 We have to know the upper bound of the iterator to generate a loop
920 in Gimple form. It can be obtained from the special representation
921 of the loop condition, which is generated by isl,
922 if the ast_build_atomic_upper_bound option is set. In this case,
923 isl generates a loop condition that consists of the current loop
924 iterator, + an operator (< or <=) and an expression not involving
925 the iterator, which is processed and returned by this function.
927 (e.g iterator <= upper-bound-expression-without-iterator) */
929 static __isl_give isl_ast_expr
*
930 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
932 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
933 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
934 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
936 switch (isl_ast_expr_get_op_type (for_cond
))
939 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
944 /* (iterator < ub) => (iterator <= ub - 1). */
946 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
947 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
948 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
955 isl_ast_expr_free (for_cond
);
959 /* All loops generated by create_empty_loop_on_edge have the form of
966 } while (lower bound < upper bound);
968 We create a new if region protecting the loop to be executed, if
969 the execution count is zero (lower bound > upper bound). */
972 translate_isl_ast_to_gimple::
973 graphite_create_new_loop_guard (edge entry_edge
,
974 __isl_keep isl_ast_node
*node_for
, tree
*type
,
975 tree
*lb
, tree
*ub
, ivs_params
&ip
)
977 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
982 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
983 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
984 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
985 /* To fail code generation, we generate wrong code until we discard it. */
987 *lb
= integer_zero_node
;
988 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
989 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
990 /* To fail code generation, we generate wrong code until we discard it. */
992 *ub
= integer_zero_node
;
994 /* When ub is simply a constant or a parameter, use lb <= ub. */
995 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
996 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
999 tree one
= (POINTER_TYPE_P (*type
)
1000 ? convert_to_ptrofftype (integer_one_node
)
1001 : fold_convert (*type
, integer_one_node
));
1002 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1003 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
1004 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
1005 is true, even if we do not want this. However lb < ub + 1 is false,
1007 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
1008 : PLUS_EXPR
, *type
, *ub
, one
);
1010 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
1013 if (integer_onep (cond_expr
))
1014 exit_edge
= entry_edge
;
1016 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1021 /* Translates an isl_ast_node_for to Gimple. */
1024 translate_isl_ast_to_gimple::
1025 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
1026 edge next_e
, ivs_params
&ip
)
1028 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
1030 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
1033 if (last_e
== next_e
)
1035 /* There was no guard generated. */
1036 last_e
= single_succ_edge (split_edge (last_e
));
1038 translate_isl_ast_for_loop (context_loop
, node
, next_e
,
1043 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1044 merge_points
.safe_push (last_e
);
1046 last_e
= single_succ_edge (split_edge (last_e
));
1047 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
1052 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
1053 variables of the loops around GBB in SESE.
1055 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
1056 chrec, we could consider using a map<int, tree> that maps loop ids to the
1057 corresponding tree expressions. */
1060 translate_isl_ast_to_gimple::
1061 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
1062 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
1065 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
1066 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
1068 isl_ast_expr
*arg_expr
;
1069 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
1071 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
1073 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1074 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
1075 /* To fail code generation, we generate wrong code until we discard it. */
1077 t
= integer_zero_node
;
1079 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
1080 iv_map
[old_loop
->num
] = t
;
1084 /* Translates an isl_ast_node_user to Gimple.
1086 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
1089 translate_isl_ast_to_gimple::
1090 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
1091 edge next_e
, ivs_params
&ip
)
1093 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
1095 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
1096 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
1097 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
1099 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
1100 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
1103 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1105 isl_ast_expr_free (name_expr
);
1106 isl_id_free (name_id
);
1108 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1109 "The entry block should not even appear within a scop");
1111 const int nb_loops
= number_of_loops (cfun
);
1113 iv_map
.create (nb_loops
);
1114 iv_map
.safe_grow_cleared (nb_loops
);
1116 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1117 isl_ast_expr_free (user_expr
);
1121 fprintf (dump_file
, "[codegen] copying from basic block\n");
1122 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1123 fprintf (dump_file
, "[codegen] to new basic block\n");
1124 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1127 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1132 if (codegen_error_p ())
1137 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1138 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1144 /* Translates an isl_ast_node_block to Gimple. */
1147 translate_isl_ast_to_gimple::
1148 translate_isl_ast_node_block (loop_p context_loop
,
1149 __isl_keep isl_ast_node
*node
,
1150 edge next_e
, ivs_params
&ip
)
1152 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1153 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1155 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1157 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1158 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1159 isl_ast_node_free (tmp_node
);
1161 isl_ast_node_list_free (node_list
);
1165 /* Creates a new if region corresponding to ISL's cond. */
1168 translate_isl_ast_to_gimple::
1169 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1173 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1174 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1175 /* To fail code generation, we generate wrong code until we discard it. */
1177 cond_expr
= integer_zero_node
;
1179 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1183 /* Translates an isl_ast_node_if to Gimple. */
1186 translate_isl_ast_to_gimple::
1187 translate_isl_ast_node_if (loop_p context_loop
,
1188 __isl_keep isl_ast_node
*node
,
1189 edge next_e
, ivs_params
&ip
)
1191 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1192 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1193 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1194 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1195 merge_points
.safe_push (last_e
);
1197 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1198 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1199 isl_ast_node_free (then_node
);
1201 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1202 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1203 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1204 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1206 isl_ast_node_free (else_node
);
1210 /* Translates an ISL AST node NODE to GCC representation in the
1211 context of a SESE. */
1214 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1215 __isl_keep isl_ast_node
*node
,
1216 edge next_e
, ivs_params
&ip
)
1218 if (codegen_error_p ())
1221 switch (isl_ast_node_get_type (node
))
1223 case isl_ast_node_error
:
1226 case isl_ast_node_for
:
1227 return translate_isl_ast_node_for (context_loop
, node
,
1230 case isl_ast_node_if
:
1231 return translate_isl_ast_node_if (context_loop
, node
,
1234 case isl_ast_node_user
:
1235 return translate_isl_ast_node_user (node
, next_e
, ip
);
1237 case isl_ast_node_block
:
1238 return translate_isl_ast_node_block (context_loop
, node
,
1246 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1247 at the exit of loop which takes one argument that is the last value of the
1248 variable being used out of the loop. */
1251 bb_contains_loop_close_phi_nodes (basic_block bb
)
1253 return single_pred_p (bb
)
1254 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1257 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1258 header containing phi nodes which has one init-edge and one back-edge. */
1261 bb_contains_loop_phi_nodes (basic_block bb
)
1263 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1265 if (bb
->preds
->length () == 1)
1268 unsigned depth
= loop_depth (bb
->loop_father
);
1270 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1272 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1273 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1276 /* When one of the edges correspond to the same loop father and other
1278 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1279 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1282 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1283 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1289 /* Check if USE is defined in a basic block from where the definition of USE can
1290 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1293 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1295 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1298 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1299 if (bb_contains_loop_close_phi_nodes (bb
))
1302 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1303 basic_block def_bb
= gimple_bb (def
);
1305 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1308 /* Return the number of phi nodes in BB. */
1311 number_of_phi_nodes (basic_block bb
)
1314 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1320 /* Returns true if BB uses name in one of its PHIs. */
1323 phi_uses_name (basic_block bb
, tree name
)
1325 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1328 gphi
*phi
= psi
.phi ();
1329 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1331 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1332 if (use_arg
== name
)
1339 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1340 definition should flow into use, and the use should respect the loop-closed
1344 translate_isl_ast_to_gimple::
1345 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1346 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1348 /* The def of the rename must either dominate the uses or come from a
1349 back-edge. Also the def must respect the loop closed ssa form. */
1350 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1354 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1355 print_generic_expr (dump_file
, rename
, 0);
1356 fprintf (dump_file
, "\n");
1361 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1364 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1366 /* The loop-header dominates the loop-body. */
1367 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1370 /* RENAME would be used in loop-phi. */
1371 gcc_assert (number_of_phi_nodes (use_bb
));
1373 /* For definitions coming from back edges, we should check that
1374 old_name is used in a loop PHI node.
1375 FIXME: Verify if this is true. */
1376 if (phi_uses_name (old_bb
, old_name
))
1382 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1383 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1384 within a loop PHI instruction. */
1387 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1390 bool loop_phi
) const
1392 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1393 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1395 if (!renames
|| renames
->is_empty ())
1398 if (1 == renames
->length ())
1400 tree rename
= (*renames
)[0];
1401 if (TREE_CODE (rename
) == SSA_NAME
)
1403 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1404 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1409 if (is_constant (rename
))
1415 /* More than one renames corresponding to the old_name. Find the rename for
1416 which the definition flows into usage at new_bb. */
1418 tree t1
= NULL_TREE
, t2
;
1419 basic_block t1_bb
= NULL
;
1420 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1422 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1424 /* Defined in the same basic block as used. */
1425 if (t2_bb
== new_bb
)
1428 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1429 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1432 /* Compute the nearest dominator. */
1433 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1443 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1444 When OLD_NAME and EXPR are the same we assert. */
1447 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1451 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1452 print_generic_expr (dump_file
, old_name
, 0);
1453 fprintf (dump_file
, ", new_name = ");
1454 print_generic_expr (dump_file
, expr
, 0);
1455 fprintf (dump_file
, "\n");
1458 if (old_name
== expr
)
1461 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1464 renames
->safe_push (expr
);
1470 region
->rename_map
->put (old_name
, r
);
1474 /* Return an iterator to the instructions comes last in the execution order.
1475 Either GSI1 and GSI2 should belong to the same basic block or one of their
1476 respective basic blocks should dominate the other. */
1478 gimple_stmt_iterator
1479 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1481 basic_block bb1
= gsi_bb (gsi1
);
1482 basic_block bb2
= gsi_bb (gsi2
);
1484 /* Find the iterator which is the latest. */
1487 /* For empty basic blocks gsis point to the end of the sequence. Since
1488 there is no operator== defined for gimple_stmt_iterator and for gsis
1489 not pointing to a valid statement gsi_next would assert. */
1490 gimple_stmt_iterator gsi
= gsi1
;
1492 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1495 } while (!gsi_end_p (gsi
));
1500 /* Find the basic block closest to the basic block which defines stmt. */
1501 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1504 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1508 /* Insert each statement from SEQ at its earliest insertion p. */
1511 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1513 update_modified_stmts (seq
);
1514 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1515 basic_block begin_bb
= get_entry_bb (codegen_region
);
1517 /* Inserting the gimple statements in a vector because gimple_seq behave
1518 in strage ways when inserting the stmts from it into different basic
1519 blocks one at a time. */
1520 auto_vec
<gimple
*, 3> stmts
;
1521 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1523 stmts
.safe_push (gsi_stmt (gsi
));
1527 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1529 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1530 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1532 use_operand_p use_p
;
1533 ssa_op_iter op_iter
;
1534 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1536 /* Iterator to the current def of use_p. For function parameters or
1537 anything where def is not found, insert at the beginning of the
1538 generated region. */
1539 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1541 tree op
= USE_FROM_PTR (use_p
);
1542 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1543 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1544 gsi_stmt
= gsi_for_stmt (stmt
);
1546 /* For region parameters, insert at the beginning of the generated
1548 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1549 gsi_stmt
= gsi_def_stmt
;
1551 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1554 if (!gsi_stmt (gsi_def_stmt
))
1556 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1557 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1559 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1561 gimple_stmt_iterator bsi
1562 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1563 /* Insert right after the PHI statements. */
1564 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1567 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1571 fprintf (dump_file
, "[codegen] inserting statement: ");
1572 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1573 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1578 /* Collect all the operands of NEW_EXPR by recursively visiting each
1582 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1586 /* Rename all uses in new_expr. */
1587 if (TREE_CODE (new_expr
) == SSA_NAME
)
1589 vec_ssa
->safe_push (new_expr
);
1593 /* Iterate over SSA_NAMES in NEW_EXPR. */
1594 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1596 tree op
= TREE_OPERAND (new_expr
, i
);
1597 collect_all_ssa_names (op
, vec_ssa
);
1601 /* This is abridged version of the function:
1602 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1605 substitute_ssa_name (tree exp
, tree f
, tree r
)
1607 enum tree_code code
= TREE_CODE (exp
);
1608 tree op0
, op1
, op2
, op3
;
1611 /* We handle TREE_LIST and COMPONENT_REF separately. */
1612 if (code
== TREE_LIST
)
1614 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1615 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1616 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1619 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1621 else if (code
== COMPONENT_REF
)
1625 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1626 and it is the right field, replace it with R. */
1627 for (inner
= TREE_OPERAND (exp
, 0);
1628 REFERENCE_CLASS_P (inner
);
1629 inner
= TREE_OPERAND (inner
, 0))
1633 op1
= TREE_OPERAND (exp
, 1);
1635 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1638 /* If this expression hasn't been completed let, leave it alone. */
1639 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1642 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1643 if (op0
== TREE_OPERAND (exp
, 0))
1647 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1650 switch (TREE_CODE_CLASS (code
))
1655 case tcc_declaration
:
1661 case tcc_expression
:
1665 /* Fall through... */
1667 case tcc_exceptional
:
1670 case tcc_comparison
:
1672 switch (TREE_CODE_LENGTH (code
))
1680 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1681 if (op0
== TREE_OPERAND (exp
, 0))
1684 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1688 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1689 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1691 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1694 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1698 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1699 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1700 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1702 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1703 && op2
== TREE_OPERAND (exp
, 2))
1706 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1710 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1711 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1712 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1713 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1715 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1716 && op2
== TREE_OPERAND (exp
, 2)
1717 && op3
== TREE_OPERAND (exp
, 3))
1721 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1734 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1736 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1737 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1742 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1745 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1748 auto_vec
<tree
, 2> ssa_names
;
1749 collect_all_ssa_names (new_expr
, &ssa_names
);
1752 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1753 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1754 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1759 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1760 scalar evolution around LOOP. */
1763 translate_isl_ast_to_gimple::
1764 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1765 basic_block new_bb
, basic_block old_bb
,
1768 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1770 /* At this point we should know the exact scev for each
1771 scalar SSA_NAME used in the scop: all the other scalar
1772 SSA_NAMEs should have been translated out of SSA using
1773 arrays with one element. */
1775 if (chrec_contains_undetermined (scev
))
1777 codegen_error
= true;
1778 return build_zero_cst (TREE_TYPE (old_name
));
1781 new_expr
= chrec_apply_map (scev
, iv_map
);
1783 /* The apply should produce an expression tree containing
1784 the uses of the new induction variables. We should be
1785 able to use new_expr instead of the old_name in the newly
1786 generated loop nest. */
1787 if (chrec_contains_undetermined (new_expr
)
1788 || tree_contains_chrecs (new_expr
, NULL
))
1790 codegen_error
= true;
1791 return build_zero_cst (TREE_TYPE (old_name
));
1794 /* We should check all the operands and all of them should dominate the use at
1796 if (TREE_CODE (new_expr
) == SSA_NAME
)
1798 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1799 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1801 codegen_error
= true;
1802 return build_zero_cst (TREE_TYPE (old_name
));
1806 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1807 /* We should check all the operands and all of them should dominate the use at
1809 if (TREE_CODE (new_expr
) == SSA_NAME
)
1811 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1812 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1814 codegen_error
= true;
1815 return build_zero_cst (TREE_TYPE (old_name
));
1819 /* Replace the old_name with the new_expr. */
1820 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1824 /* Renames the scalar uses of the statement COPY, using the
1825 substitution map RENAME_MAP, inserting the gimplification code at
1826 GSI_TGT, for the translation REGION, with the original copied
1827 statement in LOOP, and using the induction variable renaming map
1828 IV_MAP. Returns true when something has been renamed. codegen_error
1829 is set when the code generation cannot continue. */
1832 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1833 gimple_stmt_iterator
*gsi_tgt
,
1835 loop_p loop
, vec
<tree
> iv_map
)
1837 bool changed
= false;
1839 if (is_gimple_debug (copy
))
1841 if (gimple_debug_bind_p (copy
))
1842 gimple_debug_bind_reset_value (copy
);
1843 else if (gimple_debug_source_bind_p (copy
))
1853 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1854 print_gimple_stmt (dump_file
, copy
, 0, 0);
1857 use_operand_p use_p
;
1858 ssa_op_iter op_iter
;
1859 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1861 tree old_name
= USE_FROM_PTR (use_p
);
1865 fprintf (dump_file
, "[codegen] renaming old_name = ");
1866 print_generic_expr (dump_file
, old_name
, 0);
1867 fprintf (dump_file
, "\n");
1870 if (TREE_CODE (old_name
) != SSA_NAME
1871 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1875 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1880 tree type_old_name
= TREE_TYPE (old_name
);
1881 tree type_new_expr
= TREE_TYPE (new_expr
);
1885 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1886 print_generic_expr (dump_file
, new_expr
, 0);
1887 fprintf (dump_file
, "\n");
1890 if (type_old_name
!= type_new_expr
1891 || TREE_CODE (new_expr
) != SSA_NAME
)
1893 tree var
= create_tmp_var (type_old_name
, "var");
1895 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1896 new_expr
= fold_convert (type_old_name
, new_expr
);
1899 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1900 gsi_insert_earliest (stmts
);
1903 replace_exp (use_p
, new_expr
);
1908 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1910 if (!new_expr
|| codegen_error_p ())
1915 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1916 print_generic_expr (dump_file
, new_expr
, 0);
1917 fprintf (dump_file
, "\n");
1920 gsi_insert_earliest (stmts
);
1921 replace_exp (use_p
, new_expr
);
1923 if (TREE_CODE (new_expr
) == INTEGER_CST
1924 && is_gimple_assign (copy
))
1926 tree rhs
= gimple_assign_rhs1 (copy
);
1928 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1929 recompute_tree_invariant_for_addr_expr (rhs
);
1932 set_rename (old_name
, new_expr
);
1938 /* Returns a basic block that could correspond to where a constant was defined
1939 in the original code. In the original code OLD_BB had the definition, we
1940 need to find which basic block out of the copies of old_bb, in the new
1941 region, should a definition correspond to if it has to reach BB. */
1944 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1945 basic_block old_bb
) const
1947 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1949 if (!bbs
|| bbs
->is_empty ())
1952 if (1 == bbs
->length ())
1956 basic_block b1
= NULL
, b2
;
1957 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1962 /* BB and B2 are in two unrelated if-clauses. */
1963 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1966 /* Compute the nearest dominator. */
1967 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1975 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1976 when we want to rename an OP within a loop PHI instruction. */
1979 translate_isl_ast_to_gimple::
1980 get_new_name (basic_block new_bb
, tree op
,
1981 basic_block old_bb
, bool loop_phi
) const
1983 /* For constants the names are the same. */
1984 if (is_constant (op
))
1987 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1990 /* Return a debug location for OP. */
1995 location_t loc
= UNKNOWN_LOCATION
;
1997 if (TREE_CODE (op
) == SSA_NAME
)
1998 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
2002 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
2003 the init edge (from outside the loop) and the second one is the back edge
2004 from the same loop. */
2006 std::pair
<edge
, edge
>
2007 get_edges (basic_block bb
)
2009 std::pair
<edge
, edge
> edges
;
2012 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2013 if (bb
->loop_father
!= e
->src
->loop_father
)
2020 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
2021 must be found unless they can be POSTPONEd for later. */
2024 translate_isl_ast_to_gimple::
2025 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
2026 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
2029 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
2031 basic_block new_bb
= gimple_bb (new_phi
);
2032 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
2035 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
2036 e
= ibp_new_bb
.first
;
2038 e
= ibp_new_bb
.second
;
2040 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
2041 tree new_name
= get_new_name (new_bb
, old_name
,
2042 gimple_bb (old_phi
), true);
2045 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
2049 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2050 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2051 /* If the phi arg was a function arg, or wasn't defined, just use the
2053 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
2056 /* Postpone code gen for later for those back-edges we don't have the
2058 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
2060 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
2063 /* Either we should add the arg to phi or, we should postpone. */
2069 /* Copy loop phi nodes from BB to NEW_BB. */
2072 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
2076 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
2079 /* Loop phi nodes should have only two arguments. */
2080 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2082 /* First edge is the init edge and second is the back edge. */
2083 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
2085 /* First edge is the init edge and second is the back edge. */
2086 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2088 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2091 gphi
*phi
= psi
.phi ();
2092 tree res
= gimple_phi_result (phi
);
2093 if (virtual_operand_p (res
))
2095 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2098 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2099 tree new_res
= create_new_def_for (res
, new_phi
,
2100 gimple_phi_result_ptr (new_phi
));
2101 set_rename (res
, new_res
);
2102 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
2104 update_stmt (new_phi
);
2108 fprintf (dump_file
, "[codegen] creating loop-phi node: ");
2109 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2116 /* Return the init value of PHI, the value coming from outside the loop. */
2119 get_loop_init_value (gphi
*phi
)
2122 loop_p loop
= gimple_bb (phi
)->loop_father
;
2126 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2127 if (e
->src
->loop_father
!= loop
)
2128 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2133 /* Find the init value (the value which comes from outside the loop), of one of
2134 the operands of DEF which is defined by a loop phi. */
2137 find_init_value (gimple
*def
)
2139 if (gimple_code (def
) == GIMPLE_PHI
)
2140 return get_loop_init_value (as_a
<gphi
*> (def
));
2142 if (gimple_vuse (def
))
2146 use_operand_p use_p
;
2147 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2149 tree use
= USE_FROM_PTR (use_p
);
2150 if (TREE_CODE (use
) == SSA_NAME
)
2152 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2160 /* Return the init value, the value coming from outside the loop. */
2163 find_init_value_close_phi (gphi
*phi
)
2165 gcc_assert (gimple_phi_num_args (phi
) == 1);
2166 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2167 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2168 return find_init_value (def
);
2172 tree
translate_isl_ast_to_gimple::
2173 add_close_phis_to_outer_loops (tree last_merge_name
, edge last_e
,
2174 gimple
*old_close_phi
)
2176 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2177 gimple
*stmt
= SSA_NAME_DEF_STMT (last_merge_name
);
2178 basic_block bb
= gimple_bb (stmt
);
2179 if (!bb_in_sese_p (bb
, codegen_region
))
2180 return last_merge_name
;
2182 loop_p loop
= bb
->loop_father
;
2183 if (!loop_in_sese_p (loop
, codegen_region
))
2184 return last_merge_name
;
2186 edge e
= single_exit (loop
);
2188 if (dominated_by_p (CDI_DOMINATORS
, e
->dest
, last_e
->src
))
2189 return last_merge_name
;
2191 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2192 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2195 if (!bb_contains_loop_close_phi_nodes (bb
) || !single_succ_p (bb
))
2196 bb
= split_edge (e
);
2198 gphi
*close_phi
= create_phi_node (SSA_NAME_VAR (last_merge_name
), bb
);
2199 tree res
= create_new_def_for (last_merge_name
, close_phi
,
2200 gimple_phi_result_ptr (close_phi
));
2201 set_rename (old_close_phi_name
, res
);
2202 add_phi_arg (close_phi
, last_merge_name
, e
, get_loc (old_name
));
2203 last_merge_name
= res
;
2205 return add_close_phis_to_outer_loops (last_merge_name
, last_e
, old_close_phi
);
2208 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2209 the close phi node PHI. */
2211 bool translate_isl_ast_to_gimple::
2212 add_close_phis_to_merge_points (gphi
*old_close_phi
, gphi
*new_close_phi
,
2215 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
2216 basic_block default_value_bb
= get_entry_bb (codegen_region
);
2217 if (SSA_NAME
== TREE_CODE (default_value
))
2219 gimple
*stmt
= SSA_NAME_DEF_STMT (default_value
);
2220 if (!stmt
|| gimple_code (stmt
) == GIMPLE_NOP
)
2222 default_value_bb
= gimple_bb (stmt
);
2225 basic_block new_close_phi_bb
= gimple_bb (new_close_phi
);
2227 tree old_close_phi_name
= gimple_phi_result (old_close_phi
);
2228 tree new_close_phi_name
= gimple_phi_result (new_close_phi
);
2229 tree last_merge_name
= new_close_phi_name
;
2230 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2234 FOR_EACH_VEC_ELT_REVERSE (merge_points
, i
, merge_e
)
2236 basic_block new_merge_bb
= merge_e
->src
;
2237 if (!dominated_by_p (CDI_DOMINATORS
, new_merge_bb
, default_value_bb
))
2240 last_merge_name
= add_close_phis_to_outer_loops (last_merge_name
, merge_e
,
2243 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (old_close_phi_name
), new_merge_bb
);
2244 tree merge_res
= create_new_def_for (old_close_phi_name
, merge_phi
,
2245 gimple_phi_result_ptr (merge_phi
));
2246 set_rename (old_close_phi_name
, merge_res
);
2248 edge from_loop
= NULL
, from_default_value
= NULL
;
2251 FOR_EACH_EDGE (e
, ei
, new_merge_bb
->preds
)
2252 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, new_close_phi_bb
))
2255 from_default_value
= e
;
2257 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2258 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2259 is contained in another condition. */
2260 if (!from_default_value
|| !from_loop
)
2263 add_phi_arg (merge_phi
, last_merge_name
, from_loop
, get_loc (old_name
));
2264 add_phi_arg (merge_phi
, default_value
, from_default_value
, get_loc (old_name
));
2268 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2269 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2272 update_stmt (merge_phi
);
2273 last_merge_name
= merge_res
;
2279 /* Copy all the loop-close phi args from BB to NEW_BB. */
2282 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2286 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2289 gphi
*old_close_phi
= psi
.phi ();
2290 tree res
= gimple_phi_result (old_close_phi
);
2291 if (virtual_operand_p (res
))
2294 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2295 /* Loop close phi nodes should not be scev_analyzable_p. */
2298 gphi
*new_close_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2299 tree new_res
= create_new_def_for (res
, new_close_phi
,
2300 gimple_phi_result_ptr (new_close_phi
));
2301 set_rename (res
, new_res
);
2303 tree old_name
= gimple_phi_arg_def (old_close_phi
, 0);
2304 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2306 /* Predecessor basic blocks of a loop close phi should have been code
2307 generated before. FIXME: This is fixable by merging PHIs from inner
2308 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2312 add_phi_arg (new_close_phi
, new_name
, single_pred_edge (new_bb
),
2313 get_loc (old_name
));
2316 fprintf (dump_file
, "[codegen] Adding loop close phi: ");
2317 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2320 update_stmt (new_close_phi
);
2322 /* When there is no loop guard around this codegenerated loop, there is no
2323 need to collect the close-phi arg. */
2324 if (merge_points
.is_empty ())
2327 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2328 tree default_value
= find_init_value_close_phi (new_close_phi
);
2330 /* A close phi must come from a loop-phi having a default value. */
2336 region
->incomplete_phis
.safe_push (std::make_pair (old_close_phi
,
2340 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2341 print_gimple_stmt (dump_file
, new_close_phi
, 0, 0);
2346 if (!add_close_phis_to_merge_points (old_close_phi
, new_close_phi
,
2354 /* Copy loop close phi nodes from BB to NEW_BB. */
2357 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2361 fprintf (dump_file
, "[codegen] copying loop close phi nodes in bb_%d.\n",
2363 /* Loop close phi nodes should have only one argument. */
2364 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2366 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2370 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2371 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2372 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2373 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2376 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2377 In this case DOMINATING_PRED = NULL.
2379 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2381 Returns true on successful copy of the args, false otherwise. */
2384 translate_isl_ast_to_gimple::
2385 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2386 edge old_bb_dominating_edge
,
2387 edge old_bb_non_dominating_edge
,
2388 gphi
*phi
, gphi
*new_phi
,
2391 basic_block def_pred
[2] = { NULL
, NULL
};
2392 int not_found_bb_index
= -1;
2393 for (int i
= 0; i
< 2; i
++)
2395 /* If the corresponding def_bb could not be found the entry will be
2397 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2398 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2399 gimple_phi_arg_edge (phi
, i
)->src
);
2400 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2401 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2405 /* When non are available bail out. */
2406 if (not_found_bb_index
!= -1)
2408 not_found_bb_index
= i
;
2412 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2413 if (old_bb_dominating_edge
)
2415 if (not_found_bb_index
!= -1)
2418 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2419 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2420 vec
<basic_block
> *bbs
2421 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2423 /* Could not find a mapping. */
2427 basic_block new_pred
= NULL
;
2430 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2432 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2434 /* FIXME: If we have already found new_pred then we have to
2435 disambiguate, bail out for now. */
2438 new_pred
= new_pred1
;
2440 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2442 /* FIXME: If we have already found new_pred then we have to either
2443 it dominates both or we have to disambiguate, bail out. */
2446 new_pred
= new_pred2
;
2453 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2454 gcc_assert (new_non_dominating_edge
);
2455 /* FIXME: Validate each args just like in loop-phis. */
2456 /* By the process of elimination we first insert insert phi-edge for
2457 non-dominating pred which is computed above and then we insert the
2459 int inserted_edge
= 0;
2460 for (; inserted_edge
< 2; inserted_edge
++)
2462 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2463 if (new_non_dominating_edge
== new_bb_pred_edge
)
2465 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2466 new_non_dominating_edge
,
2467 get_loc (old_phi_args
[inserted_edge
]));
2471 if (inserted_edge
== 2)
2474 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2476 edge new_dominating_edge
= NULL
;
2477 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2479 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2480 if (e
!= new_non_dominating_edge
)
2482 new_dominating_edge
= e
;
2483 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2484 new_dominating_edge
,
2485 get_loc (old_phi_args
[inserted_edge
]));
2489 gcc_assert (new_dominating_edge
);
2493 /* Classic diamond structure: both edges are non-dominating. We need to
2494 find one unique edge then the other can be found be elimination. If
2495 any definition (def_pred) dominates both the preds of new_bb then we
2496 bail out. Entries of def_pred maybe NULL, in that case we must
2497 uniquely find pred with help of only one entry. */
2498 edge new_e
[2] = { NULL
, NULL
};
2499 for (int i
= 0; i
< 2; i
++)
2503 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2505 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2508 /* We do not know how to handle the case when def_pred
2509 dominates more than a predecessor. */
2515 gcc_assert (new_e
[0] || new_e
[1]);
2517 /* Find the other edge by process of elimination. */
2518 if (not_found_bb_index
!= -1)
2520 gcc_assert (!new_e
[not_found_bb_index
]);
2521 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2524 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2526 if (new_e
[found_bb_index
] == e
)
2528 new_e
[not_found_bb_index
] = e
;
2532 /* Add edges to phi args. */
2533 for (int i
= 0; i
< 2; i
++)
2534 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2535 get_loc (old_phi_args
[i
]));
2541 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2542 region. If postpone is true and it isn't possible to copy any arg of PHI,
2543 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2544 Returns false if the copying was unsuccessful. */
2547 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2552 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2553 gcc_assert (2 == gimple_phi_num_args (phi
));
2555 basic_block new_bb
= gimple_bb (new_phi
);
2556 loop_p loop
= gimple_bb (phi
)->loop_father
;
2558 basic_block old_bb
= gimple_bb (phi
);
2559 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2563 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2564 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2565 old_bb_non_dominating_edge
= e
;
2567 old_bb_dominating_edge
= e
;
2569 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2570 old_bb_non_dominating_edge
->src
));
2572 tree new_phi_args
[2];
2573 tree old_phi_args
[2];
2575 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2577 tree old_name
= gimple_phi_arg_def (phi
, i
);
2578 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2579 old_phi_args
[i
] = old_name
;
2582 new_phi_args
[i
] = new_name
;
2586 /* If the phi-arg was a parameter. */
2587 if (vec_find (region
->params
, old_name
) != -1)
2589 new_phi_args
[i
] = old_name
;
2593 "[codegen] parameter argument to phi, new_expr: ");
2594 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2595 fprintf (dump_file
, "\n");
2600 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2601 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2602 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2608 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2609 if (is_gimple_reg (old_name
)
2610 && scev_analyzable_p (old_name
, region
->region
))
2613 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2614 new_bb
, old_bb
, iv_map
);
2615 if (codegen_error_p ())
2618 gcc_assert (new_expr
);
2622 "[codegen] scev analyzeable, new_expr: ");
2623 print_generic_expr (dump_file
, new_expr
, 0);
2624 fprintf (dump_file
, "\n");
2626 gsi_insert_earliest (stmts
);
2627 new_phi_args
[i
] = new_name
;
2631 /* Postpone code gen for later for back-edges. */
2632 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2636 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2637 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2640 new_phi_args
[i
] = NULL_TREE
;
2644 /* Either we should add the arg to phi or, we should postpone. */
2648 /* If none of the args have been determined in the first stage then wait until
2650 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2653 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2654 old_bb_dominating_edge
,
2655 old_bb_non_dominating_edge
,
2656 phi
, new_phi
, new_bb
);
2659 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2660 containing phi nodes coming from two predecessors, and none of them are back
2664 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2669 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2672 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2675 /* Cond phi nodes should have exactly two arguments. */
2676 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2678 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2681 gphi
*phi
= psi
.phi ();
2682 tree res
= gimple_phi_result (phi
);
2683 if (virtual_operand_p (res
))
2685 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2686 /* Cond phi nodes should not be scev_analyzable_p. */
2689 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2690 tree new_res
= create_new_def_for (res
, new_phi
,
2691 gimple_phi_result_ptr (new_phi
));
2692 set_rename (res
, new_res
);
2694 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2697 update_stmt (new_phi
);
2703 /* Return true if STMT should be copied from region to the new code-generated
2704 region. LABELs, CONDITIONS, induction-variables and region parameters need
2708 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2710 /* Do not copy labels or conditions. */
2711 if (gimple_code (stmt
) == GIMPLE_LABEL
2712 || gimple_code (stmt
) == GIMPLE_COND
)
2716 /* Do not copy induction variables. */
2717 if (is_gimple_assign (stmt
)
2718 && (lhs
= gimple_assign_lhs (stmt
))
2719 && TREE_CODE (lhs
) == SSA_NAME
2720 && is_gimple_reg (lhs
)
2721 && scev_analyzable_p (lhs
, region
->region
))
2727 /* Create new names for all the definitions created by COPY and add replacement
2728 mappings for each new name. */
2731 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2733 def_operand_p def_p
;
2734 ssa_op_iter op_iter
;
2735 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2737 tree old_name
= DEF_FROM_PTR (def_p
);
2738 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2739 set_rename (old_name
, new_name
);
2743 /* Duplicates the statements of basic block BB into basic block NEW_BB
2744 and compute the new induction variables according to the IV_MAP.
2745 CODEGEN_ERROR is set when the code generation cannot continue. */
2748 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2752 /* Iterator poining to the place where new statement (s) will be inserted. */
2753 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2755 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2758 gimple
*stmt
= gsi_stmt (gsi
);
2759 if (!should_copy_to_new_region (stmt
, region
))
2762 /* Create a new copy of STMT and duplicate STMT's virtual
2764 gimple
*copy
= gimple_copy (stmt
);
2765 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2769 fprintf (dump_file
, "[codegen] inserting statement: ");
2770 print_gimple_stmt (dump_file
, copy
, 0, 0);
2773 maybe_duplicate_eh_stmt (copy
, stmt
);
2774 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2776 /* Crete new names for each def in the copied stmt. */
2777 set_rename_for_each_def (copy
);
2779 loop_p loop
= bb
->loop_father
;
2780 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2782 fold_stmt_inplace (&gsi_tgt
);
2783 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2786 if (codegen_error_p ())
2796 /* Given a basic block containing close-phi it returns the new basic block where
2797 to insert a copy of the close-phi nodes. All the uses in close phis should
2798 come from a single loop otherwise it returns NULL. */
2801 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2803 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2804 of close phi in the original code and then find the mapping of basic block
2805 defining that variable. If there are multiple close-phis and they are
2806 defined in different loops (in the original or in the new code) because of
2807 loop splitting, then we bail out. */
2808 loop_p new_loop
= NULL
;
2809 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2812 gphi
*phi
= psi
.phi ();
2813 tree name
= gimple_phi_arg_def (phi
, 0);
2814 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2816 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2817 if (!bbs
|| bbs
->length () != 1)
2818 /* This is one of the places which shows preserving original structure
2819 is not always possible, as we may need to insert close PHI for a loop
2820 where the latch does not have any mapping, or the mapping is
2825 new_loop
= (*bbs
)[0]->loop_father
;
2826 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2833 return single_exit (new_loop
);
2836 /* Copies BB and includes in the copied BB all the statements that can
2837 be reached following the use-def chains from the memory accesses,
2838 and returns the next edge following this new block. codegen_error is
2839 set when the code generation cannot continue. */
2842 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2846 int num_phis
= number_of_phi_nodes (bb
);
2848 if (region
->copied_bb_map
->get (bb
))
2850 /* FIXME: we should be able to handle phi nodes with args coming from
2851 outside the region. */
2854 codegen_error
= true;
2859 basic_block new_bb
= NULL
;
2860 if (bb_contains_loop_close_phi_nodes (bb
))
2863 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2866 edge e
= edge_for_new_close_phis (bb
);
2869 codegen_error
= true;
2873 basic_block phi_bb
= e
->dest
;
2875 if (!bb_contains_loop_close_phi_nodes (phi_bb
) || !single_succ_p (phi_bb
))
2876 phi_bb
= split_edge (e
);
2878 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2879 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2881 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2883 codegen_error
= true;
2890 new_bb
= split_edge (next_e
);
2894 new_bb
= split_edge (next_e
);
2895 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2897 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2899 /* At this point we are unable to codegenerate by still preserving the SSA
2900 structure because maybe the loop is completely unrolled and the PHIs
2901 and cross-bb scalar dependencies are untrackable w.r.t. the original
2902 code. See gfortran.dg/graphite/pr29832.f90. */
2903 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2905 codegen_error
= true;
2909 /* In case ISL did some loop peeling, like this:
2912 for (int c1 = 1; c1 <= 5; c1 += 1) {
2917 there should be no loop-phi nodes in S_8(0).
2919 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2920 values of all scalar variables: for the moment we instantiate only
2921 SCEV analyzable expressions on the iteration domain, and we need to
2922 extend that to reductions that cannot be analyzed by SCEV. */
2923 if (!bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
))
2925 codegen_error
= true;
2930 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2932 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2934 codegen_error
= true;
2938 else if (num_phis
> 0)
2941 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2944 basic_block phi_bb
= single_pred (new_bb
);
2945 loop_p loop_father
= new_bb
->loop_father
;
2947 /* Move back until we find the block with two predecessors. */
2948 while (single_pred_p (phi_bb
))
2949 phi_bb
= single_pred_edge (phi_bb
)->src
;
2951 /* If a corresponding merge-point was not found, then abort codegen. */
2952 if (phi_bb
->loop_father
!= loop_father
2953 || !bb_in_sese_p (phi_bb
, region
->if_region
->true_region
->region
)
2954 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2956 codegen_error
= true;
2963 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2964 bb
->index
, new_bb
->index
);
2966 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2968 copied_bbs
->safe_push (new_bb
);
2971 vec
<basic_block
> bbs
;
2973 bbs
.safe_push (new_bb
);
2974 region
->copied_bb_map
->put (bb
, bbs
);
2977 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2979 codegen_error
= true;
2983 return single_succ_edge (new_bb
);
2986 /* Patch the missing arguments of the phi nodes. */
2989 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2993 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2995 gphi
*old_phi
= rename
->first
;
2996 gphi
*new_phi
= rename
->second
;
2997 basic_block old_bb
= gimple_bb (old_phi
);
2998 basic_block new_bb
= gimple_bb (new_phi
);
3000 /* First edge is the init edge and second is the back edge. */
3001 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
3002 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
3006 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
3007 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
3010 auto_vec
<tree
, 1> iv_map
;
3011 if (bb_contains_loop_phi_nodes (new_bb
))
3012 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
3014 else if (bb_contains_loop_close_phi_nodes (new_bb
))
3015 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
3017 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
3021 fprintf (dump_file
, "[codegen] to new-phi: ");
3022 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
3029 /* Prints NODE to FILE. */
3032 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
3033 __isl_keep isl_ast_node
*node
,
3034 __isl_keep isl_ctx
*ctx
) const
3036 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
3037 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
3038 prn
= isl_printer_print_ast_node (prn
, node
);
3039 prn
= isl_printer_print_str (prn
, "\n");
3040 isl_printer_free (prn
);
3043 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
3046 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
3049 sese_info_p region
= scop
->scop_info
;
3050 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
3051 gcc_assert (nb_parameters
== region
->params
.length ());
3053 for (i
= 0; i
< nb_parameters
; i
++)
3055 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
3057 ip
[tmp_id
] = region
->params
[i
];
3062 /* Generates a build, which specifies the constraints on the parameters. */
3064 __isl_give isl_ast_build
*
3065 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
3067 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
3068 return isl_ast_build_from_context (context_isl
);
3071 /* Get the maximal number of schedule dimensions in the scop SCOP. */
3074 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
3078 int schedule_dims
= 0;
3080 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3082 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
3083 if (pbb_schedule_dims
> schedule_dims
)
3084 schedule_dims
= pbb_schedule_dims
;
3087 return schedule_dims
;
3090 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
3092 For schedules with different dimensionality, the isl AST generator can not
3093 define an order and will just randomly choose an order. The solution to this
3094 problem is to extend all schedules to the maximal number of schedule
3095 dimensions (using '0's for the remaining values). */
3097 __isl_give isl_map
*
3098 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
3099 int nb_schedule_dims
)
3101 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
3103 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
3105 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
3107 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
3110 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
3112 isl_val_free (zero
);
3116 /* Generates a schedule, which specifies an order used to
3117 visit elements in a domain. */
3119 __isl_give isl_union_map
*
3120 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
3122 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
3125 isl_union_map
*schedule_isl
=
3126 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
3128 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
3130 /* Dead code elimination: when the domain of a PBB is empty,
3131 don't generate code for the PBB. */
3132 if (isl_set_is_empty (pbb
->domain
))
3135 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
3136 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
3137 isl_set_copy (pbb
->domain
));
3138 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
3140 = isl_union_map_union (schedule_isl
,
3141 isl_union_map_from_map (bb_schedule
));
3143 return schedule_isl
;
3146 /* This method is executed before the construction of a for node. */
3148 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
3150 isl_union_map
*dependences
= (isl_union_map
*) user
;
3151 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
3152 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
3153 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
3154 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
3155 for_info
->is_parallelizable
=
3156 !carries_deps (schedule
, dependences
, dimension
);
3157 isl_union_map_free (schedule
);
3158 isl_space_free (schedule_space
);
3159 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
3163 /* Set the separate option for all dimensions.
3164 This helps to reduce control overhead. */
3166 __isl_give isl_ast_build
*
3167 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
3168 __isl_keep isl_union_map
*schedule
)
3170 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
3171 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
3173 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
3174 isl_union_set
*range
=
3175 isl_union_set_from_set (isl_set_universe (range_space
));
3176 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
3177 domain
= isl_union_set_universe (domain
);
3178 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
3179 return isl_ast_build_set_options (control
, options
);
3182 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3184 __isl_give isl_ast_node
*
3185 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
3187 /* Generate loop upper bounds that consist of the current loop iterator, an
3188 operator (< or <=) and an expression not involving the iterator. If this
3189 option is not set, then the current loop iterator may appear several times
3190 in the upper bound. See the isl manual for more details. */
3191 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
3193 add_parameters_to_ivs_params (scop
, ip
);
3194 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
3195 isl_ast_build
*context_isl
= generate_isl_context (scop
);
3196 context_isl
= set_options (context_isl
, schedule_isl
);
3197 isl_union_map
*dependences
= NULL
;
3198 if (flag_loop_parallelize_all
)
3200 dependences
= scop_get_dependences (scop
);
3202 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
3205 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
3208 isl_union_map_free (dependences
);
3209 isl_ast_build_free (context_isl
);
3213 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3214 the given SCOP. Return true if code generation succeeded.
3216 FIXME: This is not yet a full implementation of the code generator
3217 with ISL ASTs. Generation of GIMPLE code has to be completed. */
3220 graphite_regenerate_ast_isl (scop_p scop
)
3222 sese_info_p region
= scop
->scop_info
;
3223 translate_isl_ast_to_gimple
t (region
);
3225 ifsese if_region
= NULL
;
3226 isl_ast_node
*root_node
;
3229 timevar_push (TV_GRAPHITE_CODE_GEN
);
3230 root_node
= t
.scop_to_isl_ast (scop
, ip
);
3232 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3234 fprintf (dump_file
, "ISL AST generated by ISL: \n");
3235 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
3238 recompute_all_dominators ();
3241 if_region
= move_sese_in_condition (region
);
3242 region
->if_region
= if_region
;
3243 recompute_all_dominators ();
3245 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3247 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3248 basic_block bb
= split_edge (e
);
3250 /* Update the true_region exit edge. */
3251 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3253 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3254 if (t
.codegen_error_p ())
3257 fprintf (dump_file
, "[codegen] unsuccessful,"
3258 " reverting back to the original code.\n");
3259 set_ifsese_condition (if_region
, integer_zero_node
);
3263 t
.translate_pending_phi_nodes ();
3264 if (!t
.codegen_error_p ())
3266 sese_insert_phis_for_liveouts (region
,
3267 if_region
->region
->region
.exit
->src
,
3268 if_region
->false_region
->region
.exit
,
3269 if_region
->true_region
->region
.exit
);
3270 mark_virtual_operands_for_renaming (cfun
);
3271 update_ssa (TODO_update_ssa
);
3276 recompute_all_dominators ();
3282 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3283 " pending phis, reverting back to the original code.\n");
3284 set_ifsese_condition (if_region
, integer_zero_node
);
3288 free (if_region
->true_region
);
3289 free (if_region
->region
);
3292 ivs_params_clear (ip
);
3293 isl_ast_node_free (root_node
);
3294 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3299 int num_no_dependency
= 0;
3301 FOR_EACH_LOOP (loop
, 0)
3302 if (loop
->can_be_parallel
)
3303 num_no_dependency
++;
3305 fprintf (dump_file
, "%d loops carried no dependency.\n",
3309 return !t
.codegen_error_p ();
3312 #endif /* HAVE_isl */