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 void 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 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
403 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
404 the other pred of OLD_BB as well. If no such basic block exists then it is
405 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
408 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
409 versa. In this case DOMINATING_PRED = NULL.
411 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
413 Returns true on successful copy of the args, false otherwise. */
415 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
416 edge old_bb_dominating_edge
,
417 edge old_bb_non_dominating_edge
,
418 gphi
*phi
, gphi
*new_phi
,
421 /* Renames the scalar uses of the statement COPY, using the substitution map
422 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
423 translation REGION, with the original copied statement in LOOP, and using
424 the induction variable renaming map IV_MAP. Returns true when something
425 has been renamed. codegen_error is set when the code generation cannot
428 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
429 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
431 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
432 When OLD_NAME and EXPR are the same we assert. */
434 void set_rename (tree old_name
, tree expr
);
436 /* Create new names for all the definitions created by COPY and add
437 replacement mappings for each new name. */
439 void set_rename_for_each_def (gimple
*stmt
);
441 /* Insert each statement from SEQ at its earliest insertion p. */
443 void gsi_insert_earliest (gimple_seq seq
);
445 /* Rename all the operands of NEW_EXPR by recursively visiting each
448 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
450 bool codegen_error_p () const
451 { return codegen_error
; }
453 /* Prints NODE to FILE. */
455 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
456 __isl_keep isl_ctx
*ctx
) const;
461 /* This flag is set when an error occurred during the translation of ISL AST
466 /* Return the tree variable that corresponds to the given isl ast identifier
467 expression (an isl_ast_expr of type isl_ast_expr_id).
469 FIXME: We should replace blind conversation of id's type with derivation
470 of the optimal type when we get the corresponding isl support. Blindly
471 converting type sizes may be problematic when we switch to smaller
475 translate_isl_ast_to_gimple::
476 gcc_expression_from_isl_ast_expr_id (tree type
,
477 __isl_keep isl_ast_expr
*expr_id
,
480 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
481 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
482 std::map
<isl_id
*, tree
>::iterator res
;
483 res
= ip
.find (tmp_isl_id
);
484 isl_id_free (tmp_isl_id
);
485 gcc_assert (res
!= ip
.end () &&
486 "Could not map isl_id to tree expression");
487 isl_ast_expr_free (expr_id
);
488 tree t
= res
->second
;
489 return fold_convert (type
, t
);
492 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
496 translate_isl_ast_to_gimple::
497 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
499 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
500 isl_val
*val
= isl_ast_expr_get_val (expr
);
502 mpz_init (val_mpz_t
);
504 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
507 res
= gmp_cst_to_tree (type
, val_mpz_t
);
509 isl_ast_expr_free (expr
);
510 mpz_clear (val_mpz_t
);
514 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
518 translate_isl_ast_to_gimple::
519 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
521 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
522 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
523 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
524 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
525 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
526 isl_ast_expr_free (expr
);
530 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
533 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
536 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
539 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
541 case isl_ast_op_pdiv_q
:
542 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
544 case isl_ast_op_pdiv_r
:
545 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
547 case isl_ast_op_fdiv_q
:
548 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
551 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
552 tree_lhs_expr
, tree_rhs_expr
);
555 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
558 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
561 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
564 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
567 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
570 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
577 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
581 translate_isl_ast_to_gimple::
582 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
584 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
585 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
587 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
588 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
589 tree tree_second_expr
590 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
591 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
593 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
594 isl_ast_expr_free (expr
);
595 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
596 tree_second_expr
, tree_third_expr
);
599 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
603 translate_isl_ast_to_gimple::
604 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
606 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
607 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
608 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
609 isl_ast_expr_free (expr
);
610 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
613 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
614 to a GCC expression tree of type TYPE. */
617 translate_isl_ast_to_gimple::
618 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
620 enum tree_code op_code
;
621 switch (isl_ast_expr_get_op_type (expr
))
634 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
635 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
637 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
639 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
640 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
641 res
= fold_build2 (op_code
, type
, res
, t
);
643 isl_ast_expr_free (expr
);
647 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
651 translate_isl_ast_to_gimple::
652 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
655 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
656 switch (isl_ast_expr_get_op_type (expr
))
658 /* These isl ast expressions are not supported yet. */
659 case isl_ast_op_error
:
660 case isl_ast_op_call
:
661 case isl_ast_op_and_then
:
662 case isl_ast_op_or_else
:
663 case isl_ast_op_select
:
668 return nary_op_to_tree (type
, expr
, ip
);
674 case isl_ast_op_pdiv_q
:
675 case isl_ast_op_pdiv_r
:
676 case isl_ast_op_fdiv_q
:
684 return binary_op_to_tree (type
, expr
, ip
);
686 case isl_ast_op_minus
:
687 return unary_op_to_tree (type
, expr
, ip
);
689 case isl_ast_op_cond
:
690 return ternary_op_to_tree (type
, expr
, ip
);
699 /* Converts an ISL AST expression E back to a GCC expression tree of
703 translate_isl_ast_to_gimple::
704 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
707 switch (isl_ast_expr_get_type (expr
))
709 case isl_ast_expr_id
:
710 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
712 case isl_ast_expr_int
:
713 return gcc_expression_from_isl_expr_int (type
, expr
);
715 case isl_ast_expr_op
:
716 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
725 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
726 induction variable for the new LOOP. New LOOP is attached to CFG
727 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
728 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
729 ISL's scattering name to the induction variable created for the
730 loop of STMT. The new induction variable is inserted in the NEWIVS
731 vector and is of type TYPE. */
734 translate_isl_ast_to_gimple::
735 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
736 loop_p outer
, tree type
, tree lb
, tree ub
,
739 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
740 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
741 tree ivvar
= create_tmp_var (type
, "graphite_IV");
742 tree iv
, iv_after_increment
;
743 loop_p loop
= create_empty_loop_on_edge
744 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
745 outer
? outer
: entry_edge
->src
->loop_father
);
747 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
748 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
749 std::map
<isl_id
*, tree
>::iterator res
;
752 isl_id_free (res
->first
);
754 isl_ast_expr_free (for_iterator
);
758 /* Create the loop for a isl_ast_node_for.
760 - NEXT_E is the edge where new generated code should be attached. */
763 translate_isl_ast_to_gimple::
764 translate_isl_ast_for_loop (loop_p context_loop
,
765 __isl_keep isl_ast_node
*node_for
, edge next_e
,
766 tree type
, tree lb
, tree ub
,
769 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
770 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
772 edge last_e
= single_exit (loop
);
773 edge to_body
= single_succ_edge (loop
->header
);
774 basic_block after
= to_body
->dest
;
776 /* Translate the body of the loop. */
777 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
778 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
779 isl_ast_node_free (for_body
);
781 /* Early return if we failed to translate loop body. */
782 if (!next_e
|| codegen_error_p ())
785 redirect_edge_succ_nodup (next_e
, after
);
786 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
788 if (flag_loop_parallelize_all
)
790 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
792 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
793 loop
->can_be_parallel
= for_info
->is_parallelizable
;
801 /* We use this function to get the upper bound because of the form,
802 which is used by isl to represent loops:
804 for (iterator = init; cond; iterator += inc)
812 The loop condition is an arbitrary expression, which contains the
813 current loop iterator.
815 (e.g. iterator + 3 < B && C > iterator + A)
817 We have to know the upper bound of the iterator to generate a loop
818 in Gimple form. It can be obtained from the special representation
819 of the loop condition, which is generated by isl,
820 if the ast_build_atomic_upper_bound option is set. In this case,
821 isl generates a loop condition that consists of the current loop
822 iterator, + an operator (< or <=) and an expression not involving
823 the iterator, which is processed and returned by this function.
825 (e.g iterator <= upper-bound-expression-without-iterator) */
827 static __isl_give isl_ast_expr
*
828 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
830 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
831 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
832 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
834 switch (isl_ast_expr_get_op_type (for_cond
))
837 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
842 /* (iterator < ub) => (iterator <= ub - 1). */
844 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
845 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
846 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
853 isl_ast_expr_free (for_cond
);
857 /* All loops generated by create_empty_loop_on_edge have the form of
864 } while (lower bound < upper bound);
866 We create a new if region protecting the loop to be executed, if
867 the execution count is zero (lower bound > upper bound). */
870 translate_isl_ast_to_gimple::
871 graphite_create_new_loop_guard (edge entry_edge
,
872 __isl_keep isl_ast_node
*node_for
, tree
*type
,
873 tree
*lb
, tree
*ub
, ivs_params
&ip
)
875 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
880 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
881 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
882 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
883 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
884 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
886 /* When ub is simply a constant or a parameter, use lb <= ub. */
887 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
888 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
891 tree one
= (POINTER_TYPE_P (*type
)
892 ? convert_to_ptrofftype (integer_one_node
)
893 : fold_convert (*type
, integer_one_node
));
894 /* Adding +1 and using LT_EXPR helps with loop latches that have a
895 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
896 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
897 is true, even if we do not want this. However lb < ub + 1 is false,
899 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
900 : PLUS_EXPR
, *type
, *ub
, one
);
902 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
905 if (integer_onep (cond_expr
))
906 exit_edge
= entry_edge
;
908 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
913 /* Translates an isl_ast_node_for to Gimple. */
916 translate_isl_ast_to_gimple::
917 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
918 edge next_e
, ivs_params
&ip
)
920 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
922 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
925 if (last_e
== next_e
)
926 /* There was no guard generated. */
927 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
930 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
931 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
935 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
936 variables of the loops around GBB in SESE.
938 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
939 chrec, we could consider using a map<int, tree> that maps loop ids to the
940 corresponding tree expressions. */
943 translate_isl_ast_to_gimple::
944 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
945 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
948 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
949 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
951 isl_ast_expr
*arg_expr
;
952 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
954 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
956 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
957 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
958 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
959 iv_map
[old_loop
->num
] = t
;
963 /* Translates an isl_ast_node_user to Gimple.
965 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
968 translate_isl_ast_to_gimple::
969 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
970 edge next_e
, ivs_params
&ip
)
972 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
974 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
975 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
976 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
978 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
979 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
982 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
984 isl_ast_expr_free (name_expr
);
985 isl_id_free (name_id
);
987 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
988 "The entry block should not even appear within a scop");
990 const int nb_loops
= number_of_loops (cfun
);
992 iv_map
.create (nb_loops
);
993 iv_map
.safe_grow_cleared (nb_loops
);
995 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
996 isl_ast_expr_free (user_expr
);
1000 fprintf (dump_file
, "[codegen] copying from basic block\n");
1001 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1002 fprintf (dump_file
, "\n[codegen] to new basic block\n");
1003 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1006 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1011 if (codegen_error_p ())
1016 fprintf (dump_file
, "\n[codegen] (after copy) new basic block\n");
1017 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1020 mark_virtual_operands_for_renaming (cfun
);
1021 update_ssa (TODO_update_ssa
);
1025 fprintf (dump_file
, "\n[codegen] (after update SSA) new basic block\n");
1026 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1032 /* Translates an isl_ast_node_block to Gimple. */
1035 translate_isl_ast_to_gimple::
1036 translate_isl_ast_node_block (loop_p context_loop
,
1037 __isl_keep isl_ast_node
*node
,
1038 edge next_e
, ivs_params
&ip
)
1040 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1041 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1043 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1045 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1046 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1047 isl_ast_node_free (tmp_node
);
1049 isl_ast_node_list_free (node_list
);
1053 /* Creates a new if region corresponding to ISL's cond. */
1056 translate_isl_ast_to_gimple::
1057 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1061 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1062 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1063 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1067 /* Translates an isl_ast_node_if to Gimple. */
1070 translate_isl_ast_to_gimple::
1071 translate_isl_ast_node_if (loop_p context_loop
,
1072 __isl_keep isl_ast_node
*node
,
1073 edge next_e
, ivs_params
&ip
)
1075 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1076 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1077 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1079 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1080 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1081 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1082 isl_ast_node_free (then_node
);
1084 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1085 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1086 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1087 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1088 isl_ast_node_free (else_node
);
1092 /* Translates an ISL AST node NODE to GCC representation in the
1093 context of a SESE. */
1096 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1097 __isl_keep isl_ast_node
*node
,
1098 edge next_e
, ivs_params
&ip
)
1100 if (codegen_error_p ())
1103 switch (isl_ast_node_get_type (node
))
1105 case isl_ast_node_error
:
1108 case isl_ast_node_for
:
1109 return translate_isl_ast_node_for (context_loop
, node
,
1112 case isl_ast_node_if
:
1113 return translate_isl_ast_node_if (context_loop
, node
,
1116 case isl_ast_node_user
:
1117 return translate_isl_ast_node_user (node
, next_e
, ip
);
1119 case isl_ast_node_block
:
1120 return translate_isl_ast_node_block (context_loop
, node
,
1128 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
1131 get_true_edge_from_guard_bb (basic_block bb
)
1136 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1137 if (e
->flags
& EDGE_TRUE_VALUE
)
1144 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
1147 get_false_edge_from_guard_bb (basic_block bb
)
1152 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1153 if (!(e
->flags
& EDGE_TRUE_VALUE
))
1160 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1161 at the exit of loop which takes one argument that is the last value of the
1162 variable being used out of the loop. */
1165 bb_contains_loop_close_phi_nodes (basic_block bb
)
1167 return single_pred_p (bb
)
1168 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1171 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1172 header containing phi nodes which has one init-edge and one back-edge. */
1175 bb_contains_loop_phi_nodes (basic_block bb
)
1177 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1179 if (bb
->preds
->length () == 1)
1182 unsigned depth
= loop_depth (bb
->loop_father
);
1184 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1186 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1187 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1190 /* When one of the edges correspond to the same loop father and other
1192 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1193 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1196 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1197 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1203 /* Check if USE is defined in a basic block from where the definition of USE can
1204 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1207 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1209 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1212 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1213 if (bb_contains_loop_close_phi_nodes (bb
))
1216 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1217 basic_block def_bb
= gimple_bb (def
);
1219 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1222 /* Return the number of phi nodes in BB. */
1225 number_of_phi_nodes (basic_block bb
)
1228 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1234 /* Returns true if BB uses name in one of its PHIs. */
1237 phi_uses_name (basic_block bb
, tree name
)
1239 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1242 gphi
*phi
= psi
.phi ();
1243 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1245 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1246 if (use_arg
== name
)
1253 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1254 definition should flow into use, and the use should respect the loop-closed
1258 translate_isl_ast_to_gimple::
1259 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1260 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1262 /* The def of the rename must either dominate the uses or come from a
1263 back-edge. Also the def must respect the loop closed ssa form. */
1264 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1268 fprintf (dump_file
, "\n[codegen] rename not in loop closed ssa:");
1269 print_generic_expr (dump_file
, rename
, 0);
1274 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1277 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1279 /* The loop-header dominates the loop-body. */
1280 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1283 /* RENAME would be used in loop-phi. */
1284 gcc_assert (number_of_phi_nodes (use_bb
));
1286 /* For definitions coming from back edges, we should check that
1287 old_name is used in a loop PHI node.
1288 FIXME: Verify if this is true. */
1289 if (phi_uses_name (old_bb
, old_name
))
1295 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1296 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1297 within a loop PHI instruction. */
1300 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1303 bool loop_phi
) const
1305 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1306 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1308 if (!renames
|| renames
->is_empty ())
1311 if (1 == renames
->length ())
1313 tree rename
= (*renames
)[0];
1314 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1315 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1320 /* More than one renames corresponding to the old_name. Find the rename for
1321 which the definition flows into usage at new_bb. */
1323 tree t1
= NULL_TREE
, t2
;
1324 basic_block t1_bb
= NULL
;
1325 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1327 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1329 /* Defined in the same basic block as used. */
1330 if (t2_bb
== new_bb
)
1333 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1334 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1337 /* Compute the nearest dominator. */
1338 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1348 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1349 When OLD_NAME and EXPR are the same we assert. */
1352 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1356 fprintf (dump_file
, "\n[codegen] setting rename: old_name = ");
1357 print_generic_expr (dump_file
, old_name
, 0);
1358 fprintf (dump_file
, ", new_name = ");
1359 print_generic_expr (dump_file
, expr
, 0);
1362 if (old_name
== expr
)
1365 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1368 renames
->safe_push (expr
);
1374 region
->rename_map
->put (old_name
, r
);
1378 /* Return an iterator to the instructions comes last in the execution order.
1379 Either GSI1 and GSI2 should belong to the same basic block or one of their
1380 respective basic blocks should dominate the other. */
1382 gimple_stmt_iterator
1383 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1385 basic_block bb1
= gsi_bb (gsi1
);
1386 basic_block bb2
= gsi_bb (gsi2
);
1388 /* Find the iterator which is the latest. */
1391 /* For empty basic blocks gsis point to the end of the sequence. Since
1392 there is no operator== defined for gimple_stmt_iterator and for gsis
1393 not pointing to a valid statement gsi_next would assert. */
1394 gimple_stmt_iterator gsi
= gsi1
;
1396 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1399 } while (!gsi_end_p (gsi
));
1404 /* Find the basic block closest to the basic block which defines stmt. */
1405 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1408 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1412 /* Insert each statement from SEQ at its earliest insertion p. */
1415 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1417 update_modified_stmts (seq
);
1418 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1419 basic_block begin_bb
= get_entry_bb (codegen_region
);
1421 /* Inserting the gimple statements in a vector because gimple_seq behave
1422 in strage ways when inserting the stmts from it into different basic
1423 blocks one at a time. */
1424 auto_vec
<gimple
*, 3> stmts
;
1425 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1427 stmts
.safe_push (gsi_stmt (gsi
));
1431 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1433 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1434 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1436 use_operand_p use_p
;
1437 ssa_op_iter op_iter
;
1438 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1440 /* Iterator to the current def of use_p. For function parameters or
1441 anything where def is not found, insert at the beginning of the
1442 generated region. */
1443 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1445 tree op
= USE_FROM_PTR (use_p
);
1446 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1447 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1448 gsi_stmt
= gsi_for_stmt (stmt
);
1450 /* For region parameters, insert at the beginning of the generated
1452 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1453 gsi_stmt
= gsi_def_stmt
;
1455 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1458 if (!gsi_stmt (gsi_def_stmt
))
1460 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1461 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1463 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1465 gimple_stmt_iterator bsi
1466 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1467 /* Insert right after the PHI statements. */
1468 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1471 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1475 fprintf (dump_file
, "\n[codegen] inserting statement: ");
1476 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1477 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1482 /* Collect all the operands of NEW_EXPR by recursively visiting each
1486 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1490 /* Rename all uses in new_expr. */
1491 if (TREE_CODE (new_expr
) == SSA_NAME
)
1493 vec_ssa
->safe_push (new_expr
);
1497 /* Iterate over SSA_NAMES in NEW_EXPR. */
1498 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1500 tree op
= TREE_OPERAND (new_expr
, i
);
1501 collect_all_ssa_names (op
, vec_ssa
);
1505 /* This is abridged version of the function:
1506 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1509 substitute_ssa_name (tree exp
, tree f
, tree r
)
1511 enum tree_code code
= TREE_CODE (exp
);
1512 tree op0
, op1
, op2
, op3
;
1515 /* We handle TREE_LIST and COMPONENT_REF separately. */
1516 if (code
== TREE_LIST
)
1518 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1519 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1520 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1523 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1525 else if (code
== COMPONENT_REF
)
1529 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1530 and it is the right field, replace it with R. */
1531 for (inner
= TREE_OPERAND (exp
, 0);
1532 REFERENCE_CLASS_P (inner
);
1533 inner
= TREE_OPERAND (inner
, 0))
1537 op1
= TREE_OPERAND (exp
, 1);
1539 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1542 /* If this expression hasn't been completed let, leave it alone. */
1543 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1546 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1547 if (op0
== TREE_OPERAND (exp
, 0))
1551 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1554 switch (TREE_CODE_CLASS (code
))
1559 case tcc_declaration
:
1565 case tcc_expression
:
1569 /* Fall through... */
1571 case tcc_exceptional
:
1574 case tcc_comparison
:
1576 switch (TREE_CODE_LENGTH (code
))
1584 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1585 if (op0
== TREE_OPERAND (exp
, 0))
1588 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1592 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1593 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1595 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1598 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1602 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1603 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1604 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1606 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1607 && op2
== TREE_OPERAND (exp
, 2))
1610 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1614 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1615 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1616 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1617 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1619 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1620 && op2
== TREE_OPERAND (exp
, 2)
1621 && op3
== TREE_OPERAND (exp
, 3))
1625 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1638 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1640 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1641 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1646 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1649 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1652 auto_vec
<tree
, 2> ssa_names
;
1653 collect_all_ssa_names (new_expr
, &ssa_names
);
1656 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1657 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1658 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1663 /* For ops which are scev_analyzeable, we can regenerate a new name from
1664 its scalar evolution around LOOP. */
1667 translate_isl_ast_to_gimple::
1668 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1669 basic_block new_bb
, basic_block old_bb
,
1672 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1674 /* At this point we should know the exact scev for each
1675 scalar SSA_NAME used in the scop: all the other scalar
1676 SSA_NAMEs should have been translated out of SSA using
1677 arrays with one element. */
1679 if (chrec_contains_undetermined (scev
))
1681 codegen_error
= true;
1682 return build_zero_cst (TREE_TYPE (old_name
));
1685 new_expr
= chrec_apply_map (scev
, iv_map
);
1687 /* The apply should produce an expression tree containing
1688 the uses of the new induction variables. We should be
1689 able to use new_expr instead of the old_name in the newly
1690 generated loop nest. */
1691 if (chrec_contains_undetermined (new_expr
)
1692 || tree_contains_chrecs (new_expr
, NULL
))
1694 codegen_error
= true;
1695 return build_zero_cst (TREE_TYPE (old_name
));
1698 /* We should check all the operands and all of them should dominate the use at
1700 if (TREE_CODE (new_expr
) == SSA_NAME
)
1702 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1703 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1705 /* FIXME: Remove if bootstrap passes. */
1706 codegen_error
= true;
1708 return build_zero_cst (TREE_TYPE (old_name
));
1712 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1713 /* We should check all the operands and all of them should dominate the use at
1715 if (TREE_CODE (new_expr
) == SSA_NAME
)
1717 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1718 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1720 /* FIXME: Remove if bootstrap passes. */
1721 codegen_error
= true;
1723 return build_zero_cst (TREE_TYPE (old_name
));
1727 /* Replace the old_name with the new_expr. */
1728 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1732 /* Renames the scalar uses of the statement COPY, using the
1733 substitution map RENAME_MAP, inserting the gimplification code at
1734 GSI_TGT, for the translation REGION, with the original copied
1735 statement in LOOP, and using the induction variable renaming map
1736 IV_MAP. Returns true when something has been renamed. codegen_error
1737 is set when the code generation cannot continue. */
1740 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1741 gimple_stmt_iterator
*gsi_tgt
,
1743 loop_p loop
, vec
<tree
> iv_map
)
1745 bool changed
= false;
1747 if (is_gimple_debug (copy
))
1749 if (gimple_debug_bind_p (copy
))
1750 gimple_debug_bind_reset_value (copy
);
1751 else if (gimple_debug_source_bind_p (copy
))
1761 fprintf (dump_file
, "\n[codegen] renaming uses of stmt: ");
1762 print_gimple_stmt (dump_file
, copy
, 0, 0);
1765 use_operand_p use_p
;
1766 ssa_op_iter op_iter
;
1767 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1769 tree old_name
= USE_FROM_PTR (use_p
);
1773 fprintf (dump_file
, "\n[codegen] renaming old_name = ");
1774 print_generic_expr (dump_file
, old_name
, 0);
1777 if (TREE_CODE (old_name
) != SSA_NAME
1778 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1782 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1787 tree type_old_name
= TREE_TYPE (old_name
);
1788 tree type_new_expr
= TREE_TYPE (new_expr
);
1792 fprintf (dump_file
, "\n[codegen] from rename_map: new_name = ");
1793 print_generic_expr (dump_file
, new_expr
, 0);
1796 if (type_old_name
!= type_new_expr
1797 || TREE_CODE (new_expr
) != SSA_NAME
)
1799 tree var
= create_tmp_var (type_old_name
, "var");
1801 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1802 new_expr
= fold_convert (type_old_name
, new_expr
);
1805 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1806 gsi_insert_earliest (stmts
);
1809 replace_exp (use_p
, new_expr
);
1814 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1816 if (!new_expr
|| codegen_error_p ())
1821 fprintf (dump_file
, "\n[codegen] not in rename map, scev: ");
1822 print_generic_expr (dump_file
, new_expr
, 0);
1825 gsi_insert_earliest (stmts
);
1826 replace_exp (use_p
, new_expr
);
1828 if (TREE_CODE (new_expr
) == INTEGER_CST
1829 && is_gimple_assign (copy
))
1831 tree rhs
= gimple_assign_rhs1 (copy
);
1833 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1834 recompute_tree_invariant_for_addr_expr (rhs
);
1837 set_rename (old_name
, new_expr
);
1843 /* Returns a basic block that could correspond to where a constant was defined
1844 in the original code. In the original code OLD_BB had the definition, we
1845 need to find which basic block out of the copies of old_bb, in the new
1846 region, should a definition correspond to if it has to reach BB. */
1849 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1850 basic_block old_bb
) const
1852 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1854 if (!bbs
|| bbs
->is_empty ())
1857 if (1 == bbs
->length ())
1861 basic_block b1
= NULL
, b2
;
1862 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1867 /* BB and B2 are in two unrelated if-clauses. */
1868 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1871 /* Compute the nearest dominator. */
1872 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1880 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1881 when we want to rename an OP within a loop PHI instruction. */
1884 translate_isl_ast_to_gimple::
1885 get_new_name (basic_block new_bb
, tree op
,
1886 basic_block old_bb
, bool loop_phi
) const
1888 /* For constants the names are the same. */
1889 if (TREE_CODE (op
) == INTEGER_CST
1890 || TREE_CODE (op
) == REAL_CST
1891 || TREE_CODE (op
) == COMPLEX_CST
1892 || TREE_CODE (op
) == VECTOR_CST
)
1895 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1898 /* Return a debug location for OP. */
1903 location_t loc
= UNKNOWN_LOCATION
;
1905 if (TREE_CODE (op
) == SSA_NAME
)
1906 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1910 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1911 the init edge (from outside the loop) and the second one is the back edge
1912 from the same loop. */
1914 std::pair
<edge
, edge
>
1915 get_edges (basic_block bb
)
1917 std::pair
<edge
, edge
> edges
;
1920 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1921 if (bb
->loop_father
!= e
->src
->loop_father
)
1928 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1929 must be found unless they can be POSTPONEd for later. */
1932 translate_isl_ast_to_gimple::
1933 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1934 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1937 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1939 basic_block new_bb
= gimple_bb (new_phi
);
1940 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1943 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1944 e
= ibp_new_bb
.first
;
1946 e
= ibp_new_bb
.second
;
1948 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1949 tree new_name
= get_new_name (new_bb
, old_name
,
1950 gimple_bb (old_phi
), true);
1953 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1957 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1958 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1959 /* If the phi arg was a function arg, or wasn't defined, just use the
1961 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1964 /* Postpone code gen for later for those back-edges we don't have the
1966 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1968 fprintf (dump_file
, "\n[codegen] postpone loop phi nodes: ");
1971 /* Either we should add the arg to phi or, we should postpone. */
1976 /* Copy loop phi nodes from BB to NEW_BB. */
1979 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
1983 fprintf (dump_file
, "\n[codegen] copying loop phi nodes in bb_%d.",
1986 /* Loop phi nodes should have only two arguments. */
1987 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1989 /* First edge is the init edge and second is the back edge. */
1990 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1992 /* First edge is the init edge and second is the back edge. */
1993 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1995 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1998 gphi
*phi
= psi
.phi ();
1999 tree res
= gimple_phi_result (phi
);
2000 if (virtual_operand_p (res
))
2002 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2005 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2006 tree new_res
= create_new_def_for (res
, new_phi
,
2007 gimple_phi_result_ptr (new_phi
));
2008 set_rename (res
, new_res
);
2009 copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
, ibp_new_bb
, true);
2010 update_stmt (new_phi
);
2016 /* Return the init value of PHI, the value coming from outside the loop. */
2019 get_loop_init_value (gphi
*phi
)
2022 loop_p loop
= gimple_bb (phi
)->loop_father
;
2026 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2027 if (e
->src
->loop_father
!= loop
)
2028 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2033 /* Find the init value (the value which comes from outside the loop), of one of
2034 the operands of DEF which is defined by a loop phi. */
2037 find_init_value (gimple
*def
)
2039 if (gimple_code (def
) == GIMPLE_PHI
)
2040 return get_loop_init_value (as_a
<gphi
*> (def
));
2042 if (gimple_vuse (def
))
2046 use_operand_p use_p
;
2047 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2049 tree use
= USE_FROM_PTR (use_p
);
2050 if (TREE_CODE (use
) == SSA_NAME
)
2052 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2060 /* Return the init value, the value coming from outside the loop. */
2063 find_init_value_close_phi (gphi
*phi
)
2065 gcc_assert (gimple_phi_num_args (phi
) == 1);
2066 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2067 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2068 return find_init_value (def
);
2071 /* Copy all the loop-close phi args from BB to NEW_BB. */
2074 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2078 /* The successor of bb having close phi should be a merge of the diamond
2079 inserted to guard the loop during codegen. */
2080 basic_block close_phi_merge_bb
= single_succ (new_bb
);
2082 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2085 gphi
*phi
= psi
.phi ();
2086 tree res
= gimple_phi_result (phi
);
2087 if (virtual_operand_p (res
))
2090 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2091 /* Loop close phi nodes should not be scev_analyzable_p. */
2094 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2095 tree new_res
= create_new_def_for (res
, new_phi
,
2096 gimple_phi_result_ptr (new_phi
));
2097 set_rename (res
, new_res
);
2099 tree old_name
= gimple_phi_arg_def (phi
, 0);
2100 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2102 /* Predecessor basic blocks of a loop close phi should have been code
2103 generated before. FIXME: This is fixable by merging PHIs from inner
2104 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2108 add_phi_arg (new_phi
, new_name
, single_pred_edge (new_bb
),
2109 get_loc (old_name
));
2112 fprintf (dump_file
, "\n[codegen] Adding loop-closed phi: ");
2113 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2116 update_stmt (new_phi
);
2118 /* When there is no loop guard around this codegenerated loop, there is no
2119 need to collect the close-phi arg. */
2120 if (2 != EDGE_COUNT (close_phi_merge_bb
->preds
))
2123 /* Add a PHI in the close_phi_merge_bb for each close phi of the loop. */
2124 tree init
= find_init_value_close_phi (new_phi
);
2126 /* A close phi must come from a loop-phi having an init value. */
2129 gcc_assert (postpone
);
2130 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2133 fprintf (dump_file
, "\n[codegen] postpone close phi nodes: ");
2134 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2139 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (res
),
2140 close_phi_merge_bb
);
2141 tree merge_res
= create_new_def_for (res
, merge_phi
,
2142 gimple_phi_result_ptr (merge_phi
));
2143 set_rename (res
, merge_res
);
2145 edge from_loop
= single_succ_edge (new_bb
);
2146 add_phi_arg (merge_phi
, new_res
, from_loop
, get_loc (old_name
));
2148 /* The edge coming from loop guard. */
2149 edge other
= from_loop
== (*close_phi_merge_bb
->preds
)[0]
2150 ? (*close_phi_merge_bb
->preds
)[1] : (*close_phi_merge_bb
->preds
)[0];
2152 add_phi_arg (merge_phi
, init
, other
, get_loc (old_name
));
2155 fprintf (dump_file
, "\n[codegen] Adding guard-phi: ");
2156 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2159 update_stmt (new_phi
);
2165 /* Copy loop close phi nodes from BB to NEW_BB. */
2168 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2172 fprintf (dump_file
, "\n[codegen] copying loop closed phi nodes in bb_%d.",
2174 /* Loop close phi nodes should have only one argument. */
2175 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2177 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2181 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2182 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2183 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2184 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2187 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2188 In this case DOMINATING_PRED = NULL.
2190 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2192 Returns true on successful copy of the args, false otherwise. */
2195 translate_isl_ast_to_gimple::
2196 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2197 edge old_bb_dominating_edge
,
2198 edge old_bb_non_dominating_edge
,
2199 gphi
*phi
, gphi
*new_phi
,
2202 basic_block def_pred
[2];
2203 int not_found_bb_index
= -1;
2204 for (int i
= 0; i
< 2; i
++)
2206 /* If the corresponding def_bb could not be found the entry will be
2208 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2209 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2210 gimple_phi_arg_edge (phi
, i
)->src
);
2212 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2215 gcc_assert (not_found_bb_index
== -1);
2216 not_found_bb_index
= i
;
2220 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2221 if (old_bb_dominating_edge
)
2224 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2225 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2226 vec
<basic_block
> *bbs
2227 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2229 basic_block new_pred
= NULL
;
2232 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2233 if (new_pred1
== b
|| new_pred2
== b
)
2235 gcc_assert (!new_pred
);
2239 gcc_assert (new_pred
);
2241 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2242 /* By the process of elimination we first insert insert phi-edge for
2243 non-dominating pred which is computed above and then we insert the
2245 int inserted_edge
= 0;
2246 for (; inserted_edge
< 2; inserted_edge
++)
2248 edge new_bb_pred_edge
= gimple_phi_arg_edge (phi
, inserted_edge
);
2249 if (new_non_dominating_edge
== new_bb_pred_edge
)
2251 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2252 new_non_dominating_edge
,
2253 get_loc (old_phi_args
[inserted_edge
]));
2258 int edge_dominating
= 0;
2259 if (inserted_edge
== 0)
2260 edge_dominating
= 1;
2262 edge new_dominating_edge
= NULL
;
2263 for (int i
; i
< 2; i
++)
2265 edge e
= gimple_phi_arg_edge (new_phi
, i
);
2266 if (e
!= new_non_dominating_edge
)
2267 new_dominating_edge
= e
;
2270 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
], new_dominating_edge
,
2271 get_loc (old_phi_args
[inserted_edge
]));
2275 /* Classic diamond structure: both edges are non-dominating. We need to
2276 find one unique edge then the other can be found be elimination. If
2277 any definition (def_pred) dominates both the preds of new_bb then we
2278 bail out. Entries of def_pred maybe NULL, in that case we must
2279 uniquely find pred with help of only one entry. */
2280 edge new_e
[2] = { NULL
, NULL
};
2281 for (int i
= 0; i
< 2; i
++)
2285 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2287 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2290 /* We do not know how to handle the case when def_pred
2291 dominates more than a predecessor. */
2297 gcc_assert (new_e
[0] || new_e
[1]);
2299 /* Find the other edge by process of elimination. */
2300 if (not_found_bb_index
!= -1)
2302 gcc_assert (!new_e
[not_found_bb_index
]);
2303 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2306 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2308 if (new_e
[found_bb_index
] == e
)
2310 new_e
[not_found_bb_index
] = e
;
2314 /* Add edges to phi args. */
2315 for (int i
= 0; i
< 2; i
++)
2316 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2317 get_loc (old_phi_args
[i
]));
2323 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2324 region. If postpone is true and it isn't possible to copy any arg of PHI,
2325 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2326 Returns false if the copying was unsuccessful. */
2329 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2334 fprintf (dump_file
, "\n[codegen] copying cond phi args: ");
2335 gcc_assert (2 == gimple_phi_num_args (phi
));
2337 basic_block new_bb
= gimple_bb (new_phi
);
2338 loop_p loop
= gimple_bb (phi
)->loop_father
;
2340 basic_block old_bb
= gimple_bb (phi
);
2341 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2345 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2346 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2347 old_bb_non_dominating_edge
= e
;
2349 old_bb_dominating_edge
= e
;
2351 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2352 old_bb_non_dominating_edge
->src
));
2354 tree new_phi_args
[2];
2355 tree old_phi_args
[2];
2357 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2359 tree old_name
= gimple_phi_arg_def (phi
, i
);
2360 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2361 old_phi_args
[i
] = old_name
;
2364 new_phi_args
[i
] = new_name
;
2368 /* If the phi-arg was a parameter. */
2369 if (vec_find (region
->params
, old_name
))
2371 new_phi_args
[i
] = old_name
;
2375 "\n[codegen] parameter argument to phi, new_expr: ");
2376 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2381 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2382 if (postpone
&& is_gimple_reg (old_name
)
2383 && scev_analyzable_p (old_name
, region
->region
))
2386 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, new_bb
,
2388 if (codegen_error_p ())
2391 gcc_assert (new_expr
);
2394 fprintf (dump_file
, "\n[codegen] scev analyzeable, new_expr: ");
2395 print_generic_expr (dump_file
, new_expr
, 0);
2397 gsi_insert_earliest (stmts
);
2398 new_phi_args
[i
] = new_name
;
2402 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2403 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2404 /* If the phi arg was a function arg, or wasn't defined, just use the
2407 //add_phi_arg (new_phi, old_name, new_e, get_loc (old_name));
2410 /* Postpone code gen for later for back-edges. */
2411 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2415 fprintf (dump_file
, "\n[codegen] postpone cond phi nodes: ");
2416 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2419 new_phi_args
[i
] = NULL_TREE
;
2426 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2427 old_bb_dominating_edge
,
2428 old_bb_non_dominating_edge
,
2429 phi
, new_phi
, new_bb
);
2432 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2433 containing phi nodes coming from two predecessors, and none of them are back
2437 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2442 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2445 fprintf (dump_file
, "\n[codegen] copying cond phi nodes in bb_%d:",
2448 /* Cond phi nodes should have exactly two arguments. */
2449 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2451 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2454 gphi
*phi
= psi
.phi ();
2455 tree res
= gimple_phi_result (phi
);
2456 if (virtual_operand_p (res
))
2458 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2459 /* Cond phi nodes should not be scev_analyzable_p. */
2462 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2463 tree new_res
= create_new_def_for (res
, new_phi
,
2464 gimple_phi_result_ptr (new_phi
));
2465 set_rename (res
, new_res
);
2467 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2470 update_stmt (new_phi
);
2476 /* Return true if STMT should be copied from region to the new code-generated
2477 region. LABELs, CONDITIONS, induction-variables and region parameters need
2481 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2483 /* Do not copy labels or conditions. */
2484 if (gimple_code (stmt
) == GIMPLE_LABEL
2485 || gimple_code (stmt
) == GIMPLE_COND
)
2489 /* Do not copy induction variables. */
2490 if (is_gimple_assign (stmt
)
2491 && (lhs
= gimple_assign_lhs (stmt
))
2492 && TREE_CODE (lhs
) == SSA_NAME
2493 && is_gimple_reg (lhs
)
2494 && scev_analyzable_p (lhs
, region
->region
))
2500 /* Create new names for all the definitions created by COPY and add replacement
2501 mappings for each new name. */
2504 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2506 def_operand_p def_p
;
2507 ssa_op_iter op_iter
;
2508 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2510 tree old_name
= DEF_FROM_PTR (def_p
);
2511 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2512 set_rename (old_name
, new_name
);
2516 /* Duplicates the statements of basic block BB into basic block NEW_BB
2517 and compute the new induction variables according to the IV_MAP.
2518 CODEGEN_ERROR is set when the code generation cannot continue. */
2521 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2525 /* Iterator poining to the place where new statement (s) will be inserted. */
2526 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2528 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2531 gimple
*stmt
= gsi_stmt (gsi
);
2532 if (!should_copy_to_new_region (stmt
, region
))
2535 /* Create a new copy of STMT and duplicate STMT's virtual
2537 gimple
*copy
= gimple_copy (stmt
);
2538 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2542 fprintf (dump_file
, "\n[codegen] inserting statement: ");
2543 print_gimple_stmt (dump_file
, copy
, 0, 0);
2546 maybe_duplicate_eh_stmt (copy
, stmt
);
2547 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2549 /* Crete new names for each def in the copied stmt. */
2550 set_rename_for_each_def (copy
);
2552 loop_p loop
= bb
->loop_father
;
2553 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2555 fold_stmt_inplace (&gsi_tgt
);
2556 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2559 if (codegen_error_p ())
2568 /* Copies BB and includes in the copied BB all the statements that can
2569 be reached following the use-def chains from the memory accesses,
2570 and returns the next edge following this new block. codegen_error is
2571 set when the code generation cannot continue. */
2574 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2578 int num_phis
= number_of_phi_nodes (bb
);
2580 if (region
->copied_bb_map
->get (bb
))
2582 /* FIXME: we should be able to handle phi nodes with args coming from
2583 outside the region. */
2586 codegen_error
= true;
2591 basic_block new_bb
= split_edge (next_e
);
2592 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2594 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2596 /* At this point we are unable to codegenerate by still preserving the SSA
2597 structure because maybe the loop is completely unrolled and the PHIs
2598 and cross-bb scalar dependencies are untrackable w.r.t. the original
2599 code. See gfortran.dg/graphite/pr29832.f90. */
2600 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2602 codegen_error
= true;
2607 fprintf (dump_file
, "\n[codegen] bb_%d contains loop phi nodes",
2609 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2611 codegen_error
= true;
2615 else if (bb_contains_loop_close_phi_nodes (bb
))
2618 fprintf (dump_file
, "\n[codegen] bb_%d contains close phi nodes",
2621 /* Make sure that NEW_BB is the loop->exit->dest. */
2622 edge e
= single_pred_edge (new_bb
);
2623 basic_block phi_bb
= new_bb
;
2624 if (e
->src
->loop_father
== e
->dest
->loop_father
)
2626 /* This is one of the places which shows preserving original structure
2627 is not always possible, as we may need to insert close PHI for a
2628 loop where the latch does not have any mapping, or the mapping is
2630 basic_block old_loop_bb
= single_pred_edge (bb
)->src
;
2631 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2632 if (!bbs
|| bbs
->length () != 1)
2634 codegen_error
= true;
2638 basic_block new_loop_bb
= (*bbs
)[0];
2639 loop_p new_loop
= new_loop_bb
->loop_father
;
2640 phi_bb
= single_exit (new_loop
)->dest
;
2641 e
= single_pred_edge (phi_bb
);
2644 gcc_assert (e
->src
->loop_father
!= e
->dest
->loop_father
);
2646 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2648 codegen_error
= true;
2652 else if (num_phis
> 0)
2655 fprintf (dump_file
, "\n[codegen] bb_%d contains cond phi nodes",
2658 basic_block phi_bb
= single_pred (new_bb
);
2659 loop_p loop_father
= new_bb
->loop_father
;
2661 /* Move back until we find the block with two predecessors. */
2662 while (single_pred_p (phi_bb
))
2663 phi_bb
= single_pred_edge (phi_bb
)->src
;
2665 /* If a corresponding merge-point was not found, then abort codegen. */
2666 if (phi_bb
->loop_father
!= loop_father
2667 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2669 codegen_error
= true;
2675 fprintf (dump_file
, "\n[codegen] copying from bb_%d to bb_%d",
2676 bb
->index
, new_bb
->index
);
2678 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2680 copied_bbs
->safe_push (new_bb
);
2683 vec
<basic_block
> bbs
;
2685 bbs
.safe_push (new_bb
);
2686 region
->copied_bb_map
->put (bb
, bbs
);
2689 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2691 codegen_error
= true;
2695 return single_succ_edge (new_bb
);
2698 /* Patch the missing arguments of the phi nodes. */
2701 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2705 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2707 gphi
*old_phi
= rename
->first
;
2708 gphi
*new_phi
= rename
->second
;
2709 basic_block old_bb
= gimple_bb (old_phi
);
2710 basic_block new_bb
= gimple_bb (new_phi
);
2712 /* First edge is the init edge and second is the back edge. */
2713 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2714 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2718 fprintf (dump_file
, "\n[codegen] translating pending old-phi: ");
2719 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2722 auto_vec
<tree
, 1> iv_map
;
2723 if (bb_contains_loop_phi_nodes (new_bb
))
2724 copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2726 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2727 copy_loop_close_phi_args (old_bb
, new_bb
, false);
2728 else if (!copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false))
2733 fprintf (dump_file
, "[codegen] to new-phi: ");
2734 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2739 /* Prints NODE to FILE. */
2742 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
2743 __isl_keep isl_ast_node
*node
,
2744 __isl_keep isl_ctx
*ctx
) const
2746 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
2747 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
2748 prn
= isl_printer_print_ast_node (prn
, node
);
2749 prn
= isl_printer_print_str (prn
, "\n");
2750 isl_printer_free (prn
);
2753 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
2756 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
2759 sese_info_p region
= scop
->scop_info
;
2760 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2761 gcc_assert (nb_parameters
== region
->params
.length ());
2763 for (i
= 0; i
< nb_parameters
; i
++)
2765 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2767 ip
[tmp_id
] = region
->params
[i
];
2772 /* Generates a build, which specifies the constraints on the parameters. */
2774 __isl_give isl_ast_build
*
2775 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
2777 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2778 return isl_ast_build_from_context (context_isl
);
2781 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2784 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
2788 int schedule_dims
= 0;
2790 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2792 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
2793 if (pbb_schedule_dims
> schedule_dims
)
2794 schedule_dims
= pbb_schedule_dims
;
2797 return schedule_dims
;
2800 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2802 For schedules with different dimensionality, the isl AST generator can not
2803 define an order and will just randomly choose an order. The solution to this
2804 problem is to extend all schedules to the maximal number of schedule
2805 dimensions (using '0's for the remaining values). */
2807 __isl_give isl_map
*
2808 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
2809 int nb_schedule_dims
)
2811 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
2813 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
2815 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
2817 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
2820 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
2822 isl_val_free (zero
);
2826 /* Generates a schedule, which specifies an order used to
2827 visit elements in a domain. */
2829 __isl_give isl_union_map
*
2830 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
2832 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
2835 isl_union_map
*schedule_isl
=
2836 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
2838 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2840 /* Dead code elimination: when the domain of a PBB is empty,
2841 don't generate code for the PBB. */
2842 if (isl_set_is_empty (pbb
->domain
))
2845 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
2846 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
2847 isl_set_copy (pbb
->domain
));
2848 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
2850 = isl_union_map_union (schedule_isl
,
2851 isl_union_map_from_map (bb_schedule
));
2853 return schedule_isl
;
2856 /* This method is executed before the construction of a for node. */
2858 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2860 isl_union_map
*dependences
= (isl_union_map
*) user
;
2861 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2862 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2863 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2864 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2865 for_info
->is_parallelizable
=
2866 !carries_deps (schedule
, dependences
, dimension
);
2867 isl_union_map_free (schedule
);
2868 isl_space_free (schedule_space
);
2869 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2873 /* Set the separate option for all dimensions.
2874 This helps to reduce control overhead. */
2876 __isl_give isl_ast_build
*
2877 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
2878 __isl_keep isl_union_map
*schedule
)
2880 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
2881 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
2883 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
2884 isl_union_set
*range
=
2885 isl_union_set_from_set (isl_set_universe (range_space
));
2886 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
2887 domain
= isl_union_set_universe (domain
);
2888 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
2889 return isl_ast_build_set_options (control
, options
);
2892 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
2894 __isl_give isl_ast_node
*
2895 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
2897 /* Generate loop upper bounds that consist of the current loop iterator, an
2898 operator (< or <=) and an expression not involving the iterator. If this
2899 option is not set, then the current loop iterator may appear several times
2900 in the upper bound. See the isl manual for more details. */
2901 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
2903 add_parameters_to_ivs_params (scop
, ip
);
2904 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
2905 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2906 context_isl
= set_options (context_isl
, schedule_isl
);
2907 isl_union_map
*dependences
= NULL
;
2908 if (flag_loop_parallelize_all
)
2910 dependences
= scop_get_dependences (scop
);
2912 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2915 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
2918 isl_union_map_free (dependences
);
2919 isl_ast_build_free (context_isl
);
2923 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
2924 the given SCOP. Return true if code generation succeeded.
2926 FIXME: This is not yet a full implementation of the code generator
2927 with ISL ASTs. Generation of GIMPLE code has to be completed. */
2930 graphite_regenerate_ast_isl (scop_p scop
)
2932 sese_info_p region
= scop
->scop_info
;
2933 translate_isl_ast_to_gimple
t (region
);
2935 ifsese if_region
= NULL
;
2936 isl_ast_node
*root_node
;
2939 timevar_push (TV_GRAPHITE_CODE_GEN
);
2940 root_node
= t
.scop_to_isl_ast (scop
, ip
);
2942 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2944 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
2945 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
2948 recompute_all_dominators ();
2951 if_region
= move_sese_in_condition (region
);
2952 region
->if_region
= if_region
;
2953 recompute_all_dominators ();
2955 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2957 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2958 basic_block bb
= split_edge (e
);
2960 /* Update the true_region exit edge. */
2961 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2963 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2964 if (t
.codegen_error_p ())
2967 fprintf (dump_file
, "\n[codegen] unsuccessful,"
2968 " reverting back to the original code.");
2969 set_ifsese_condition (if_region
, integer_zero_node
);
2973 t
.translate_pending_phi_nodes ();
2974 if (!t
.codegen_error_p ())
2976 sese_insert_phis_for_liveouts (region
,
2977 if_region
->region
->region
.exit
->src
,
2978 if_region
->false_region
->region
.exit
,
2979 if_region
->true_region
->region
.exit
);
2980 mark_virtual_operands_for_renaming (cfun
);
2981 update_ssa (TODO_update_ssa
);
2986 recompute_all_dominators ();
2990 fprintf (dump_file
, "\n[codegen] unsuccessful in translating"
2991 " pending phis, reverting back to the original code.");
2994 free (if_region
->true_region
);
2995 free (if_region
->region
);
2998 ivs_params_clear (ip
);
2999 isl_ast_node_free (root_node
);
3000 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3005 int num_no_dependency
= 0;
3007 FOR_EACH_LOOP (loop
, 0)
3008 if (loop
->can_be_parallel
)
3009 num_no_dependency
++;
3011 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
3015 return !t
.codegen_error_p ();
3018 #endif /* HAVE_isl */