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/>. */
24 /* Workaround for GMP 5.1.3 bug, see PR56019. */
27 #include <isl/constraint.h>
29 #include <isl/union_set.h>
31 #include <isl/union_map.h>
32 #include <isl/ast_build.h>
34 /* Since ISL-0.13, the extern is in val_gmp.h. */
35 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
38 #include <isl/val_gmp.h>
39 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
44 #include "coretypes.h"
50 #include "fold-const.h"
51 #include "gimple-fold.h"
52 #include "gimple-iterator.h"
54 #include "gimplify-me.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-ssa-operands.h"
58 #include "tree-ssa-propagate.h"
59 #include "tree-pass.h"
61 #include "tree-data-ref.h"
62 #include "graphite-poly.h"
63 #include "tree-ssa-loop-manip.h"
64 #include "tree-scalar-evolution.h"
65 #include "gimple-ssa.h"
66 #include "tree-phinodes.h"
67 #include "tree-into-ssa.h"
68 #include "ssa-iterators.h"
69 #include "graphite-isl-ast-to-gimple.h"
71 #include "gimple-pretty-print.h"
73 #include "value-prof.h"
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 /* Copy all the loop-close phi args from BB to NEW_BB. */
365 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
368 /* Copy loop close phi nodes from BB to NEW_BB. */
370 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
372 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
373 region. If postpone is true and it isn't possible to copy any arg of PHI,
374 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
375 Returns false if the copying was unsuccessful. */
377 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
380 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
381 containing phi nodes coming from two predecessors, and none of them are back
384 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
387 /* Duplicates the statements of basic block BB into basic block NEW_BB
388 and compute the new induction variables according to the IV_MAP.
389 CODEGEN_ERROR is set when the code generation cannot continue. */
391 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
394 /* Copies BB and includes in the copied BB all the statements that can
395 be reached following the use-def chains from the memory accesses,
396 and returns the next edge following this new block. codegen_error is
397 set when the code generation cannot continue. */
399 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
402 /* Given a basic block containing close-phi it returns the new basic block
403 where to insert a copy of the close-phi nodes. All the uses in close phis
404 should come from a single loop otherwise it returns NULL. */
405 edge
edge_for_new_close_phis (basic_block bb
);
407 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
408 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
409 the other pred of OLD_BB as well. If no such basic block exists then it is
410 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
413 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
414 versa. In this case DOMINATING_PRED = NULL.
416 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
418 Returns true on successful copy of the args, false otherwise. */
420 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
421 edge old_bb_dominating_edge
,
422 edge old_bb_non_dominating_edge
,
423 gphi
*phi
, gphi
*new_phi
,
426 /* Renames the scalar uses of the statement COPY, using the substitution map
427 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
428 translation REGION, with the original copied statement in LOOP, and using
429 the induction variable renaming map IV_MAP. Returns true when something
430 has been renamed. codegen_error is set when the code generation cannot
433 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
434 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
436 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
437 When OLD_NAME and EXPR are the same we assert. */
439 void set_rename (tree old_name
, tree expr
);
441 /* Create new names for all the definitions created by COPY and add
442 replacement mappings for each new name. */
444 void set_rename_for_each_def (gimple
*stmt
);
446 /* Insert each statement from SEQ at its earliest insertion p. */
448 void gsi_insert_earliest (gimple_seq seq
);
450 /* Rename all the operands of NEW_EXPR by recursively visiting each
453 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
455 bool codegen_error_p () const
456 { return codegen_error
; }
458 /* Prints NODE to FILE. */
460 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
461 __isl_keep isl_ctx
*ctx
) const;
466 /* This flag is set when an error occurred during the translation of ISL AST
471 /* Return the tree variable that corresponds to the given isl ast identifier
472 expression (an isl_ast_expr of type isl_ast_expr_id).
474 FIXME: We should replace blind conversation of id's type with derivation
475 of the optimal type when we get the corresponding isl support. Blindly
476 converting type sizes may be problematic when we switch to smaller
480 translate_isl_ast_to_gimple::
481 gcc_expression_from_isl_ast_expr_id (tree type
,
482 __isl_keep isl_ast_expr
*expr_id
,
485 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
486 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
487 std::map
<isl_id
*, tree
>::iterator res
;
488 res
= ip
.find (tmp_isl_id
);
489 isl_id_free (tmp_isl_id
);
490 gcc_assert (res
!= ip
.end () &&
491 "Could not map isl_id to tree expression");
492 isl_ast_expr_free (expr_id
);
493 tree t
= res
->second
;
494 return fold_convert (type
, t
);
497 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
501 translate_isl_ast_to_gimple::
502 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
504 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
505 isl_val
*val
= isl_ast_expr_get_val (expr
);
507 mpz_init (val_mpz_t
);
509 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
512 res
= gmp_cst_to_tree (type
, val_mpz_t
);
514 isl_ast_expr_free (expr
);
515 mpz_clear (val_mpz_t
);
519 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
523 translate_isl_ast_to_gimple::
524 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
526 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
527 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
528 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
529 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
530 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
531 isl_ast_expr_free (expr
);
535 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
538 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
541 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
544 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
546 case isl_ast_op_pdiv_q
:
547 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
549 case isl_ast_op_pdiv_r
:
550 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
552 case isl_ast_op_fdiv_q
:
553 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
556 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
557 tree_lhs_expr
, tree_rhs_expr
);
560 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
563 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
566 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
569 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
572 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
575 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
582 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
586 translate_isl_ast_to_gimple::
587 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
589 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
590 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
592 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
593 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
594 tree tree_second_expr
595 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
596 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
598 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
599 isl_ast_expr_free (expr
);
600 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
601 tree_second_expr
, tree_third_expr
);
604 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
608 translate_isl_ast_to_gimple::
609 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
611 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
612 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
613 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
614 isl_ast_expr_free (expr
);
615 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
618 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
619 to a GCC expression tree of type TYPE. */
622 translate_isl_ast_to_gimple::
623 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
625 enum tree_code op_code
;
626 switch (isl_ast_expr_get_op_type (expr
))
639 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
640 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
642 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
644 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
645 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
646 res
= fold_build2 (op_code
, type
, res
, t
);
648 isl_ast_expr_free (expr
);
652 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
656 translate_isl_ast_to_gimple::
657 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
660 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
661 switch (isl_ast_expr_get_op_type (expr
))
663 /* These isl ast expressions are not supported yet. */
664 case isl_ast_op_error
:
665 case isl_ast_op_call
:
666 case isl_ast_op_and_then
:
667 case isl_ast_op_or_else
:
668 case isl_ast_op_select
:
673 return nary_op_to_tree (type
, expr
, ip
);
679 case isl_ast_op_pdiv_q
:
680 case isl_ast_op_pdiv_r
:
681 case isl_ast_op_fdiv_q
:
689 return binary_op_to_tree (type
, expr
, ip
);
691 case isl_ast_op_minus
:
692 return unary_op_to_tree (type
, expr
, ip
);
694 case isl_ast_op_cond
:
695 return ternary_op_to_tree (type
, expr
, ip
);
704 /* Converts an ISL AST expression E back to a GCC expression tree of
708 translate_isl_ast_to_gimple::
709 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
712 switch (isl_ast_expr_get_type (expr
))
714 case isl_ast_expr_id
:
715 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
717 case isl_ast_expr_int
:
718 return gcc_expression_from_isl_expr_int (type
, expr
);
720 case isl_ast_expr_op
:
721 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
730 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
731 induction variable for the new LOOP. New LOOP is attached to CFG
732 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
733 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
734 ISL's scattering name to the induction variable created for the
735 loop of STMT. The new induction variable is inserted in the NEWIVS
736 vector and is of type TYPE. */
739 translate_isl_ast_to_gimple::
740 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
741 loop_p outer
, tree type
, tree lb
, tree ub
,
744 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
745 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
746 tree ivvar
= create_tmp_var (type
, "graphite_IV");
747 tree iv
, iv_after_increment
;
748 loop_p loop
= create_empty_loop_on_edge
749 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
750 outer
? outer
: entry_edge
->src
->loop_father
);
752 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
753 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
754 std::map
<isl_id
*, tree
>::iterator res
;
757 isl_id_free (res
->first
);
759 isl_ast_expr_free (for_iterator
);
763 /* Create the loop for a isl_ast_node_for.
765 - NEXT_E is the edge where new generated code should be attached. */
768 translate_isl_ast_to_gimple::
769 translate_isl_ast_for_loop (loop_p context_loop
,
770 __isl_keep isl_ast_node
*node_for
, edge next_e
,
771 tree type
, tree lb
, tree ub
,
774 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
775 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
777 edge last_e
= single_exit (loop
);
778 edge to_body
= single_succ_edge (loop
->header
);
779 basic_block after
= to_body
->dest
;
781 /* Translate the body of the loop. */
782 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
783 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
784 isl_ast_node_free (for_body
);
786 /* Early return if we failed to translate loop body. */
787 if (!next_e
|| codegen_error_p ())
790 redirect_edge_succ_nodup (next_e
, after
);
791 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
793 if (flag_loop_parallelize_all
)
795 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
797 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
798 loop
->can_be_parallel
= for_info
->is_parallelizable
;
806 /* We use this function to get the upper bound because of the form,
807 which is used by isl to represent loops:
809 for (iterator = init; cond; iterator += inc)
817 The loop condition is an arbitrary expression, which contains the
818 current loop iterator.
820 (e.g. iterator + 3 < B && C > iterator + A)
822 We have to know the upper bound of the iterator to generate a loop
823 in Gimple form. It can be obtained from the special representation
824 of the loop condition, which is generated by isl,
825 if the ast_build_atomic_upper_bound option is set. In this case,
826 isl generates a loop condition that consists of the current loop
827 iterator, + an operator (< or <=) and an expression not involving
828 the iterator, which is processed and returned by this function.
830 (e.g iterator <= upper-bound-expression-without-iterator) */
832 static __isl_give isl_ast_expr
*
833 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
835 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
836 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
837 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
839 switch (isl_ast_expr_get_op_type (for_cond
))
842 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
847 /* (iterator < ub) => (iterator <= ub - 1). */
849 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
850 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
851 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
858 isl_ast_expr_free (for_cond
);
862 /* All loops generated by create_empty_loop_on_edge have the form of
869 } while (lower bound < upper bound);
871 We create a new if region protecting the loop to be executed, if
872 the execution count is zero (lower bound > upper bound). */
875 translate_isl_ast_to_gimple::
876 graphite_create_new_loop_guard (edge entry_edge
,
877 __isl_keep isl_ast_node
*node_for
, tree
*type
,
878 tree
*lb
, tree
*ub
, ivs_params
&ip
)
880 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
885 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
886 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
887 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
888 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
889 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
891 /* When ub is simply a constant or a parameter, use lb <= ub. */
892 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
893 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
896 tree one
= (POINTER_TYPE_P (*type
)
897 ? convert_to_ptrofftype (integer_one_node
)
898 : fold_convert (*type
, integer_one_node
));
899 /* Adding +1 and using LT_EXPR helps with loop latches that have a
900 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
901 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
902 is true, even if we do not want this. However lb < ub + 1 is false,
904 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
905 : PLUS_EXPR
, *type
, *ub
, one
);
907 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
910 if (integer_onep (cond_expr
))
911 exit_edge
= entry_edge
;
913 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
918 /* Translates an isl_ast_node_for to Gimple. */
921 translate_isl_ast_to_gimple::
922 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
923 edge next_e
, ivs_params
&ip
)
925 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
927 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
930 if (last_e
== next_e
)
931 /* There was no guard generated. */
932 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
935 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
936 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
940 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
941 variables of the loops around GBB in SESE.
943 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
944 chrec, we could consider using a map<int, tree> that maps loop ids to the
945 corresponding tree expressions. */
948 translate_isl_ast_to_gimple::
949 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
950 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
953 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
954 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
956 isl_ast_expr
*arg_expr
;
957 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
959 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
961 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
962 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
963 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
964 iv_map
[old_loop
->num
] = t
;
968 /* Translates an isl_ast_node_user to Gimple.
970 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
973 translate_isl_ast_to_gimple::
974 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
975 edge next_e
, ivs_params
&ip
)
977 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
979 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
980 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
981 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
983 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
984 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
987 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
989 isl_ast_expr_free (name_expr
);
990 isl_id_free (name_id
);
992 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
993 "The entry block should not even appear within a scop");
995 const int nb_loops
= number_of_loops (cfun
);
997 iv_map
.create (nb_loops
);
998 iv_map
.safe_grow_cleared (nb_loops
);
1000 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1001 isl_ast_expr_free (user_expr
);
1005 fprintf (dump_file
, "[codegen] copying from basic block\n");
1006 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1007 fprintf (dump_file
, "\n[codegen] to new basic block\n");
1008 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1011 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1016 if (codegen_error_p ())
1021 fprintf (dump_file
, "\n[codegen] (after copy) new basic block\n");
1022 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1025 mark_virtual_operands_for_renaming (cfun
);
1026 update_ssa (TODO_update_ssa
);
1030 fprintf (dump_file
, "\n[codegen] (after update SSA) new basic block\n");
1031 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1037 /* Translates an isl_ast_node_block to Gimple. */
1040 translate_isl_ast_to_gimple::
1041 translate_isl_ast_node_block (loop_p context_loop
,
1042 __isl_keep isl_ast_node
*node
,
1043 edge next_e
, ivs_params
&ip
)
1045 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1046 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1048 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1050 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1051 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1052 isl_ast_node_free (tmp_node
);
1054 isl_ast_node_list_free (node_list
);
1058 /* Creates a new if region corresponding to ISL's cond. */
1061 translate_isl_ast_to_gimple::
1062 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1066 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1067 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1068 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1072 /* Translates an isl_ast_node_if to Gimple. */
1075 translate_isl_ast_to_gimple::
1076 translate_isl_ast_node_if (loop_p context_loop
,
1077 __isl_keep isl_ast_node
*node
,
1078 edge next_e
, ivs_params
&ip
)
1080 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1081 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1082 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1084 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1085 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1086 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1087 isl_ast_node_free (then_node
);
1089 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1090 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1091 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1092 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1093 isl_ast_node_free (else_node
);
1097 /* Translates an ISL AST node NODE to GCC representation in the
1098 context of a SESE. */
1101 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1102 __isl_keep isl_ast_node
*node
,
1103 edge next_e
, ivs_params
&ip
)
1105 if (codegen_error_p ())
1108 switch (isl_ast_node_get_type (node
))
1110 case isl_ast_node_error
:
1113 case isl_ast_node_for
:
1114 return translate_isl_ast_node_for (context_loop
, node
,
1117 case isl_ast_node_if
:
1118 return translate_isl_ast_node_if (context_loop
, node
,
1121 case isl_ast_node_user
:
1122 return translate_isl_ast_node_user (node
, next_e
, ip
);
1124 case isl_ast_node_block
:
1125 return translate_isl_ast_node_block (context_loop
, node
,
1133 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1134 at the exit of loop which takes one argument that is the last value of the
1135 variable being used out of the loop. */
1138 bb_contains_loop_close_phi_nodes (basic_block bb
)
1140 return single_pred_p (bb
)
1141 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1144 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1145 header containing phi nodes which has one init-edge and one back-edge. */
1148 bb_contains_loop_phi_nodes (basic_block bb
)
1150 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1152 if (bb
->preds
->length () == 1)
1155 unsigned depth
= loop_depth (bb
->loop_father
);
1157 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1159 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1160 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1163 /* When one of the edges correspond to the same loop father and other
1165 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1166 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1169 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1170 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1176 /* Check if USE is defined in a basic block from where the definition of USE can
1177 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1180 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1182 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1185 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1186 if (bb_contains_loop_close_phi_nodes (bb
))
1189 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1190 basic_block def_bb
= gimple_bb (def
);
1192 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1195 /* Return the number of phi nodes in BB. */
1198 number_of_phi_nodes (basic_block bb
)
1201 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1207 /* Returns true if BB uses name in one of its PHIs. */
1210 phi_uses_name (basic_block bb
, tree name
)
1212 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1215 gphi
*phi
= psi
.phi ();
1216 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1218 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1219 if (use_arg
== name
)
1226 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1227 definition should flow into use, and the use should respect the loop-closed
1231 translate_isl_ast_to_gimple::
1232 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1233 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1235 /* The def of the rename must either dominate the uses or come from a
1236 back-edge. Also the def must respect the loop closed ssa form. */
1237 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1241 fprintf (dump_file
, "\n[codegen] rename not in loop closed ssa:");
1242 print_generic_expr (dump_file
, rename
, 0);
1247 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1250 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1252 /* The loop-header dominates the loop-body. */
1253 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1256 /* RENAME would be used in loop-phi. */
1257 gcc_assert (number_of_phi_nodes (use_bb
));
1259 /* For definitions coming from back edges, we should check that
1260 old_name is used in a loop PHI node.
1261 FIXME: Verify if this is true. */
1262 if (phi_uses_name (old_bb
, old_name
))
1268 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1269 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1270 within a loop PHI instruction. */
1273 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1276 bool loop_phi
) const
1278 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1279 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1281 if (!renames
|| renames
->is_empty ())
1284 if (1 == renames
->length ())
1286 tree rename
= (*renames
)[0];
1287 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1288 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1293 /* More than one renames corresponding to the old_name. Find the rename for
1294 which the definition flows into usage at new_bb. */
1296 tree t1
= NULL_TREE
, t2
;
1297 basic_block t1_bb
= NULL
;
1298 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1300 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1302 /* Defined in the same basic block as used. */
1303 if (t2_bb
== new_bb
)
1306 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1307 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1310 /* Compute the nearest dominator. */
1311 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1321 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1322 When OLD_NAME and EXPR are the same we assert. */
1325 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1329 fprintf (dump_file
, "\n[codegen] setting rename: old_name = ");
1330 print_generic_expr (dump_file
, old_name
, 0);
1331 fprintf (dump_file
, ", new_name = ");
1332 print_generic_expr (dump_file
, expr
, 0);
1335 if (old_name
== expr
)
1338 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1341 renames
->safe_push (expr
);
1347 region
->rename_map
->put (old_name
, r
);
1351 /* Return an iterator to the instructions comes last in the execution order.
1352 Either GSI1 and GSI2 should belong to the same basic block or one of their
1353 respective basic blocks should dominate the other. */
1355 gimple_stmt_iterator
1356 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1358 basic_block bb1
= gsi_bb (gsi1
);
1359 basic_block bb2
= gsi_bb (gsi2
);
1361 /* Find the iterator which is the latest. */
1364 /* For empty basic blocks gsis point to the end of the sequence. Since
1365 there is no operator== defined for gimple_stmt_iterator and for gsis
1366 not pointing to a valid statement gsi_next would assert. */
1367 gimple_stmt_iterator gsi
= gsi1
;
1369 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1372 } while (!gsi_end_p (gsi
));
1377 /* Find the basic block closest to the basic block which defines stmt. */
1378 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1381 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1385 /* Insert each statement from SEQ at its earliest insertion p. */
1388 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1390 update_modified_stmts (seq
);
1391 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1392 basic_block begin_bb
= get_entry_bb (codegen_region
);
1394 /* Inserting the gimple statements in a vector because gimple_seq behave
1395 in strage ways when inserting the stmts from it into different basic
1396 blocks one at a time. */
1397 auto_vec
<gimple
*, 3> stmts
;
1398 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1400 stmts
.safe_push (gsi_stmt (gsi
));
1404 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1406 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1407 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1409 use_operand_p use_p
;
1410 ssa_op_iter op_iter
;
1411 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1413 /* Iterator to the current def of use_p. For function parameters or
1414 anything where def is not found, insert at the beginning of the
1415 generated region. */
1416 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1418 tree op
= USE_FROM_PTR (use_p
);
1419 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1420 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1421 gsi_stmt
= gsi_for_stmt (stmt
);
1423 /* For region parameters, insert at the beginning of the generated
1425 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1426 gsi_stmt
= gsi_def_stmt
;
1428 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1431 if (!gsi_stmt (gsi_def_stmt
))
1433 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1434 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1436 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1438 gimple_stmt_iterator bsi
1439 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1440 /* Insert right after the PHI statements. */
1441 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1444 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1448 fprintf (dump_file
, "\n[codegen] inserting statement: ");
1449 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1450 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1455 /* Collect all the operands of NEW_EXPR by recursively visiting each
1459 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1463 /* Rename all uses in new_expr. */
1464 if (TREE_CODE (new_expr
) == SSA_NAME
)
1466 vec_ssa
->safe_push (new_expr
);
1470 /* Iterate over SSA_NAMES in NEW_EXPR. */
1471 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1473 tree op
= TREE_OPERAND (new_expr
, i
);
1474 collect_all_ssa_names (op
, vec_ssa
);
1478 /* This is abridged version of the function:
1479 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1482 substitute_ssa_name (tree exp
, tree f
, tree r
)
1484 enum tree_code code
= TREE_CODE (exp
);
1485 tree op0
, op1
, op2
, op3
;
1488 /* We handle TREE_LIST and COMPONENT_REF separately. */
1489 if (code
== TREE_LIST
)
1491 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1492 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1493 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1496 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1498 else if (code
== COMPONENT_REF
)
1502 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1503 and it is the right field, replace it with R. */
1504 for (inner
= TREE_OPERAND (exp
, 0);
1505 REFERENCE_CLASS_P (inner
);
1506 inner
= TREE_OPERAND (inner
, 0))
1510 op1
= TREE_OPERAND (exp
, 1);
1512 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1515 /* If this expression hasn't been completed let, leave it alone. */
1516 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1519 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1520 if (op0
== TREE_OPERAND (exp
, 0))
1524 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1527 switch (TREE_CODE_CLASS (code
))
1532 case tcc_declaration
:
1538 case tcc_expression
:
1542 /* Fall through... */
1544 case tcc_exceptional
:
1547 case tcc_comparison
:
1549 switch (TREE_CODE_LENGTH (code
))
1557 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1558 if (op0
== TREE_OPERAND (exp
, 0))
1561 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1565 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1566 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1568 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1571 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1575 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1576 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1577 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1579 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1580 && op2
== TREE_OPERAND (exp
, 2))
1583 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1587 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1588 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1589 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1590 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1592 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1593 && op2
== TREE_OPERAND (exp
, 2)
1594 && op3
== TREE_OPERAND (exp
, 3))
1598 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1611 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1613 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1614 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1619 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1622 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1625 auto_vec
<tree
, 2> ssa_names
;
1626 collect_all_ssa_names (new_expr
, &ssa_names
);
1629 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1630 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1631 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1636 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1637 scalar evolution around LOOP. */
1640 translate_isl_ast_to_gimple::
1641 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1642 basic_block new_bb
, basic_block old_bb
,
1645 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1647 /* At this point we should know the exact scev for each
1648 scalar SSA_NAME used in the scop: all the other scalar
1649 SSA_NAMEs should have been translated out of SSA using
1650 arrays with one element. */
1652 if (chrec_contains_undetermined (scev
))
1654 codegen_error
= true;
1655 return build_zero_cst (TREE_TYPE (old_name
));
1658 new_expr
= chrec_apply_map (scev
, iv_map
);
1660 /* The apply should produce an expression tree containing
1661 the uses of the new induction variables. We should be
1662 able to use new_expr instead of the old_name in the newly
1663 generated loop nest. */
1664 if (chrec_contains_undetermined (new_expr
)
1665 || tree_contains_chrecs (new_expr
, NULL
))
1667 codegen_error
= true;
1668 return build_zero_cst (TREE_TYPE (old_name
));
1671 /* We should check all the operands and all of them should dominate the use at
1673 if (TREE_CODE (new_expr
) == SSA_NAME
)
1675 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1676 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1678 codegen_error
= true;
1679 return build_zero_cst (TREE_TYPE (old_name
));
1683 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1684 /* We should check all the operands and all of them should dominate the use at
1686 if (TREE_CODE (new_expr
) == SSA_NAME
)
1688 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1689 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1691 codegen_error
= true;
1692 return build_zero_cst (TREE_TYPE (old_name
));
1696 /* Replace the old_name with the new_expr. */
1697 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1701 /* Renames the scalar uses of the statement COPY, using the
1702 substitution map RENAME_MAP, inserting the gimplification code at
1703 GSI_TGT, for the translation REGION, with the original copied
1704 statement in LOOP, and using the induction variable renaming map
1705 IV_MAP. Returns true when something has been renamed. codegen_error
1706 is set when the code generation cannot continue. */
1709 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1710 gimple_stmt_iterator
*gsi_tgt
,
1712 loop_p loop
, vec
<tree
> iv_map
)
1714 bool changed
= false;
1716 if (is_gimple_debug (copy
))
1718 if (gimple_debug_bind_p (copy
))
1719 gimple_debug_bind_reset_value (copy
);
1720 else if (gimple_debug_source_bind_p (copy
))
1730 fprintf (dump_file
, "\n[codegen] renaming uses of stmt: ");
1731 print_gimple_stmt (dump_file
, copy
, 0, 0);
1734 use_operand_p use_p
;
1735 ssa_op_iter op_iter
;
1736 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1738 tree old_name
= USE_FROM_PTR (use_p
);
1742 fprintf (dump_file
, "\n[codegen] renaming old_name = ");
1743 print_generic_expr (dump_file
, old_name
, 0);
1746 if (TREE_CODE (old_name
) != SSA_NAME
1747 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1751 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1756 tree type_old_name
= TREE_TYPE (old_name
);
1757 tree type_new_expr
= TREE_TYPE (new_expr
);
1761 fprintf (dump_file
, "\n[codegen] from rename_map: new_name = ");
1762 print_generic_expr (dump_file
, new_expr
, 0);
1765 if (type_old_name
!= type_new_expr
1766 || TREE_CODE (new_expr
) != SSA_NAME
)
1768 tree var
= create_tmp_var (type_old_name
, "var");
1770 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1771 new_expr
= fold_convert (type_old_name
, new_expr
);
1774 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1775 gsi_insert_earliest (stmts
);
1778 replace_exp (use_p
, new_expr
);
1783 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1785 if (!new_expr
|| codegen_error_p ())
1790 fprintf (dump_file
, "\n[codegen] not in rename map, scev: ");
1791 print_generic_expr (dump_file
, new_expr
, 0);
1794 gsi_insert_earliest (stmts
);
1795 replace_exp (use_p
, new_expr
);
1797 if (TREE_CODE (new_expr
) == INTEGER_CST
1798 && is_gimple_assign (copy
))
1800 tree rhs
= gimple_assign_rhs1 (copy
);
1802 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1803 recompute_tree_invariant_for_addr_expr (rhs
);
1806 set_rename (old_name
, new_expr
);
1812 /* Returns a basic block that could correspond to where a constant was defined
1813 in the original code. In the original code OLD_BB had the definition, we
1814 need to find which basic block out of the copies of old_bb, in the new
1815 region, should a definition correspond to if it has to reach BB. */
1818 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1819 basic_block old_bb
) const
1821 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1823 if (!bbs
|| bbs
->is_empty ())
1826 if (1 == bbs
->length ())
1830 basic_block b1
= NULL
, b2
;
1831 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1836 /* BB and B2 are in two unrelated if-clauses. */
1837 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1840 /* Compute the nearest dominator. */
1841 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1849 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1850 when we want to rename an OP within a loop PHI instruction. */
1853 translate_isl_ast_to_gimple::
1854 get_new_name (basic_block new_bb
, tree op
,
1855 basic_block old_bb
, bool loop_phi
) const
1857 /* For constants the names are the same. */
1858 if (TREE_CODE (op
) == INTEGER_CST
1859 || TREE_CODE (op
) == REAL_CST
1860 || TREE_CODE (op
) == COMPLEX_CST
1861 || TREE_CODE (op
) == VECTOR_CST
)
1864 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1867 /* Return a debug location for OP. */
1872 location_t loc
= UNKNOWN_LOCATION
;
1874 if (TREE_CODE (op
) == SSA_NAME
)
1875 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1879 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1880 the init edge (from outside the loop) and the second one is the back edge
1881 from the same loop. */
1883 std::pair
<edge
, edge
>
1884 get_edges (basic_block bb
)
1886 std::pair
<edge
, edge
> edges
;
1889 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1890 if (bb
->loop_father
!= e
->src
->loop_father
)
1897 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1898 must be found unless they can be POSTPONEd for later. */
1901 translate_isl_ast_to_gimple::
1902 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1903 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1906 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1908 basic_block new_bb
= gimple_bb (new_phi
);
1909 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1912 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1913 e
= ibp_new_bb
.first
;
1915 e
= ibp_new_bb
.second
;
1917 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1918 tree new_name
= get_new_name (new_bb
, old_name
,
1919 gimple_bb (old_phi
), true);
1922 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1926 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1927 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1928 /* If the phi arg was a function arg, or wasn't defined, just use the
1930 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1933 /* Postpone code gen for later for those back-edges we don't have the
1935 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1937 fprintf (dump_file
, "\n[codegen] postpone loop phi nodes: ");
1940 /* Either we should add the arg to phi or, we should postpone. */
1946 /* Copy loop phi nodes from BB to NEW_BB. */
1949 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
1953 fprintf (dump_file
, "\n[codegen] copying loop phi nodes in bb_%d.",
1956 /* Loop phi nodes should have only two arguments. */
1957 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1959 /* First edge is the init edge and second is the back edge. */
1960 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1962 /* First edge is the init edge and second is the back edge. */
1963 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1965 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1968 gphi
*phi
= psi
.phi ();
1969 tree res
= gimple_phi_result (phi
);
1970 if (virtual_operand_p (res
))
1972 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1975 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1976 tree new_res
= create_new_def_for (res
, new_phi
,
1977 gimple_phi_result_ptr (new_phi
));
1978 set_rename (res
, new_res
);
1979 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1981 update_stmt (new_phi
);
1987 /* Return the init value of PHI, the value coming from outside the loop. */
1990 get_loop_init_value (gphi
*phi
)
1993 loop_p loop
= gimple_bb (phi
)->loop_father
;
1997 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1998 if (e
->src
->loop_father
!= loop
)
1999 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2004 /* Find the init value (the value which comes from outside the loop), of one of
2005 the operands of DEF which is defined by a loop phi. */
2008 find_init_value (gimple
*def
)
2010 if (gimple_code (def
) == GIMPLE_PHI
)
2011 return get_loop_init_value (as_a
<gphi
*> (def
));
2013 if (gimple_vuse (def
))
2017 use_operand_p use_p
;
2018 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2020 tree use
= USE_FROM_PTR (use_p
);
2021 if (TREE_CODE (use
) == SSA_NAME
)
2023 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2031 /* Return the init value, the value coming from outside the loop. */
2034 find_init_value_close_phi (gphi
*phi
)
2036 gcc_assert (gimple_phi_num_args (phi
) == 1);
2037 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2038 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2039 return find_init_value (def
);
2042 /* Copy all the loop-close phi args from BB to NEW_BB. */
2045 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2049 /* The successor of bb having close phi should be a merge of the diamond
2050 inserted to guard the loop during codegen. */
2051 basic_block succ_new_bb
= single_succ (new_bb
);
2053 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2056 gphi
*phi
= psi
.phi ();
2057 tree res
= gimple_phi_result (phi
);
2058 if (virtual_operand_p (res
))
2061 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2062 /* Loop close phi nodes should not be scev_analyzable_p. */
2065 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2066 tree new_res
= create_new_def_for (res
, new_phi
,
2067 gimple_phi_result_ptr (new_phi
));
2068 set_rename (res
, new_res
);
2070 tree old_name
= gimple_phi_arg_def (phi
, 0);
2071 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2073 /* Predecessor basic blocks of a loop close phi should have been code
2074 generated before. FIXME: This is fixable by merging PHIs from inner
2075 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2079 add_phi_arg (new_phi
, new_name
, single_pred_edge (new_bb
),
2080 get_loc (old_name
));
2083 fprintf (dump_file
, "\n[codegen] Adding loop-closed phi: ");
2084 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2087 update_stmt (new_phi
);
2089 /* When there is no loop guard around this codegenerated loop, there is no
2090 need to collect the close-phi arg. */
2091 if (2 != EDGE_COUNT (succ_new_bb
->preds
)
2092 || bb_contains_loop_phi_nodes (succ_new_bb
))
2095 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2096 tree init
= find_init_value_close_phi (new_phi
);
2098 /* A close phi must come from a loop-phi having an init value. */
2104 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2107 fprintf (dump_file
, "\n[codegen] postpone close phi nodes: ");
2108 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2113 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (res
), succ_new_bb
);
2114 tree merge_res
= create_new_def_for (res
, merge_phi
,
2115 gimple_phi_result_ptr (merge_phi
));
2116 set_rename (res
, merge_res
);
2118 edge from_loop
= single_succ_edge (new_bb
);
2119 add_phi_arg (merge_phi
, new_res
, from_loop
, get_loc (old_name
));
2121 /* The edge coming from loop guard. */
2122 edge other
= from_loop
== (*succ_new_bb
->preds
)[0]
2123 ? (*succ_new_bb
->preds
)[1] : (*succ_new_bb
->preds
)[0];
2125 add_phi_arg (merge_phi
, init
, other
, get_loc (old_name
));
2128 fprintf (dump_file
, "\n[codegen] Adding guard-phi: ");
2129 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2132 update_stmt (new_phi
);
2138 /* Copy loop close phi nodes from BB to NEW_BB. */
2141 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2145 fprintf (dump_file
, "\n[codegen] copying loop closed phi nodes in bb_%d.",
2147 /* Loop close phi nodes should have only one argument. */
2148 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2150 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2154 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2155 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2156 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2157 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2160 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2161 In this case DOMINATING_PRED = NULL.
2163 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2165 Returns true on successful copy of the args, false otherwise. */
2168 translate_isl_ast_to_gimple::
2169 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2170 edge old_bb_dominating_edge
,
2171 edge old_bb_non_dominating_edge
,
2172 gphi
*phi
, gphi
*new_phi
,
2175 basic_block def_pred
[2] = { NULL
, NULL
};
2176 int not_found_bb_index
= -1;
2177 for (int i
= 0; i
< 2; i
++)
2179 /* If the corresponding def_bb could not be found the entry will be
2181 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2182 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2183 gimple_phi_arg_edge (phi
, i
)->src
);
2184 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2185 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2189 /* When non are available bail out. */
2190 if (not_found_bb_index
!= -1)
2192 not_found_bb_index
= i
;
2196 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2197 if (old_bb_dominating_edge
)
2199 if (not_found_bb_index
!= -1)
2202 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2203 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2204 vec
<basic_block
> *bbs
2205 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2207 /* Could not find a mapping. */
2211 basic_block new_pred
= NULL
;
2214 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2216 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2218 /* FIXME: If we have already found new_pred then we have to
2219 disambiguate, bail out for now. */
2222 new_pred
= new_pred1
;
2224 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2226 /* FIXME: If we have already found new_pred then we have to either
2227 it dominates both or we have to disambiguate, bail out. */
2230 new_pred
= new_pred2
;
2237 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2238 gcc_assert (new_non_dominating_edge
);
2239 /* FIXME: Validate each args just like in loop-phis. */
2240 /* By the process of elimination we first insert insert phi-edge for
2241 non-dominating pred which is computed above and then we insert the
2243 int inserted_edge
= 0;
2244 for (; inserted_edge
< 2; inserted_edge
++)
2246 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2247 if (new_non_dominating_edge
== new_bb_pred_edge
)
2249 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2250 new_non_dominating_edge
,
2251 get_loc (old_phi_args
[inserted_edge
]));
2255 if (inserted_edge
== 2)
2258 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2260 edge new_dominating_edge
= NULL
;
2261 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2263 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2264 if (e
!= new_non_dominating_edge
)
2266 new_dominating_edge
= e
;
2267 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2268 new_dominating_edge
,
2269 get_loc (old_phi_args
[inserted_edge
]));
2273 gcc_assert (new_dominating_edge
);
2277 /* Classic diamond structure: both edges are non-dominating. We need to
2278 find one unique edge then the other can be found be elimination. If
2279 any definition (def_pred) dominates both the preds of new_bb then we
2280 bail out. Entries of def_pred maybe NULL, in that case we must
2281 uniquely find pred with help of only one entry. */
2282 edge new_e
[2] = { NULL
, NULL
};
2283 for (int i
= 0; i
< 2; i
++)
2287 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2289 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2292 /* We do not know how to handle the case when def_pred
2293 dominates more than a predecessor. */
2299 gcc_assert (new_e
[0] || new_e
[1]);
2301 /* Find the other edge by process of elimination. */
2302 if (not_found_bb_index
!= -1)
2304 gcc_assert (!new_e
[not_found_bb_index
]);
2305 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2308 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2310 if (new_e
[found_bb_index
] == e
)
2312 new_e
[not_found_bb_index
] = e
;
2316 /* Add edges to phi args. */
2317 for (int i
= 0; i
< 2; i
++)
2318 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2319 get_loc (old_phi_args
[i
]));
2325 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2326 region. If postpone is true and it isn't possible to copy any arg of PHI,
2327 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2328 Returns false if the copying was unsuccessful. */
2331 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2336 fprintf (dump_file
, "\n[codegen] copying cond phi args: ");
2337 gcc_assert (2 == gimple_phi_num_args (phi
));
2339 basic_block new_bb
= gimple_bb (new_phi
);
2340 loop_p loop
= gimple_bb (phi
)->loop_father
;
2342 basic_block old_bb
= gimple_bb (phi
);
2343 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2347 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2348 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2349 old_bb_non_dominating_edge
= e
;
2351 old_bb_dominating_edge
= e
;
2353 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2354 old_bb_non_dominating_edge
->src
));
2356 tree new_phi_args
[2];
2357 tree old_phi_args
[2];
2359 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2361 tree old_name
= gimple_phi_arg_def (phi
, i
);
2362 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2363 old_phi_args
[i
] = old_name
;
2366 new_phi_args
[i
] = new_name
;
2370 /* If the phi-arg was a parameter. */
2371 if (vec_find (region
->params
, old_name
) != -1)
2373 new_phi_args
[i
] = old_name
;
2377 "\n[codegen] parameter argument to phi, new_expr: ");
2378 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2383 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2384 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2385 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2391 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2392 if (is_gimple_reg (old_name
)
2393 && scev_analyzable_p (old_name
, region
->region
))
2396 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2397 new_bb
, old_bb
, iv_map
);
2398 if (codegen_error_p ())
2401 gcc_assert (new_expr
);
2405 "\n[codegen] scev analyzeable, new_expr: ");
2406 print_generic_expr (dump_file
, new_expr
, 0);
2408 gsi_insert_earliest (stmts
);
2409 new_phi_args
[i
] = new_name
;
2413 /* Postpone code gen for later for back-edges. */
2414 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2418 fprintf (dump_file
, "\n[codegen] postpone cond phi nodes: ");
2419 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2422 new_phi_args
[i
] = NULL_TREE
;
2426 /* Either we should add the arg to phi or, we should postpone. */
2430 /* If none of the args have been determined in the first stage then wait until
2432 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2435 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2436 old_bb_dominating_edge
,
2437 old_bb_non_dominating_edge
,
2438 phi
, new_phi
, new_bb
);
2441 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2442 containing phi nodes coming from two predecessors, and none of them are back
2446 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2451 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2454 fprintf (dump_file
, "\n[codegen] copying cond phi nodes in bb_%d:",
2457 /* Cond phi nodes should have exactly two arguments. */
2458 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2460 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2463 gphi
*phi
= psi
.phi ();
2464 tree res
= gimple_phi_result (phi
);
2465 if (virtual_operand_p (res
))
2467 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2468 /* Cond phi nodes should not be scev_analyzable_p. */
2471 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2472 tree new_res
= create_new_def_for (res
, new_phi
,
2473 gimple_phi_result_ptr (new_phi
));
2474 set_rename (res
, new_res
);
2476 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2479 update_stmt (new_phi
);
2485 /* Return true if STMT should be copied from region to the new code-generated
2486 region. LABELs, CONDITIONS, induction-variables and region parameters need
2490 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2492 /* Do not copy labels or conditions. */
2493 if (gimple_code (stmt
) == GIMPLE_LABEL
2494 || gimple_code (stmt
) == GIMPLE_COND
)
2498 /* Do not copy induction variables. */
2499 if (is_gimple_assign (stmt
)
2500 && (lhs
= gimple_assign_lhs (stmt
))
2501 && TREE_CODE (lhs
) == SSA_NAME
2502 && is_gimple_reg (lhs
)
2503 && scev_analyzable_p (lhs
, region
->region
))
2509 /* Create new names for all the definitions created by COPY and add replacement
2510 mappings for each new name. */
2513 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2515 def_operand_p def_p
;
2516 ssa_op_iter op_iter
;
2517 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2519 tree old_name
= DEF_FROM_PTR (def_p
);
2520 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2521 set_rename (old_name
, new_name
);
2525 /* Duplicates the statements of basic block BB into basic block NEW_BB
2526 and compute the new induction variables according to the IV_MAP.
2527 CODEGEN_ERROR is set when the code generation cannot continue. */
2530 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2534 /* Iterator poining to the place where new statement (s) will be inserted. */
2535 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2537 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2540 gimple
*stmt
= gsi_stmt (gsi
);
2541 if (!should_copy_to_new_region (stmt
, region
))
2544 /* Create a new copy of STMT and duplicate STMT's virtual
2546 gimple
*copy
= gimple_copy (stmt
);
2547 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2551 fprintf (dump_file
, "\n[codegen] inserting statement: ");
2552 print_gimple_stmt (dump_file
, copy
, 0, 0);
2555 maybe_duplicate_eh_stmt (copy
, stmt
);
2556 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2558 /* Crete new names for each def in the copied stmt. */
2559 set_rename_for_each_def (copy
);
2561 loop_p loop
= bb
->loop_father
;
2562 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2564 fold_stmt_inplace (&gsi_tgt
);
2565 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2568 if (codegen_error_p ())
2578 /* Given a basic block containing close-phi it returns the new basic block where
2579 to insert a copy of the close-phi nodes. All the uses in close phis should
2580 come from a single loop otherwise it returns NULL. */
2583 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2585 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2586 of close phi in the original code and then find the mapping of basic block
2587 defining that variable. If there are multiple close-phis and they are
2588 defined in different loops (in the original or in the new code) because of
2589 loop splitting, then we bail out. */
2590 loop_p new_loop
= NULL
;
2591 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2594 gphi
*phi
= psi
.phi ();
2595 tree name
= gimple_phi_arg_def (phi
, 0);
2596 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2598 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2599 if (!bbs
|| bbs
->length () != 1)
2600 /* This is one of the places which shows preserving original structure
2601 is not always possible, as we may need to insert close PHI for a loop
2602 where the latch does not have any mapping, or the mapping is
2607 new_loop
= (*bbs
)[0]->loop_father
;
2608 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2615 return single_exit (new_loop
);
2618 /* Copies BB and includes in the copied BB all the statements that can
2619 be reached following the use-def chains from the memory accesses,
2620 and returns the next edge following this new block. codegen_error is
2621 set when the code generation cannot continue. */
2624 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2628 int num_phis
= number_of_phi_nodes (bb
);
2630 if (region
->copied_bb_map
->get (bb
))
2632 /* FIXME: we should be able to handle phi nodes with args coming from
2633 outside the region. */
2636 codegen_error
= true;
2641 basic_block new_bb
= split_edge (next_e
);
2642 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2644 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2646 /* At this point we are unable to codegenerate by still preserving the SSA
2647 structure because maybe the loop is completely unrolled and the PHIs
2648 and cross-bb scalar dependencies are untrackable w.r.t. the original
2649 code. See gfortran.dg/graphite/pr29832.f90. */
2650 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2652 codegen_error
= true;
2657 fprintf (dump_file
, "\n[codegen] bb_%d contains loop phi nodes",
2659 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2661 codegen_error
= true;
2665 else if (bb_contains_loop_close_phi_nodes (bb
))
2668 fprintf (dump_file
, "\n[codegen] bb_%d contains close phi nodes",
2671 edge e
= edge_for_new_close_phis (bb
);
2674 codegen_error
= true;
2678 basic_block phi_bb
= split_edge (e
);
2679 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2680 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2682 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2684 codegen_error
= true;
2688 else if (num_phis
> 0)
2691 fprintf (dump_file
, "\n[codegen] bb_%d contains cond phi nodes",
2694 basic_block phi_bb
= single_pred (new_bb
);
2695 loop_p loop_father
= new_bb
->loop_father
;
2697 /* Move back until we find the block with two predecessors. */
2698 while (single_pred_p (phi_bb
))
2699 phi_bb
= single_pred_edge (phi_bb
)->src
;
2701 /* If a corresponding merge-point was not found, then abort codegen. */
2702 if (phi_bb
->loop_father
!= loop_father
2703 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2705 codegen_error
= true;
2711 fprintf (dump_file
, "\n[codegen] copying from bb_%d to bb_%d",
2712 bb
->index
, new_bb
->index
);
2714 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2716 copied_bbs
->safe_push (new_bb
);
2719 vec
<basic_block
> bbs
;
2721 bbs
.safe_push (new_bb
);
2722 region
->copied_bb_map
->put (bb
, bbs
);
2725 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2727 codegen_error
= true;
2731 return single_succ_edge (new_bb
);
2734 /* Patch the missing arguments of the phi nodes. */
2737 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2741 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2743 gphi
*old_phi
= rename
->first
;
2744 gphi
*new_phi
= rename
->second
;
2745 basic_block old_bb
= gimple_bb (old_phi
);
2746 basic_block new_bb
= gimple_bb (new_phi
);
2748 /* First edge is the init edge and second is the back edge. */
2749 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2750 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2754 fprintf (dump_file
, "\n[codegen] translating pending old-phi: ");
2755 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2758 auto_vec
<tree
, 1> iv_map
;
2759 if (bb_contains_loop_phi_nodes (new_bb
))
2760 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2762 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2763 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2765 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2769 fprintf (dump_file
, "[codegen] to new-phi: ");
2770 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2775 /* Prints NODE to FILE. */
2778 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
2779 __isl_keep isl_ast_node
*node
,
2780 __isl_keep isl_ctx
*ctx
) const
2782 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
2783 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
2784 prn
= isl_printer_print_ast_node (prn
, node
);
2785 prn
= isl_printer_print_str (prn
, "\n");
2786 isl_printer_free (prn
);
2789 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
2792 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
2795 sese_info_p region
= scop
->scop_info
;
2796 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2797 gcc_assert (nb_parameters
== region
->params
.length ());
2799 for (i
= 0; i
< nb_parameters
; i
++)
2801 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2803 ip
[tmp_id
] = region
->params
[i
];
2808 /* Generates a build, which specifies the constraints on the parameters. */
2810 __isl_give isl_ast_build
*
2811 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
2813 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2814 return isl_ast_build_from_context (context_isl
);
2817 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2820 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
2824 int schedule_dims
= 0;
2826 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2828 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
2829 if (pbb_schedule_dims
> schedule_dims
)
2830 schedule_dims
= pbb_schedule_dims
;
2833 return schedule_dims
;
2836 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2838 For schedules with different dimensionality, the isl AST generator can not
2839 define an order and will just randomly choose an order. The solution to this
2840 problem is to extend all schedules to the maximal number of schedule
2841 dimensions (using '0's for the remaining values). */
2843 __isl_give isl_map
*
2844 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
2845 int nb_schedule_dims
)
2847 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
2849 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
2851 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
2853 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
2856 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
2858 isl_val_free (zero
);
2862 /* Generates a schedule, which specifies an order used to
2863 visit elements in a domain. */
2865 __isl_give isl_union_map
*
2866 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
2868 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
2871 isl_union_map
*schedule_isl
=
2872 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
2874 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2876 /* Dead code elimination: when the domain of a PBB is empty,
2877 don't generate code for the PBB. */
2878 if (isl_set_is_empty (pbb
->domain
))
2881 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
2882 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
2883 isl_set_copy (pbb
->domain
));
2884 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
2886 = isl_union_map_union (schedule_isl
,
2887 isl_union_map_from_map (bb_schedule
));
2889 return schedule_isl
;
2892 /* This method is executed before the construction of a for node. */
2894 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2896 isl_union_map
*dependences
= (isl_union_map
*) user
;
2897 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2898 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2899 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2900 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2901 for_info
->is_parallelizable
=
2902 !carries_deps (schedule
, dependences
, dimension
);
2903 isl_union_map_free (schedule
);
2904 isl_space_free (schedule_space
);
2905 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2909 /* Set the separate option for all dimensions.
2910 This helps to reduce control overhead. */
2912 __isl_give isl_ast_build
*
2913 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
2914 __isl_keep isl_union_map
*schedule
)
2916 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
2917 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
2919 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
2920 isl_union_set
*range
=
2921 isl_union_set_from_set (isl_set_universe (range_space
));
2922 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
2923 domain
= isl_union_set_universe (domain
);
2924 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
2925 return isl_ast_build_set_options (control
, options
);
2928 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
2930 __isl_give isl_ast_node
*
2931 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
2933 /* Generate loop upper bounds that consist of the current loop iterator, an
2934 operator (< or <=) and an expression not involving the iterator. If this
2935 option is not set, then the current loop iterator may appear several times
2936 in the upper bound. See the isl manual for more details. */
2937 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
2939 add_parameters_to_ivs_params (scop
, ip
);
2940 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
2941 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2942 context_isl
= set_options (context_isl
, schedule_isl
);
2943 isl_union_map
*dependences
= NULL
;
2944 if (flag_loop_parallelize_all
)
2946 dependences
= scop_get_dependences (scop
);
2948 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2951 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
2954 isl_union_map_free (dependences
);
2955 isl_ast_build_free (context_isl
);
2959 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
2960 the given SCOP. Return true if code generation succeeded.
2962 FIXME: This is not yet a full implementation of the code generator
2963 with ISL ASTs. Generation of GIMPLE code has to be completed. */
2966 graphite_regenerate_ast_isl (scop_p scop
)
2968 sese_info_p region
= scop
->scop_info
;
2969 translate_isl_ast_to_gimple
t (region
);
2971 ifsese if_region
= NULL
;
2972 isl_ast_node
*root_node
;
2975 timevar_push (TV_GRAPHITE_CODE_GEN
);
2976 root_node
= t
.scop_to_isl_ast (scop
, ip
);
2978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2980 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
2981 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
2984 recompute_all_dominators ();
2987 if_region
= move_sese_in_condition (region
);
2988 region
->if_region
= if_region
;
2989 recompute_all_dominators ();
2991 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2993 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2994 basic_block bb
= split_edge (e
);
2996 /* Update the true_region exit edge. */
2997 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2999 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3000 if (t
.codegen_error_p ())
3003 fprintf (dump_file
, "\n[codegen] unsuccessful,"
3004 " reverting back to the original code.");
3005 set_ifsese_condition (if_region
, integer_zero_node
);
3009 t
.translate_pending_phi_nodes ();
3010 if (!t
.codegen_error_p ())
3012 sese_insert_phis_for_liveouts (region
,
3013 if_region
->region
->region
.exit
->src
,
3014 if_region
->false_region
->region
.exit
,
3015 if_region
->true_region
->region
.exit
);
3016 mark_virtual_operands_for_renaming (cfun
);
3017 update_ssa (TODO_update_ssa
);
3022 recompute_all_dominators ();
3028 fprintf (dump_file
, "\n[codegen] unsuccessful in translating"
3029 " pending phis, reverting back to the original code.");
3030 set_ifsese_condition (if_region
, integer_zero_node
);
3034 free (if_region
->true_region
);
3035 free (if_region
->region
);
3038 ivs_params_clear (ip
);
3039 isl_ast_node_free (root_node
);
3040 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3045 int num_no_dependency
= 0;
3047 FOR_EACH_LOOP (loop
, 0)
3048 if (loop
->can_be_parallel
)
3049 num_no_dependency
++;
3051 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
3055 return !t
.codegen_error_p ();
3058 #endif /* HAVE_isl */