1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
34 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
40 #include "tree-ssa-loop.h"
41 #include "tree-ssa-operands.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-pass.h"
45 #include "tree-data-ref.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-scalar-evolution.h"
48 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "tree-into-ssa.h"
51 #include "ssa-iterators.h"
53 #include "gimple-pretty-print.h"
55 #include "value-prof.h"
57 #include <isl/constraint.h>
59 #include <isl/union_set.h>
61 #include <isl/union_map.h>
62 #include <isl/ast_build.h>
64 /* Since ISL-0.13, the extern is in val_gmp.h. */
65 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
68 #include <isl/val_gmp.h>
69 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
73 #include "graphite-poly.h"
74 #include "graphite-isl-ast-to-gimple.h"
78 /* We always try to use signed 128 bit types, but fall back to smaller types
79 in case a platform does not provide types of these sizes. In the future we
80 should use isl to derive the optimal type for each subexpression. */
82 static int max_mode_int_precision
=
83 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
84 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
85 128 : max_mode_int_precision
;
90 : is_parallelizable(false)
92 bool is_parallelizable
;
95 /* Converts a GMP constant VAL to a tree and returns it. */
98 gmp_cst_to_tree (tree type
, mpz_t val
)
100 tree t
= type
? type
: integer_type_node
;
105 wide_int wi
= wi::from_mpz (t
, tmp
, true);
108 return wide_int_to_tree (t
, wi
);
111 /* Verifies properties that GRAPHITE should maintain during translation. */
114 graphite_verify (void)
116 checking_verify_loop_structure ();
117 checking_verify_loop_closed_ssa (true);
120 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
121 to corresponding trees. */
123 typedef std::map
<isl_id
*, tree
> ivs_params
;
125 /* Free all memory allocated for ISL's identifiers. */
127 void ivs_params_clear (ivs_params
&ip
)
129 std::map
<isl_id
*, tree
>::iterator it
;
130 for (it
= ip
.begin ();
131 it
!= ip
.end (); it
++)
133 isl_id_free (it
->first
);
137 class translate_isl_ast_to_gimple
140 translate_isl_ast_to_gimple (sese_info_p r
)
141 : region (r
), codegen_error (false)
144 /* Translates an ISL AST node NODE to GCC representation in the
145 context of a SESE. */
146 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
147 edge next_e
, ivs_params
&ip
);
149 /* Translates an isl_ast_node_for to Gimple. */
150 edge
translate_isl_ast_node_for (loop_p context_loop
,
151 __isl_keep isl_ast_node
*node
,
152 edge next_e
, ivs_params
&ip
);
154 /* Create the loop for a isl_ast_node_for.
156 - NEXT_E is the edge where new generated code should be attached. */
157 edge
translate_isl_ast_for_loop (loop_p context_loop
,
158 __isl_keep isl_ast_node
*node_for
,
160 tree type
, tree lb
, tree ub
,
163 /* Translates an isl_ast_node_if to Gimple. */
164 edge
translate_isl_ast_node_if (loop_p context_loop
,
165 __isl_keep isl_ast_node
*node
,
166 edge next_e
, ivs_params
&ip
);
168 /* Translates an isl_ast_node_user to Gimple.
170 FIXME: We should remove iv_map.create (loop->num + 1), if it is
172 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
173 edge next_e
, ivs_params
&ip
);
175 /* Translates an isl_ast_node_block to Gimple. */
176 edge
translate_isl_ast_node_block (loop_p context_loop
,
177 __isl_keep isl_ast_node
*node
,
178 edge next_e
, ivs_params
&ip
);
180 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
182 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
185 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
187 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
190 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
192 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
195 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
196 to a GCC expression tree of type TYPE. */
197 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
200 /* Converts an ISL AST expression E back to a GCC expression tree of
202 tree
gcc_expression_from_isl_expression (tree type
,
203 __isl_take isl_ast_expr
*,
206 /* Return the tree variable that corresponds to the given isl ast identifier
207 expression (an isl_ast_expr of type isl_ast_expr_id).
209 FIXME: We should replace blind conversation of id's type with derivation
210 of the optimal type when we get the corresponding isl support. Blindly
211 converting type sizes may be problematic when we switch to smaller
213 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
214 __isl_keep isl_ast_expr
*expr_id
,
217 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
219 tree
gcc_expression_from_isl_expr_int (tree type
,
220 __isl_take isl_ast_expr
*expr
);
222 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
224 tree
gcc_expression_from_isl_expr_op (tree type
,
225 __isl_take isl_ast_expr
*expr
,
228 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
229 induction variable for the new LOOP. New LOOP is attached to CFG
230 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
231 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
232 ISL's scattering name to the induction variable created for the
233 loop of STMT. The new induction variable is inserted in the NEWIVS
234 vector and is of type TYPE. */
235 struct loop
*graphite_create_new_loop (edge entry_edge
,
236 __isl_keep isl_ast_node
*node_for
,
237 loop_p outer
, tree type
,
238 tree lb
, tree ub
, ivs_params
&ip
);
240 /* All loops generated by create_empty_loop_on_edge have the form of
247 } while (lower bound < upper bound);
249 We create a new if region protecting the loop to be executed, if
250 the execution count is zero (lower bound > upper bound). */
251 edge
graphite_create_new_loop_guard (edge entry_edge
,
252 __isl_keep isl_ast_node
*node_for
,
254 tree
*lb
, tree
*ub
, ivs_params
&ip
);
256 /* Creates a new if region corresponding to ISL's cond. */
257 edge
graphite_create_new_guard (edge entry_edge
,
258 __isl_take isl_ast_expr
*if_cond
,
261 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
262 variables of the loops around GBB in SESE.
264 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
265 chrec, we could consider using a map<int, tree> that maps loop ids to the
266 corresponding tree expressions. */
267 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
268 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
271 /* Patch the missing arguments of the phi nodes. */
273 void translate_pending_phi_nodes (void);
275 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
277 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
279 /* Get the maximal number of schedule dimensions in the scop SCOP. */
281 int get_max_schedule_dimensions (scop_p scop
);
283 /* Generates a build, which specifies the constraints on the parameters. */
285 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
287 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
289 For schedules with different dimensionality, the isl AST generator can not
290 define an order and will just randomly choose an order. The solution to
291 this problem is to extend all schedules to the maximal number of schedule
292 dimensions (using '0's for the remaining values). */
294 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
295 int nb_schedule_dims
);
297 /* Generates a schedule, which specifies an order used to
298 visit elements in a domain. */
300 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
302 /* Set the separate option for all dimensions.
303 This helps to reduce control overhead. */
305 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
306 __isl_keep isl_union_map
*schedule
);
308 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
311 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
314 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
315 definition should flow into use, and the use should respect the loop-closed
318 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
319 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
321 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
322 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
323 within a loop PHI instruction. */
325 tree
get_rename (basic_block new_bb
, tree old_name
,
326 basic_block old_bb
, bool loop_phi
) const;
328 /* For ops which are scev_analyzeable, we can regenerate a new name from
329 its scalar evolution around LOOP. */
331 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
332 basic_block new_bb
, basic_block old_bb
,
335 /* Returns a basic block that could correspond to where a constant was defined
336 in the original code. In the original code OLD_BB had the definition, we
337 need to find which basic block out of the copies of old_bb, in the new
338 region, should a definition correspond to if it has to reach BB. */
340 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
342 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
343 true when we want to rename an OP within a loop PHI instruction. */
345 tree
get_new_name (basic_block new_bb
, tree op
,
346 basic_block old_bb
, bool loop_phi
) const;
348 /* Collect all the operands of NEW_EXPR by recursively visiting each
351 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
353 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
354 NEW_PHI must be found unless they can be POSTPONEd for later. */
356 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
357 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
360 /* Copy loop phi nodes from BB to NEW_BB. */
362 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
364 /* Copy all the loop-close phi args from BB to NEW_BB. */
366 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
369 /* Copy loop close phi nodes from BB to NEW_BB. */
371 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
373 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
374 region. If postpone is true and it isn't possible to copy any arg of PHI,
375 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
376 Returns false if the copying was unsuccessful. */
378 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
381 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
382 containing phi nodes coming from two predecessors, and none of them are back
385 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
388 /* Duplicates the statements of basic block BB into basic block NEW_BB
389 and compute the new induction variables according to the IV_MAP.
390 CODEGEN_ERROR is set when the code generation cannot continue. */
392 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
395 /* Copies BB and includes in the copied BB all the statements that can
396 be reached following the use-def chains from the memory accesses,
397 and returns the next edge following this new block. codegen_error is
398 set when the code generation cannot continue. */
400 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
403 /* Given a basic block containing close-phi it returns the new basic block
404 where to insert a copy of the close-phi nodes. All the uses in close phis
405 should come from a single loop otherwise it returns NULL. */
406 edge
edge_for_new_close_phis (basic_block bb
);
408 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
409 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
410 the other pred of OLD_BB as well. If no such basic block exists then it is
411 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
414 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
415 versa. In this case DOMINATING_PRED = NULL.
417 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
419 Returns true on successful copy of the args, false otherwise. */
421 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
422 edge old_bb_dominating_edge
,
423 edge old_bb_non_dominating_edge
,
424 gphi
*phi
, gphi
*new_phi
,
427 /* Renames the scalar uses of the statement COPY, using the substitution map
428 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
429 translation REGION, with the original copied statement in LOOP, and using
430 the induction variable renaming map IV_MAP. Returns true when something
431 has been renamed. codegen_error is set when the code generation cannot
434 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
435 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
437 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
438 When OLD_NAME and EXPR are the same we assert. */
440 void set_rename (tree old_name
, tree expr
);
442 /* Create new names for all the definitions created by COPY and add
443 replacement mappings for each new name. */
445 void set_rename_for_each_def (gimple
*stmt
);
447 /* Insert each statement from SEQ at its earliest insertion p. */
449 void gsi_insert_earliest (gimple_seq seq
);
451 /* Rename all the operands of NEW_EXPR by recursively visiting each
454 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
456 bool codegen_error_p () const
457 { return codegen_error
; }
459 /* Prints NODE to FILE. */
461 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
462 __isl_keep isl_ctx
*ctx
) const;
467 /* This flag is set when an error occurred during the translation of ISL AST
472 /* Return the tree variable that corresponds to the given isl ast identifier
473 expression (an isl_ast_expr of type isl_ast_expr_id).
475 FIXME: We should replace blind conversation of id's type with derivation
476 of the optimal type when we get the corresponding isl support. Blindly
477 converting type sizes may be problematic when we switch to smaller
481 translate_isl_ast_to_gimple::
482 gcc_expression_from_isl_ast_expr_id (tree type
,
483 __isl_keep isl_ast_expr
*expr_id
,
486 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
487 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
488 std::map
<isl_id
*, tree
>::iterator res
;
489 res
= ip
.find (tmp_isl_id
);
490 isl_id_free (tmp_isl_id
);
491 gcc_assert (res
!= ip
.end () &&
492 "Could not map isl_id to tree expression");
493 isl_ast_expr_free (expr_id
);
494 tree t
= res
->second
;
495 return fold_convert (type
, t
);
498 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
502 translate_isl_ast_to_gimple::
503 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
505 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
506 isl_val
*val
= isl_ast_expr_get_val (expr
);
508 mpz_init (val_mpz_t
);
510 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
513 res
= gmp_cst_to_tree (type
, val_mpz_t
);
515 isl_ast_expr_free (expr
);
516 mpz_clear (val_mpz_t
);
520 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
524 translate_isl_ast_to_gimple::
525 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
527 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
528 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
529 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
530 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
531 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
532 isl_ast_expr_free (expr
);
536 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
539 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
542 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
545 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
547 case isl_ast_op_pdiv_q
:
548 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
550 case isl_ast_op_pdiv_r
:
551 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
553 case isl_ast_op_fdiv_q
:
554 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
557 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
558 tree_lhs_expr
, tree_rhs_expr
);
561 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
564 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
567 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
570 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
573 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
576 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
583 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
587 translate_isl_ast_to_gimple::
588 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
590 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
591 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
593 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
594 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
595 tree tree_second_expr
596 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
597 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
599 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
600 isl_ast_expr_free (expr
);
601 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
602 tree_second_expr
, tree_third_expr
);
605 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
609 translate_isl_ast_to_gimple::
610 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
612 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
613 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
614 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
615 isl_ast_expr_free (expr
);
616 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
619 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
620 to a GCC expression tree of type TYPE. */
623 translate_isl_ast_to_gimple::
624 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
626 enum tree_code op_code
;
627 switch (isl_ast_expr_get_op_type (expr
))
640 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
641 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
643 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
645 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
646 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
647 res
= fold_build2 (op_code
, type
, res
, t
);
649 isl_ast_expr_free (expr
);
653 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
657 translate_isl_ast_to_gimple::
658 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
661 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
662 switch (isl_ast_expr_get_op_type (expr
))
664 /* These isl ast expressions are not supported yet. */
665 case isl_ast_op_error
:
666 case isl_ast_op_call
:
667 case isl_ast_op_and_then
:
668 case isl_ast_op_or_else
:
669 case isl_ast_op_select
:
674 return nary_op_to_tree (type
, expr
, ip
);
680 case isl_ast_op_pdiv_q
:
681 case isl_ast_op_pdiv_r
:
682 case isl_ast_op_fdiv_q
:
690 return binary_op_to_tree (type
, expr
, ip
);
692 case isl_ast_op_minus
:
693 return unary_op_to_tree (type
, expr
, ip
);
695 case isl_ast_op_cond
:
696 return ternary_op_to_tree (type
, expr
, ip
);
705 /* Converts an ISL AST expression E back to a GCC expression tree of
709 translate_isl_ast_to_gimple::
710 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
713 switch (isl_ast_expr_get_type (expr
))
715 case isl_ast_expr_id
:
716 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
718 case isl_ast_expr_int
:
719 return gcc_expression_from_isl_expr_int (type
, expr
);
721 case isl_ast_expr_op
:
722 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
731 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
732 induction variable for the new LOOP. New LOOP is attached to CFG
733 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
734 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
735 ISL's scattering name to the induction variable created for the
736 loop of STMT. The new induction variable is inserted in the NEWIVS
737 vector and is of type TYPE. */
740 translate_isl_ast_to_gimple::
741 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
742 loop_p outer
, tree type
, tree lb
, tree ub
,
745 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
746 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
747 tree ivvar
= create_tmp_var (type
, "graphite_IV");
748 tree iv
, iv_after_increment
;
749 loop_p loop
= create_empty_loop_on_edge
750 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
751 outer
? outer
: entry_edge
->src
->loop_father
);
753 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
754 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
755 std::map
<isl_id
*, tree
>::iterator res
;
758 isl_id_free (res
->first
);
760 isl_ast_expr_free (for_iterator
);
764 /* Create the loop for a isl_ast_node_for.
766 - NEXT_E is the edge where new generated code should be attached. */
769 translate_isl_ast_to_gimple::
770 translate_isl_ast_for_loop (loop_p context_loop
,
771 __isl_keep isl_ast_node
*node_for
, edge next_e
,
772 tree type
, tree lb
, tree ub
,
775 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
776 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
778 edge last_e
= single_exit (loop
);
779 edge to_body
= single_succ_edge (loop
->header
);
780 basic_block after
= to_body
->dest
;
782 /* Translate the body of the loop. */
783 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
784 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
785 isl_ast_node_free (for_body
);
787 /* Early return if we failed to translate loop body. */
788 if (!next_e
|| codegen_error_p ())
791 redirect_edge_succ_nodup (next_e
, after
);
792 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
794 if (flag_loop_parallelize_all
)
796 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
798 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
799 loop
->can_be_parallel
= for_info
->is_parallelizable
;
807 /* We use this function to get the upper bound because of the form,
808 which is used by isl to represent loops:
810 for (iterator = init; cond; iterator += inc)
818 The loop condition is an arbitrary expression, which contains the
819 current loop iterator.
821 (e.g. iterator + 3 < B && C > iterator + A)
823 We have to know the upper bound of the iterator to generate a loop
824 in Gimple form. It can be obtained from the special representation
825 of the loop condition, which is generated by isl,
826 if the ast_build_atomic_upper_bound option is set. In this case,
827 isl generates a loop condition that consists of the current loop
828 iterator, + an operator (< or <=) and an expression not involving
829 the iterator, which is processed and returned by this function.
831 (e.g iterator <= upper-bound-expression-without-iterator) */
833 static __isl_give isl_ast_expr
*
834 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
836 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
837 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
838 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
840 switch (isl_ast_expr_get_op_type (for_cond
))
843 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
848 /* (iterator < ub) => (iterator <= ub - 1). */
850 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
851 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
852 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
859 isl_ast_expr_free (for_cond
);
863 /* All loops generated by create_empty_loop_on_edge have the form of
870 } while (lower bound < upper bound);
872 We create a new if region protecting the loop to be executed, if
873 the execution count is zero (lower bound > upper bound). */
876 translate_isl_ast_to_gimple::
877 graphite_create_new_loop_guard (edge entry_edge
,
878 __isl_keep isl_ast_node
*node_for
, tree
*type
,
879 tree
*lb
, tree
*ub
, ivs_params
&ip
)
881 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
886 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
887 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
888 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
889 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
890 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
892 /* When ub is simply a constant or a parameter, use lb <= ub. */
893 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
894 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
897 tree one
= (POINTER_TYPE_P (*type
)
898 ? convert_to_ptrofftype (integer_one_node
)
899 : fold_convert (*type
, integer_one_node
));
900 /* Adding +1 and using LT_EXPR helps with loop latches that have a
901 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
902 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
903 is true, even if we do not want this. However lb < ub + 1 is false,
905 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
906 : PLUS_EXPR
, *type
, *ub
, one
);
908 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
911 if (integer_onep (cond_expr
))
912 exit_edge
= entry_edge
;
914 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
919 /* Translates an isl_ast_node_for to Gimple. */
922 translate_isl_ast_to_gimple::
923 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
924 edge next_e
, ivs_params
&ip
)
926 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
928 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
931 if (last_e
== next_e
)
932 /* There was no guard generated. */
933 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
936 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
937 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
941 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
942 variables of the loops around GBB in SESE.
944 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
945 chrec, we could consider using a map<int, tree> that maps loop ids to the
946 corresponding tree expressions. */
949 translate_isl_ast_to_gimple::
950 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
951 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
954 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
955 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
957 isl_ast_expr
*arg_expr
;
958 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
960 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
962 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
963 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
964 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
965 iv_map
[old_loop
->num
] = t
;
969 /* Translates an isl_ast_node_user to Gimple.
971 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
974 translate_isl_ast_to_gimple::
975 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
976 edge next_e
, ivs_params
&ip
)
978 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
980 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
981 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
982 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
984 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
985 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
988 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
990 isl_ast_expr_free (name_expr
);
991 isl_id_free (name_id
);
993 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
994 "The entry block should not even appear within a scop");
996 const int nb_loops
= number_of_loops (cfun
);
998 iv_map
.create (nb_loops
);
999 iv_map
.safe_grow_cleared (nb_loops
);
1001 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1002 isl_ast_expr_free (user_expr
);
1006 fprintf (dump_file
, "[codegen] copying from basic block\n");
1007 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1008 fprintf (dump_file
, "\n[codegen] to new basic block\n");
1009 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1012 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1017 if (codegen_error_p ())
1022 fprintf (dump_file
, "\n[codegen] (after copy) new basic block\n");
1023 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1029 /* Translates an isl_ast_node_block to Gimple. */
1032 translate_isl_ast_to_gimple::
1033 translate_isl_ast_node_block (loop_p context_loop
,
1034 __isl_keep isl_ast_node
*node
,
1035 edge next_e
, ivs_params
&ip
)
1037 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1038 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1040 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1042 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1043 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1044 isl_ast_node_free (tmp_node
);
1046 isl_ast_node_list_free (node_list
);
1050 /* Creates a new if region corresponding to ISL's cond. */
1053 translate_isl_ast_to_gimple::
1054 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1058 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1059 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1060 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1064 /* Translates an isl_ast_node_if to Gimple. */
1067 translate_isl_ast_to_gimple::
1068 translate_isl_ast_node_if (loop_p context_loop
,
1069 __isl_keep isl_ast_node
*node
,
1070 edge next_e
, ivs_params
&ip
)
1072 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1073 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1074 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1076 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1077 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1078 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1079 isl_ast_node_free (then_node
);
1081 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1082 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1083 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1084 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1085 isl_ast_node_free (else_node
);
1089 /* Translates an ISL AST node NODE to GCC representation in the
1090 context of a SESE. */
1093 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1094 __isl_keep isl_ast_node
*node
,
1095 edge next_e
, ivs_params
&ip
)
1097 if (codegen_error_p ())
1100 switch (isl_ast_node_get_type (node
))
1102 case isl_ast_node_error
:
1105 case isl_ast_node_for
:
1106 return translate_isl_ast_node_for (context_loop
, node
,
1109 case isl_ast_node_if
:
1110 return translate_isl_ast_node_if (context_loop
, node
,
1113 case isl_ast_node_user
:
1114 return translate_isl_ast_node_user (node
, next_e
, ip
);
1116 case isl_ast_node_block
:
1117 return translate_isl_ast_node_block (context_loop
, node
,
1125 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1126 at the exit of loop which takes one argument that is the last value of the
1127 variable being used out of the loop. */
1130 bb_contains_loop_close_phi_nodes (basic_block bb
)
1132 return single_pred_p (bb
)
1133 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1136 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1137 header containing phi nodes which has one init-edge and one back-edge. */
1140 bb_contains_loop_phi_nodes (basic_block bb
)
1142 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1144 if (bb
->preds
->length () == 1)
1147 unsigned depth
= loop_depth (bb
->loop_father
);
1149 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1151 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1152 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1155 /* When one of the edges correspond to the same loop father and other
1157 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1158 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1161 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1162 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1168 /* Check if USE is defined in a basic block from where the definition of USE can
1169 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1172 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1174 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1177 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1178 if (bb_contains_loop_close_phi_nodes (bb
))
1181 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1182 basic_block def_bb
= gimple_bb (def
);
1184 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1187 /* Return the number of phi nodes in BB. */
1190 number_of_phi_nodes (basic_block bb
)
1193 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1199 /* Returns true if BB uses name in one of its PHIs. */
1202 phi_uses_name (basic_block bb
, tree name
)
1204 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1207 gphi
*phi
= psi
.phi ();
1208 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1210 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1211 if (use_arg
== name
)
1218 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1219 definition should flow into use, and the use should respect the loop-closed
1223 translate_isl_ast_to_gimple::
1224 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1225 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1227 /* The def of the rename must either dominate the uses or come from a
1228 back-edge. Also the def must respect the loop closed ssa form. */
1229 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1233 fprintf (dump_file
, "\n[codegen] rename not in loop closed ssa:");
1234 print_generic_expr (dump_file
, rename
, 0);
1239 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1242 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1244 /* The loop-header dominates the loop-body. */
1245 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1248 /* RENAME would be used in loop-phi. */
1249 gcc_assert (number_of_phi_nodes (use_bb
));
1251 /* For definitions coming from back edges, we should check that
1252 old_name is used in a loop PHI node.
1253 FIXME: Verify if this is true. */
1254 if (phi_uses_name (old_bb
, old_name
))
1260 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1261 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1262 within a loop PHI instruction. */
1265 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1268 bool loop_phi
) const
1270 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1271 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1273 if (!renames
|| renames
->is_empty ())
1276 if (1 == renames
->length ())
1278 tree rename
= (*renames
)[0];
1279 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1280 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1285 /* More than one renames corresponding to the old_name. Find the rename for
1286 which the definition flows into usage at new_bb. */
1288 tree t1
= NULL_TREE
, t2
;
1289 basic_block t1_bb
= NULL
;
1290 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1292 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1294 /* Defined in the same basic block as used. */
1295 if (t2_bb
== new_bb
)
1298 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1299 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1302 /* Compute the nearest dominator. */
1303 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1313 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1314 When OLD_NAME and EXPR are the same we assert. */
1317 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1321 fprintf (dump_file
, "\n[codegen] setting rename: old_name = ");
1322 print_generic_expr (dump_file
, old_name
, 0);
1323 fprintf (dump_file
, ", new_name = ");
1324 print_generic_expr (dump_file
, expr
, 0);
1327 if (old_name
== expr
)
1330 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1333 renames
->safe_push (expr
);
1339 region
->rename_map
->put (old_name
, r
);
1343 /* Return an iterator to the instructions comes last in the execution order.
1344 Either GSI1 and GSI2 should belong to the same basic block or one of their
1345 respective basic blocks should dominate the other. */
1347 gimple_stmt_iterator
1348 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1350 basic_block bb1
= gsi_bb (gsi1
);
1351 basic_block bb2
= gsi_bb (gsi2
);
1353 /* Find the iterator which is the latest. */
1356 /* For empty basic blocks gsis point to the end of the sequence. Since
1357 there is no operator== defined for gimple_stmt_iterator and for gsis
1358 not pointing to a valid statement gsi_next would assert. */
1359 gimple_stmt_iterator gsi
= gsi1
;
1361 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1364 } while (!gsi_end_p (gsi
));
1369 /* Find the basic block closest to the basic block which defines stmt. */
1370 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1373 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1377 /* Insert each statement from SEQ at its earliest insertion p. */
1380 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1382 update_modified_stmts (seq
);
1383 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1384 basic_block begin_bb
= get_entry_bb (codegen_region
);
1386 /* Inserting the gimple statements in a vector because gimple_seq behave
1387 in strage ways when inserting the stmts from it into different basic
1388 blocks one at a time. */
1389 auto_vec
<gimple
*, 3> stmts
;
1390 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1392 stmts
.safe_push (gsi_stmt (gsi
));
1396 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1398 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1399 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1401 use_operand_p use_p
;
1402 ssa_op_iter op_iter
;
1403 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1405 /* Iterator to the current def of use_p. For function parameters or
1406 anything where def is not found, insert at the beginning of the
1407 generated region. */
1408 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1410 tree op
= USE_FROM_PTR (use_p
);
1411 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1412 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1413 gsi_stmt
= gsi_for_stmt (stmt
);
1415 /* For region parameters, insert at the beginning of the generated
1417 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1418 gsi_stmt
= gsi_def_stmt
;
1420 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1423 if (!gsi_stmt (gsi_def_stmt
))
1425 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1426 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1428 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1430 gimple_stmt_iterator bsi
1431 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1432 /* Insert right after the PHI statements. */
1433 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1436 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1440 fprintf (dump_file
, "\n[codegen] inserting statement: ");
1441 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1442 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1447 /* Collect all the operands of NEW_EXPR by recursively visiting each
1451 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1455 /* Rename all uses in new_expr. */
1456 if (TREE_CODE (new_expr
) == SSA_NAME
)
1458 vec_ssa
->safe_push (new_expr
);
1462 /* Iterate over SSA_NAMES in NEW_EXPR. */
1463 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1465 tree op
= TREE_OPERAND (new_expr
, i
);
1466 collect_all_ssa_names (op
, vec_ssa
);
1470 /* This is abridged version of the function:
1471 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1474 substitute_ssa_name (tree exp
, tree f
, tree r
)
1476 enum tree_code code
= TREE_CODE (exp
);
1477 tree op0
, op1
, op2
, op3
;
1480 /* We handle TREE_LIST and COMPONENT_REF separately. */
1481 if (code
== TREE_LIST
)
1483 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1484 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1485 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1488 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1490 else if (code
== COMPONENT_REF
)
1494 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1495 and it is the right field, replace it with R. */
1496 for (inner
= TREE_OPERAND (exp
, 0);
1497 REFERENCE_CLASS_P (inner
);
1498 inner
= TREE_OPERAND (inner
, 0))
1502 op1
= TREE_OPERAND (exp
, 1);
1504 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1507 /* If this expression hasn't been completed let, leave it alone. */
1508 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1511 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1512 if (op0
== TREE_OPERAND (exp
, 0))
1516 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1519 switch (TREE_CODE_CLASS (code
))
1524 case tcc_declaration
:
1530 case tcc_expression
:
1534 /* Fall through... */
1536 case tcc_exceptional
:
1539 case tcc_comparison
:
1541 switch (TREE_CODE_LENGTH (code
))
1549 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1550 if (op0
== TREE_OPERAND (exp
, 0))
1553 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1557 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1558 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1560 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1563 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1567 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1568 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1569 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1571 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1572 && op2
== TREE_OPERAND (exp
, 2))
1575 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1579 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1580 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1581 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1582 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1584 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1585 && op2
== TREE_OPERAND (exp
, 2)
1586 && op3
== TREE_OPERAND (exp
, 3))
1590 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1603 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1605 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1606 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1611 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1614 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1617 auto_vec
<tree
, 2> ssa_names
;
1618 collect_all_ssa_names (new_expr
, &ssa_names
);
1621 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1622 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1623 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1628 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1629 scalar evolution around LOOP. */
1632 translate_isl_ast_to_gimple::
1633 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1634 basic_block new_bb
, basic_block old_bb
,
1637 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1639 /* At this point we should know the exact scev for each
1640 scalar SSA_NAME used in the scop: all the other scalar
1641 SSA_NAMEs should have been translated out of SSA using
1642 arrays with one element. */
1644 if (chrec_contains_undetermined (scev
))
1646 codegen_error
= true;
1647 return build_zero_cst (TREE_TYPE (old_name
));
1650 new_expr
= chrec_apply_map (scev
, iv_map
);
1652 /* The apply should produce an expression tree containing
1653 the uses of the new induction variables. We should be
1654 able to use new_expr instead of the old_name in the newly
1655 generated loop nest. */
1656 if (chrec_contains_undetermined (new_expr
)
1657 || tree_contains_chrecs (new_expr
, NULL
))
1659 codegen_error
= true;
1660 return build_zero_cst (TREE_TYPE (old_name
));
1663 /* We should check all the operands and all of them should dominate the use at
1665 if (TREE_CODE (new_expr
) == SSA_NAME
)
1667 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1668 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1670 codegen_error
= true;
1671 return build_zero_cst (TREE_TYPE (old_name
));
1675 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1676 /* We should check all the operands and all of them should dominate the use at
1678 if (TREE_CODE (new_expr
) == SSA_NAME
)
1680 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1681 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1683 codegen_error
= true;
1684 return build_zero_cst (TREE_TYPE (old_name
));
1688 /* Replace the old_name with the new_expr. */
1689 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1693 /* Renames the scalar uses of the statement COPY, using the
1694 substitution map RENAME_MAP, inserting the gimplification code at
1695 GSI_TGT, for the translation REGION, with the original copied
1696 statement in LOOP, and using the induction variable renaming map
1697 IV_MAP. Returns true when something has been renamed. codegen_error
1698 is set when the code generation cannot continue. */
1701 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1702 gimple_stmt_iterator
*gsi_tgt
,
1704 loop_p loop
, vec
<tree
> iv_map
)
1706 bool changed
= false;
1708 if (is_gimple_debug (copy
))
1710 if (gimple_debug_bind_p (copy
))
1711 gimple_debug_bind_reset_value (copy
);
1712 else if (gimple_debug_source_bind_p (copy
))
1722 fprintf (dump_file
, "\n[codegen] renaming uses of stmt: ");
1723 print_gimple_stmt (dump_file
, copy
, 0, 0);
1726 use_operand_p use_p
;
1727 ssa_op_iter op_iter
;
1728 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1730 tree old_name
= USE_FROM_PTR (use_p
);
1734 fprintf (dump_file
, "\n[codegen] renaming old_name = ");
1735 print_generic_expr (dump_file
, old_name
, 0);
1738 if (TREE_CODE (old_name
) != SSA_NAME
1739 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1743 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1748 tree type_old_name
= TREE_TYPE (old_name
);
1749 tree type_new_expr
= TREE_TYPE (new_expr
);
1753 fprintf (dump_file
, "\n[codegen] from rename_map: new_name = ");
1754 print_generic_expr (dump_file
, new_expr
, 0);
1757 if (type_old_name
!= type_new_expr
1758 || TREE_CODE (new_expr
) != SSA_NAME
)
1760 tree var
= create_tmp_var (type_old_name
, "var");
1762 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1763 new_expr
= fold_convert (type_old_name
, new_expr
);
1766 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1767 gsi_insert_earliest (stmts
);
1770 replace_exp (use_p
, new_expr
);
1775 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1777 if (!new_expr
|| codegen_error_p ())
1782 fprintf (dump_file
, "\n[codegen] not in rename map, scev: ");
1783 print_generic_expr (dump_file
, new_expr
, 0);
1786 gsi_insert_earliest (stmts
);
1787 replace_exp (use_p
, new_expr
);
1789 if (TREE_CODE (new_expr
) == INTEGER_CST
1790 && is_gimple_assign (copy
))
1792 tree rhs
= gimple_assign_rhs1 (copy
);
1794 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1795 recompute_tree_invariant_for_addr_expr (rhs
);
1798 set_rename (old_name
, new_expr
);
1804 /* Returns a basic block that could correspond to where a constant was defined
1805 in the original code. In the original code OLD_BB had the definition, we
1806 need to find which basic block out of the copies of old_bb, in the new
1807 region, should a definition correspond to if it has to reach BB. */
1810 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1811 basic_block old_bb
) const
1813 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1815 if (!bbs
|| bbs
->is_empty ())
1818 if (1 == bbs
->length ())
1822 basic_block b1
= NULL
, b2
;
1823 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1828 /* BB and B2 are in two unrelated if-clauses. */
1829 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1832 /* Compute the nearest dominator. */
1833 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1841 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1842 when we want to rename an OP within a loop PHI instruction. */
1845 translate_isl_ast_to_gimple::
1846 get_new_name (basic_block new_bb
, tree op
,
1847 basic_block old_bb
, bool loop_phi
) const
1849 /* For constants the names are the same. */
1850 if (TREE_CODE (op
) == INTEGER_CST
1851 || TREE_CODE (op
) == REAL_CST
1852 || TREE_CODE (op
) == COMPLEX_CST
1853 || TREE_CODE (op
) == VECTOR_CST
)
1856 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1859 /* Return a debug location for OP. */
1864 location_t loc
= UNKNOWN_LOCATION
;
1866 if (TREE_CODE (op
) == SSA_NAME
)
1867 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1871 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1872 the init edge (from outside the loop) and the second one is the back edge
1873 from the same loop. */
1875 std::pair
<edge
, edge
>
1876 get_edges (basic_block bb
)
1878 std::pair
<edge
, edge
> edges
;
1881 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1882 if (bb
->loop_father
!= e
->src
->loop_father
)
1889 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1890 must be found unless they can be POSTPONEd for later. */
1893 translate_isl_ast_to_gimple::
1894 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1895 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1898 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1900 basic_block new_bb
= gimple_bb (new_phi
);
1901 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1904 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1905 e
= ibp_new_bb
.first
;
1907 e
= ibp_new_bb
.second
;
1909 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1910 tree new_name
= get_new_name (new_bb
, old_name
,
1911 gimple_bb (old_phi
), true);
1914 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1918 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1919 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1920 /* If the phi arg was a function arg, or wasn't defined, just use the
1922 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1925 /* Postpone code gen for later for those back-edges we don't have the
1927 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1929 fprintf (dump_file
, "\n[codegen] postpone loop phi nodes: ");
1932 /* Either we should add the arg to phi or, we should postpone. */
1938 /* Copy loop phi nodes from BB to NEW_BB. */
1941 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
1945 fprintf (dump_file
, "\n[codegen] copying loop phi nodes in bb_%d.",
1948 /* Loop phi nodes should have only two arguments. */
1949 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1951 /* First edge is the init edge and second is the back edge. */
1952 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1954 /* First edge is the init edge and second is the back edge. */
1955 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1957 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1960 gphi
*phi
= psi
.phi ();
1961 tree res
= gimple_phi_result (phi
);
1962 if (virtual_operand_p (res
))
1964 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1967 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1968 tree new_res
= create_new_def_for (res
, new_phi
,
1969 gimple_phi_result_ptr (new_phi
));
1970 set_rename (res
, new_res
);
1971 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1973 update_stmt (new_phi
);
1979 /* Return the init value of PHI, the value coming from outside the loop. */
1982 get_loop_init_value (gphi
*phi
)
1985 loop_p loop
= gimple_bb (phi
)->loop_father
;
1989 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
1990 if (e
->src
->loop_father
!= loop
)
1991 return gimple_phi_arg_def (phi
, e
->dest_idx
);
1996 /* Find the init value (the value which comes from outside the loop), of one of
1997 the operands of DEF which is defined by a loop phi. */
2000 find_init_value (gimple
*def
)
2002 if (gimple_code (def
) == GIMPLE_PHI
)
2003 return get_loop_init_value (as_a
<gphi
*> (def
));
2005 if (gimple_vuse (def
))
2009 use_operand_p use_p
;
2010 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2012 tree use
= USE_FROM_PTR (use_p
);
2013 if (TREE_CODE (use
) == SSA_NAME
)
2015 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2023 /* Return the init value, the value coming from outside the loop. */
2026 find_init_value_close_phi (gphi
*phi
)
2028 gcc_assert (gimple_phi_num_args (phi
) == 1);
2029 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2030 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2031 return find_init_value (def
);
2034 /* Copy all the loop-close phi args from BB to NEW_BB. */
2037 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2041 /* The successor of bb having close phi should be a merge of the diamond
2042 inserted to guard the loop during codegen. */
2043 basic_block succ_new_bb
= single_succ (new_bb
);
2045 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2048 gphi
*phi
= psi
.phi ();
2049 tree res
= gimple_phi_result (phi
);
2050 if (virtual_operand_p (res
))
2053 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2054 /* Loop close phi nodes should not be scev_analyzable_p. */
2057 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2058 tree new_res
= create_new_def_for (res
, new_phi
,
2059 gimple_phi_result_ptr (new_phi
));
2060 set_rename (res
, new_res
);
2062 tree old_name
= gimple_phi_arg_def (phi
, 0);
2063 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2065 /* Predecessor basic blocks of a loop close phi should have been code
2066 generated before. FIXME: This is fixable by merging PHIs from inner
2067 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2071 add_phi_arg (new_phi
, new_name
, single_pred_edge (new_bb
),
2072 get_loc (old_name
));
2075 fprintf (dump_file
, "\n[codegen] Adding loop-closed phi: ");
2076 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2079 update_stmt (new_phi
);
2081 /* When there is no loop guard around this codegenerated loop, there is no
2082 need to collect the close-phi arg. */
2083 if (2 != EDGE_COUNT (succ_new_bb
->preds
)
2084 || bb_contains_loop_phi_nodes (succ_new_bb
))
2087 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2088 tree init
= find_init_value_close_phi (new_phi
);
2090 /* A close phi must come from a loop-phi having an init value. */
2096 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2099 fprintf (dump_file
, "\n[codegen] postpone close phi nodes: ");
2100 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2105 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (res
), succ_new_bb
);
2106 tree merge_res
= create_new_def_for (res
, merge_phi
,
2107 gimple_phi_result_ptr (merge_phi
));
2108 set_rename (res
, merge_res
);
2110 edge from_loop
= single_succ_edge (new_bb
);
2111 add_phi_arg (merge_phi
, new_res
, from_loop
, get_loc (old_name
));
2113 /* The edge coming from loop guard. */
2114 edge other
= from_loop
== (*succ_new_bb
->preds
)[0]
2115 ? (*succ_new_bb
->preds
)[1] : (*succ_new_bb
->preds
)[0];
2117 add_phi_arg (merge_phi
, init
, other
, get_loc (old_name
));
2120 fprintf (dump_file
, "\n[codegen] Adding guard-phi: ");
2121 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2124 update_stmt (new_phi
);
2130 /* Copy loop close phi nodes from BB to NEW_BB. */
2133 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2137 fprintf (dump_file
, "\n[codegen] copying loop closed phi nodes in bb_%d.",
2139 /* Loop close phi nodes should have only one argument. */
2140 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2142 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2146 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2147 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2148 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2149 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2152 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2153 In this case DOMINATING_PRED = NULL.
2155 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2157 Returns true on successful copy of the args, false otherwise. */
2160 translate_isl_ast_to_gimple::
2161 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2162 edge old_bb_dominating_edge
,
2163 edge old_bb_non_dominating_edge
,
2164 gphi
*phi
, gphi
*new_phi
,
2167 basic_block def_pred
[2] = { NULL
, NULL
};
2168 int not_found_bb_index
= -1;
2169 for (int i
= 0; i
< 2; i
++)
2171 /* If the corresponding def_bb could not be found the entry will be
2173 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2174 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2175 gimple_phi_arg_edge (phi
, i
)->src
);
2176 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2177 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2181 /* When non are available bail out. */
2182 if (not_found_bb_index
!= -1)
2184 not_found_bb_index
= i
;
2188 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2189 if (old_bb_dominating_edge
)
2191 if (not_found_bb_index
!= -1)
2194 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2195 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2196 vec
<basic_block
> *bbs
2197 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2199 /* Could not find a mapping. */
2203 basic_block new_pred
= NULL
;
2206 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2208 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2210 /* FIXME: If we have already found new_pred then we have to
2211 disambiguate, bail out for now. */
2214 new_pred
= new_pred1
;
2216 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2218 /* FIXME: If we have already found new_pred then we have to either
2219 it dominates both or we have to disambiguate, bail out. */
2222 new_pred
= new_pred2
;
2229 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2230 gcc_assert (new_non_dominating_edge
);
2231 /* FIXME: Validate each args just like in loop-phis. */
2232 /* By the process of elimination we first insert insert phi-edge for
2233 non-dominating pred which is computed above and then we insert the
2235 int inserted_edge
= 0;
2236 for (; inserted_edge
< 2; inserted_edge
++)
2238 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2239 if (new_non_dominating_edge
== new_bb_pred_edge
)
2241 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2242 new_non_dominating_edge
,
2243 get_loc (old_phi_args
[inserted_edge
]));
2247 if (inserted_edge
== 2)
2250 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2252 edge new_dominating_edge
= NULL
;
2253 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2255 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2256 if (e
!= new_non_dominating_edge
)
2258 new_dominating_edge
= e
;
2259 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2260 new_dominating_edge
,
2261 get_loc (old_phi_args
[inserted_edge
]));
2265 gcc_assert (new_dominating_edge
);
2269 /* Classic diamond structure: both edges are non-dominating. We need to
2270 find one unique edge then the other can be found be elimination. If
2271 any definition (def_pred) dominates both the preds of new_bb then we
2272 bail out. Entries of def_pred maybe NULL, in that case we must
2273 uniquely find pred with help of only one entry. */
2274 edge new_e
[2] = { NULL
, NULL
};
2275 for (int i
= 0; i
< 2; i
++)
2279 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2281 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2284 /* We do not know how to handle the case when def_pred
2285 dominates more than a predecessor. */
2291 gcc_assert (new_e
[0] || new_e
[1]);
2293 /* Find the other edge by process of elimination. */
2294 if (not_found_bb_index
!= -1)
2296 gcc_assert (!new_e
[not_found_bb_index
]);
2297 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2300 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2302 if (new_e
[found_bb_index
] == e
)
2304 new_e
[not_found_bb_index
] = e
;
2308 /* Add edges to phi args. */
2309 for (int i
= 0; i
< 2; i
++)
2310 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2311 get_loc (old_phi_args
[i
]));
2317 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2318 region. If postpone is true and it isn't possible to copy any arg of PHI,
2319 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2320 Returns false if the copying was unsuccessful. */
2323 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2328 fprintf (dump_file
, "\n[codegen] copying cond phi args: ");
2329 gcc_assert (2 == gimple_phi_num_args (phi
));
2331 basic_block new_bb
= gimple_bb (new_phi
);
2332 loop_p loop
= gimple_bb (phi
)->loop_father
;
2334 basic_block old_bb
= gimple_bb (phi
);
2335 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2339 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2340 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2341 old_bb_non_dominating_edge
= e
;
2343 old_bb_dominating_edge
= e
;
2345 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2346 old_bb_non_dominating_edge
->src
));
2348 tree new_phi_args
[2];
2349 tree old_phi_args
[2];
2351 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2353 tree old_name
= gimple_phi_arg_def (phi
, i
);
2354 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2355 old_phi_args
[i
] = old_name
;
2358 new_phi_args
[i
] = new_name
;
2362 /* If the phi-arg was a parameter. */
2363 if (vec_find (region
->params
, old_name
) != -1)
2365 new_phi_args
[i
] = old_name
;
2369 "\n[codegen] parameter argument to phi, new_expr: ");
2370 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2375 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2376 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2377 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2383 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2384 if (is_gimple_reg (old_name
)
2385 && scev_analyzable_p (old_name
, region
->region
))
2388 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2389 new_bb
, old_bb
, iv_map
);
2390 if (codegen_error_p ())
2393 gcc_assert (new_expr
);
2397 "\n[codegen] scev analyzeable, new_expr: ");
2398 print_generic_expr (dump_file
, new_expr
, 0);
2400 gsi_insert_earliest (stmts
);
2401 new_phi_args
[i
] = new_name
;
2405 /* Postpone code gen for later for back-edges. */
2406 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2410 fprintf (dump_file
, "\n[codegen] postpone cond phi nodes: ");
2411 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2414 new_phi_args
[i
] = NULL_TREE
;
2418 /* Either we should add the arg to phi or, we should postpone. */
2422 /* If none of the args have been determined in the first stage then wait until
2424 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2427 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2428 old_bb_dominating_edge
,
2429 old_bb_non_dominating_edge
,
2430 phi
, new_phi
, new_bb
);
2433 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2434 containing phi nodes coming from two predecessors, and none of them are back
2438 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2443 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2446 fprintf (dump_file
, "\n[codegen] copying cond phi nodes in bb_%d:",
2449 /* Cond phi nodes should have exactly two arguments. */
2450 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2452 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2455 gphi
*phi
= psi
.phi ();
2456 tree res
= gimple_phi_result (phi
);
2457 if (virtual_operand_p (res
))
2459 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2460 /* Cond phi nodes should not be scev_analyzable_p. */
2463 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2464 tree new_res
= create_new_def_for (res
, new_phi
,
2465 gimple_phi_result_ptr (new_phi
));
2466 set_rename (res
, new_res
);
2468 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2471 update_stmt (new_phi
);
2477 /* Return true if STMT should be copied from region to the new code-generated
2478 region. LABELs, CONDITIONS, induction-variables and region parameters need
2482 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2484 /* Do not copy labels or conditions. */
2485 if (gimple_code (stmt
) == GIMPLE_LABEL
2486 || gimple_code (stmt
) == GIMPLE_COND
)
2490 /* Do not copy induction variables. */
2491 if (is_gimple_assign (stmt
)
2492 && (lhs
= gimple_assign_lhs (stmt
))
2493 && TREE_CODE (lhs
) == SSA_NAME
2494 && is_gimple_reg (lhs
)
2495 && scev_analyzable_p (lhs
, region
->region
))
2501 /* Create new names for all the definitions created by COPY and add replacement
2502 mappings for each new name. */
2505 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2507 def_operand_p def_p
;
2508 ssa_op_iter op_iter
;
2509 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2511 tree old_name
= DEF_FROM_PTR (def_p
);
2512 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2513 set_rename (old_name
, new_name
);
2517 /* Duplicates the statements of basic block BB into basic block NEW_BB
2518 and compute the new induction variables according to the IV_MAP.
2519 CODEGEN_ERROR is set when the code generation cannot continue. */
2522 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2526 /* Iterator poining to the place where new statement (s) will be inserted. */
2527 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2529 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2532 gimple
*stmt
= gsi_stmt (gsi
);
2533 if (!should_copy_to_new_region (stmt
, region
))
2536 /* Create a new copy of STMT and duplicate STMT's virtual
2538 gimple
*copy
= gimple_copy (stmt
);
2539 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2543 fprintf (dump_file
, "\n[codegen] inserting statement: ");
2544 print_gimple_stmt (dump_file
, copy
, 0, 0);
2547 maybe_duplicate_eh_stmt (copy
, stmt
);
2548 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2550 /* Crete new names for each def in the copied stmt. */
2551 set_rename_for_each_def (copy
);
2553 loop_p loop
= bb
->loop_father
;
2554 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2556 fold_stmt_inplace (&gsi_tgt
);
2557 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2560 if (codegen_error_p ())
2570 /* Given a basic block containing close-phi it returns the new basic block where
2571 to insert a copy of the close-phi nodes. All the uses in close phis should
2572 come from a single loop otherwise it returns NULL. */
2575 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2577 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2578 of close phi in the original code and then find the mapping of basic block
2579 defining that variable. If there are multiple close-phis and they are
2580 defined in different loops (in the original or in the new code) because of
2581 loop splitting, then we bail out. */
2582 loop_p new_loop
= NULL
;
2583 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2586 gphi
*phi
= psi
.phi ();
2587 tree name
= gimple_phi_arg_def (phi
, 0);
2588 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2590 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2591 if (!bbs
|| bbs
->length () != 1)
2592 /* This is one of the places which shows preserving original structure
2593 is not always possible, as we may need to insert close PHI for a loop
2594 where the latch does not have any mapping, or the mapping is
2599 new_loop
= (*bbs
)[0]->loop_father
;
2600 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2607 return single_exit (new_loop
);
2610 /* Copies BB and includes in the copied BB all the statements that can
2611 be reached following the use-def chains from the memory accesses,
2612 and returns the next edge following this new block. codegen_error is
2613 set when the code generation cannot continue. */
2616 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2620 int num_phis
= number_of_phi_nodes (bb
);
2622 if (region
->copied_bb_map
->get (bb
))
2624 /* FIXME: we should be able to handle phi nodes with args coming from
2625 outside the region. */
2628 codegen_error
= true;
2633 basic_block new_bb
= split_edge (next_e
);
2634 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2636 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2638 /* At this point we are unable to codegenerate by still preserving the SSA
2639 structure because maybe the loop is completely unrolled and the PHIs
2640 and cross-bb scalar dependencies are untrackable w.r.t. the original
2641 code. See gfortran.dg/graphite/pr29832.f90. */
2642 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2644 codegen_error
= true;
2649 fprintf (dump_file
, "\n[codegen] bb_%d contains loop phi nodes",
2651 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2653 codegen_error
= true;
2657 else if (bb_contains_loop_close_phi_nodes (bb
))
2660 fprintf (dump_file
, "\n[codegen] bb_%d contains close phi nodes",
2663 edge e
= edge_for_new_close_phis (bb
);
2666 codegen_error
= true;
2670 basic_block phi_bb
= split_edge (e
);
2671 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2672 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2674 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2676 codegen_error
= true;
2680 else if (num_phis
> 0)
2683 fprintf (dump_file
, "\n[codegen] bb_%d contains cond phi nodes",
2686 basic_block phi_bb
= single_pred (new_bb
);
2687 loop_p loop_father
= new_bb
->loop_father
;
2689 /* Move back until we find the block with two predecessors. */
2690 while (single_pred_p (phi_bb
))
2691 phi_bb
= single_pred_edge (phi_bb
)->src
;
2693 /* If a corresponding merge-point was not found, then abort codegen. */
2694 if (phi_bb
->loop_father
!= loop_father
2695 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2697 codegen_error
= true;
2703 fprintf (dump_file
, "\n[codegen] copying from bb_%d to bb_%d",
2704 bb
->index
, new_bb
->index
);
2706 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2708 copied_bbs
->safe_push (new_bb
);
2711 vec
<basic_block
> bbs
;
2713 bbs
.safe_push (new_bb
);
2714 region
->copied_bb_map
->put (bb
, bbs
);
2717 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2719 codegen_error
= true;
2723 return single_succ_edge (new_bb
);
2726 /* Patch the missing arguments of the phi nodes. */
2729 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2733 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2735 gphi
*old_phi
= rename
->first
;
2736 gphi
*new_phi
= rename
->second
;
2737 basic_block old_bb
= gimple_bb (old_phi
);
2738 basic_block new_bb
= gimple_bb (new_phi
);
2740 /* First edge is the init edge and second is the back edge. */
2741 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2742 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2746 fprintf (dump_file
, "\n[codegen] translating pending old-phi: ");
2747 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2750 auto_vec
<tree
, 1> iv_map
;
2751 if (bb_contains_loop_phi_nodes (new_bb
))
2752 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2754 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2755 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2757 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2761 fprintf (dump_file
, "[codegen] to new-phi: ");
2762 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2767 /* Prints NODE to FILE. */
2770 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
2771 __isl_keep isl_ast_node
*node
,
2772 __isl_keep isl_ctx
*ctx
) const
2774 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
2775 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
2776 prn
= isl_printer_print_ast_node (prn
, node
);
2777 prn
= isl_printer_print_str (prn
, "\n");
2778 isl_printer_free (prn
);
2781 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
2784 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
2787 sese_info_p region
= scop
->scop_info
;
2788 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2789 gcc_assert (nb_parameters
== region
->params
.length ());
2791 for (i
= 0; i
< nb_parameters
; i
++)
2793 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2795 ip
[tmp_id
] = region
->params
[i
];
2800 /* Generates a build, which specifies the constraints on the parameters. */
2802 __isl_give isl_ast_build
*
2803 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
2805 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2806 return isl_ast_build_from_context (context_isl
);
2809 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2812 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
2816 int schedule_dims
= 0;
2818 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2820 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
2821 if (pbb_schedule_dims
> schedule_dims
)
2822 schedule_dims
= pbb_schedule_dims
;
2825 return schedule_dims
;
2828 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2830 For schedules with different dimensionality, the isl AST generator can not
2831 define an order and will just randomly choose an order. The solution to this
2832 problem is to extend all schedules to the maximal number of schedule
2833 dimensions (using '0's for the remaining values). */
2835 __isl_give isl_map
*
2836 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
2837 int nb_schedule_dims
)
2839 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
2841 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
2843 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
2845 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
2848 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
2850 isl_val_free (zero
);
2854 /* Generates a schedule, which specifies an order used to
2855 visit elements in a domain. */
2857 __isl_give isl_union_map
*
2858 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
2860 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
2863 isl_union_map
*schedule_isl
=
2864 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
2866 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2868 /* Dead code elimination: when the domain of a PBB is empty,
2869 don't generate code for the PBB. */
2870 if (isl_set_is_empty (pbb
->domain
))
2873 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
2874 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
2875 isl_set_copy (pbb
->domain
));
2876 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
2878 = isl_union_map_union (schedule_isl
,
2879 isl_union_map_from_map (bb_schedule
));
2881 return schedule_isl
;
2884 /* This method is executed before the construction of a for node. */
2886 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2888 isl_union_map
*dependences
= (isl_union_map
*) user
;
2889 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2890 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2891 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2892 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2893 for_info
->is_parallelizable
=
2894 !carries_deps (schedule
, dependences
, dimension
);
2895 isl_union_map_free (schedule
);
2896 isl_space_free (schedule_space
);
2897 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2901 /* Set the separate option for all dimensions.
2902 This helps to reduce control overhead. */
2904 __isl_give isl_ast_build
*
2905 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
2906 __isl_keep isl_union_map
*schedule
)
2908 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
2909 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
2911 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
2912 isl_union_set
*range
=
2913 isl_union_set_from_set (isl_set_universe (range_space
));
2914 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
2915 domain
= isl_union_set_universe (domain
);
2916 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
2917 return isl_ast_build_set_options (control
, options
);
2920 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
2922 __isl_give isl_ast_node
*
2923 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
2925 /* Generate loop upper bounds that consist of the current loop iterator, an
2926 operator (< or <=) and an expression not involving the iterator. If this
2927 option is not set, then the current loop iterator may appear several times
2928 in the upper bound. See the isl manual for more details. */
2929 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
2931 add_parameters_to_ivs_params (scop
, ip
);
2932 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
2933 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2934 context_isl
= set_options (context_isl
, schedule_isl
);
2935 isl_union_map
*dependences
= NULL
;
2936 if (flag_loop_parallelize_all
)
2938 dependences
= scop_get_dependences (scop
);
2940 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2943 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
2946 isl_union_map_free (dependences
);
2947 isl_ast_build_free (context_isl
);
2951 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
2952 the given SCOP. Return true if code generation succeeded.
2954 FIXME: This is not yet a full implementation of the code generator
2955 with ISL ASTs. Generation of GIMPLE code has to be completed. */
2958 graphite_regenerate_ast_isl (scop_p scop
)
2960 sese_info_p region
= scop
->scop_info
;
2961 translate_isl_ast_to_gimple
t (region
);
2963 ifsese if_region
= NULL
;
2964 isl_ast_node
*root_node
;
2967 timevar_push (TV_GRAPHITE_CODE_GEN
);
2968 root_node
= t
.scop_to_isl_ast (scop
, ip
);
2970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2972 fprintf (dump_file
, "\nISL AST generated by ISL: \n");
2973 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
2976 recompute_all_dominators ();
2979 if_region
= move_sese_in_condition (region
);
2980 region
->if_region
= if_region
;
2981 recompute_all_dominators ();
2983 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
2985 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
2986 basic_block bb
= split_edge (e
);
2988 /* Update the true_region exit edge. */
2989 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
2991 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
2992 if (t
.codegen_error_p ())
2995 fprintf (dump_file
, "\n[codegen] unsuccessful,"
2996 " reverting back to the original code.");
2997 set_ifsese_condition (if_region
, integer_zero_node
);
3001 t
.translate_pending_phi_nodes ();
3002 if (!t
.codegen_error_p ())
3004 sese_insert_phis_for_liveouts (region
,
3005 if_region
->region
->region
.exit
->src
,
3006 if_region
->false_region
->region
.exit
,
3007 if_region
->true_region
->region
.exit
);
3008 mark_virtual_operands_for_renaming (cfun
);
3009 update_ssa (TODO_update_ssa
);
3014 recompute_all_dominators ();
3020 fprintf (dump_file
, "\n[codegen] unsuccessful in translating"
3021 " pending phis, reverting back to the original code.");
3022 set_ifsese_condition (if_region
, integer_zero_node
);
3026 free (if_region
->true_region
);
3027 free (if_region
->region
);
3030 ivs_params_clear (ip
);
3031 isl_ast_node_free (root_node
);
3032 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3037 int num_no_dependency
= 0;
3039 FOR_EACH_LOOP (loop
, 0)
3040 if (loop
->can_be_parallel
)
3041 num_no_dependency
++;
3043 fprintf (dump_file
, "\n%d loops carried no dependency.\n",
3047 return !t
.codegen_error_p ();
3050 #endif /* HAVE_isl */