1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
34 #include "fold-const.h"
35 #include "gimple-fold.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
40 #include "tree-ssa-loop.h"
41 #include "tree-ssa-operands.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-pass.h"
45 #include "tree-data-ref.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-scalar-evolution.h"
48 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "tree-into-ssa.h"
51 #include "ssa-iterators.h"
53 #include "gimple-pretty-print.h"
55 #include "value-prof.h"
57 #include <isl/constraint.h>
59 #include <isl/union_set.h>
61 #include <isl/union_map.h>
62 #include <isl/ast_build.h>
64 /* Since ISL-0.13, the extern is in val_gmp.h. */
65 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
68 #include <isl/val_gmp.h>
69 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
77 /* We always try to use signed 128 bit types, but fall back to smaller types
78 in case a platform does not provide types of these sizes. In the future we
79 should use isl to derive the optimal type for each subexpression. */
81 static int max_mode_int_precision
=
82 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE
, MODE_INT
, 0));
83 static int graphite_expression_type_precision
= 128 <= max_mode_int_precision
?
84 128 : max_mode_int_precision
;
89 : is_parallelizable(false)
91 bool is_parallelizable
;
94 /* Converts a GMP constant VAL to a tree and returns it. */
97 gmp_cst_to_tree (tree type
, mpz_t val
)
99 tree t
= type
? type
: integer_type_node
;
104 wide_int wi
= wi::from_mpz (t
, tmp
, true);
107 return wide_int_to_tree (t
, wi
);
110 /* Verifies properties that GRAPHITE should maintain during translation. */
113 graphite_verify (void)
115 checking_verify_loop_structure ();
116 checking_verify_loop_closed_ssa (true);
119 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
120 to corresponding trees. */
122 typedef std::map
<isl_id
*, tree
> ivs_params
;
124 /* Free all memory allocated for ISL's identifiers. */
126 void ivs_params_clear (ivs_params
&ip
)
128 std::map
<isl_id
*, tree
>::iterator it
;
129 for (it
= ip
.begin ();
130 it
!= ip
.end (); it
++)
132 isl_id_free (it
->first
);
136 class translate_isl_ast_to_gimple
139 translate_isl_ast_to_gimple (sese_info_p r
)
140 : region (r
), codegen_error (false)
143 /* Translates an ISL AST node NODE to GCC representation in the
144 context of a SESE. */
145 edge
translate_isl_ast (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
146 edge next_e
, ivs_params
&ip
);
148 /* Translates an isl_ast_node_for to Gimple. */
149 edge
translate_isl_ast_node_for (loop_p context_loop
,
150 __isl_keep isl_ast_node
*node
,
151 edge next_e
, ivs_params
&ip
);
153 /* Create the loop for a isl_ast_node_for.
155 - NEXT_E is the edge where new generated code should be attached. */
156 edge
translate_isl_ast_for_loop (loop_p context_loop
,
157 __isl_keep isl_ast_node
*node_for
,
159 tree type
, tree lb
, tree ub
,
162 /* Translates an isl_ast_node_if to Gimple. */
163 edge
translate_isl_ast_node_if (loop_p context_loop
,
164 __isl_keep isl_ast_node
*node
,
165 edge next_e
, ivs_params
&ip
);
167 /* Translates an isl_ast_node_user to Gimple.
169 FIXME: We should remove iv_map.create (loop->num + 1), if it is
171 edge
translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
172 edge next_e
, ivs_params
&ip
);
174 /* Translates an isl_ast_node_block to Gimple. */
175 edge
translate_isl_ast_node_block (loop_p context_loop
,
176 __isl_keep isl_ast_node
*node
,
177 edge next_e
, ivs_params
&ip
);
179 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
181 tree
unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
184 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
186 tree
binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
189 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
191 tree
ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
194 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
195 to a GCC expression tree of type TYPE. */
196 tree
nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
,
199 /* Converts an ISL AST expression E back to a GCC expression tree of
201 tree
gcc_expression_from_isl_expression (tree type
,
202 __isl_take isl_ast_expr
*,
205 /* Return the tree variable that corresponds to the given isl ast identifier
206 expression (an isl_ast_expr of type isl_ast_expr_id).
208 FIXME: We should replace blind conversation of id's type with derivation
209 of the optimal type when we get the corresponding isl support. Blindly
210 converting type sizes may be problematic when we switch to smaller
212 tree
gcc_expression_from_isl_ast_expr_id (tree type
,
213 __isl_keep isl_ast_expr
*expr_id
,
216 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
218 tree
gcc_expression_from_isl_expr_int (tree type
,
219 __isl_take isl_ast_expr
*expr
);
221 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
223 tree
gcc_expression_from_isl_expr_op (tree type
,
224 __isl_take isl_ast_expr
*expr
,
227 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
228 induction variable for the new LOOP. New LOOP is attached to CFG
229 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
230 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
231 ISL's scattering name to the induction variable created for the
232 loop of STMT. The new induction variable is inserted in the NEWIVS
233 vector and is of type TYPE. */
234 struct loop
*graphite_create_new_loop (edge entry_edge
,
235 __isl_keep isl_ast_node
*node_for
,
236 loop_p outer
, tree type
,
237 tree lb
, tree ub
, ivs_params
&ip
);
239 /* All loops generated by create_empty_loop_on_edge have the form of
246 } while (lower bound < upper bound);
248 We create a new if region protecting the loop to be executed, if
249 the execution count is zero (lower bound > upper bound). */
250 edge
graphite_create_new_loop_guard (edge entry_edge
,
251 __isl_keep isl_ast_node
*node_for
,
253 tree
*lb
, tree
*ub
, ivs_params
&ip
);
255 /* Creates a new if region corresponding to ISL's cond. */
256 edge
graphite_create_new_guard (edge entry_edge
,
257 __isl_take isl_ast_expr
*if_cond
,
260 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
261 variables of the loops around GBB in SESE.
263 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
264 chrec, we could consider using a map<int, tree> that maps loop ids to the
265 corresponding tree expressions. */
266 void build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
267 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
270 /* Patch the missing arguments of the phi nodes. */
272 void translate_pending_phi_nodes (void);
274 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
276 void add_parameters_to_ivs_params (scop_p scop
, ivs_params
&ip
);
278 /* Get the maximal number of schedule dimensions in the scop SCOP. */
280 int get_max_schedule_dimensions (scop_p scop
);
282 /* Generates a build, which specifies the constraints on the parameters. */
284 __isl_give isl_ast_build
*generate_isl_context (scop_p scop
);
286 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
288 For schedules with different dimensionality, the isl AST generator can not
289 define an order and will just randomly choose an order. The solution to
290 this problem is to extend all schedules to the maximal number of schedule
291 dimensions (using '0's for the remaining values). */
293 __isl_give isl_map
*extend_schedule (__isl_take isl_map
*schedule
,
294 int nb_schedule_dims
);
296 /* Generates a schedule, which specifies an order used to
297 visit elements in a domain. */
299 __isl_give isl_union_map
*generate_isl_schedule (scop_p scop
);
301 /* Set the separate option for all dimensions.
302 This helps to reduce control overhead. */
304 __isl_give isl_ast_build
* set_options (__isl_take isl_ast_build
*control
,
305 __isl_keep isl_union_map
*schedule
);
307 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in
310 __isl_give isl_ast_node
* scop_to_isl_ast (scop_p scop
, ivs_params
&ip
);
313 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
314 definition should flow into use, and the use should respect the loop-closed
317 bool is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
318 bool loop_phi
, tree old_name
, basic_block old_bb
) const;
320 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
321 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
322 within a loop PHI instruction. */
324 tree
get_rename (basic_block new_bb
, tree old_name
,
325 basic_block old_bb
, bool loop_phi
) const;
327 /* For ops which are scev_analyzeable, we can regenerate a new name from
328 its scalar evolution around LOOP. */
330 tree
get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
331 basic_block new_bb
, basic_block old_bb
,
334 /* Returns a basic block that could correspond to where a constant was defined
335 in the original code. In the original code OLD_BB had the definition, we
336 need to find which basic block out of the copies of old_bb, in the new
337 region, should a definition correspond to if it has to reach BB. */
339 basic_block
get_def_bb_for_const (basic_block bb
, basic_block old_bb
) const;
341 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is
342 true when we want to rename an OP within a loop PHI instruction. */
344 tree
get_new_name (basic_block new_bb
, tree op
,
345 basic_block old_bb
, bool loop_phi
) const;
347 /* Collect all the operands of NEW_EXPR by recursively visiting each
350 void collect_all_ssa_names (tree new_expr
, vec
<tree
> *vec_ssa
);
352 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to
353 NEW_PHI must be found unless they can be POSTPONEd for later. */
355 bool copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
356 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
359 /* Copy loop phi nodes from BB to NEW_BB. */
361 bool copy_loop_phi_nodes (basic_block bb
, basic_block new_bb
);
363 /* Copy all the loop-close phi args from BB to NEW_BB. */
365 bool copy_loop_close_phi_args (basic_block old_bb
, basic_block new_bb
,
368 /* Copy loop close phi nodes from BB to NEW_BB. */
370 bool copy_loop_close_phi_nodes (basic_block old_bb
, basic_block new_bb
);
372 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
373 region. If postpone is true and it isn't possible to copy any arg of PHI,
374 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
375 Returns false if the copying was unsuccessful. */
377 bool copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
, vec
<tree
> iv_map
,
380 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
381 containing phi nodes coming from two predecessors, and none of them are back
384 bool copy_cond_phi_nodes (basic_block bb
, basic_block new_bb
,
387 /* Duplicates the statements of basic block BB into basic block NEW_BB
388 and compute the new induction variables according to the IV_MAP.
389 CODEGEN_ERROR is set when the code generation cannot continue. */
391 bool graphite_copy_stmts_from_block (basic_block bb
, basic_block new_bb
,
394 /* Copies BB and includes in the copied BB all the statements that can
395 be reached following the use-def chains from the memory accesses,
396 and returns the next edge following this new block. codegen_error is
397 set when the code generation cannot continue. */
399 edge
copy_bb_and_scalar_dependences (basic_block bb
, edge next_e
,
402 /* Given a basic block containing close-phi it returns the new basic block
403 where to insert a copy of the close-phi nodes. All the uses in close phis
404 should come from a single loop otherwise it returns NULL. */
405 edge
edge_for_new_close_phis (basic_block bb
);
407 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
408 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates
409 the other pred of OLD_BB as well. If no such basic block exists then it is
410 NULL. NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it
413 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice
414 versa. In this case DOMINATING_PRED = NULL.
416 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
418 Returns true on successful copy of the args, false otherwise. */
420 bool add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
421 edge old_bb_dominating_edge
,
422 edge old_bb_non_dominating_edge
,
423 gphi
*phi
, gphi
*new_phi
,
426 /* Renames the scalar uses of the statement COPY, using the substitution map
427 RENAME_MAP, inserting the gimplification code at GSI_TGT, for the
428 translation REGION, with the original copied statement in LOOP, and using
429 the induction variable renaming map IV_MAP. Returns true when something
430 has been renamed. codegen_error is set when the code generation cannot
433 bool rename_uses (gimple
*copy
, gimple_stmt_iterator
*gsi_tgt
,
434 basic_block old_bb
, loop_p loop
, vec
<tree
> iv_map
);
436 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
437 When OLD_NAME and EXPR are the same we assert. */
439 void set_rename (tree old_name
, tree expr
);
441 /* Create new names for all the definitions created by COPY and add
442 replacement mappings for each new name. */
444 void set_rename_for_each_def (gimple
*stmt
);
446 /* Insert each statement from SEQ at its earliest insertion p. */
448 void gsi_insert_earliest (gimple_seq seq
);
450 /* Rename all the operands of NEW_EXPR by recursively visiting each
453 tree
rename_all_uses (tree new_expr
, basic_block new_bb
, basic_block old_bb
);
455 bool codegen_error_p () const
456 { return codegen_error
; }
458 /* Prints NODE to FILE. */
460 void print_isl_ast_node (FILE *file
, __isl_keep isl_ast_node
*node
,
461 __isl_keep isl_ctx
*ctx
) const;
463 /* Return true when OP is a constant tree. */
465 bool is_constant (tree op
) const
467 return TREE_CODE (op
) == INTEGER_CST
468 || TREE_CODE (op
) == REAL_CST
469 || TREE_CODE (op
) == COMPLEX_CST
470 || TREE_CODE (op
) == VECTOR_CST
;
476 /* This flag is set when an error occurred during the translation of ISL AST
481 /* Return the tree variable that corresponds to the given isl ast identifier
482 expression (an isl_ast_expr of type isl_ast_expr_id).
484 FIXME: We should replace blind conversation of id's type with derivation
485 of the optimal type when we get the corresponding isl support. Blindly
486 converting type sizes may be problematic when we switch to smaller
490 translate_isl_ast_to_gimple::
491 gcc_expression_from_isl_ast_expr_id (tree type
,
492 __isl_keep isl_ast_expr
*expr_id
,
495 gcc_assert (isl_ast_expr_get_type (expr_id
) == isl_ast_expr_id
);
496 isl_id
*tmp_isl_id
= isl_ast_expr_get_id (expr_id
);
497 std::map
<isl_id
*, tree
>::iterator res
;
498 res
= ip
.find (tmp_isl_id
);
499 isl_id_free (tmp_isl_id
);
500 gcc_assert (res
!= ip
.end () &&
501 "Could not map isl_id to tree expression");
502 isl_ast_expr_free (expr_id
);
503 tree t
= res
->second
;
504 return fold_convert (type
, t
);
507 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
511 translate_isl_ast_to_gimple::
512 gcc_expression_from_isl_expr_int (tree type
, __isl_take isl_ast_expr
*expr
)
514 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_int
);
515 isl_val
*val
= isl_ast_expr_get_val (expr
);
517 mpz_init (val_mpz_t
);
519 if (isl_val_get_num_gmp (val
, val_mpz_t
) == -1)
522 res
= gmp_cst_to_tree (type
, val_mpz_t
);
524 isl_ast_expr_free (expr
);
525 mpz_clear (val_mpz_t
);
529 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
533 translate_isl_ast_to_gimple::
534 binary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
536 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
537 tree tree_lhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
538 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
539 tree tree_rhs_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
540 enum isl_ast_op_type expr_type
= isl_ast_expr_get_op_type (expr
);
541 isl_ast_expr_free (expr
);
545 return fold_build2 (PLUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
548 return fold_build2 (MINUS_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
551 return fold_build2 (MULT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
554 return fold_build2 (EXACT_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
556 case isl_ast_op_pdiv_q
:
557 return fold_build2 (TRUNC_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
559 case isl_ast_op_pdiv_r
:
560 return fold_build2 (TRUNC_MOD_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
562 case isl_ast_op_fdiv_q
:
563 return fold_build2 (FLOOR_DIV_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
566 return fold_build2 (TRUTH_ANDIF_EXPR
, type
,
567 tree_lhs_expr
, tree_rhs_expr
);
570 return fold_build2 (TRUTH_ORIF_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
573 return fold_build2 (EQ_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
576 return fold_build2 (LE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
579 return fold_build2 (LT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
582 return fold_build2 (GE_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
585 return fold_build2 (GT_EXPR
, type
, tree_lhs_expr
, tree_rhs_expr
);
592 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
596 translate_isl_ast_to_gimple::
597 ternary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
599 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
600 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
602 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
603 arg_expr
= isl_ast_expr_get_op_arg (expr
, 1);
604 tree tree_second_expr
605 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
606 arg_expr
= isl_ast_expr_get_op_arg (expr
, 2);
608 = gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
609 isl_ast_expr_free (expr
);
610 return fold_build3 (COND_EXPR
, type
, tree_first_expr
,
611 tree_second_expr
, tree_third_expr
);
614 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
618 translate_isl_ast_to_gimple::
619 unary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
621 gcc_assert (isl_ast_expr_get_op_type (expr
) == isl_ast_op_minus
);
622 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
623 tree tree_expr
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
624 isl_ast_expr_free (expr
);
625 return fold_build1 (NEGATE_EXPR
, type
, tree_expr
);
628 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
629 to a GCC expression tree of type TYPE. */
632 translate_isl_ast_to_gimple::
633 nary_op_to_tree (tree type
, __isl_take isl_ast_expr
*expr
, ivs_params
&ip
)
635 enum tree_code op_code
;
636 switch (isl_ast_expr_get_op_type (expr
))
649 isl_ast_expr
*arg_expr
= isl_ast_expr_get_op_arg (expr
, 0);
650 tree res
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
652 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (expr
); i
++)
654 arg_expr
= isl_ast_expr_get_op_arg (expr
, i
);
655 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
656 res
= fold_build2 (op_code
, type
, res
, t
);
658 isl_ast_expr_free (expr
);
662 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
666 translate_isl_ast_to_gimple::
667 gcc_expression_from_isl_expr_op (tree type
, __isl_take isl_ast_expr
*expr
,
670 gcc_assert (isl_ast_expr_get_type (expr
) == isl_ast_expr_op
);
671 switch (isl_ast_expr_get_op_type (expr
))
673 /* These isl ast expressions are not supported yet. */
674 case isl_ast_op_error
:
675 case isl_ast_op_call
:
676 case isl_ast_op_and_then
:
677 case isl_ast_op_or_else
:
678 case isl_ast_op_select
:
683 return nary_op_to_tree (type
, expr
, ip
);
689 case isl_ast_op_pdiv_q
:
690 case isl_ast_op_pdiv_r
:
691 case isl_ast_op_fdiv_q
:
699 return binary_op_to_tree (type
, expr
, ip
);
701 case isl_ast_op_minus
:
702 return unary_op_to_tree (type
, expr
, ip
);
704 case isl_ast_op_cond
:
705 return ternary_op_to_tree (type
, expr
, ip
);
714 /* Converts an ISL AST expression E back to a GCC expression tree of
718 translate_isl_ast_to_gimple::
719 gcc_expression_from_isl_expression (tree type
, __isl_take isl_ast_expr
*expr
,
722 switch (isl_ast_expr_get_type (expr
))
724 case isl_ast_expr_id
:
725 return gcc_expression_from_isl_ast_expr_id (type
, expr
, ip
);
727 case isl_ast_expr_int
:
728 return gcc_expression_from_isl_expr_int (type
, expr
);
730 case isl_ast_expr_op
:
731 return gcc_expression_from_isl_expr_op (type
, expr
, ip
);
740 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
741 induction variable for the new LOOP. New LOOP is attached to CFG
742 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
743 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
744 ISL's scattering name to the induction variable created for the
745 loop of STMT. The new induction variable is inserted in the NEWIVS
746 vector and is of type TYPE. */
749 translate_isl_ast_to_gimple::
750 graphite_create_new_loop (edge entry_edge
, __isl_keep isl_ast_node
*node_for
,
751 loop_p outer
, tree type
, tree lb
, tree ub
,
754 isl_ast_expr
*for_inc
= isl_ast_node_for_get_inc (node_for
);
755 tree stride
= gcc_expression_from_isl_expression (type
, for_inc
, ip
);
756 tree ivvar
= create_tmp_var (type
, "graphite_IV");
757 tree iv
, iv_after_increment
;
758 loop_p loop
= create_empty_loop_on_edge
759 (entry_edge
, lb
, stride
, ub
, ivvar
, &iv
, &iv_after_increment
,
760 outer
? outer
: entry_edge
->src
->loop_father
);
762 isl_ast_expr
*for_iterator
= isl_ast_node_for_get_iterator (node_for
);
763 isl_id
*id
= isl_ast_expr_get_id (for_iterator
);
764 std::map
<isl_id
*, tree
>::iterator res
;
767 isl_id_free (res
->first
);
769 isl_ast_expr_free (for_iterator
);
773 /* Create the loop for a isl_ast_node_for.
775 - NEXT_E is the edge where new generated code should be attached. */
778 translate_isl_ast_to_gimple::
779 translate_isl_ast_for_loop (loop_p context_loop
,
780 __isl_keep isl_ast_node
*node_for
, edge next_e
,
781 tree type
, tree lb
, tree ub
,
784 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
785 struct loop
*loop
= graphite_create_new_loop (next_e
, node_for
, context_loop
,
787 edge last_e
= single_exit (loop
);
788 edge to_body
= single_succ_edge (loop
->header
);
789 basic_block after
= to_body
->dest
;
791 /* Translate the body of the loop. */
792 isl_ast_node
*for_body
= isl_ast_node_for_get_body (node_for
);
793 next_e
= translate_isl_ast (loop
, for_body
, to_body
, ip
);
794 isl_ast_node_free (for_body
);
796 /* Early return if we failed to translate loop body. */
797 if (!next_e
|| codegen_error_p ())
800 redirect_edge_succ_nodup (next_e
, after
);
801 set_immediate_dominator (CDI_DOMINATORS
, next_e
->dest
, next_e
->src
);
803 if (flag_loop_parallelize_all
)
805 isl_id
*id
= isl_ast_node_get_annotation (node_for
);
807 ast_build_info
*for_info
= (ast_build_info
*) isl_id_get_user (id
);
808 loop
->can_be_parallel
= for_info
->is_parallelizable
;
816 /* We use this function to get the upper bound because of the form,
817 which is used by isl to represent loops:
819 for (iterator = init; cond; iterator += inc)
827 The loop condition is an arbitrary expression, which contains the
828 current loop iterator.
830 (e.g. iterator + 3 < B && C > iterator + A)
832 We have to know the upper bound of the iterator to generate a loop
833 in Gimple form. It can be obtained from the special representation
834 of the loop condition, which is generated by isl,
835 if the ast_build_atomic_upper_bound option is set. In this case,
836 isl generates a loop condition that consists of the current loop
837 iterator, + an operator (< or <=) and an expression not involving
838 the iterator, which is processed and returned by this function.
840 (e.g iterator <= upper-bound-expression-without-iterator) */
842 static __isl_give isl_ast_expr
*
843 get_upper_bound (__isl_keep isl_ast_node
*node_for
)
845 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
846 isl_ast_expr
*for_cond
= isl_ast_node_for_get_cond (node_for
);
847 gcc_assert (isl_ast_expr_get_type (for_cond
) == isl_ast_expr_op
);
849 switch (isl_ast_expr_get_op_type (for_cond
))
852 res
= isl_ast_expr_get_op_arg (for_cond
, 1);
857 /* (iterator < ub) => (iterator <= ub - 1). */
859 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond
), 1);
860 isl_ast_expr
*ub
= isl_ast_expr_get_op_arg (for_cond
, 1);
861 res
= isl_ast_expr_sub (ub
, isl_ast_expr_from_val (one
));
868 isl_ast_expr_free (for_cond
);
872 /* All loops generated by create_empty_loop_on_edge have the form of
879 } while (lower bound < upper bound);
881 We create a new if region protecting the loop to be executed, if
882 the execution count is zero (lower bound > upper bound). */
885 translate_isl_ast_to_gimple::
886 graphite_create_new_loop_guard (edge entry_edge
,
887 __isl_keep isl_ast_node
*node_for
, tree
*type
,
888 tree
*lb
, tree
*ub
, ivs_params
&ip
)
890 gcc_assert (isl_ast_node_get_type (node_for
) == isl_ast_node_for
);
895 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
896 isl_ast_expr
*for_init
= isl_ast_node_for_get_init (node_for
);
897 *lb
= gcc_expression_from_isl_expression (*type
, for_init
, ip
);
898 isl_ast_expr
*upper_bound
= get_upper_bound (node_for
);
899 *ub
= gcc_expression_from_isl_expression (*type
, upper_bound
, ip
);
901 /* When ub is simply a constant or a parameter, use lb <= ub. */
902 if (TREE_CODE (*ub
) == INTEGER_CST
|| TREE_CODE (*ub
) == SSA_NAME
)
903 cond_expr
= fold_build2 (LE_EXPR
, boolean_type_node
, *lb
, *ub
);
906 tree one
= (POINTER_TYPE_P (*type
)
907 ? convert_to_ptrofftype (integer_one_node
)
908 : fold_convert (*type
, integer_one_node
));
909 /* Adding +1 and using LT_EXPR helps with loop latches that have a
910 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
911 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
912 is true, even if we do not want this. However lb < ub + 1 is false,
914 tree ub_one
= fold_build2 (POINTER_TYPE_P (*type
) ? POINTER_PLUS_EXPR
915 : PLUS_EXPR
, *type
, *ub
, one
);
917 cond_expr
= fold_build2 (LT_EXPR
, boolean_type_node
, *lb
, ub_one
);
920 if (integer_onep (cond_expr
))
921 exit_edge
= entry_edge
;
923 exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
928 /* Translates an isl_ast_node_for to Gimple. */
931 translate_isl_ast_to_gimple::
932 translate_isl_ast_node_for (loop_p context_loop
, __isl_keep isl_ast_node
*node
,
933 edge next_e
, ivs_params
&ip
)
935 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_for
);
937 edge last_e
= graphite_create_new_loop_guard (next_e
, node
, &type
,
940 if (last_e
== next_e
)
941 /* There was no guard generated. */
942 return translate_isl_ast_for_loop (context_loop
, node
, last_e
,
945 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
946 translate_isl_ast_for_loop (context_loop
, node
, true_e
, type
, lb
, ub
, ip
);
950 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
951 variables of the loops around GBB in SESE.
953 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
954 chrec, we could consider using a map<int, tree> that maps loop ids to the
955 corresponding tree expressions. */
958 translate_isl_ast_to_gimple::
959 build_iv_mapping (vec
<tree
> iv_map
, gimple_poly_bb_p gbb
,
960 __isl_keep isl_ast_expr
*user_expr
, ivs_params
&ip
,
963 gcc_assert (isl_ast_expr_get_type (user_expr
) == isl_ast_expr_op
&&
964 isl_ast_expr_get_op_type (user_expr
) == isl_ast_op_call
);
966 isl_ast_expr
*arg_expr
;
967 for (i
= 1; i
< isl_ast_expr_get_op_n_arg (user_expr
); i
++)
969 arg_expr
= isl_ast_expr_get_op_arg (user_expr
, i
);
971 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
972 tree t
= gcc_expression_from_isl_expression (type
, arg_expr
, ip
);
973 loop_p old_loop
= gbb_loop_at_index (gbb
, region
, i
- 1);
974 iv_map
[old_loop
->num
] = t
;
978 /* Translates an isl_ast_node_user to Gimple.
980 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
983 translate_isl_ast_to_gimple::
984 translate_isl_ast_node_user (__isl_keep isl_ast_node
*node
,
985 edge next_e
, ivs_params
&ip
)
987 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_user
);
989 isl_ast_expr
*user_expr
= isl_ast_node_user_get_expr (node
);
990 isl_ast_expr
*name_expr
= isl_ast_expr_get_op_arg (user_expr
, 0);
991 gcc_assert (isl_ast_expr_get_type (name_expr
) == isl_ast_expr_id
);
993 isl_id
*name_id
= isl_ast_expr_get_id (name_expr
);
994 poly_bb_p pbb
= (poly_bb_p
) isl_id_get_user (name_id
);
997 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
999 isl_ast_expr_free (name_expr
);
1000 isl_id_free (name_id
);
1002 gcc_assert (GBB_BB (gbb
) != ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1003 "The entry block should not even appear within a scop");
1005 const int nb_loops
= number_of_loops (cfun
);
1007 iv_map
.create (nb_loops
);
1008 iv_map
.safe_grow_cleared (nb_loops
);
1010 build_iv_mapping (iv_map
, gbb
, user_expr
, ip
, pbb
->scop
->scop_info
->region
);
1011 isl_ast_expr_free (user_expr
);
1015 fprintf (dump_file
, "[codegen] copying from basic block\n");
1016 print_loops_bb (dump_file
, GBB_BB (gbb
), 0, 3);
1017 fprintf (dump_file
, "[codegen] to new basic block\n");
1018 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1021 next_e
= copy_bb_and_scalar_dependences (GBB_BB (gbb
), next_e
,
1026 if (codegen_error_p ())
1031 fprintf (dump_file
, "[codegen] (after copy) new basic block\n");
1032 print_loops_bb (dump_file
, next_e
->src
, 0, 3);
1038 /* Translates an isl_ast_node_block to Gimple. */
1041 translate_isl_ast_to_gimple::
1042 translate_isl_ast_node_block (loop_p context_loop
,
1043 __isl_keep isl_ast_node
*node
,
1044 edge next_e
, ivs_params
&ip
)
1046 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_block
);
1047 isl_ast_node_list
*node_list
= isl_ast_node_block_get_children (node
);
1049 for (i
= 0; i
< isl_ast_node_list_n_ast_node (node_list
); i
++)
1051 isl_ast_node
*tmp_node
= isl_ast_node_list_get_ast_node (node_list
, i
);
1052 next_e
= translate_isl_ast (context_loop
, tmp_node
, next_e
, ip
);
1053 isl_ast_node_free (tmp_node
);
1055 isl_ast_node_list_free (node_list
);
1059 /* Creates a new if region corresponding to ISL's cond. */
1062 translate_isl_ast_to_gimple::
1063 graphite_create_new_guard (edge entry_edge
, __isl_take isl_ast_expr
*if_cond
,
1067 build_nonstandard_integer_type (graphite_expression_type_precision
, 0);
1068 tree cond_expr
= gcc_expression_from_isl_expression (type
, if_cond
, ip
);
1069 edge exit_edge
= create_empty_if_region_on_edge (entry_edge
, cond_expr
);
1073 /* Translates an isl_ast_node_if to Gimple. */
1076 translate_isl_ast_to_gimple::
1077 translate_isl_ast_node_if (loop_p context_loop
,
1078 __isl_keep isl_ast_node
*node
,
1079 edge next_e
, ivs_params
&ip
)
1081 gcc_assert (isl_ast_node_get_type (node
) == isl_ast_node_if
);
1082 isl_ast_expr
*if_cond
= isl_ast_node_if_get_cond (node
);
1083 edge last_e
= graphite_create_new_guard (next_e
, if_cond
, ip
);
1085 edge true_e
= get_true_edge_from_guard_bb (next_e
->dest
);
1086 isl_ast_node
*then_node
= isl_ast_node_if_get_then (node
);
1087 translate_isl_ast (context_loop
, then_node
, true_e
, ip
);
1088 isl_ast_node_free (then_node
);
1090 edge false_e
= get_false_edge_from_guard_bb (next_e
->dest
);
1091 isl_ast_node
*else_node
= isl_ast_node_if_get_else (node
);
1092 if (isl_ast_node_get_type (else_node
) != isl_ast_node_error
)
1093 translate_isl_ast (context_loop
, else_node
, false_e
, ip
);
1094 isl_ast_node_free (else_node
);
1098 /* Translates an ISL AST node NODE to GCC representation in the
1099 context of a SESE. */
1102 translate_isl_ast_to_gimple::translate_isl_ast (loop_p context_loop
,
1103 __isl_keep isl_ast_node
*node
,
1104 edge next_e
, ivs_params
&ip
)
1106 if (codegen_error_p ())
1109 switch (isl_ast_node_get_type (node
))
1111 case isl_ast_node_error
:
1114 case isl_ast_node_for
:
1115 return translate_isl_ast_node_for (context_loop
, node
,
1118 case isl_ast_node_if
:
1119 return translate_isl_ast_node_if (context_loop
, node
,
1122 case isl_ast_node_user
:
1123 return translate_isl_ast_node_user (node
, next_e
, ip
);
1125 case isl_ast_node_block
:
1126 return translate_isl_ast_node_block (context_loop
, node
,
1134 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1135 at the exit of loop which takes one argument that is the last value of the
1136 variable being used out of the loop. */
1139 bb_contains_loop_close_phi_nodes (basic_block bb
)
1141 return single_pred_p (bb
)
1142 && bb
->loop_father
!= single_pred_edge (bb
)->src
->loop_father
;
1145 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1146 header containing phi nodes which has one init-edge and one back-edge. */
1149 bb_contains_loop_phi_nodes (basic_block bb
)
1151 gcc_assert (EDGE_COUNT (bb
->preds
) <= 2);
1153 if (bb
->preds
->length () == 1)
1156 unsigned depth
= loop_depth (bb
->loop_father
);
1158 edge preds
[2] = { (*bb
->preds
)[0], (*bb
->preds
)[1] };
1160 if (depth
> loop_depth (preds
[0]->src
->loop_father
)
1161 || depth
> loop_depth (preds
[1]->src
->loop_father
))
1164 /* When one of the edges correspond to the same loop father and other
1166 if (bb
->loop_father
!= preds
[0]->src
->loop_father
1167 && bb
->loop_father
== preds
[1]->src
->loop_father
)
1170 if (bb
->loop_father
!= preds
[1]->src
->loop_father
1171 && bb
->loop_father
== preds
[0]->src
->loop_father
)
1177 /* Check if USE is defined in a basic block from where the definition of USE can
1178 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1181 is_loop_closed_ssa_use (basic_block bb
, tree use
)
1183 if (TREE_CODE (use
) != SSA_NAME
|| virtual_operand_p (use
))
1186 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1187 if (bb_contains_loop_close_phi_nodes (bb
))
1190 gimple
*def
= SSA_NAME_DEF_STMT (use
);
1191 basic_block def_bb
= gimple_bb (def
);
1193 || flow_bb_inside_loop_p (def_bb
->loop_father
, bb
));
1196 /* Return the number of phi nodes in BB. */
1199 number_of_phi_nodes (basic_block bb
)
1202 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1208 /* Returns true if BB uses name in one of its PHIs. */
1211 phi_uses_name (basic_block bb
, tree name
)
1213 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1216 gphi
*phi
= psi
.phi ();
1217 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1219 tree use_arg
= gimple_phi_arg_def (phi
, i
);
1220 if (use_arg
== name
)
1227 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1228 definition should flow into use, and the use should respect the loop-closed
1232 translate_isl_ast_to_gimple::
1233 is_valid_rename (tree rename
, basic_block def_bb
, basic_block use_bb
,
1234 bool loop_phi
, tree old_name
, basic_block old_bb
) const
1236 /* The def of the rename must either dominate the uses or come from a
1237 back-edge. Also the def must respect the loop closed ssa form. */
1238 if (!is_loop_closed_ssa_use (use_bb
, rename
))
1242 fprintf (dump_file
, "[codegen] rename not in loop closed ssa:");
1243 print_generic_expr (dump_file
, rename
, 0);
1244 fprintf (dump_file
, "\n");
1249 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
))
1252 if (bb_contains_loop_phi_nodes (use_bb
) && loop_phi
)
1254 /* The loop-header dominates the loop-body. */
1255 if (!dominated_by_p (CDI_DOMINATORS
, def_bb
, use_bb
))
1258 /* RENAME would be used in loop-phi. */
1259 gcc_assert (number_of_phi_nodes (use_bb
));
1261 /* For definitions coming from back edges, we should check that
1262 old_name is used in a loop PHI node.
1263 FIXME: Verify if this is true. */
1264 if (phi_uses_name (old_bb
, old_name
))
1270 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1271 NEW_BB from RENAME_MAP. LOOP_PHI is true when we want to rename OLD_NAME
1272 within a loop PHI instruction. */
1275 translate_isl_ast_to_gimple::get_rename (basic_block new_bb
,
1278 bool loop_phi
) const
1280 gcc_assert (TREE_CODE (old_name
) == SSA_NAME
);
1281 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1283 if (!renames
|| renames
->is_empty ())
1286 if (1 == renames
->length ())
1288 tree rename
= (*renames
)[0];
1289 if (TREE_CODE (rename
) == SSA_NAME
)
1291 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (rename
));
1292 if (is_valid_rename (rename
, bb
, new_bb
, loop_phi
, old_name
, old_bb
))
1297 if (is_constant (rename
))
1303 /* More than one renames corresponding to the old_name. Find the rename for
1304 which the definition flows into usage at new_bb. */
1306 tree t1
= NULL_TREE
, t2
;
1307 basic_block t1_bb
= NULL
;
1308 FOR_EACH_VEC_ELT (*renames
, i
, t2
)
1310 basic_block t2_bb
= gimple_bb (SSA_NAME_DEF_STMT (t2
));
1312 /* Defined in the same basic block as used. */
1313 if (t2_bb
== new_bb
)
1316 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1317 if (!dominated_by_p (CDI_DOMINATORS
, new_bb
, t2_bb
))
1320 /* Compute the nearest dominator. */
1321 if (!t1
|| dominated_by_p (CDI_DOMINATORS
, t2_bb
, t1_bb
))
1331 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1332 When OLD_NAME and EXPR are the same we assert. */
1335 translate_isl_ast_to_gimple::set_rename (tree old_name
, tree expr
)
1339 fprintf (dump_file
, "[codegen] setting rename: old_name = ");
1340 print_generic_expr (dump_file
, old_name
, 0);
1341 fprintf (dump_file
, ", new_name = ");
1342 print_generic_expr (dump_file
, expr
, 0);
1343 fprintf (dump_file
, "\n");
1346 if (old_name
== expr
)
1349 vec
<tree
> *renames
= region
->rename_map
->get (old_name
);
1352 renames
->safe_push (expr
);
1358 region
->rename_map
->put (old_name
, r
);
1362 /* Return an iterator to the instructions comes last in the execution order.
1363 Either GSI1 and GSI2 should belong to the same basic block or one of their
1364 respective basic blocks should dominate the other. */
1366 gimple_stmt_iterator
1367 later_of_the_two (gimple_stmt_iterator gsi1
, gimple_stmt_iterator gsi2
)
1369 basic_block bb1
= gsi_bb (gsi1
);
1370 basic_block bb2
= gsi_bb (gsi2
);
1372 /* Find the iterator which is the latest. */
1375 /* For empty basic blocks gsis point to the end of the sequence. Since
1376 there is no operator== defined for gimple_stmt_iterator and for gsis
1377 not pointing to a valid statement gsi_next would assert. */
1378 gimple_stmt_iterator gsi
= gsi1
;
1380 if (gsi_stmt (gsi
) == gsi_stmt (gsi2
))
1383 } while (!gsi_end_p (gsi
));
1388 /* Find the basic block closest to the basic block which defines stmt. */
1389 if (dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
))
1392 gcc_assert (dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
));
1396 /* Insert each statement from SEQ at its earliest insertion p. */
1399 translate_isl_ast_to_gimple::gsi_insert_earliest (gimple_seq seq
)
1401 update_modified_stmts (seq
);
1402 sese_l
&codegen_region
= region
->if_region
->true_region
->region
;
1403 basic_block begin_bb
= get_entry_bb (codegen_region
);
1405 /* Inserting the gimple statements in a vector because gimple_seq behave
1406 in strage ways when inserting the stmts from it into different basic
1407 blocks one at a time. */
1408 auto_vec
<gimple
*, 3> stmts
;
1409 for (gimple_stmt_iterator gsi
= gsi_start (seq
); !gsi_end_p (gsi
);
1411 stmts
.safe_push (gsi_stmt (gsi
));
1415 FOR_EACH_VEC_ELT (stmts
, i
, use_stmt
)
1417 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1418 gimple_stmt_iterator gsi_def_stmt
= gsi_start_bb_nondebug (begin_bb
);
1420 use_operand_p use_p
;
1421 ssa_op_iter op_iter
;
1422 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, op_iter
, SSA_OP_USE
)
1424 /* Iterator to the current def of use_p. For function parameters or
1425 anything where def is not found, insert at the beginning of the
1426 generated region. */
1427 gimple_stmt_iterator gsi_stmt
= gsi_def_stmt
;
1429 tree op
= USE_FROM_PTR (use_p
);
1430 gimple
*stmt
= SSA_NAME_DEF_STMT (op
);
1431 if (stmt
&& (gimple_code (stmt
) != GIMPLE_NOP
))
1432 gsi_stmt
= gsi_for_stmt (stmt
);
1434 /* For region parameters, insert at the beginning of the generated
1436 if (!bb_in_sese_p (gsi_bb (gsi_stmt
), codegen_region
))
1437 gsi_stmt
= gsi_def_stmt
;
1439 gsi_def_stmt
= later_of_the_two (gsi_stmt
, gsi_def_stmt
);
1442 if (!gsi_stmt (gsi_def_stmt
))
1444 gimple_stmt_iterator gsi
= gsi_after_labels (gsi_bb (gsi_def_stmt
));
1445 gsi_insert_before (&gsi
, use_stmt
, GSI_NEW_STMT
);
1447 else if (gimple_code (gsi_stmt (gsi_def_stmt
)) == GIMPLE_PHI
)
1449 gimple_stmt_iterator bsi
1450 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt
));
1451 /* Insert right after the PHI statements. */
1452 gsi_insert_before (&bsi
, use_stmt
, GSI_NEW_STMT
);
1455 gsi_insert_after (&gsi_def_stmt
, use_stmt
, GSI_NEW_STMT
);
1459 fprintf (dump_file
, "[codegen] inserting statement: ");
1460 print_gimple_stmt (dump_file
, use_stmt
, 0, TDF_VOPS
| TDF_MEMSYMS
);
1461 print_loops_bb (dump_file
, gimple_bb (use_stmt
), 0, 3);
1466 /* Collect all the operands of NEW_EXPR by recursively visiting each
1470 translate_isl_ast_to_gimple::collect_all_ssa_names (tree new_expr
,
1474 /* Rename all uses in new_expr. */
1475 if (TREE_CODE (new_expr
) == SSA_NAME
)
1477 vec_ssa
->safe_push (new_expr
);
1481 /* Iterate over SSA_NAMES in NEW_EXPR. */
1482 for (int i
= 0; i
< (TREE_CODE_LENGTH (TREE_CODE (new_expr
))); i
++)
1484 tree op
= TREE_OPERAND (new_expr
, i
);
1485 collect_all_ssa_names (op
, vec_ssa
);
1489 /* This is abridged version of the function:
1490 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1493 substitute_ssa_name (tree exp
, tree f
, tree r
)
1495 enum tree_code code
= TREE_CODE (exp
);
1496 tree op0
, op1
, op2
, op3
;
1499 /* We handle TREE_LIST and COMPONENT_REF separately. */
1500 if (code
== TREE_LIST
)
1502 op0
= substitute_ssa_name (TREE_CHAIN (exp
), f
, r
);
1503 op1
= substitute_ssa_name (TREE_VALUE (exp
), f
, r
);
1504 if (op0
== TREE_CHAIN (exp
) && op1
== TREE_VALUE (exp
))
1507 return tree_cons (TREE_PURPOSE (exp
), op1
, op0
);
1509 else if (code
== COMPONENT_REF
)
1513 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1514 and it is the right field, replace it with R. */
1515 for (inner
= TREE_OPERAND (exp
, 0);
1516 REFERENCE_CLASS_P (inner
);
1517 inner
= TREE_OPERAND (inner
, 0))
1521 op1
= TREE_OPERAND (exp
, 1);
1523 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& op1
== f
)
1526 /* If this expression hasn't been completed let, leave it alone. */
1527 if (TREE_CODE (inner
) == PLACEHOLDER_EXPR
&& !TREE_TYPE (inner
))
1530 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1531 if (op0
== TREE_OPERAND (exp
, 0))
1535 = fold_build3 (COMPONENT_REF
, TREE_TYPE (exp
), op0
, op1
, NULL_TREE
);
1538 switch (TREE_CODE_CLASS (code
))
1543 case tcc_declaration
:
1549 case tcc_expression
:
1553 /* Fall through... */
1555 case tcc_exceptional
:
1558 case tcc_comparison
:
1560 switch (TREE_CODE_LENGTH (code
))
1568 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1569 if (op0
== TREE_OPERAND (exp
, 0))
1572 new_tree
= fold_build1 (code
, TREE_TYPE (exp
), op0
);
1576 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1577 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1579 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1))
1582 new_tree
= fold_build2 (code
, TREE_TYPE (exp
), op0
, op1
);
1586 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1587 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1588 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1590 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1591 && op2
== TREE_OPERAND (exp
, 2))
1594 new_tree
= fold_build3 (code
, TREE_TYPE (exp
), op0
, op1
, op2
);
1598 op0
= substitute_ssa_name (TREE_OPERAND (exp
, 0), f
, r
);
1599 op1
= substitute_ssa_name (TREE_OPERAND (exp
, 1), f
, r
);
1600 op2
= substitute_ssa_name (TREE_OPERAND (exp
, 2), f
, r
);
1601 op3
= substitute_ssa_name (TREE_OPERAND (exp
, 3), f
, r
);
1603 if (op0
== TREE_OPERAND (exp
, 0) && op1
== TREE_OPERAND (exp
, 1)
1604 && op2
== TREE_OPERAND (exp
, 2)
1605 && op3
== TREE_OPERAND (exp
, 3))
1609 = fold (build4 (code
, TREE_TYPE (exp
), op0
, op1
, op2
, op3
));
1622 TREE_READONLY (new_tree
) |= TREE_READONLY (exp
);
1624 if (code
== INDIRECT_REF
|| code
== ARRAY_REF
|| code
== ARRAY_RANGE_REF
)
1625 TREE_THIS_NOTRAP (new_tree
) |= TREE_THIS_NOTRAP (exp
);
1630 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1633 translate_isl_ast_to_gimple::rename_all_uses (tree new_expr
, basic_block new_bb
,
1636 auto_vec
<tree
, 2> ssa_names
;
1637 collect_all_ssa_names (new_expr
, &ssa_names
);
1640 FOR_EACH_VEC_ELT (ssa_names
, i
, t
)
1641 if (tree r
= get_rename (new_bb
, t
, old_bb
, false))
1642 new_expr
= substitute_ssa_name (new_expr
, t
, r
);
1647 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1648 scalar evolution around LOOP. */
1651 translate_isl_ast_to_gimple::
1652 get_rename_from_scev (tree old_name
, gimple_seq
*stmts
, loop_p loop
,
1653 basic_block new_bb
, basic_block old_bb
,
1656 tree scev
= scalar_evolution_in_region (region
->region
, loop
, old_name
);
1658 /* At this point we should know the exact scev for each
1659 scalar SSA_NAME used in the scop: all the other scalar
1660 SSA_NAMEs should have been translated out of SSA using
1661 arrays with one element. */
1663 if (chrec_contains_undetermined (scev
))
1665 codegen_error
= true;
1666 return build_zero_cst (TREE_TYPE (old_name
));
1669 new_expr
= chrec_apply_map (scev
, iv_map
);
1671 /* The apply should produce an expression tree containing
1672 the uses of the new induction variables. We should be
1673 able to use new_expr instead of the old_name in the newly
1674 generated loop nest. */
1675 if (chrec_contains_undetermined (new_expr
)
1676 || tree_contains_chrecs (new_expr
, NULL
))
1678 codegen_error
= true;
1679 return build_zero_cst (TREE_TYPE (old_name
));
1682 /* We should check all the operands and all of them should dominate the use at
1684 if (TREE_CODE (new_expr
) == SSA_NAME
)
1686 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1687 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1689 codegen_error
= true;
1690 return build_zero_cst (TREE_TYPE (old_name
));
1694 new_expr
= rename_all_uses (new_expr
, new_bb
, old_bb
);
1695 /* We should check all the operands and all of them should dominate the use at
1697 if (TREE_CODE (new_expr
) == SSA_NAME
)
1699 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (new_expr
));
1700 if (bb
&& !dominated_by_p (CDI_DOMINATORS
, new_bb
, bb
))
1702 codegen_error
= true;
1703 return build_zero_cst (TREE_TYPE (old_name
));
1707 /* Replace the old_name with the new_expr. */
1708 return force_gimple_operand (unshare_expr (new_expr
), stmts
,
1712 /* Renames the scalar uses of the statement COPY, using the
1713 substitution map RENAME_MAP, inserting the gimplification code at
1714 GSI_TGT, for the translation REGION, with the original copied
1715 statement in LOOP, and using the induction variable renaming map
1716 IV_MAP. Returns true when something has been renamed. codegen_error
1717 is set when the code generation cannot continue. */
1720 translate_isl_ast_to_gimple::rename_uses (gimple
*copy
,
1721 gimple_stmt_iterator
*gsi_tgt
,
1723 loop_p loop
, vec
<tree
> iv_map
)
1725 bool changed
= false;
1727 if (is_gimple_debug (copy
))
1729 if (gimple_debug_bind_p (copy
))
1730 gimple_debug_bind_reset_value (copy
);
1731 else if (gimple_debug_source_bind_p (copy
))
1741 fprintf (dump_file
, "[codegen] renaming uses of stmt: ");
1742 print_gimple_stmt (dump_file
, copy
, 0, 0);
1745 use_operand_p use_p
;
1746 ssa_op_iter op_iter
;
1747 FOR_EACH_SSA_USE_OPERAND (use_p
, copy
, op_iter
, SSA_OP_USE
)
1749 tree old_name
= USE_FROM_PTR (use_p
);
1753 fprintf (dump_file
, "[codegen] renaming old_name = ");
1754 print_generic_expr (dump_file
, old_name
, 0);
1755 fprintf (dump_file
, "\n");
1758 if (TREE_CODE (old_name
) != SSA_NAME
1759 || SSA_NAME_IS_DEFAULT_DEF (old_name
))
1763 tree new_expr
= get_rename (gsi_tgt
->bb
, old_name
,
1768 tree type_old_name
= TREE_TYPE (old_name
);
1769 tree type_new_expr
= TREE_TYPE (new_expr
);
1773 fprintf (dump_file
, "[codegen] from rename_map: new_name = ");
1774 print_generic_expr (dump_file
, new_expr
, 0);
1775 fprintf (dump_file
, "\n");
1778 if (type_old_name
!= type_new_expr
1779 || TREE_CODE (new_expr
) != SSA_NAME
)
1781 tree var
= create_tmp_var (type_old_name
, "var");
1783 if (!useless_type_conversion_p (type_old_name
, type_new_expr
))
1784 new_expr
= fold_convert (type_old_name
, new_expr
);
1787 new_expr
= force_gimple_operand (new_expr
, &stmts
, true, var
);
1788 gsi_insert_earliest (stmts
);
1791 replace_exp (use_p
, new_expr
);
1796 new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
, gimple_bb (copy
),
1798 if (!new_expr
|| codegen_error_p ())
1803 fprintf (dump_file
, "[codegen] not in rename map, scev: ");
1804 print_generic_expr (dump_file
, new_expr
, 0);
1805 fprintf (dump_file
, "\n");
1808 gsi_insert_earliest (stmts
);
1809 replace_exp (use_p
, new_expr
);
1811 if (TREE_CODE (new_expr
) == INTEGER_CST
1812 && is_gimple_assign (copy
))
1814 tree rhs
= gimple_assign_rhs1 (copy
);
1816 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1817 recompute_tree_invariant_for_addr_expr (rhs
);
1820 set_rename (old_name
, new_expr
);
1826 /* Returns a basic block that could correspond to where a constant was defined
1827 in the original code. In the original code OLD_BB had the definition, we
1828 need to find which basic block out of the copies of old_bb, in the new
1829 region, should a definition correspond to if it has to reach BB. */
1832 translate_isl_ast_to_gimple::get_def_bb_for_const (basic_block bb
,
1833 basic_block old_bb
) const
1835 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_bb
);
1837 if (!bbs
|| bbs
->is_empty ())
1840 if (1 == bbs
->length ())
1844 basic_block b1
= NULL
, b2
;
1845 FOR_EACH_VEC_ELT (*bbs
, i
, b2
)
1850 /* BB and B2 are in two unrelated if-clauses. */
1851 if (!dominated_by_p (CDI_DOMINATORS
, bb
, b2
))
1854 /* Compute the nearest dominator. */
1855 if (!b1
|| dominated_by_p (CDI_DOMINATORS
, b2
, b1
))
1863 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. LOOP_PHI is true
1864 when we want to rename an OP within a loop PHI instruction. */
1867 translate_isl_ast_to_gimple::
1868 get_new_name (basic_block new_bb
, tree op
,
1869 basic_block old_bb
, bool loop_phi
) const
1871 /* For constants the names are the same. */
1872 if (is_constant (op
))
1875 return get_rename (new_bb
, op
, old_bb
, loop_phi
);
1878 /* Return a debug location for OP. */
1883 location_t loc
= UNKNOWN_LOCATION
;
1885 if (TREE_CODE (op
) == SSA_NAME
)
1886 loc
= gimple_location (SSA_NAME_DEF_STMT (op
));
1890 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1891 the init edge (from outside the loop) and the second one is the back edge
1892 from the same loop. */
1894 std::pair
<edge
, edge
>
1895 get_edges (basic_block bb
)
1897 std::pair
<edge
, edge
> edges
;
1900 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1901 if (bb
->loop_father
!= e
->src
->loop_father
)
1908 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1909 must be found unless they can be POSTPONEd for later. */
1912 translate_isl_ast_to_gimple::
1913 copy_loop_phi_args (gphi
*old_phi
, init_back_edge_pair_t
&ibp_old_bb
,
1914 gphi
*new_phi
, init_back_edge_pair_t
&ibp_new_bb
,
1917 gcc_assert (gimple_phi_num_args (old_phi
) == gimple_phi_num_args (new_phi
));
1919 basic_block new_bb
= gimple_bb (new_phi
);
1920 for (unsigned i
= 0; i
< gimple_phi_num_args (old_phi
); i
++)
1923 if (gimple_phi_arg_edge (old_phi
, i
) == ibp_old_bb
.first
)
1924 e
= ibp_new_bb
.first
;
1926 e
= ibp_new_bb
.second
;
1928 tree old_name
= gimple_phi_arg_def (old_phi
, i
);
1929 tree new_name
= get_new_name (new_bb
, old_name
,
1930 gimple_bb (old_phi
), true);
1933 add_phi_arg (new_phi
, new_name
, e
, get_loc (old_name
));
1937 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
1938 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
1939 /* If the phi arg was a function arg, or wasn't defined, just use the
1941 add_phi_arg (new_phi
, old_name
, e
, get_loc (old_name
));
1944 /* Postpone code gen for later for those back-edges we don't have the
1946 region
->incomplete_phis
.safe_push (std::make_pair (old_phi
, new_phi
));
1948 fprintf (dump_file
, "[codegen] postpone loop phi nodes.\n");
1951 /* Either we should add the arg to phi or, we should postpone. */
1957 /* Copy loop phi nodes from BB to NEW_BB. */
1960 translate_isl_ast_to_gimple::copy_loop_phi_nodes (basic_block bb
,
1964 fprintf (dump_file
, "[codegen] copying loop phi nodes in bb_%d.\n",
1967 /* Loop phi nodes should have only two arguments. */
1968 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
1970 /* First edge is the init edge and second is the back edge. */
1971 init_back_edge_pair_t ibp_old_bb
= get_edges (bb
);
1973 /* First edge is the init edge and second is the back edge. */
1974 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
1976 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
1979 gphi
*phi
= psi
.phi ();
1980 tree res
= gimple_phi_result (phi
);
1981 if (virtual_operand_p (res
))
1983 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
1986 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
1987 tree new_res
= create_new_def_for (res
, new_phi
,
1988 gimple_phi_result_ptr (new_phi
));
1989 set_rename (res
, new_res
);
1990 codegen_error
= !copy_loop_phi_args (phi
, ibp_old_bb
, new_phi
,
1992 update_stmt (new_phi
);
1998 /* Return the init value of PHI, the value coming from outside the loop. */
2001 get_loop_init_value (gphi
*phi
)
2004 loop_p loop
= gimple_bb (phi
)->loop_father
;
2008 FOR_EACH_EDGE (e
, ei
, gimple_bb (phi
)->preds
)
2009 if (e
->src
->loop_father
!= loop
)
2010 return gimple_phi_arg_def (phi
, e
->dest_idx
);
2015 /* Find the init value (the value which comes from outside the loop), of one of
2016 the operands of DEF which is defined by a loop phi. */
2019 find_init_value (gimple
*def
)
2021 if (gimple_code (def
) == GIMPLE_PHI
)
2022 return get_loop_init_value (as_a
<gphi
*> (def
));
2024 if (gimple_vuse (def
))
2028 use_operand_p use_p
;
2029 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
2031 tree use
= USE_FROM_PTR (use_p
);
2032 if (TREE_CODE (use
) == SSA_NAME
)
2034 if (tree res
= find_init_value (SSA_NAME_DEF_STMT (use
)))
2042 /* Return the init value, the value coming from outside the loop. */
2045 find_init_value_close_phi (gphi
*phi
)
2047 gcc_assert (gimple_phi_num_args (phi
) == 1);
2048 tree use_arg
= gimple_phi_arg_def (phi
, 0);
2049 gimple
*def
= SSA_NAME_DEF_STMT (use_arg
);
2050 return find_init_value (def
);
2053 /* Copy all the loop-close phi args from BB to NEW_BB. */
2056 translate_isl_ast_to_gimple::copy_loop_close_phi_args (basic_block old_bb
,
2060 /* The successor of bb having close phi should be a merge of the diamond
2061 inserted to guard the loop during codegen. */
2062 basic_block succ_new_bb
= single_succ (new_bb
);
2064 for (gphi_iterator psi
= gsi_start_phis (old_bb
); !gsi_end_p (psi
);
2067 gphi
*phi
= psi
.phi ();
2068 tree res
= gimple_phi_result (phi
);
2069 if (virtual_operand_p (res
))
2072 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2073 /* Loop close phi nodes should not be scev_analyzable_p. */
2076 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2077 tree new_res
= create_new_def_for (res
, new_phi
,
2078 gimple_phi_result_ptr (new_phi
));
2079 set_rename (res
, new_res
);
2081 tree old_name
= gimple_phi_arg_def (phi
, 0);
2082 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2084 /* Predecessor basic blocks of a loop close phi should have been code
2085 generated before. FIXME: This is fixable by merging PHIs from inner
2086 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2090 add_phi_arg (new_phi
, new_name
, single_pred_edge (new_bb
),
2091 get_loc (old_name
));
2094 fprintf (dump_file
, "[codegen] Adding loop-closed phi: ");
2095 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2098 update_stmt (new_phi
);
2100 /* When there is no loop guard around this codegenerated loop, there is no
2101 need to collect the close-phi arg. */
2102 if (2 != EDGE_COUNT (succ_new_bb
->preds
)
2103 || bb_contains_loop_phi_nodes (succ_new_bb
))
2106 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2107 tree init
= find_init_value_close_phi (new_phi
);
2109 /* A close phi must come from a loop-phi having an init value. */
2115 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2118 fprintf (dump_file
, "[codegen] postpone close phi nodes: ");
2119 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2124 gphi
*merge_phi
= create_phi_node (SSA_NAME_VAR (res
), succ_new_bb
);
2125 tree merge_res
= create_new_def_for (res
, merge_phi
,
2126 gimple_phi_result_ptr (merge_phi
));
2127 set_rename (res
, merge_res
);
2129 edge from_loop
= single_succ_edge (new_bb
);
2130 add_phi_arg (merge_phi
, new_res
, from_loop
, get_loc (old_name
));
2132 /* The edge coming from loop guard. */
2133 edge other
= from_loop
== (*succ_new_bb
->preds
)[0]
2134 ? (*succ_new_bb
->preds
)[1] : (*succ_new_bb
->preds
)[0];
2136 add_phi_arg (merge_phi
, init
, other
, get_loc (old_name
));
2139 fprintf (dump_file
, "[codegen] Adding guard-phi: ");
2140 print_gimple_stmt (dump_file
, merge_phi
, 0, 0);
2143 update_stmt (new_phi
);
2149 /* Copy loop close phi nodes from BB to NEW_BB. */
2152 translate_isl_ast_to_gimple::copy_loop_close_phi_nodes (basic_block old_bb
,
2156 fprintf (dump_file
, "[codegen] copying loop closed phi nodes in bb_%d.\n",
2158 /* Loop close phi nodes should have only one argument. */
2159 gcc_assert (1 == EDGE_COUNT (old_bb
->preds
));
2161 return copy_loop_close_phi_args (old_bb
, new_bb
, true);
2165 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2166 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2167 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2168 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2171 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2172 In this case DOMINATING_PRED = NULL.
2174 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2176 Returns true on successful copy of the args, false otherwise. */
2179 translate_isl_ast_to_gimple::
2180 add_phi_arg_for_new_expr (tree old_phi_args
[2], tree new_phi_args
[2],
2181 edge old_bb_dominating_edge
,
2182 edge old_bb_non_dominating_edge
,
2183 gphi
*phi
, gphi
*new_phi
,
2186 basic_block def_pred
[2] = { NULL
, NULL
};
2187 int not_found_bb_index
= -1;
2188 for (int i
= 0; i
< 2; i
++)
2190 /* If the corresponding def_bb could not be found the entry will be
2192 if (TREE_CODE (old_phi_args
[i
]) == INTEGER_CST
)
2193 def_pred
[i
] = get_def_bb_for_const (new_bb
,
2194 gimple_phi_arg_edge (phi
, i
)->src
);
2195 else if (new_phi_args
[i
] && (TREE_CODE (new_phi_args
[i
]) == SSA_NAME
))
2196 def_pred
[i
] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args
[i
]));
2200 /* When non are available bail out. */
2201 if (not_found_bb_index
!= -1)
2203 not_found_bb_index
= i
;
2207 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2208 if (old_bb_dominating_edge
)
2210 if (not_found_bb_index
!= -1)
2213 basic_block new_pred1
= (*new_bb
->preds
)[0]->src
;
2214 basic_block new_pred2
= (*new_bb
->preds
)[1]->src
;
2215 vec
<basic_block
> *bbs
2216 = region
->copied_bb_map
->get (old_bb_non_dominating_edge
->src
);
2218 /* Could not find a mapping. */
2222 basic_block new_pred
= NULL
;
2225 FOR_EACH_VEC_ELT (*bbs
, i
, b
)
2227 if (dominated_by_p (CDI_DOMINATORS
, new_pred1
, b
))
2229 /* FIXME: If we have already found new_pred then we have to
2230 disambiguate, bail out for now. */
2233 new_pred
= new_pred1
;
2235 if (dominated_by_p (CDI_DOMINATORS
, new_pred2
, b
))
2237 /* FIXME: If we have already found new_pred then we have to either
2238 it dominates both or we have to disambiguate, bail out. */
2241 new_pred
= new_pred2
;
2248 edge new_non_dominating_edge
= find_edge (new_pred
, new_bb
);
2249 gcc_assert (new_non_dominating_edge
);
2250 /* FIXME: Validate each args just like in loop-phis. */
2251 /* By the process of elimination we first insert insert phi-edge for
2252 non-dominating pred which is computed above and then we insert the
2254 int inserted_edge
= 0;
2255 for (; inserted_edge
< 2; inserted_edge
++)
2257 edge new_bb_pred_edge
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2258 if (new_non_dominating_edge
== new_bb_pred_edge
)
2260 add_phi_arg (new_phi
, new_phi_args
[inserted_edge
],
2261 new_non_dominating_edge
,
2262 get_loc (old_phi_args
[inserted_edge
]));
2266 if (inserted_edge
== 2)
2269 int edge_dominating
= inserted_edge
== 0 ? 1 : 0;
2271 edge new_dominating_edge
= NULL
;
2272 for (inserted_edge
= 0; inserted_edge
< 2; inserted_edge
++)
2274 edge e
= gimple_phi_arg_edge (new_phi
, inserted_edge
);
2275 if (e
!= new_non_dominating_edge
)
2277 new_dominating_edge
= e
;
2278 add_phi_arg (new_phi
, new_phi_args
[edge_dominating
],
2279 new_dominating_edge
,
2280 get_loc (old_phi_args
[inserted_edge
]));
2284 gcc_assert (new_dominating_edge
);
2288 /* Classic diamond structure: both edges are non-dominating. We need to
2289 find one unique edge then the other can be found be elimination. If
2290 any definition (def_pred) dominates both the preds of new_bb then we
2291 bail out. Entries of def_pred maybe NULL, in that case we must
2292 uniquely find pred with help of only one entry. */
2293 edge new_e
[2] = { NULL
, NULL
};
2294 for (int i
= 0; i
< 2; i
++)
2298 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2300 && dominated_by_p (CDI_DOMINATORS
, e
->src
, def_pred
[i
]))
2303 /* We do not know how to handle the case when def_pred
2304 dominates more than a predecessor. */
2310 gcc_assert (new_e
[0] || new_e
[1]);
2312 /* Find the other edge by process of elimination. */
2313 if (not_found_bb_index
!= -1)
2315 gcc_assert (!new_e
[not_found_bb_index
]);
2316 int found_bb_index
= not_found_bb_index
== 1 ? 0 : 1;
2319 FOR_EACH_EDGE (e
, ei
, new_bb
->preds
)
2321 if (new_e
[found_bb_index
] == e
)
2323 new_e
[not_found_bb_index
] = e
;
2327 /* Add edges to phi args. */
2328 for (int i
= 0; i
< 2; i
++)
2329 add_phi_arg (new_phi
, new_phi_args
[i
], new_e
[i
],
2330 get_loc (old_phi_args
[i
]));
2336 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2337 region. If postpone is true and it isn't possible to copy any arg of PHI,
2338 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2339 Returns false if the copying was unsuccessful. */
2342 translate_isl_ast_to_gimple::copy_cond_phi_args (gphi
*phi
, gphi
*new_phi
,
2347 fprintf (dump_file
, "[codegen] copying cond phi args.\n");
2348 gcc_assert (2 == gimple_phi_num_args (phi
));
2350 basic_block new_bb
= gimple_bb (new_phi
);
2351 loop_p loop
= gimple_bb (phi
)->loop_father
;
2353 basic_block old_bb
= gimple_bb (phi
);
2354 edge old_bb_non_dominating_edge
= NULL
, old_bb_dominating_edge
= NULL
;
2358 FOR_EACH_EDGE (e
, ei
, old_bb
->preds
)
2359 if (!dominated_by_p (CDI_DOMINATORS
, old_bb
, e
->src
))
2360 old_bb_non_dominating_edge
= e
;
2362 old_bb_dominating_edge
= e
;
2364 gcc_assert (!dominated_by_p (CDI_DOMINATORS
, old_bb
,
2365 old_bb_non_dominating_edge
->src
));
2367 tree new_phi_args
[2];
2368 tree old_phi_args
[2];
2370 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2372 tree old_name
= gimple_phi_arg_def (phi
, i
);
2373 tree new_name
= get_new_name (new_bb
, old_name
, old_bb
, false);
2374 old_phi_args
[i
] = old_name
;
2377 new_phi_args
[i
] = new_name
;
2381 /* If the phi-arg was a parameter. */
2382 if (vec_find (region
->params
, old_name
) != -1)
2384 new_phi_args
[i
] = old_name
;
2388 "[codegen] parameter argument to phi, new_expr: ");
2389 print_generic_expr (dump_file
, new_phi_args
[i
], 0);
2390 fprintf (dump_file
, "\n");
2395 gimple
*old_def_stmt
= SSA_NAME_DEF_STMT (old_name
);
2396 if (!old_def_stmt
|| gimple_code (old_def_stmt
) == GIMPLE_NOP
)
2397 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2403 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2404 if (is_gimple_reg (old_name
)
2405 && scev_analyzable_p (old_name
, region
->region
))
2408 tree new_expr
= get_rename_from_scev (old_name
, &stmts
, loop
,
2409 new_bb
, old_bb
, iv_map
);
2410 if (codegen_error_p ())
2413 gcc_assert (new_expr
);
2417 "[codegen] scev analyzeable, new_expr: ");
2418 print_generic_expr (dump_file
, new_expr
, 0);
2419 fprintf (dump_file
, "\n");
2421 gsi_insert_earliest (stmts
);
2422 new_phi_args
[i
] = new_name
;
2426 /* Postpone code gen for later for back-edges. */
2427 region
->incomplete_phis
.safe_push (std::make_pair (phi
, new_phi
));
2431 fprintf (dump_file
, "[codegen] postpone cond phi nodes: ");
2432 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2435 new_phi_args
[i
] = NULL_TREE
;
2439 /* Either we should add the arg to phi or, we should postpone. */
2443 /* If none of the args have been determined in the first stage then wait until
2445 if (postpone
&& !new_phi_args
[0] && !new_phi_args
[1])
2448 return add_phi_arg_for_new_expr (old_phi_args
, new_phi_args
,
2449 old_bb_dominating_edge
,
2450 old_bb_non_dominating_edge
,
2451 phi
, new_phi
, new_bb
);
2454 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2455 containing phi nodes coming from two predecessors, and none of them are back
2459 translate_isl_ast_to_gimple::copy_cond_phi_nodes (basic_block bb
,
2464 gcc_assert (!bb_contains_loop_close_phi_nodes (bb
));
2467 fprintf (dump_file
, "[codegen] copying cond phi nodes in bb_%d.\n",
2470 /* Cond phi nodes should have exactly two arguments. */
2471 gcc_assert (2 == EDGE_COUNT (bb
->preds
));
2473 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2476 gphi
*phi
= psi
.phi ();
2477 tree res
= gimple_phi_result (phi
);
2478 if (virtual_operand_p (res
))
2480 if (is_gimple_reg (res
) && scev_analyzable_p (res
, region
->region
))
2481 /* Cond phi nodes should not be scev_analyzable_p. */
2484 gphi
*new_phi
= create_phi_node (SSA_NAME_VAR (res
), new_bb
);
2485 tree new_res
= create_new_def_for (res
, new_phi
,
2486 gimple_phi_result_ptr (new_phi
));
2487 set_rename (res
, new_res
);
2489 if (!copy_cond_phi_args (phi
, new_phi
, iv_map
, true))
2492 update_stmt (new_phi
);
2498 /* Return true if STMT should be copied from region to the new code-generated
2499 region. LABELs, CONDITIONS, induction-variables and region parameters need
2503 should_copy_to_new_region (gimple
*stmt
, sese_info_p region
)
2505 /* Do not copy labels or conditions. */
2506 if (gimple_code (stmt
) == GIMPLE_LABEL
2507 || gimple_code (stmt
) == GIMPLE_COND
)
2511 /* Do not copy induction variables. */
2512 if (is_gimple_assign (stmt
)
2513 && (lhs
= gimple_assign_lhs (stmt
))
2514 && TREE_CODE (lhs
) == SSA_NAME
2515 && is_gimple_reg (lhs
)
2516 && scev_analyzable_p (lhs
, region
->region
))
2522 /* Create new names for all the definitions created by COPY and add replacement
2523 mappings for each new name. */
2526 translate_isl_ast_to_gimple::set_rename_for_each_def (gimple
*stmt
)
2528 def_operand_p def_p
;
2529 ssa_op_iter op_iter
;
2530 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
2532 tree old_name
= DEF_FROM_PTR (def_p
);
2533 tree new_name
= create_new_def_for (old_name
, stmt
, def_p
);
2534 set_rename (old_name
, new_name
);
2538 /* Duplicates the statements of basic block BB into basic block NEW_BB
2539 and compute the new induction variables according to the IV_MAP.
2540 CODEGEN_ERROR is set when the code generation cannot continue. */
2543 translate_isl_ast_to_gimple::graphite_copy_stmts_from_block (basic_block bb
,
2547 /* Iterator poining to the place where new statement (s) will be inserted. */
2548 gimple_stmt_iterator gsi_tgt
= gsi_last_bb (new_bb
);
2550 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2553 gimple
*stmt
= gsi_stmt (gsi
);
2554 if (!should_copy_to_new_region (stmt
, region
))
2557 /* Create a new copy of STMT and duplicate STMT's virtual
2559 gimple
*copy
= gimple_copy (stmt
);
2560 gsi_insert_after (&gsi_tgt
, copy
, GSI_NEW_STMT
);
2564 fprintf (dump_file
, "[codegen] inserting statement: ");
2565 print_gimple_stmt (dump_file
, copy
, 0, 0);
2568 maybe_duplicate_eh_stmt (copy
, stmt
);
2569 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
2571 /* Crete new names for each def in the copied stmt. */
2572 set_rename_for_each_def (copy
);
2574 loop_p loop
= bb
->loop_father
;
2575 if (rename_uses (copy
, &gsi_tgt
, bb
, loop
, iv_map
))
2577 fold_stmt_inplace (&gsi_tgt
);
2578 gcc_assert (gsi_stmt (gsi_tgt
) == copy
);
2581 if (codegen_error_p ())
2591 /* Given a basic block containing close-phi it returns the new basic block where
2592 to insert a copy of the close-phi nodes. All the uses in close phis should
2593 come from a single loop otherwise it returns NULL. */
2596 translate_isl_ast_to_gimple::edge_for_new_close_phis (basic_block bb
)
2598 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2599 of close phi in the original code and then find the mapping of basic block
2600 defining that variable. If there are multiple close-phis and they are
2601 defined in different loops (in the original or in the new code) because of
2602 loop splitting, then we bail out. */
2603 loop_p new_loop
= NULL
;
2604 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);
2607 gphi
*phi
= psi
.phi ();
2608 tree name
= gimple_phi_arg_def (phi
, 0);
2609 basic_block old_loop_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
2611 vec
<basic_block
> *bbs
= region
->copied_bb_map
->get (old_loop_bb
);
2612 if (!bbs
|| bbs
->length () != 1)
2613 /* This is one of the places which shows preserving original structure
2614 is not always possible, as we may need to insert close PHI for a loop
2615 where the latch does not have any mapping, or the mapping is
2620 new_loop
= (*bbs
)[0]->loop_father
;
2621 else if (new_loop
!= (*bbs
)[0]->loop_father
)
2628 return single_exit (new_loop
);
2631 /* Copies BB and includes in the copied BB all the statements that can
2632 be reached following the use-def chains from the memory accesses,
2633 and returns the next edge following this new block. codegen_error is
2634 set when the code generation cannot continue. */
2637 translate_isl_ast_to_gimple::copy_bb_and_scalar_dependences (basic_block bb
,
2641 int num_phis
= number_of_phi_nodes (bb
);
2643 if (region
->copied_bb_map
->get (bb
))
2645 /* FIXME: we should be able to handle phi nodes with args coming from
2646 outside the region. */
2649 codegen_error
= true;
2654 basic_block new_bb
= split_edge (next_e
);
2655 if (num_phis
> 0 && bb_contains_loop_phi_nodes (bb
))
2657 basic_block phi_bb
= next_e
->dest
->loop_father
->header
;
2659 /* At this point we are unable to codegenerate by still preserving the SSA
2660 structure because maybe the loop is completely unrolled and the PHIs
2661 and cross-bb scalar dependencies are untrackable w.r.t. the original
2662 code. See gfortran.dg/graphite/pr29832.f90. */
2663 if (EDGE_COUNT (bb
->preds
) != EDGE_COUNT (phi_bb
->preds
))
2665 codegen_error
= true;
2670 fprintf (dump_file
, "[codegen] bb_%d contains loop phi nodes.\n",
2672 if (!copy_loop_phi_nodes (bb
, phi_bb
))
2674 codegen_error
= true;
2678 else if (bb_contains_loop_close_phi_nodes (bb
))
2681 fprintf (dump_file
, "[codegen] bb_%d contains close phi nodes.\n",
2684 edge e
= edge_for_new_close_phis (bb
);
2687 codegen_error
= true;
2691 basic_block phi_bb
= split_edge (e
);
2692 gcc_assert (single_pred_edge (phi_bb
)->src
->loop_father
2693 != single_pred_edge (phi_bb
)->dest
->loop_father
);
2695 if (!copy_loop_close_phi_nodes (bb
, phi_bb
))
2697 codegen_error
= true;
2701 else if (num_phis
> 0)
2704 fprintf (dump_file
, "[codegen] bb_%d contains cond phi nodes.\n",
2707 basic_block phi_bb
= single_pred (new_bb
);
2708 loop_p loop_father
= new_bb
->loop_father
;
2710 /* Move back until we find the block with two predecessors. */
2711 while (single_pred_p (phi_bb
))
2712 phi_bb
= single_pred_edge (phi_bb
)->src
;
2714 /* If a corresponding merge-point was not found, then abort codegen. */
2715 if (phi_bb
->loop_father
!= loop_father
2716 || !copy_cond_phi_nodes (bb
, phi_bb
, iv_map
))
2718 codegen_error
= true;
2724 fprintf (dump_file
, "[codegen] copying from bb_%d to bb_%d.\n",
2725 bb
->index
, new_bb
->index
);
2727 vec
<basic_block
> *copied_bbs
= region
->copied_bb_map
->get (bb
);
2729 copied_bbs
->safe_push (new_bb
);
2732 vec
<basic_block
> bbs
;
2734 bbs
.safe_push (new_bb
);
2735 region
->copied_bb_map
->put (bb
, bbs
);
2738 if (!graphite_copy_stmts_from_block (bb
, new_bb
, iv_map
))
2740 codegen_error
= true;
2744 return single_succ_edge (new_bb
);
2747 /* Patch the missing arguments of the phi nodes. */
2750 translate_isl_ast_to_gimple::translate_pending_phi_nodes ()
2754 FOR_EACH_VEC_ELT (region
->incomplete_phis
, i
, rename
)
2756 gphi
*old_phi
= rename
->first
;
2757 gphi
*new_phi
= rename
->second
;
2758 basic_block old_bb
= gimple_bb (old_phi
);
2759 basic_block new_bb
= gimple_bb (new_phi
);
2761 /* First edge is the init edge and second is the back edge. */
2762 init_back_edge_pair_t ibp_old_bb
= get_edges (old_bb
);
2763 init_back_edge_pair_t ibp_new_bb
= get_edges (new_bb
);
2767 fprintf (dump_file
, "[codegen] translating pending old-phi: ");
2768 print_gimple_stmt (dump_file
, old_phi
, 0, 0);
2771 auto_vec
<tree
, 1> iv_map
;
2772 if (bb_contains_loop_phi_nodes (new_bb
))
2773 codegen_error
= !copy_loop_phi_args (old_phi
, ibp_old_bb
, new_phi
,
2775 else if (bb_contains_loop_close_phi_nodes (new_bb
))
2776 codegen_error
= !copy_loop_close_phi_args (old_bb
, new_bb
, false);
2778 codegen_error
= !copy_cond_phi_args (old_phi
, new_phi
, iv_map
, false);
2782 fprintf (dump_file
, "[codegen] to new-phi: ");
2783 print_gimple_stmt (dump_file
, new_phi
, 0, 0);
2790 /* Prints NODE to FILE. */
2793 translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file
,
2794 __isl_keep isl_ast_node
*node
,
2795 __isl_keep isl_ctx
*ctx
) const
2797 isl_printer
*prn
= isl_printer_to_file (ctx
, file
);
2798 prn
= isl_printer_set_output_format (prn
, ISL_FORMAT_C
);
2799 prn
= isl_printer_print_ast_node (prn
, node
);
2800 prn
= isl_printer_print_str (prn
, "\n");
2801 isl_printer_free (prn
);
2804 /* Add ISL's parameter identifiers and corresponding trees to ivs_params. */
2807 translate_isl_ast_to_gimple::add_parameters_to_ivs_params (scop_p scop
,
2810 sese_info_p region
= scop
->scop_info
;
2811 unsigned nb_parameters
= isl_set_dim (scop
->param_context
, isl_dim_param
);
2812 gcc_assert (nb_parameters
== region
->params
.length ());
2814 for (i
= 0; i
< nb_parameters
; i
++)
2816 isl_id
*tmp_id
= isl_set_get_dim_id (scop
->param_context
,
2818 ip
[tmp_id
] = region
->params
[i
];
2823 /* Generates a build, which specifies the constraints on the parameters. */
2825 __isl_give isl_ast_build
*
2826 translate_isl_ast_to_gimple::generate_isl_context (scop_p scop
)
2828 isl_set
*context_isl
= isl_set_params (isl_set_copy (scop
->param_context
));
2829 return isl_ast_build_from_context (context_isl
);
2832 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2835 translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop
)
2839 int schedule_dims
= 0;
2841 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2843 int pbb_schedule_dims
= isl_map_dim (pbb
->transformed
, isl_dim_out
);
2844 if (pbb_schedule_dims
> schedule_dims
)
2845 schedule_dims
= pbb_schedule_dims
;
2848 return schedule_dims
;
2851 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2853 For schedules with different dimensionality, the isl AST generator can not
2854 define an order and will just randomly choose an order. The solution to this
2855 problem is to extend all schedules to the maximal number of schedule
2856 dimensions (using '0's for the remaining values). */
2858 __isl_give isl_map
*
2859 translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map
*schedule
,
2860 int nb_schedule_dims
)
2862 int tmp_dims
= isl_map_dim (schedule
, isl_dim_out
);
2864 isl_map_add_dims (schedule
, isl_dim_out
, nb_schedule_dims
- tmp_dims
);
2866 isl_val_int_from_si (isl_map_get_ctx (schedule
), 0);
2868 for (i
= tmp_dims
; i
< nb_schedule_dims
; i
++)
2871 = isl_map_fix_val (schedule
, isl_dim_out
, i
, isl_val_copy (zero
));
2873 isl_val_free (zero
);
2877 /* Generates a schedule, which specifies an order used to
2878 visit elements in a domain. */
2880 __isl_give isl_union_map
*
2881 translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop
)
2883 int nb_schedule_dims
= get_max_schedule_dimensions (scop
);
2886 isl_union_map
*schedule_isl
=
2887 isl_union_map_empty (isl_set_get_space (scop
->param_context
));
2889 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
2891 /* Dead code elimination: when the domain of a PBB is empty,
2892 don't generate code for the PBB. */
2893 if (isl_set_is_empty (pbb
->domain
))
2896 isl_map
*bb_schedule
= isl_map_copy (pbb
->transformed
);
2897 bb_schedule
= isl_map_intersect_domain (bb_schedule
,
2898 isl_set_copy (pbb
->domain
));
2899 bb_schedule
= extend_schedule (bb_schedule
, nb_schedule_dims
);
2901 = isl_union_map_union (schedule_isl
,
2902 isl_union_map_from_map (bb_schedule
));
2904 return schedule_isl
;
2907 /* This method is executed before the construction of a for node. */
2909 ast_build_before_for (__isl_keep isl_ast_build
*build
, void *user
)
2911 isl_union_map
*dependences
= (isl_union_map
*) user
;
2912 ast_build_info
*for_info
= XNEW (struct ast_build_info
);
2913 isl_union_map
*schedule
= isl_ast_build_get_schedule (build
);
2914 isl_space
*schedule_space
= isl_ast_build_get_schedule_space (build
);
2915 int dimension
= isl_space_dim (schedule_space
, isl_dim_out
);
2916 for_info
->is_parallelizable
=
2917 !carries_deps (schedule
, dependences
, dimension
);
2918 isl_union_map_free (schedule
);
2919 isl_space_free (schedule_space
);
2920 isl_id
*id
= isl_id_alloc (isl_ast_build_get_ctx (build
), "", for_info
);
2924 /* Set the separate option for all dimensions.
2925 This helps to reduce control overhead. */
2927 __isl_give isl_ast_build
*
2928 translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build
*control
,
2929 __isl_keep isl_union_map
*schedule
)
2931 isl_ctx
*ctx
= isl_union_map_get_ctx (schedule
);
2932 isl_space
*range_space
= isl_space_set_alloc (ctx
, 0, 1);
2934 isl_space_set_tuple_name (range_space
, isl_dim_set
, "separate");
2935 isl_union_set
*range
=
2936 isl_union_set_from_set (isl_set_universe (range_space
));
2937 isl_union_set
*domain
= isl_union_map_range (isl_union_map_copy (schedule
));
2938 domain
= isl_union_set_universe (domain
);
2939 isl_union_map
*options
= isl_union_map_from_domain_and_range (domain
, range
);
2940 return isl_ast_build_set_options (control
, options
);
2943 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
2945 __isl_give isl_ast_node
*
2946 translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop
, ivs_params
&ip
)
2948 /* Generate loop upper bounds that consist of the current loop iterator, an
2949 operator (< or <=) and an expression not involving the iterator. If this
2950 option is not set, then the current loop iterator may appear several times
2951 in the upper bound. See the isl manual for more details. */
2952 isl_options_set_ast_build_atomic_upper_bound (scop
->isl_context
, true);
2954 add_parameters_to_ivs_params (scop
, ip
);
2955 isl_union_map
*schedule_isl
= generate_isl_schedule (scop
);
2956 isl_ast_build
*context_isl
= generate_isl_context (scop
);
2957 context_isl
= set_options (context_isl
, schedule_isl
);
2958 isl_union_map
*dependences
= NULL
;
2959 if (flag_loop_parallelize_all
)
2961 dependences
= scop_get_dependences (scop
);
2963 isl_ast_build_set_before_each_for (context_isl
, ast_build_before_for
,
2966 isl_ast_node
*ast_isl
= isl_ast_build_ast_from_schedule (context_isl
,
2969 isl_union_map_free (dependences
);
2970 isl_ast_build_free (context_isl
);
2974 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
2975 the given SCOP. Return true if code generation succeeded.
2977 FIXME: This is not yet a full implementation of the code generator
2978 with ISL ASTs. Generation of GIMPLE code has to be completed. */
2981 graphite_regenerate_ast_isl (scop_p scop
)
2983 sese_info_p region
= scop
->scop_info
;
2984 translate_isl_ast_to_gimple
t (region
);
2986 ifsese if_region
= NULL
;
2987 isl_ast_node
*root_node
;
2990 timevar_push (TV_GRAPHITE_CODE_GEN
);
2991 root_node
= t
.scop_to_isl_ast (scop
, ip
);
2993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2995 fprintf (dump_file
, "ISL AST generated by ISL: \n");
2996 t
.print_isl_ast_node (dump_file
, root_node
, scop
->isl_context
);
2999 recompute_all_dominators ();
3002 if_region
= move_sese_in_condition (region
);
3003 region
->if_region
= if_region
;
3004 recompute_all_dominators ();
3006 loop_p context_loop
= region
->region
.entry
->src
->loop_father
;
3008 edge e
= single_succ_edge (if_region
->true_region
->region
.entry
->dest
);
3009 basic_block bb
= split_edge (e
);
3011 /* Update the true_region exit edge. */
3012 region
->if_region
->true_region
->region
.exit
= single_succ_edge (bb
);
3014 t
.translate_isl_ast (context_loop
, root_node
, e
, ip
);
3015 if (t
.codegen_error_p ())
3018 fprintf (dump_file
, "[codegen] unsuccessful,"
3019 " reverting back to the original code.\n");
3020 set_ifsese_condition (if_region
, integer_zero_node
);
3024 t
.translate_pending_phi_nodes ();
3025 if (!t
.codegen_error_p ())
3027 sese_insert_phis_for_liveouts (region
,
3028 if_region
->region
->region
.exit
->src
,
3029 if_region
->false_region
->region
.exit
,
3030 if_region
->true_region
->region
.exit
);
3031 mark_virtual_operands_for_renaming (cfun
);
3032 update_ssa (TODO_update_ssa
);
3037 recompute_all_dominators ();
3043 fprintf (dump_file
, "[codegen] unsuccessful in translating"
3044 " pending phis, reverting back to the original code.\n");
3045 set_ifsese_condition (if_region
, integer_zero_node
);
3049 free (if_region
->true_region
);
3050 free (if_region
->region
);
3053 ivs_params_clear (ip
);
3054 isl_ast_node_free (root_node
);
3055 timevar_pop (TV_GRAPHITE_CODE_GEN
);
3057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3060 int num_no_dependency
= 0;
3062 FOR_EACH_LOOP (loop
, 0)
3063 if (loop
->can_be_parallel
)
3064 num_no_dependency
++;
3066 fprintf (dump_file
, "%d loops carried no dependency.\n",
3070 return !t
.codegen_error_p ();
3073 #endif /* HAVE_isl */