1 /* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2016 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
4
5 This file is part of GCC.
6
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)
10 any later version.
11
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.
16
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/>. */
20
21 #define USES_ISL
22
23 #include "config.h"
24
25 #ifdef HAVE_isl
26
27 #define INCLUDE_MAP
28 #include "system.h"
29 #include "coretypes.h"
30 #include "backend.h"
31 #include "cfghooks.h"
32 #include "tree.h"
33 #include "gimple.h"
34 #include "params.h"
35 #include "fold-const.h"
36 #include "gimple-fold.h"
37 #include "gimple-iterator.h"
38 #include "gimplify.h"
39 #include "gimplify-me.h"
40 #include "tree-eh.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-ssa-operands.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-pass.h"
45 #include "cfgloop.h"
46 #include "tree-data-ref.h"
47 #include "tree-ssa-loop-manip.h"
48 #include "tree-scalar-evolution.h"
49 #include "gimple-ssa.h"
50 #include "tree-phinodes.h"
51 #include "tree-into-ssa.h"
52 #include "ssa-iterators.h"
53 #include "tree-cfg.h"
54 #include "gimple-pretty-print.h"
55 #include "cfganal.h"
56 #include "value-prof.h"
57 #include "graphite.h"
58
59 /* We always try to use signed 128 bit types, but fall back to smaller types
60 in case a platform does not provide types of these sizes. In the future we
61 should use isl to derive the optimal type for each subexpression. */
62
63 static int max_mode_int_precision =
64 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
65 static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
66 128 : max_mode_int_precision;
67
68 struct ast_build_info
69 {
ast_build_infoast_build_info70 ast_build_info()
71 : is_parallelizable(false)
72 { }
73 bool is_parallelizable;
74 };
75
76 /* Converts a GMP constant VAL to a tree and returns it. */
77
78 static tree
gmp_cst_to_tree(tree type,mpz_t val)79 gmp_cst_to_tree (tree type, mpz_t val)
80 {
81 tree t = type ? type : integer_type_node;
82 mpz_t tmp;
83
84 mpz_init (tmp);
85 mpz_set (tmp, val);
86 wide_int wi = wi::from_mpz (t, tmp, true);
87 mpz_clear (tmp);
88
89 return wide_int_to_tree (t, wi);
90 }
91
92 /* Verifies properties that GRAPHITE should maintain during translation. */
93
94 static inline void
graphite_verify(void)95 graphite_verify (void)
96 {
97 checking_verify_loop_structure ();
98 checking_verify_loop_closed_ssa (true);
99 }
100
101 /* IVS_PARAMS maps isl's scattering and parameter identifiers
102 to corresponding trees. */
103
104 typedef std::map<isl_id *, tree> ivs_params;
105
106 /* Free all memory allocated for isl's identifiers. */
107
ivs_params_clear(ivs_params & ip)108 static void ivs_params_clear (ivs_params &ip)
109 {
110 std::map<isl_id *, tree>::iterator it;
111 for (it = ip.begin ();
112 it != ip.end (); it++)
113 {
114 isl_id_free (it->first);
115 }
116 }
117
118 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
119
120 /* Set the "separate" option for the schedule node. */
121
122 static isl_schedule_node *
set_separate_option(__isl_take isl_schedule_node * node,void * user)123 set_separate_option (__isl_take isl_schedule_node *node, void *user)
124 {
125 if (user)
126 return node;
127
128 if (isl_schedule_node_get_type (node) != isl_schedule_node_band)
129 return node;
130
131 /* Set the "separate" option unless it is set earlier to another option. */
132 if (isl_schedule_node_band_member_get_ast_loop_type (node, 0)
133 == isl_ast_loop_default)
134 return isl_schedule_node_band_member_set_ast_loop_type
135 (node, 0, isl_ast_loop_separate);
136
137 return node;
138 }
139
140 /* Print SCHEDULE under an AST form on file F. */
141
142 void
print_schedule_ast(FILE * f,__isl_keep isl_schedule * schedule,scop_p scop)143 print_schedule_ast (FILE *f, __isl_keep isl_schedule *schedule, scop_p scop)
144 {
145 isl_set *set = isl_set_params (isl_set_copy (scop->param_context));
146 isl_ast_build *context = isl_ast_build_from_context (set);
147 isl_ast_node *ast
148 = isl_ast_build_node_from_schedule (context, isl_schedule_copy (schedule));
149 isl_ast_build_free (context);
150 print_isl_ast (f, ast);
151 isl_ast_node_free (ast);
152 }
153
154 DEBUG_FUNCTION void
debug_schedule_ast(__isl_keep isl_schedule * s,scop_p scop)155 debug_schedule_ast (__isl_keep isl_schedule *s, scop_p scop)
156 {
157 print_schedule_ast (stderr, s, scop);
158 }
159
160 #endif
161
162 enum phi_node_kind
163 {
164 unknown_phi,
165 loop_phi,
166 close_phi,
167 cond_phi
168 };
169
170 class translate_isl_ast_to_gimple
171 {
172 public:
translate_isl_ast_to_gimple(sese_info_p r)173 translate_isl_ast_to_gimple (sese_info_p r)
174 : region (r), codegen_error (false) { }
175 edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
176 edge next_e, ivs_params &ip);
177 edge translate_isl_ast_node_for (loop_p context_loop,
178 __isl_keep isl_ast_node *node,
179 edge next_e, ivs_params &ip);
180 edge translate_isl_ast_for_loop (loop_p context_loop,
181 __isl_keep isl_ast_node *node_for,
182 edge next_e,
183 tree type, tree lb, tree ub,
184 ivs_params &ip);
185 edge translate_isl_ast_node_if (loop_p context_loop,
186 __isl_keep isl_ast_node *node,
187 edge next_e, ivs_params &ip);
188 edge translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
189 edge next_e, ivs_params &ip);
190 edge translate_isl_ast_node_block (loop_p context_loop,
191 __isl_keep isl_ast_node *node,
192 edge next_e, ivs_params &ip);
193 tree unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
194 ivs_params &ip);
195 tree binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
196 ivs_params &ip);
197 tree ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
198 ivs_params &ip);
199 tree nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
200 ivs_params &ip);
201 tree gcc_expression_from_isl_expression (tree type,
202 __isl_take isl_ast_expr *,
203 ivs_params &ip);
204 tree gcc_expression_from_isl_ast_expr_id (tree type,
205 __isl_keep isl_ast_expr *expr_id,
206 ivs_params &ip);
207 tree gcc_expression_from_isl_expr_int (tree type,
208 __isl_take isl_ast_expr *expr);
209 tree gcc_expression_from_isl_expr_op (tree type,
210 __isl_take isl_ast_expr *expr,
211 ivs_params &ip);
212 struct loop *graphite_create_new_loop (edge entry_edge,
213 __isl_keep isl_ast_node *node_for,
214 loop_p outer, tree type,
215 tree lb, tree ub, ivs_params &ip);
216 edge graphite_create_new_loop_guard (edge entry_edge,
217 __isl_keep isl_ast_node *node_for,
218 tree *type,
219 tree *lb, tree *ub, ivs_params &ip);
220 edge graphite_create_new_guard (edge entry_edge,
221 __isl_take isl_ast_expr *if_cond,
222 ivs_params &ip);
223 void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
224 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
225 sese_l ®ion);
226 void translate_pending_phi_nodes (void);
227 void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip);
228 __isl_give isl_ast_build *generate_isl_context (scop_p scop);
229
230 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
231 __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
232 #else
233 int get_max_schedule_dimensions (scop_p scop);
234 __isl_give isl_map *extend_schedule (__isl_take isl_map *schedule,
235 int nb_schedule_dims);
236 __isl_give isl_union_map *generate_isl_schedule (scop_p scop);
237 __isl_give isl_ast_build *set_options (__isl_take isl_ast_build *control,
238 __isl_keep isl_union_map *schedule);
239 __isl_give isl_ast_node *scop_to_isl_ast (scop_p scop, ivs_params &ip);
240 #endif
241
242 bool is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb,
243 phi_node_kind, tree old_name, basic_block old_bb) const;
244 tree get_rename (basic_block new_bb, tree old_name,
245 basic_block old_bb, phi_node_kind) const;
246 tree get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
247 basic_block new_bb, basic_block old_bb,
248 vec<tree> iv_map);
249 basic_block get_def_bb_for_const (basic_block bb, basic_block old_bb) const;
250 tree get_new_name (basic_block new_bb, tree op,
251 basic_block old_bb, phi_node_kind) const;
252 void collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa);
253 bool copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb,
254 gphi *new_phi, init_back_edge_pair_t &ibp_new_bb,
255 bool postpone);
256 bool copy_loop_phi_nodes (basic_block bb, basic_block new_bb);
257 bool add_close_phis_to_merge_points (gphi *old_phi, gphi *new_phi,
258 tree default_value);
259 tree add_close_phis_to_outer_loops (tree last_merge_name, edge merge_e,
260 gimple *old_close_phi);
261 bool copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb,
262 bool postpone);
263 bool copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb);
264 bool copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map,
265 bool postpone);
266 bool copy_cond_phi_nodes (basic_block bb, basic_block new_bb,
267 vec<tree> iv_map);
268 bool graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
269 vec<tree> iv_map);
270 edge copy_bb_and_scalar_dependences (basic_block bb, edge next_e,
271 vec<tree> iv_map);
272 edge edge_for_new_close_phis (basic_block bb);
273 bool add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2],
274 edge old_bb_dominating_edge,
275 edge old_bb_non_dominating_edge,
276 gphi *phi, gphi *new_phi,
277 basic_block new_bb);
278 bool rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt,
279 basic_block old_bb, loop_p loop, vec<tree> iv_map);
280 void set_rename (tree old_name, tree expr);
281 void set_rename_for_each_def (gimple *stmt);
282 void gsi_insert_earliest (gimple_seq seq);
283 tree rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb);
codegen_error_p()284 bool codegen_error_p () const { return codegen_error; }
is_constant(tree op)285 bool is_constant (tree op) const
286 {
287 return TREE_CODE (op) == INTEGER_CST
288 || TREE_CODE (op) == REAL_CST
289 || TREE_CODE (op) == COMPLEX_CST
290 || TREE_CODE (op) == VECTOR_CST;
291 }
292
293 private:
294 /* The region to be translated. */
295 sese_info_p region;
296
297 /* This flag is set when an error occurred during the translation of isl AST
298 to Gimple. */
299 bool codegen_error;
300
301 /* A vector of all the edges at if_condition merge points. */
302 auto_vec<edge, 2> merge_points;
303 };
304
305 /* Return the tree variable that corresponds to the given isl ast identifier
306 expression (an isl_ast_expr of type isl_ast_expr_id).
307
308 FIXME: We should replace blind conversion of id's type with derivation
309 of the optimal type when we get the corresponding isl support. Blindly
310 converting type sizes may be problematic when we switch to smaller
311 types. */
312
313 tree translate_isl_ast_to_gimple::
gcc_expression_from_isl_ast_expr_id(tree type,__isl_take isl_ast_expr * expr_id,ivs_params & ip)314 gcc_expression_from_isl_ast_expr_id (tree type,
315 __isl_take isl_ast_expr *expr_id,
316 ivs_params &ip)
317 {
318 gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
319 isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
320 std::map<isl_id *, tree>::iterator res;
321 res = ip.find (tmp_isl_id);
322 isl_id_free (tmp_isl_id);
323 gcc_assert (res != ip.end () &&
324 "Could not map isl_id to tree expression");
325 isl_ast_expr_free (expr_id);
326 tree t = res->second;
327 tree *val = region->parameter_rename_map->get(t);
328
329 if (!val)
330 val = &t;
331 return fold_convert (type, *val);
332 }
333
334 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
335 type TYPE. */
336
337 tree translate_isl_ast_to_gimple::
gcc_expression_from_isl_expr_int(tree type,__isl_take isl_ast_expr * expr)338 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
339 {
340 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
341 isl_val *val = isl_ast_expr_get_val (expr);
342 mpz_t val_mpz_t;
343 mpz_init (val_mpz_t);
344 tree res;
345 if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
346 res = NULL_TREE;
347 else
348 res = gmp_cst_to_tree (type, val_mpz_t);
349 isl_val_free (val);
350 isl_ast_expr_free (expr);
351 mpz_clear (val_mpz_t);
352 return res;
353 }
354
355 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
356 type TYPE. */
357
358 tree translate_isl_ast_to_gimple::
binary_op_to_tree(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)359 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
360 {
361 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
362 tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
363 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
364 tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
365
366 enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
367 isl_ast_expr_free (expr);
368
369 if (codegen_error_p ())
370 return NULL_TREE;
371
372 switch (expr_type)
373 {
374 case isl_ast_op_add:
375 return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
376
377 case isl_ast_op_sub:
378 return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
379
380 case isl_ast_op_mul:
381 return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
382
383 case isl_ast_op_div:
384 /* As isl operates on arbitrary precision numbers, we may end up with
385 division by 2^64 that is folded to 0. */
386 if (integer_zerop (tree_rhs_expr))
387 {
388 codegen_error = true;
389 return NULL_TREE;
390 }
391 return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
392
393 case isl_ast_op_pdiv_q:
394 /* As isl operates on arbitrary precision numbers, we may end up with
395 division by 2^64 that is folded to 0. */
396 if (integer_zerop (tree_rhs_expr))
397 {
398 codegen_error = true;
399 return NULL_TREE;
400 }
401 return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
402
403 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
404 /* isl 0.15 or later. */
405 case isl_ast_op_zdiv_r:
406 #endif
407 case isl_ast_op_pdiv_r:
408 /* As isl operates on arbitrary precision numbers, we may end up with
409 division by 2^64 that is folded to 0. */
410 if (integer_zerop (tree_rhs_expr))
411 {
412 codegen_error = true;
413 return NULL_TREE;
414 }
415 return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
416
417 case isl_ast_op_fdiv_q:
418 /* As isl operates on arbitrary precision numbers, we may end up with
419 division by 2^64 that is folded to 0. */
420 if (integer_zerop (tree_rhs_expr))
421 {
422 codegen_error = true;
423 return NULL_TREE;
424 }
425 return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
426
427 case isl_ast_op_and:
428 return fold_build2 (TRUTH_ANDIF_EXPR, type,
429 tree_lhs_expr, tree_rhs_expr);
430
431 case isl_ast_op_or:
432 return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
433
434 case isl_ast_op_eq:
435 return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
436
437 case isl_ast_op_le:
438 return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
439
440 case isl_ast_op_lt:
441 return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
442
443 case isl_ast_op_ge:
444 return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
445
446 case isl_ast_op_gt:
447 return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
448
449 default:
450 gcc_unreachable ();
451 }
452 }
453
454 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
455 type TYPE. */
456
457 tree translate_isl_ast_to_gimple::
ternary_op_to_tree(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)458 ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
459 {
460 enum isl_ast_op_type t = isl_ast_expr_get_op_type (expr);
461 gcc_assert (t == isl_ast_op_cond || t == isl_ast_op_select);
462 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
463 tree a = gcc_expression_from_isl_expression (type, arg_expr, ip);
464 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
465 tree b = gcc_expression_from_isl_expression (type, arg_expr, ip);
466 arg_expr = isl_ast_expr_get_op_arg (expr, 2);
467 tree c = gcc_expression_from_isl_expression (type, arg_expr, ip);
468 isl_ast_expr_free (expr);
469
470 if (codegen_error_p ())
471 return NULL_TREE;
472
473 return fold_build3 (COND_EXPR, type, a, b, c);
474 }
475
476 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
477 type TYPE. */
478
479 tree translate_isl_ast_to_gimple::
unary_op_to_tree(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)480 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
481 {
482 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
483 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
484 tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
485 isl_ast_expr_free (expr);
486 return codegen_error_p () ? NULL_TREE
487 : fold_build1 (NEGATE_EXPR, type, tree_expr);
488 }
489
490 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
491 to a GCC expression tree of type TYPE. */
492
493 tree translate_isl_ast_to_gimple::
nary_op_to_tree(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)494 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
495 {
496 enum tree_code op_code;
497 switch (isl_ast_expr_get_op_type (expr))
498 {
499 case isl_ast_op_max:
500 op_code = MAX_EXPR;
501 break;
502
503 case isl_ast_op_min:
504 op_code = MIN_EXPR;
505 break;
506
507 default:
508 gcc_unreachable ();
509 }
510 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
511 tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
512
513 if (codegen_error_p ())
514 {
515 isl_ast_expr_free (expr);
516 return NULL_TREE;
517 }
518
519 int i;
520 for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
521 {
522 arg_expr = isl_ast_expr_get_op_arg (expr, i);
523 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
524
525 if (codegen_error_p ())
526 {
527 isl_ast_expr_free (expr);
528 return NULL_TREE;
529 }
530
531 res = fold_build2 (op_code, type, res, t);
532 }
533 isl_ast_expr_free (expr);
534 return res;
535 }
536
537 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
538 type TYPE. */
539
540 tree translate_isl_ast_to_gimple::
gcc_expression_from_isl_expr_op(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)541 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
542 ivs_params &ip)
543 {
544 if (codegen_error_p ())
545 {
546 isl_ast_expr_free (expr);
547 return NULL_TREE;
548 }
549
550 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
551 switch (isl_ast_expr_get_op_type (expr))
552 {
553 /* These isl ast expressions are not supported yet. */
554 case isl_ast_op_error:
555 case isl_ast_op_call:
556 case isl_ast_op_and_then:
557 case isl_ast_op_or_else:
558 gcc_unreachable ();
559
560 case isl_ast_op_max:
561 case isl_ast_op_min:
562 return nary_op_to_tree (type, expr, ip);
563
564 case isl_ast_op_add:
565 case isl_ast_op_sub:
566 case isl_ast_op_mul:
567 case isl_ast_op_div:
568 case isl_ast_op_pdiv_q:
569 case isl_ast_op_pdiv_r:
570 case isl_ast_op_fdiv_q:
571 #if HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
572 /* isl 0.15 or later. */
573 case isl_ast_op_zdiv_r:
574 #endif
575 case isl_ast_op_and:
576 case isl_ast_op_or:
577 case isl_ast_op_eq:
578 case isl_ast_op_le:
579 case isl_ast_op_lt:
580 case isl_ast_op_ge:
581 case isl_ast_op_gt:
582 return binary_op_to_tree (type, expr, ip);
583
584 case isl_ast_op_minus:
585 return unary_op_to_tree (type, expr, ip);
586
587 case isl_ast_op_cond:
588 case isl_ast_op_select:
589 return ternary_op_to_tree (type, expr, ip);
590
591 default:
592 gcc_unreachable ();
593 }
594
595 return NULL_TREE;
596 }
597
598 /* Converts an isl AST expression E back to a GCC expression tree of
599 type TYPE. */
600
601 tree translate_isl_ast_to_gimple::
gcc_expression_from_isl_expression(tree type,__isl_take isl_ast_expr * expr,ivs_params & ip)602 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
603 ivs_params &ip)
604 {
605 if (codegen_error_p ())
606 {
607 isl_ast_expr_free (expr);
608 return NULL_TREE;
609 }
610
611 switch (isl_ast_expr_get_type (expr))
612 {
613 case isl_ast_expr_id:
614 return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
615
616 case isl_ast_expr_int:
617 return gcc_expression_from_isl_expr_int (type, expr);
618
619 case isl_ast_expr_op:
620 return gcc_expression_from_isl_expr_op (type, expr, ip);
621
622 default:
623 gcc_unreachable ();
624 }
625
626 return NULL_TREE;
627 }
628
629 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
630 induction variable for the new LOOP. New LOOP is attached to CFG
631 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
632 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
633 isl's scattering name to the induction variable created for the
634 loop of STMT. The new induction variable is inserted in the NEWIVS
635 vector and is of type TYPE. */
636
637 struct loop *translate_isl_ast_to_gimple::
graphite_create_new_loop(edge entry_edge,__isl_keep isl_ast_node * node_for,loop_p outer,tree type,tree lb,tree ub,ivs_params & ip)638 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
639 loop_p outer, tree type, tree lb, tree ub,
640 ivs_params &ip)
641 {
642 isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
643 tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
644
645 /* To fail code generation, we generate wrong code until we discard it. */
646 if (codegen_error_p ())
647 stride = integer_zero_node;
648
649 tree ivvar = create_tmp_var (type, "graphite_IV");
650 tree iv, iv_after_increment;
651 loop_p loop = create_empty_loop_on_edge
652 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
653 outer ? outer : entry_edge->src->loop_father);
654
655 isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
656 isl_id *id = isl_ast_expr_get_id (for_iterator);
657 std::map<isl_id *, tree>::iterator res;
658 res = ip.find (id);
659 if (ip.count (id))
660 isl_id_free (res->first);
661 ip[id] = iv;
662 isl_ast_expr_free (for_iterator);
663 return loop;
664 }
665
666 /* Create the loop for a isl_ast_node_for.
667
668 - NEXT_E is the edge where new generated code should be attached. */
669
670 edge translate_isl_ast_to_gimple::
translate_isl_ast_for_loop(loop_p context_loop,__isl_keep isl_ast_node * node_for,edge next_e,tree type,tree lb,tree ub,ivs_params & ip)671 translate_isl_ast_for_loop (loop_p context_loop,
672 __isl_keep isl_ast_node *node_for, edge next_e,
673 tree type, tree lb, tree ub,
674 ivs_params &ip)
675 {
676 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
677 struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
678 type, lb, ub, ip);
679 edge last_e = single_exit (loop);
680 edge to_body = single_succ_edge (loop->header);
681 basic_block after = to_body->dest;
682
683 /* Translate the body of the loop. */
684 isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
685 next_e = translate_isl_ast (loop, for_body, to_body, ip);
686 isl_ast_node_free (for_body);
687
688 /* Early return if we failed to translate loop body. */
689 if (!next_e || codegen_error_p ())
690 return NULL;
691
692 if (next_e->dest != after)
693 redirect_edge_succ_nodup (next_e, after);
694 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
695
696 if (flag_loop_parallelize_all)
697 {
698 isl_id *id = isl_ast_node_get_annotation (node_for);
699 gcc_assert (id);
700 ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
701 loop->can_be_parallel = for_info->is_parallelizable;
702 free (for_info);
703 isl_id_free (id);
704 }
705
706 return last_e;
707 }
708
709 /* We use this function to get the upper bound because of the form,
710 which is used by isl to represent loops:
711
712 for (iterator = init; cond; iterator += inc)
713
714 {
715
716 ...
717
718 }
719
720 The loop condition is an arbitrary expression, which contains the
721 current loop iterator.
722
723 (e.g. iterator + 3 < B && C > iterator + A)
724
725 We have to know the upper bound of the iterator to generate a loop
726 in Gimple form. It can be obtained from the special representation
727 of the loop condition, which is generated by isl,
728 if the ast_build_atomic_upper_bound option is set. In this case,
729 isl generates a loop condition that consists of the current loop
730 iterator, + an operator (< or <=) and an expression not involving
731 the iterator, which is processed and returned by this function.
732
733 (e.g iterator <= upper-bound-expression-without-iterator) */
734
735 static __isl_give isl_ast_expr *
get_upper_bound(__isl_keep isl_ast_node * node_for)736 get_upper_bound (__isl_keep isl_ast_node *node_for)
737 {
738 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
739 isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
740 gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
741 isl_ast_expr *res;
742 switch (isl_ast_expr_get_op_type (for_cond))
743 {
744 case isl_ast_op_le:
745 res = isl_ast_expr_get_op_arg (for_cond, 1);
746 break;
747
748 case isl_ast_op_lt:
749 {
750 /* (iterator < ub) => (iterator <= ub - 1). */
751 isl_val *one =
752 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
753 isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
754 res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
755 break;
756 }
757
758 default:
759 gcc_unreachable ();
760 }
761 isl_ast_expr_free (for_cond);
762 return res;
763 }
764
765 /* All loops generated by create_empty_loop_on_edge have the form of
766 a post-test loop:
767
768 do
769
770 {
771 body of the loop;
772 } while (lower bound < upper bound);
773
774 We create a new if region protecting the loop to be executed, if
775 the execution count is zero (lower bound > upper bound). */
776
777 edge translate_isl_ast_to_gimple::
graphite_create_new_loop_guard(edge entry_edge,__isl_keep isl_ast_node * node_for,tree * type,tree * lb,tree * ub,ivs_params & ip)778 graphite_create_new_loop_guard (edge entry_edge,
779 __isl_keep isl_ast_node *node_for, tree *type,
780 tree *lb, tree *ub, ivs_params &ip)
781 {
782 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
783 tree cond_expr;
784 edge exit_edge;
785
786 *type =
787 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
788 isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
789 *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
790
791 /* To fail code generation, we generate wrong code until we discard it. */
792 if (codegen_error_p ())
793 *lb = integer_zero_node;
794
795 isl_ast_expr *upper_bound = get_upper_bound (node_for);
796 *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
797
798 /* To fail code generation, we generate wrong code until we discard it. */
799 if (codegen_error_p ())
800 *ub = integer_zero_node;
801
802 /* When ub is simply a constant or a parameter, use lb <= ub. */
803 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
804 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
805 else
806 {
807 tree one = (POINTER_TYPE_P (*type)
808 ? convert_to_ptrofftype (integer_one_node)
809 : fold_convert (*type, integer_one_node));
810 /* Adding +1 and using LT_EXPR helps with loop latches that have a
811 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
812 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
813 is true, even if we do not want this. However lb < ub + 1 is false,
814 as expected. */
815 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
816 : PLUS_EXPR, *type, *ub, one);
817
818 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
819 }
820
821 if (integer_onep (cond_expr))
822 exit_edge = entry_edge;
823 else
824 exit_edge = create_empty_if_region_on_edge (entry_edge,
825 unshare_expr (cond_expr));
826
827 return exit_edge;
828 }
829
830 /* Translates an isl_ast_node_for to Gimple. */
831
832 edge translate_isl_ast_to_gimple::
translate_isl_ast_node_for(loop_p context_loop,__isl_keep isl_ast_node * node,edge next_e,ivs_params & ip)833 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
834 edge next_e, ivs_params &ip)
835 {
836 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
837 tree type, lb, ub;
838 edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
839 &lb, &ub, ip);
840
841 if (last_e == next_e)
842 {
843 /* There was no guard generated. */
844 last_e = single_succ_edge (split_edge (last_e));
845
846 translate_isl_ast_for_loop (context_loop, node, next_e,
847 type, lb, ub, ip);
848 return last_e;
849 }
850
851 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
852 merge_points.safe_push (last_e);
853
854 last_e = single_succ_edge (split_edge (last_e));
855 translate_isl_ast_for_loop (context_loop, node, true_e, type, lb, ub, ip);
856
857 return last_e;
858 }
859
860 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
861 variables of the loops around GBB in SESE.
862
863 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
864 chrec, we could consider using a map<int, tree> that maps loop ids to the
865 corresponding tree expressions. */
866
867 void translate_isl_ast_to_gimple::
build_iv_mapping(vec<tree> iv_map,gimple_poly_bb_p gbb,__isl_keep isl_ast_expr * user_expr,ivs_params & ip,sese_l & region)868 build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
869 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
870 sese_l ®ion)
871 {
872 gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
873 isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
874 int i;
875 isl_ast_expr *arg_expr;
876 for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
877 {
878 arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
879 tree type =
880 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
881 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
882
883 /* To fail code generation, we generate wrong code until we discard it. */
884 if (codegen_error_p ())
885 t = integer_zero_node;
886
887 loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
888 iv_map[old_loop->num] = t;
889 }
890 }
891
892 /* Translates an isl_ast_node_user to Gimple.
893
894 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
895
896 edge translate_isl_ast_to_gimple::
translate_isl_ast_node_user(__isl_keep isl_ast_node * node,edge next_e,ivs_params & ip)897 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
898 edge next_e, ivs_params &ip)
899 {
900 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
901
902 isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
903 isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
904 gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
905
906 isl_id *name_id = isl_ast_expr_get_id (name_expr);
907 poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
908 gcc_assert (pbb);
909
910 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
911
912 isl_ast_expr_free (name_expr);
913 isl_id_free (name_id);
914
915 gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
916 "The entry block should not even appear within a scop");
917
918 const int nb_loops = number_of_loops (cfun);
919 vec<tree> iv_map;
920 iv_map.create (nb_loops);
921 iv_map.safe_grow_cleared (nb_loops);
922
923 build_iv_mapping (iv_map, gbb, user_expr, ip, pbb->scop->scop_info->region);
924 isl_ast_expr_free (user_expr);
925
926 basic_block old_bb = GBB_BB (gbb);
927 if (dump_file)
928 {
929 fprintf (dump_file,
930 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
931 old_bb->index, next_e->src->index, next_e->dest->index);
932 print_loops_bb (dump_file, GBB_BB (gbb), 0, 3);
933
934 }
935
936 next_e = copy_bb_and_scalar_dependences (old_bb, next_e, iv_map);
937
938 iv_map.release ();
939
940 if (codegen_error_p ())
941 return NULL;
942
943 if (dump_file)
944 {
945 fprintf (dump_file, "[codegen] (after copy) new basic block\n");
946 print_loops_bb (dump_file, next_e->src, 0, 3);
947 }
948
949 return next_e;
950 }
951
952 /* Translates an isl_ast_node_block to Gimple. */
953
954 edge translate_isl_ast_to_gimple::
translate_isl_ast_node_block(loop_p context_loop,__isl_keep isl_ast_node * node,edge next_e,ivs_params & ip)955 translate_isl_ast_node_block (loop_p context_loop,
956 __isl_keep isl_ast_node *node,
957 edge next_e, ivs_params &ip)
958 {
959 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
960 isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
961 int i;
962 for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
963 {
964 isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
965 next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
966 isl_ast_node_free (tmp_node);
967 }
968 isl_ast_node_list_free (node_list);
969 return next_e;
970 }
971
972 /* Creates a new if region corresponding to isl's cond. */
973
974 edge translate_isl_ast_to_gimple::
graphite_create_new_guard(edge entry_edge,__isl_take isl_ast_expr * if_cond,ivs_params & ip)975 graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
976 ivs_params &ip)
977 {
978 tree type =
979 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
980 tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
981
982 /* To fail code generation, we generate wrong code until we discard it. */
983 if (codegen_error_p ())
984 cond_expr = integer_zero_node;
985
986 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
987 return exit_edge;
988 }
989
990 /* Translates an isl_ast_node_if to Gimple. */
991
992 edge translate_isl_ast_to_gimple::
translate_isl_ast_node_if(loop_p context_loop,__isl_keep isl_ast_node * node,edge next_e,ivs_params & ip)993 translate_isl_ast_node_if (loop_p context_loop,
994 __isl_keep isl_ast_node *node,
995 edge next_e, ivs_params &ip)
996 {
997 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
998 isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
999 edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
1000 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1001 merge_points.safe_push (last_e);
1002
1003 isl_ast_node *then_node = isl_ast_node_if_get_then (node);
1004 translate_isl_ast (context_loop, then_node, true_e, ip);
1005 isl_ast_node_free (then_node);
1006
1007 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
1008 isl_ast_node *else_node = isl_ast_node_if_get_else (node);
1009 if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
1010 translate_isl_ast (context_loop, else_node, false_e, ip);
1011
1012 isl_ast_node_free (else_node);
1013 return last_e;
1014 }
1015
1016 /* Translates an isl AST node NODE to GCC representation in the
1017 context of a SESE. */
1018
1019 edge translate_isl_ast_to_gimple::
translate_isl_ast(loop_p context_loop,__isl_keep isl_ast_node * node,edge next_e,ivs_params & ip)1020 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
1021 edge next_e, ivs_params &ip)
1022 {
1023 if (codegen_error_p ())
1024 return NULL;
1025
1026 switch (isl_ast_node_get_type (node))
1027 {
1028 case isl_ast_node_error:
1029 gcc_unreachable ();
1030
1031 case isl_ast_node_for:
1032 return translate_isl_ast_node_for (context_loop, node,
1033 next_e, ip);
1034
1035 case isl_ast_node_if:
1036 return translate_isl_ast_node_if (context_loop, node,
1037 next_e, ip);
1038
1039 case isl_ast_node_user:
1040 return translate_isl_ast_node_user (node, next_e, ip);
1041
1042 case isl_ast_node_block:
1043 return translate_isl_ast_node_block (context_loop, node,
1044 next_e, ip);
1045
1046 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
1047 case isl_ast_node_mark:
1048 {
1049 isl_ast_node *n = isl_ast_node_mark_get_node (node);
1050 edge e = translate_isl_ast (context_loop, n, next_e, ip);
1051 isl_ast_node_free (n);
1052 return e;
1053 }
1054 #endif
1055
1056 default:
1057 gcc_unreachable ();
1058 }
1059 }
1060
1061 /* Return true when BB contains loop close phi nodes. A loop close phi node is
1062 at the exit of loop which takes one argument that is the last value of the
1063 variable being used out of the loop. */
1064
1065 static bool
bb_contains_loop_close_phi_nodes(basic_block bb)1066 bb_contains_loop_close_phi_nodes (basic_block bb)
1067 {
1068 return single_pred_p (bb)
1069 && bb->loop_father != single_pred_edge (bb)->src->loop_father;
1070 }
1071
1072 /* Return true when BB contains loop phi nodes. A loop phi node is the loop
1073 header containing phi nodes which has one init-edge and one back-edge. */
1074
1075 static bool
bb_contains_loop_phi_nodes(basic_block bb)1076 bb_contains_loop_phi_nodes (basic_block bb)
1077 {
1078 if (EDGE_COUNT (bb->preds) != 2)
1079 return false;
1080
1081 unsigned depth = loop_depth (bb->loop_father);
1082
1083 edge preds[2] = { (*bb->preds)[0], (*bb->preds)[1] };
1084
1085 if (depth > loop_depth (preds[0]->src->loop_father)
1086 || depth > loop_depth (preds[1]->src->loop_father))
1087 return true;
1088
1089 /* When one of the edges correspond to the same loop father and other
1090 doesn't. */
1091 if (bb->loop_father != preds[0]->src->loop_father
1092 && bb->loop_father == preds[1]->src->loop_father)
1093 return true;
1094
1095 if (bb->loop_father != preds[1]->src->loop_father
1096 && bb->loop_father == preds[0]->src->loop_father)
1097 return true;
1098
1099 return false;
1100 }
1101
1102 /* Check if USE is defined in a basic block from where the definition of USE can
1103 propagate from all the paths. FIXME: Verify checks for virtual operands. */
1104
1105 static bool
is_loop_closed_ssa_use(basic_block bb,tree use)1106 is_loop_closed_ssa_use (basic_block bb, tree use)
1107 {
1108 if (TREE_CODE (use) != SSA_NAME || virtual_operand_p (use))
1109 return true;
1110
1111 /* For close-phi nodes def always comes from a loop which has a back-edge. */
1112 if (bb_contains_loop_close_phi_nodes (bb))
1113 return true;
1114
1115 gimple *def = SSA_NAME_DEF_STMT (use);
1116 basic_block def_bb = gimple_bb (def);
1117 return (!def_bb
1118 || flow_bb_inside_loop_p (def_bb->loop_father, bb));
1119 }
1120
1121 /* Return the number of phi nodes in BB. */
1122
1123 static int
number_of_phi_nodes(basic_block bb)1124 number_of_phi_nodes (basic_block bb)
1125 {
1126 int num_phis = 0;
1127 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1128 gsi_next (&psi))
1129 num_phis++;
1130 return num_phis;
1131 }
1132
1133 /* Returns true if BB uses name in one of its PHIs. */
1134
1135 static bool
phi_uses_name(basic_block bb,tree name)1136 phi_uses_name (basic_block bb, tree name)
1137 {
1138 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1139 gsi_next (&psi))
1140 {
1141 gphi *phi = psi.phi ();
1142 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
1143 {
1144 tree use_arg = gimple_phi_arg_def (phi, i);
1145 if (use_arg == name)
1146 return true;
1147 }
1148 }
1149 return false;
1150 }
1151
1152 /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The
1153 definition should flow into use, and the use should respect the loop-closed
1154 SSA form. */
1155
1156 bool translate_isl_ast_to_gimple::
is_valid_rename(tree rename,basic_block def_bb,basic_block use_bb,phi_node_kind phi_kind,tree old_name,basic_block old_bb)1157 is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb,
1158 phi_node_kind phi_kind, tree old_name, basic_block old_bb) const
1159 {
1160 if (SSA_NAME_IS_DEFAULT_DEF (rename))
1161 return true;
1162
1163 /* The def of the rename must either dominate the uses or come from a
1164 back-edge. Also the def must respect the loop closed ssa form. */
1165 if (!is_loop_closed_ssa_use (use_bb, rename))
1166 {
1167 if (dump_file)
1168 {
1169 fprintf (dump_file, "[codegen] rename not in loop closed ssa: ");
1170 print_generic_expr (dump_file, rename, 0);
1171 fprintf (dump_file, "\n");
1172 }
1173 return false;
1174 }
1175
1176 if (dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
1177 return true;
1178
1179 if (bb_contains_loop_phi_nodes (use_bb) && phi_kind == loop_phi)
1180 {
1181 /* The loop-header dominates the loop-body. */
1182 if (!dominated_by_p (CDI_DOMINATORS, def_bb, use_bb))
1183 return false;
1184
1185 /* RENAME would be used in loop-phi. */
1186 gcc_assert (number_of_phi_nodes (use_bb));
1187
1188 /* For definitions coming from back edges, we should check that
1189 old_name is used in a loop PHI node.
1190 FIXME: Verify if this is true. */
1191 if (phi_uses_name (old_bb, old_name))
1192 return true;
1193 }
1194 return false;
1195 }
1196
1197 /* Returns the expression associated to OLD_NAME (which is used in OLD_BB), in
1198 NEW_BB from RENAME_MAP. PHI_KIND determines the kind of phi node. */
1199
1200 tree translate_isl_ast_to_gimple::
get_rename(basic_block new_bb,tree old_name,basic_block old_bb,phi_node_kind phi_kind)1201 get_rename (basic_block new_bb, tree old_name, basic_block old_bb,
1202 phi_node_kind phi_kind) const
1203 {
1204 gcc_assert (TREE_CODE (old_name) == SSA_NAME);
1205 vec <tree> *renames = region->rename_map->get (old_name);
1206
1207 if (!renames || renames->is_empty ())
1208 return NULL_TREE;
1209
1210 if (1 == renames->length ())
1211 {
1212 tree rename = (*renames)[0];
1213 if (TREE_CODE (rename) == SSA_NAME)
1214 {
1215 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (rename));
1216 if (is_valid_rename (rename, bb, new_bb, phi_kind, old_name, old_bb)
1217 && (phi_kind == close_phi
1218 || ! bb
1219 || flow_bb_inside_loop_p (bb->loop_father, new_bb)))
1220 return rename;
1221 return NULL_TREE;
1222 }
1223
1224 if (is_constant (rename))
1225 return rename;
1226
1227 return NULL_TREE;
1228 }
1229
1230 /* More than one renames corresponding to the old_name. Find the rename for
1231 which the definition flows into usage at new_bb. */
1232 int i;
1233 tree t1 = NULL_TREE, t2;
1234 basic_block t1_bb = NULL;
1235 FOR_EACH_VEC_ELT (*renames, i, t2)
1236 {
1237 basic_block t2_bb = gimple_bb (SSA_NAME_DEF_STMT (t2));
1238
1239 /* Defined in the same basic block as used. */
1240 if (t2_bb == new_bb)
1241 return t2;
1242
1243 /* NEW_BB and T2_BB are in two unrelated if-clauses. */
1244 if (!dominated_by_p (CDI_DOMINATORS, new_bb, t2_bb))
1245 continue;
1246
1247 if (!flow_bb_inside_loop_p (t2_bb->loop_father, new_bb))
1248 continue;
1249
1250 /* Compute the nearest dominator. */
1251 if (!t1 || dominated_by_p (CDI_DOMINATORS, t2_bb, t1_bb))
1252 {
1253 t1_bb = t2_bb;
1254 t1 = t2;
1255 }
1256 }
1257
1258 return t1;
1259 }
1260
1261 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
1262 When OLD_NAME and EXPR are the same we assert. */
1263
1264 void translate_isl_ast_to_gimple::
set_rename(tree old_name,tree expr)1265 set_rename (tree old_name, tree expr)
1266 {
1267 if (dump_file)
1268 {
1269 fprintf (dump_file, "[codegen] setting rename: old_name = ");
1270 print_generic_expr (dump_file, old_name, 0);
1271 fprintf (dump_file, ", new_name = ");
1272 print_generic_expr (dump_file, expr, 0);
1273 fprintf (dump_file, "\n");
1274 }
1275
1276 if (old_name == expr)
1277 return;
1278
1279 vec <tree> *renames = region->rename_map->get (old_name);
1280
1281 if (renames)
1282 renames->safe_push (expr);
1283 else
1284 {
1285 vec<tree> r;
1286 r.create (2);
1287 r.safe_push (expr);
1288 region->rename_map->put (old_name, r);
1289 }
1290
1291 tree t;
1292 int i;
1293 /* For a parameter of a scop we don't want to rename it. */
1294 FOR_EACH_VEC_ELT (region->params, i, t)
1295 if (old_name == t)
1296 region->parameter_rename_map->put(old_name, expr);
1297 }
1298
1299 /* Return an iterator to the instructions comes last in the execution order.
1300 Either GSI1 and GSI2 should belong to the same basic block or one of their
1301 respective basic blocks should dominate the other. */
1302
1303 gimple_stmt_iterator
later_of_the_two(gimple_stmt_iterator gsi1,gimple_stmt_iterator gsi2)1304 later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
1305 {
1306 basic_block bb1 = gsi_bb (gsi1);
1307 basic_block bb2 = gsi_bb (gsi2);
1308
1309 /* Find the iterator which is the latest. */
1310 if (bb1 == bb2)
1311 {
1312 /* For empty basic blocks gsis point to the end of the sequence. Since
1313 there is no operator== defined for gimple_stmt_iterator and for gsis
1314 not pointing to a valid statement gsi_next would assert. */
1315 gimple_stmt_iterator gsi = gsi1;
1316 do {
1317 if (gsi_stmt (gsi) == gsi_stmt (gsi2))
1318 return gsi2;
1319 gsi_next (&gsi);
1320 } while (!gsi_end_p (gsi));
1321
1322 return gsi1;
1323 }
1324
1325 /* Find the basic block closest to the basic block which defines stmt. */
1326 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
1327 return gsi1;
1328
1329 gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
1330 return gsi2;
1331 }
1332
1333 /* Insert each statement from SEQ at its earliest insertion p. */
1334
1335 void translate_isl_ast_to_gimple::
gsi_insert_earliest(gimple_seq seq)1336 gsi_insert_earliest (gimple_seq seq)
1337 {
1338 update_modified_stmts (seq);
1339 sese_l &codegen_region = region->if_region->true_region->region;
1340 basic_block begin_bb = get_entry_bb (codegen_region);
1341
1342 /* Inserting the gimple statements in a vector because gimple_seq behave
1343 in strage ways when inserting the stmts from it into different basic
1344 blocks one at a time. */
1345 auto_vec<gimple *, 3> stmts;
1346 for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
1347 gsi_next (&gsi))
1348 stmts.safe_push (gsi_stmt (gsi));
1349
1350 int i;
1351 gimple *use_stmt;
1352 FOR_EACH_VEC_ELT (stmts, i, use_stmt)
1353 {
1354 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
1355 gimple_stmt_iterator gsi_def_stmt = gsi_start_bb_nondebug (begin_bb);
1356
1357 use_operand_p use_p;
1358 ssa_op_iter op_iter;
1359 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
1360 {
1361 /* Iterator to the current def of use_p. For function parameters or
1362 anything where def is not found, insert at the beginning of the
1363 generated region. */
1364 gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
1365
1366 tree op = USE_FROM_PTR (use_p);
1367 gimple *stmt = SSA_NAME_DEF_STMT (op);
1368 if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
1369 gsi_stmt = gsi_for_stmt (stmt);
1370
1371 /* For region parameters, insert at the beginning of the generated
1372 region. */
1373 if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
1374 gsi_stmt = gsi_def_stmt;
1375
1376 gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
1377 }
1378
1379 if (!gsi_stmt (gsi_def_stmt))
1380 {
1381 gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
1382 gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
1383 }
1384 else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
1385 {
1386 gimple_stmt_iterator bsi
1387 = gsi_start_bb_nondebug (gsi_bb (gsi_def_stmt));
1388 /* Insert right after the PHI statements. */
1389 gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
1390 }
1391 else
1392 gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
1393
1394 if (dump_file)
1395 {
1396 fprintf (dump_file, "[codegen] inserting statement: ");
1397 print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
1398 print_loops_bb (dump_file, gimple_bb (use_stmt), 0, 3);
1399 }
1400 }
1401 }
1402
1403 /* Collect all the operands of NEW_EXPR by recursively visiting each
1404 operand. */
1405
1406 void translate_isl_ast_to_gimple::
collect_all_ssa_names(tree new_expr,vec<tree> * vec_ssa)1407 collect_all_ssa_names (tree new_expr, vec<tree> *vec_ssa)
1408 {
1409 if (new_expr == NULL_TREE)
1410 return;
1411
1412 /* Rename all uses in new_expr. */
1413 if (TREE_CODE (new_expr) == SSA_NAME)
1414 {
1415 vec_ssa->safe_push (new_expr);
1416 return;
1417 }
1418
1419 /* Iterate over SSA_NAMES in NEW_EXPR. */
1420 for (int i = 0; i < (TREE_CODE_LENGTH (TREE_CODE (new_expr))); i++)
1421 {
1422 tree op = TREE_OPERAND (new_expr, i);
1423 collect_all_ssa_names (op, vec_ssa);
1424 }
1425 }
1426
1427 /* This is abridged version of the function copied from:
1428 tree.c:substitute_in_expr (tree exp, tree f, tree r). */
1429
1430 static tree
substitute_ssa_name(tree exp,tree f,tree r)1431 substitute_ssa_name (tree exp, tree f, tree r)
1432 {
1433 enum tree_code code = TREE_CODE (exp);
1434 tree op0, op1, op2, op3;
1435 tree new_tree;
1436
1437 /* We handle TREE_LIST and COMPONENT_REF separately. */
1438 if (code == TREE_LIST)
1439 {
1440 op0 = substitute_ssa_name (TREE_CHAIN (exp), f, r);
1441 op1 = substitute_ssa_name (TREE_VALUE (exp), f, r);
1442 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1443 return exp;
1444
1445 return tree_cons (TREE_PURPOSE (exp), op1, op0);
1446 }
1447 else if (code == COMPONENT_REF)
1448 {
1449 tree inner;
1450
1451 /* If this expression is getting a value from a PLACEHOLDER_EXPR
1452 and it is the right field, replace it with R. */
1453 for (inner = TREE_OPERAND (exp, 0);
1454 REFERENCE_CLASS_P (inner);
1455 inner = TREE_OPERAND (inner, 0))
1456 ;
1457
1458 /* The field. */
1459 op1 = TREE_OPERAND (exp, 1);
1460
1461 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f)
1462 return r;
1463
1464 /* If this expression hasn't been completed let, leave it alone. */
1465 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner))
1466 return exp;
1467
1468 op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
1469 if (op0 == TREE_OPERAND (exp, 0))
1470 return exp;
1471
1472 new_tree
1473 = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE);
1474 }
1475 else
1476 switch (TREE_CODE_CLASS (code))
1477 {
1478 case tcc_constant:
1479 return exp;
1480
1481 case tcc_declaration:
1482 if (exp == f)
1483 return r;
1484 else
1485 return exp;
1486
1487 case tcc_expression:
1488 if (exp == f)
1489 return r;
1490
1491 /* Fall through... */
1492
1493 case tcc_exceptional:
1494 case tcc_unary:
1495 case tcc_binary:
1496 case tcc_comparison:
1497 case tcc_reference:
1498 switch (TREE_CODE_LENGTH (code))
1499 {
1500 case 0:
1501 if (exp == f)
1502 return r;
1503 return exp;
1504
1505 case 1:
1506 op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
1507 if (op0 == TREE_OPERAND (exp, 0))
1508 return exp;
1509
1510 new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
1511 break;
1512
1513 case 2:
1514 op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
1515 op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
1516
1517 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1518 return exp;
1519
1520 new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
1521 break;
1522
1523 case 3:
1524 op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
1525 op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
1526 op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
1527
1528 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1529 && op2 == TREE_OPERAND (exp, 2))
1530 return exp;
1531
1532 new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
1533 break;
1534
1535 case 4:
1536 op0 = substitute_ssa_name (TREE_OPERAND (exp, 0), f, r);
1537 op1 = substitute_ssa_name (TREE_OPERAND (exp, 1), f, r);
1538 op2 = substitute_ssa_name (TREE_OPERAND (exp, 2), f, r);
1539 op3 = substitute_ssa_name (TREE_OPERAND (exp, 3), f, r);
1540
1541 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1542 && op2 == TREE_OPERAND (exp, 2)
1543 && op3 == TREE_OPERAND (exp, 3))
1544 return exp;
1545
1546 new_tree
1547 = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
1548 break;
1549
1550 default:
1551 gcc_unreachable ();
1552 }
1553 break;
1554
1555 case tcc_vl_exp:
1556 default:
1557 gcc_unreachable ();
1558 }
1559
1560 TREE_READONLY (new_tree) |= TREE_READONLY (exp);
1561
1562 if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF)
1563 TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp);
1564
1565 return new_tree;
1566 }
1567
1568 /* Rename all the operands of NEW_EXPR by recursively visiting each operand. */
1569
1570 tree translate_isl_ast_to_gimple::
rename_all_uses(tree new_expr,basic_block new_bb,basic_block old_bb)1571 rename_all_uses (tree new_expr, basic_block new_bb, basic_block old_bb)
1572 {
1573 auto_vec<tree, 2> ssa_names;
1574 collect_all_ssa_names (new_expr, &ssa_names);
1575 tree t;
1576 int i;
1577 FOR_EACH_VEC_ELT (ssa_names, i, t)
1578 if (tree r = get_rename (new_bb, t, old_bb, unknown_phi))
1579 new_expr = substitute_ssa_name (new_expr, t, r);
1580
1581 return new_expr;
1582 }
1583
1584 /* For ops which are scev_analyzeable, we can regenerate a new name from its
1585 scalar evolution around LOOP. */
1586
1587 tree translate_isl_ast_to_gimple::
get_rename_from_scev(tree old_name,gimple_seq * stmts,loop_p loop,basic_block new_bb,basic_block old_bb,vec<tree> iv_map)1588 get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
1589 basic_block new_bb, basic_block old_bb,
1590 vec<tree> iv_map)
1591 {
1592 tree scev = scalar_evolution_in_region (region->region, loop, old_name);
1593
1594 /* At this point we should know the exact scev for each
1595 scalar SSA_NAME used in the scop: all the other scalar
1596 SSA_NAMEs should have been translated out of SSA using
1597 arrays with one element. */
1598 tree new_expr;
1599 if (chrec_contains_undetermined (scev))
1600 {
1601 codegen_error = true;
1602 return build_zero_cst (TREE_TYPE (old_name));
1603 }
1604
1605 new_expr = chrec_apply_map (scev, iv_map);
1606
1607 /* The apply should produce an expression tree containing
1608 the uses of the new induction variables. We should be
1609 able to use new_expr instead of the old_name in the newly
1610 generated loop nest. */
1611 if (chrec_contains_undetermined (new_expr)
1612 || tree_contains_chrecs (new_expr, NULL))
1613 {
1614 codegen_error = true;
1615 return build_zero_cst (TREE_TYPE (old_name));
1616 }
1617
1618 if (TREE_CODE (new_expr) == SSA_NAME)
1619 {
1620 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_expr));
1621 if (bb && !dominated_by_p (CDI_DOMINATORS, new_bb, bb))
1622 {
1623 codegen_error = true;
1624 return build_zero_cst (TREE_TYPE (old_name));
1625 }
1626 }
1627
1628 new_expr = rename_all_uses (new_expr, new_bb, old_bb);
1629
1630 /* We check all the operands and all of them should dominate the use at
1631 new_expr. */
1632 auto_vec <tree, 2> new_ssa_names;
1633 collect_all_ssa_names (new_expr, &new_ssa_names);
1634 int i;
1635 tree new_ssa_name;
1636 FOR_EACH_VEC_ELT (new_ssa_names, i, new_ssa_name)
1637 {
1638 if (TREE_CODE (new_ssa_name) == SSA_NAME)
1639 {
1640 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (new_ssa_name));
1641 if (bb && !dominated_by_p (CDI_DOMINATORS, new_bb, bb))
1642 {
1643 codegen_error = true;
1644 return build_zero_cst (TREE_TYPE (old_name));
1645 }
1646 }
1647 }
1648
1649 /* Replace the old_name with the new_expr. */
1650 return force_gimple_operand (unshare_expr (new_expr), stmts,
1651 true, NULL_TREE);
1652 }
1653
1654 /* Renames the scalar uses of the statement COPY, using the
1655 substitution map RENAME_MAP, inserting the gimplification code at
1656 GSI_TGT, for the translation REGION, with the original copied
1657 statement in LOOP, and using the induction variable renaming map
1658 IV_MAP. Returns true when something has been renamed. */
1659
1660 bool translate_isl_ast_to_gimple::
rename_uses(gimple * copy,gimple_stmt_iterator * gsi_tgt,basic_block old_bb,loop_p loop,vec<tree> iv_map)1661 rename_uses (gimple *copy, gimple_stmt_iterator *gsi_tgt, basic_block old_bb,
1662 loop_p loop, vec<tree> iv_map)
1663 {
1664 bool changed = false;
1665
1666 if (is_gimple_debug (copy))
1667 {
1668 if (gimple_debug_bind_p (copy))
1669 gimple_debug_bind_reset_value (copy);
1670 else if (gimple_debug_source_bind_p (copy))
1671 return false;
1672 else
1673 gcc_unreachable ();
1674
1675 return false;
1676 }
1677
1678 if (dump_file)
1679 {
1680 fprintf (dump_file, "[codegen] renaming uses of stmt: ");
1681 print_gimple_stmt (dump_file, copy, 0, 0);
1682 }
1683
1684 use_operand_p use_p;
1685 ssa_op_iter op_iter;
1686 FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE)
1687 {
1688 tree old_name = USE_FROM_PTR (use_p);
1689
1690 if (dump_file)
1691 {
1692 fprintf (dump_file, "[codegen] renaming old_name = ");
1693 print_generic_expr (dump_file, old_name, 0);
1694 fprintf (dump_file, "\n");
1695 }
1696
1697 if (TREE_CODE (old_name) != SSA_NAME
1698 || SSA_NAME_IS_DEFAULT_DEF (old_name))
1699 continue;
1700
1701 changed = true;
1702 tree new_expr = get_rename (gsi_tgt->bb, old_name,
1703 old_bb, unknown_phi);
1704
1705 if (new_expr)
1706 {
1707 tree type_old_name = TREE_TYPE (old_name);
1708 tree type_new_expr = TREE_TYPE (new_expr);
1709
1710 if (dump_file)
1711 {
1712 fprintf (dump_file, "[codegen] from rename_map: new_name = ");
1713 print_generic_expr (dump_file, new_expr, 0);
1714 fprintf (dump_file, "\n");
1715 }
1716
1717 if (type_old_name != type_new_expr
1718 || TREE_CODE (new_expr) != SSA_NAME)
1719 {
1720 tree var = create_tmp_var (type_old_name, "var");
1721
1722 if (!useless_type_conversion_p (type_old_name, type_new_expr))
1723 new_expr = fold_convert (type_old_name, new_expr);
1724
1725 gimple_seq stmts;
1726 new_expr = force_gimple_operand (new_expr, &stmts, true, var);
1727 gsi_insert_earliest (stmts);
1728 }
1729
1730 replace_exp (use_p, new_expr);
1731 continue;
1732 }
1733
1734 gimple_seq stmts;
1735 new_expr = get_rename_from_scev (old_name, &stmts, loop, gimple_bb (copy),
1736 old_bb, iv_map);
1737 if (!new_expr || codegen_error_p ())
1738 return false;
1739
1740 if (dump_file)
1741 {
1742 fprintf (dump_file, "[codegen] not in rename map, scev: ");
1743 print_generic_expr (dump_file, new_expr, 0);
1744 fprintf (dump_file, "\n");
1745 }
1746
1747 gsi_insert_earliest (stmts);
1748 replace_exp (use_p, new_expr);
1749
1750 if (TREE_CODE (new_expr) == INTEGER_CST
1751 && is_gimple_assign (copy))
1752 {
1753 tree rhs = gimple_assign_rhs1 (copy);
1754
1755 if (TREE_CODE (rhs) == ADDR_EXPR)
1756 recompute_tree_invariant_for_addr_expr (rhs);
1757 }
1758
1759 set_rename (old_name, new_expr);
1760 }
1761
1762 return changed;
1763 }
1764
1765 /* Returns a basic block that could correspond to where a constant was defined
1766 in the original code. In the original code OLD_BB had the definition, we
1767 need to find which basic block out of the copies of old_bb, in the new
1768 region, should a definition correspond to if it has to reach BB. */
1769
1770 basic_block translate_isl_ast_to_gimple::
get_def_bb_for_const(basic_block bb,basic_block old_bb)1771 get_def_bb_for_const (basic_block bb, basic_block old_bb) const
1772 {
1773 vec <basic_block> *bbs = region->copied_bb_map->get (old_bb);
1774
1775 if (!bbs || bbs->is_empty ())
1776 return NULL;
1777
1778 if (1 == bbs->length ())
1779 return (*bbs)[0];
1780
1781 int i;
1782 basic_block b1 = NULL, b2;
1783 FOR_EACH_VEC_ELT (*bbs, i, b2)
1784 {
1785 if (b2 == bb)
1786 return bb;
1787
1788 /* BB and B2 are in two unrelated if-clauses. */
1789 if (!dominated_by_p (CDI_DOMINATORS, bb, b2))
1790 continue;
1791
1792 /* Compute the nearest dominator. */
1793 if (!b1 || dominated_by_p (CDI_DOMINATORS, b2, b1))
1794 b1 = b2;
1795 }
1796
1797 return b1;
1798 }
1799
1800 /* Get the new name of OP (from OLD_BB) to be used in NEW_BB. PHI_KIND
1801 determines the kind of phi node. */
1802
1803 tree translate_isl_ast_to_gimple::
get_new_name(basic_block new_bb,tree op,basic_block old_bb,phi_node_kind phi_kind)1804 get_new_name (basic_block new_bb, tree op,
1805 basic_block old_bb, phi_node_kind phi_kind) const
1806 {
1807 /* For constants the names are the same. */
1808 if (TREE_CODE (op) != SSA_NAME)
1809 return op;
1810
1811 return get_rename (new_bb, op, old_bb, phi_kind);
1812 }
1813
1814 /* Return a debug location for OP. */
1815
1816 static location_t
get_loc(tree op)1817 get_loc (tree op)
1818 {
1819 location_t loc = UNKNOWN_LOCATION;
1820
1821 if (TREE_CODE (op) == SSA_NAME)
1822 loc = gimple_location (SSA_NAME_DEF_STMT (op));
1823 return loc;
1824 }
1825
1826 /* Returns the incoming edges of basic_block BB in the pair. The first edge is
1827 the init edge (from outside the loop) and the second one is the back edge
1828 from the same loop. */
1829
1830 std::pair<edge, edge>
get_edges(basic_block bb)1831 get_edges (basic_block bb)
1832 {
1833 std::pair<edge, edge> edges;
1834 edge e;
1835 edge_iterator ei;
1836 FOR_EACH_EDGE (e, ei, bb->preds)
1837 if (bb->loop_father != e->src->loop_father)
1838 edges.first = e;
1839 else
1840 edges.second = e;
1841 return edges;
1842 }
1843
1844 /* Copy the PHI arguments from OLD_PHI to the NEW_PHI. The arguments to NEW_PHI
1845 must be found unless they can be POSTPONEd for later. */
1846
1847 bool translate_isl_ast_to_gimple::
copy_loop_phi_args(gphi * old_phi,init_back_edge_pair_t & ibp_old_bb,gphi * new_phi,init_back_edge_pair_t & ibp_new_bb,bool postpone)1848 copy_loop_phi_args (gphi *old_phi, init_back_edge_pair_t &ibp_old_bb,
1849 gphi *new_phi, init_back_edge_pair_t &ibp_new_bb,
1850 bool postpone)
1851 {
1852 gcc_assert (gimple_phi_num_args (old_phi) == gimple_phi_num_args (new_phi));
1853
1854 basic_block new_bb = gimple_bb (new_phi);
1855 for (unsigned i = 0; i < gimple_phi_num_args (old_phi); i++)
1856 {
1857 edge e;
1858 if (gimple_phi_arg_edge (old_phi, i) == ibp_old_bb.first)
1859 e = ibp_new_bb.first;
1860 else
1861 e = ibp_new_bb.second;
1862
1863 tree old_name = gimple_phi_arg_def (old_phi, i);
1864 tree new_name = get_new_name (new_bb, old_name,
1865 gimple_bb (old_phi), loop_phi);
1866 if (new_name)
1867 {
1868 add_phi_arg (new_phi, new_name, e, get_loc (old_name));
1869 continue;
1870 }
1871
1872 gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
1873 if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
1874 /* If the phi arg was a function arg, or wasn't defined, just use the
1875 old name. */
1876 add_phi_arg (new_phi, old_name, e, get_loc (old_name));
1877 else if (postpone)
1878 {
1879 /* Postpone code gen for later for those back-edges we don't have the
1880 names yet. */
1881 region->incomplete_phis.safe_push (std::make_pair (old_phi, new_phi));
1882 if (dump_file)
1883 fprintf (dump_file, "[codegen] postpone loop phi nodes.\n");
1884 }
1885 else
1886 /* Either we should add the arg to phi or, we should postpone. */
1887 return false;
1888 }
1889 return true;
1890 }
1891
1892 /* Copy loop phi nodes from BB to NEW_BB. */
1893
1894 bool translate_isl_ast_to_gimple::
copy_loop_phi_nodes(basic_block bb,basic_block new_bb)1895 copy_loop_phi_nodes (basic_block bb, basic_block new_bb)
1896 {
1897 if (dump_file)
1898 fprintf (dump_file, "[codegen] copying loop phi nodes in bb_%d.\n",
1899 new_bb->index);
1900
1901 /* Loop phi nodes should have only two arguments. */
1902 gcc_assert (2 == EDGE_COUNT (bb->preds));
1903
1904 /* First edge is the init edge and second is the back edge. */
1905 init_back_edge_pair_t ibp_old_bb = get_edges (bb);
1906
1907 /* First edge is the init edge and second is the back edge. */
1908 init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
1909
1910 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1911 gsi_next (&psi))
1912 {
1913 gphi *phi = psi.phi ();
1914 tree res = gimple_phi_result (phi);
1915 if (virtual_operand_p (res))
1916 continue;
1917 if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
1918 continue;
1919
1920 gphi *new_phi = create_phi_node (NULL_TREE, new_bb);
1921 tree new_res = create_new_def_for (res, new_phi,
1922 gimple_phi_result_ptr (new_phi));
1923 set_rename (res, new_res);
1924 codegen_error = !copy_loop_phi_args (phi, ibp_old_bb, new_phi,
1925 ibp_new_bb, true);
1926 update_stmt (new_phi);
1927
1928 if (dump_file)
1929 {
1930 fprintf (dump_file, "[codegen] creating loop-phi node: ");
1931 print_gimple_stmt (dump_file, new_phi, 0, 0);
1932 }
1933 }
1934
1935 return true;
1936 }
1937
1938 /* Return the init value of PHI, the value coming from outside the loop. */
1939
1940 static tree
get_loop_init_value(gphi * phi)1941 get_loop_init_value (gphi *phi)
1942 {
1943
1944 loop_p loop = gimple_bb (phi)->loop_father;
1945
1946 edge e;
1947 edge_iterator ei;
1948 FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
1949 if (e->src->loop_father != loop)
1950 return gimple_phi_arg_def (phi, e->dest_idx);
1951
1952 return NULL_TREE;
1953 }
1954
1955 /* Find the init value (the value which comes from outside the loop), of one of
1956 the operands of DEF which is defined by a loop phi. */
1957
1958 static tree
find_init_value(gimple * def)1959 find_init_value (gimple *def)
1960 {
1961 if (gimple_code (def) == GIMPLE_PHI)
1962 return get_loop_init_value (as_a <gphi*> (def));
1963
1964 if (gimple_vuse (def))
1965 return NULL_TREE;
1966
1967 ssa_op_iter iter;
1968 use_operand_p use_p;
1969 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
1970 {
1971 tree use = USE_FROM_PTR (use_p);
1972 if (TREE_CODE (use) == SSA_NAME)
1973 {
1974 if (tree res = find_init_value (SSA_NAME_DEF_STMT (use)))
1975 return res;
1976 }
1977 }
1978
1979 return NULL_TREE;
1980 }
1981
1982 /* Return the init value, the value coming from outside the loop. */
1983
1984 static tree
find_init_value_close_phi(gphi * phi)1985 find_init_value_close_phi (gphi *phi)
1986 {
1987 gcc_assert (gimple_phi_num_args (phi) == 1);
1988 tree use_arg = gimple_phi_arg_def (phi, 0);
1989 gimple *def = SSA_NAME_DEF_STMT (use_arg);
1990 return find_init_value (def);
1991 }
1992
1993
1994 tree translate_isl_ast_to_gimple::
add_close_phis_to_outer_loops(tree last_merge_name,edge last_e,gimple * old_close_phi)1995 add_close_phis_to_outer_loops (tree last_merge_name, edge last_e,
1996 gimple *old_close_phi)
1997 {
1998 sese_l &codegen_region = region->if_region->true_region->region;
1999 gimple *stmt = SSA_NAME_DEF_STMT (last_merge_name);
2000 basic_block bb = gimple_bb (stmt);
2001 if (!bb_in_sese_p (bb, codegen_region))
2002 return last_merge_name;
2003
2004 loop_p loop = bb->loop_father;
2005 if (!loop_in_sese_p (loop, codegen_region))
2006 return last_merge_name;
2007
2008 edge e = single_exit (loop);
2009
2010 if (dominated_by_p (CDI_DOMINATORS, e->dest, last_e->src))
2011 return last_merge_name;
2012
2013 tree old_name = gimple_phi_arg_def (old_close_phi, 0);
2014 tree old_close_phi_name = gimple_phi_result (old_close_phi);
2015
2016 bb = e->dest;
2017 if (!bb_contains_loop_close_phi_nodes (bb) || !single_succ_p (bb))
2018 bb = split_edge (e);
2019
2020 gphi *close_phi = create_phi_node (NULL_TREE, bb);
2021 tree res = create_new_def_for (last_merge_name, close_phi,
2022 gimple_phi_result_ptr (close_phi));
2023 set_rename (old_close_phi_name, res);
2024 add_phi_arg (close_phi, last_merge_name, e, get_loc (old_name));
2025 last_merge_name = res;
2026
2027 return add_close_phis_to_outer_loops (last_merge_name, last_e, old_close_phi);
2028 }
2029
2030 /* Add phi nodes to all merge points of all the diamonds enclosing the loop of
2031 the close phi node PHI. */
2032
2033 bool translate_isl_ast_to_gimple::
add_close_phis_to_merge_points(gphi * old_close_phi,gphi * new_close_phi,tree default_value)2034 add_close_phis_to_merge_points (gphi *old_close_phi, gphi *new_close_phi,
2035 tree default_value)
2036 {
2037 sese_l &codegen_region = region->if_region->true_region->region;
2038 basic_block default_value_bb = get_entry_bb (codegen_region);
2039 if (SSA_NAME == TREE_CODE (default_value))
2040 {
2041 gimple *stmt = SSA_NAME_DEF_STMT (default_value);
2042 if (!stmt || gimple_code (stmt) == GIMPLE_NOP)
2043 return false;
2044 default_value_bb = gimple_bb (stmt);
2045 }
2046
2047 basic_block new_close_phi_bb = gimple_bb (new_close_phi);
2048
2049 tree old_close_phi_name = gimple_phi_result (old_close_phi);
2050 tree new_close_phi_name = gimple_phi_result (new_close_phi);
2051 tree last_merge_name = new_close_phi_name;
2052 tree old_name = gimple_phi_arg_def (old_close_phi, 0);
2053
2054 int i;
2055 edge merge_e;
2056 FOR_EACH_VEC_ELT_REVERSE (merge_points, i, merge_e)
2057 {
2058 basic_block new_merge_bb = merge_e->src;
2059 if (!dominated_by_p (CDI_DOMINATORS, new_merge_bb, default_value_bb))
2060 continue;
2061
2062 last_merge_name = add_close_phis_to_outer_loops (last_merge_name, merge_e,
2063 old_close_phi);
2064
2065 gphi *merge_phi = create_phi_node (NULL_TREE, new_merge_bb);
2066 tree merge_res = create_new_def_for (old_close_phi_name, merge_phi,
2067 gimple_phi_result_ptr (merge_phi));
2068 set_rename (old_close_phi_name, merge_res);
2069
2070 edge from_loop = NULL, from_default_value = NULL;
2071 edge e;
2072 edge_iterator ei;
2073 FOR_EACH_EDGE (e, ei, new_merge_bb->preds)
2074 if (dominated_by_p (CDI_DOMINATORS, e->src, new_close_phi_bb))
2075 from_loop = e;
2076 else
2077 from_default_value = e;
2078
2079 /* Because CDI_POST_DOMINATORS are not updated, we only rely on
2080 CDI_DOMINATORS, which may not handle all cases where new_close_phi_bb
2081 is contained in another condition. */
2082 if (!from_default_value || !from_loop)
2083 return false;
2084
2085 add_phi_arg (merge_phi, last_merge_name, from_loop, get_loc (old_name));
2086 add_phi_arg (merge_phi, default_value, from_default_value, get_loc (old_name));
2087
2088 if (dump_file)
2089 {
2090 fprintf (dump_file, "[codegen] Adding guard-phi: ");
2091 print_gimple_stmt (dump_file, merge_phi, 0, 0);
2092 }
2093
2094 update_stmt (merge_phi);
2095 last_merge_name = merge_res;
2096 }
2097
2098 return true;
2099 }
2100
2101 /* Copy all the loop-close phi args from BB to NEW_BB. */
2102
2103 bool translate_isl_ast_to_gimple::
copy_loop_close_phi_args(basic_block old_bb,basic_block new_bb,bool postpone)2104 copy_loop_close_phi_args (basic_block old_bb, basic_block new_bb, bool postpone)
2105 {
2106 for (gphi_iterator psi = gsi_start_phis (old_bb); !gsi_end_p (psi);
2107 gsi_next (&psi))
2108 {
2109 gphi *old_close_phi = psi.phi ();
2110 tree res = gimple_phi_result (old_close_phi);
2111 if (virtual_operand_p (res))
2112 continue;
2113
2114 if (is_gimple_reg (res) && scev_analyzable_p (res, region->region))
2115 /* Loop close phi nodes should not be scev_analyzable_p. */
2116 gcc_unreachable ();
2117
2118 gphi *new_close_phi = create_phi_node (NULL_TREE, new_bb);
2119 tree new_res = create_new_def_for (res, new_close_phi,
2120 gimple_phi_result_ptr (new_close_phi));
2121 set_rename (res, new_res);
2122
2123 tree old_name = gimple_phi_arg_def (old_close_phi, 0);
2124 tree new_name = get_new_name (new_bb, old_name, old_bb, close_phi);
2125
2126 /* Predecessor basic blocks of a loop close phi should have been code
2127 generated before. FIXME: This is fixable by merging PHIs from inner
2128 loops as well. See: gfortran.dg/graphite/interchange-3.f90. */
2129 if (!new_name)
2130 return false;
2131
2132 add_phi_arg (new_close_phi, new_name, single_pred_edge (new_bb),
2133 get_loc (old_name));
2134 if (dump_file)
2135 {
2136 fprintf (dump_file, "[codegen] Adding loop close phi: ");
2137 print_gimple_stmt (dump_file, new_close_phi, 0, 0);
2138 }
2139
2140 update_stmt (new_close_phi);
2141
2142 /* When there is no loop guard around this codegenerated loop, there is no
2143 need to collect the close-phi arg. */
2144 if (merge_points.is_empty ())
2145 continue;
2146
2147 /* Add a PHI in the succ_new_bb for each close phi of the loop. */
2148 tree default_value = find_init_value_close_phi (new_close_phi);
2149
2150 /* A close phi must come from a loop-phi having a default value. */
2151 if (!default_value)
2152 {
2153 if (!postpone)
2154 return false;
2155
2156 region->incomplete_phis.safe_push (std::make_pair (old_close_phi,
2157 new_close_phi));
2158 if (dump_file)
2159 {
2160 fprintf (dump_file, "[codegen] postpone close phi nodes: ");
2161 print_gimple_stmt (dump_file, new_close_phi, 0, 0);
2162 }
2163 continue;
2164 }
2165
2166 if (!add_close_phis_to_merge_points (old_close_phi, new_close_phi,
2167 default_value))
2168 return false;
2169 }
2170
2171 return true;
2172 }
2173
2174 /* Copy loop close phi nodes from BB to NEW_BB. */
2175
2176 bool translate_isl_ast_to_gimple::
copy_loop_close_phi_nodes(basic_block old_bb,basic_block new_bb)2177 copy_loop_close_phi_nodes (basic_block old_bb, basic_block new_bb)
2178 {
2179 if (dump_file)
2180 fprintf (dump_file, "[codegen] copying loop close phi nodes in bb_%d.\n",
2181 new_bb->index);
2182 /* Loop close phi nodes should have only one argument. */
2183 gcc_assert (1 == EDGE_COUNT (old_bb->preds));
2184
2185 return copy_loop_close_phi_args (old_bb, new_bb, true);
2186 }
2187
2188
2189 /* Add NEW_NAME as the ARGNUM-th arg of NEW_PHI which is in NEW_BB.
2190 DOMINATING_PRED is the predecessor basic block of OLD_BB which dominates the
2191 other pred of OLD_BB as well. If no such basic block exists then it is NULL.
2192 NON_DOMINATING_PRED is a pred which does not dominate OLD_BB, it cannot be
2193 NULL.
2194
2195 Case1: OLD_BB->preds {BB1, BB2} and BB1 does not dominate BB2 and vice versa.
2196 In this case DOMINATING_PRED = NULL.
2197
2198 Case2: OLD_BB->preds {BB1, BB2} and BB1 dominates BB2.
2199
2200 Returns true on successful copy of the args, false otherwise. */
2201
2202 bool translate_isl_ast_to_gimple::
add_phi_arg_for_new_expr(tree old_phi_args[2],tree new_phi_args[2],edge old_bb_dominating_edge,edge old_bb_non_dominating_edge,gphi * phi,gphi * new_phi,basic_block new_bb)2203 add_phi_arg_for_new_expr (tree old_phi_args[2], tree new_phi_args[2],
2204 edge old_bb_dominating_edge,
2205 edge old_bb_non_dominating_edge,
2206 gphi *phi, gphi *new_phi,
2207 basic_block new_bb)
2208 {
2209 basic_block def_pred[2] = { NULL, NULL };
2210 int not_found_bb_index = -1;
2211 for (int i = 0; i < 2; i++)
2212 {
2213 /* If the corresponding def_bb could not be found the entry will be
2214 NULL. */
2215 if (TREE_CODE (old_phi_args[i]) == INTEGER_CST)
2216 def_pred[i] = get_def_bb_for_const (new_bb,
2217 gimple_phi_arg_edge (phi, i)->src);
2218 else if (new_phi_args[i] && (TREE_CODE (new_phi_args[i]) == SSA_NAME))
2219 def_pred[i] = gimple_bb (SSA_NAME_DEF_STMT (new_phi_args[i]));
2220
2221 if (!def_pred[i])
2222 {
2223 /* When non are available bail out. */
2224 if (not_found_bb_index != -1)
2225 return false;
2226 not_found_bb_index = i;
2227 }
2228 }
2229
2230 /* Here we are pattern matching on the structure of CFG w.r.t. old one. */
2231 if (old_bb_dominating_edge)
2232 {
2233 if (not_found_bb_index != -1)
2234 return false;
2235
2236 basic_block new_pred1 = (*new_bb->preds)[0]->src;
2237 basic_block new_pred2 = (*new_bb->preds)[1]->src;
2238 vec <basic_block> *bbs
2239 = region->copied_bb_map->get (old_bb_non_dominating_edge->src);
2240
2241 /* Could not find a mapping. */
2242 if (!bbs)
2243 return false;
2244
2245 basic_block new_pred = NULL;
2246 basic_block b;
2247 int i;
2248 FOR_EACH_VEC_ELT (*bbs, i, b)
2249 {
2250 if (dominated_by_p (CDI_DOMINATORS, new_pred1, b))
2251 {
2252 /* FIXME: If we have already found new_pred then we have to
2253 disambiguate, bail out for now. */
2254 if (new_pred)
2255 return false;
2256 new_pred = new_pred1;
2257 }
2258 if (dominated_by_p (CDI_DOMINATORS, new_pred2, b))
2259 {
2260 /* FIXME: If we have already found new_pred then we have to either
2261 it dominates both or we have to disambiguate, bail out. */
2262 if (new_pred)
2263 return false;
2264 new_pred = new_pred2;
2265 }
2266 }
2267
2268 if (!new_pred)
2269 return false;
2270
2271 edge new_non_dominating_edge = find_edge (new_pred, new_bb);
2272 gcc_assert (new_non_dominating_edge);
2273 /* FIXME: Validate each args just like in loop-phis. */
2274 /* By the process of elimination we first insert insert phi-edge for
2275 non-dominating pred which is computed above and then we insert the
2276 remaining one. */
2277 int inserted_edge = 0;
2278 for (; inserted_edge < 2; inserted_edge++)
2279 {
2280 edge new_bb_pred_edge = gimple_phi_arg_edge (new_phi, inserted_edge);
2281 if (new_non_dominating_edge == new_bb_pred_edge)
2282 {
2283 add_phi_arg (new_phi, new_phi_args[inserted_edge],
2284 new_non_dominating_edge,
2285 get_loc (old_phi_args[inserted_edge]));
2286 break;
2287 }
2288 }
2289 if (inserted_edge == 2)
2290 return false;
2291
2292 int edge_dominating = inserted_edge == 0 ? 1 : 0;
2293
2294 edge new_dominating_edge = NULL;
2295 for (inserted_edge = 0; inserted_edge < 2; inserted_edge++)
2296 {
2297 edge e = gimple_phi_arg_edge (new_phi, inserted_edge);
2298 if (e != new_non_dominating_edge)
2299 {
2300 new_dominating_edge = e;
2301 add_phi_arg (new_phi, new_phi_args[edge_dominating],
2302 new_dominating_edge,
2303 get_loc (old_phi_args[inserted_edge]));
2304 break;
2305 }
2306 }
2307 gcc_assert (new_dominating_edge);
2308 }
2309 else
2310 {
2311 /* Classic diamond structure: both edges are non-dominating. We need to
2312 find one unique edge then the other can be found be elimination. If
2313 any definition (def_pred) dominates both the preds of new_bb then we
2314 bail out. Entries of def_pred maybe NULL, in that case we must
2315 uniquely find pred with help of only one entry. */
2316 edge new_e[2] = { NULL, NULL };
2317 for (int i = 0; i < 2; i++)
2318 {
2319 edge e;
2320 edge_iterator ei;
2321 FOR_EACH_EDGE (e, ei, new_bb->preds)
2322 if (def_pred[i]
2323 && dominated_by_p (CDI_DOMINATORS, e->src, def_pred[i]))
2324 {
2325 if (new_e[i])
2326 /* We do not know how to handle the case when def_pred
2327 dominates more than a predecessor. */
2328 return false;
2329 new_e[i] = e;
2330 }
2331 }
2332
2333 gcc_assert (new_e[0] || new_e[1]);
2334
2335 /* Find the other edge by process of elimination. */
2336 if (not_found_bb_index != -1)
2337 {
2338 gcc_assert (!new_e[not_found_bb_index]);
2339 int found_bb_index = not_found_bb_index == 1 ? 0 : 1;
2340 edge e;
2341 edge_iterator ei;
2342 FOR_EACH_EDGE (e, ei, new_bb->preds)
2343 {
2344 if (new_e[found_bb_index] == e)
2345 continue;
2346 new_e[not_found_bb_index] = e;
2347 }
2348 }
2349
2350 /* Add edges to phi args. */
2351 for (int i = 0; i < 2; i++)
2352 add_phi_arg (new_phi, new_phi_args[i], new_e[i],
2353 get_loc (old_phi_args[i]));
2354 }
2355
2356 return true;
2357 }
2358
2359 /* Copy the arguments of cond-phi node PHI, to NEW_PHI in the codegenerated
2360 region. If postpone is true and it isn't possible to copy any arg of PHI,
2361 the PHI is added to the REGION->INCOMPLETE_PHIS to be codegenerated later.
2362 Returns false if the copying was unsuccessful. */
2363
2364 bool translate_isl_ast_to_gimple::
copy_cond_phi_args(gphi * phi,gphi * new_phi,vec<tree> iv_map,bool postpone)2365 copy_cond_phi_args (gphi *phi, gphi *new_phi, vec<tree> iv_map, bool postpone)
2366 {
2367 if (dump_file)
2368 fprintf (dump_file, "[codegen] copying cond phi args.\n");
2369 gcc_assert (2 == gimple_phi_num_args (phi));
2370
2371 basic_block new_bb = gimple_bb (new_phi);
2372 loop_p loop = gimple_bb (phi)->loop_father;
2373
2374 basic_block old_bb = gimple_bb (phi);
2375 edge old_bb_non_dominating_edge = NULL, old_bb_dominating_edge = NULL;
2376
2377 edge e;
2378 edge_iterator ei;
2379 FOR_EACH_EDGE (e, ei, old_bb->preds)
2380 if (!dominated_by_p (CDI_DOMINATORS, old_bb, e->src))
2381 old_bb_non_dominating_edge = e;
2382 else
2383 old_bb_dominating_edge = e;
2384
2385 gcc_assert (!dominated_by_p (CDI_DOMINATORS, old_bb,
2386 old_bb_non_dominating_edge->src));
2387
2388 tree new_phi_args[2];
2389 tree old_phi_args[2];
2390
2391 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2392 {
2393 tree old_name = gimple_phi_arg_def (phi, i);
2394 tree new_name = get_new_name (new_bb, old_name, old_bb, cond_phi);
2395 old_phi_args[i] = old_name;
2396 if (new_name)
2397 {
2398 new_phi_args [i] = new_name;
2399 continue;
2400 }
2401
2402 /* If the phi-arg was a parameter. */
2403 if (vec_find (region->params, old_name) != -1)
2404 {
2405 new_phi_args [i] = old_name;
2406 if (dump_file)
2407 {
2408 fprintf (dump_file,
2409 "[codegen] parameter argument to phi, new_expr: ");
2410 print_generic_expr (dump_file, new_phi_args[i], 0);
2411 fprintf (dump_file, "\n");
2412 }
2413 continue;
2414 }
2415
2416 gimple *old_def_stmt = SSA_NAME_DEF_STMT (old_name);
2417 if (!old_def_stmt || gimple_code (old_def_stmt) == GIMPLE_NOP)
2418 /* FIXME: If the phi arg was a function arg, or wasn't defined, just use
2419 the old name. */
2420 return false;
2421
2422 if (postpone)
2423 {
2424 /* If the phi-arg is scev-analyzeable but only in the first stage. */
2425 if (is_gimple_reg (old_name)
2426 && scev_analyzable_p (old_name, region->region))
2427 {
2428 gimple_seq stmts;
2429 tree new_expr = get_rename_from_scev (old_name, &stmts, loop,
2430 new_bb, old_bb, iv_map);
2431 if (codegen_error_p ())
2432 return false;
2433
2434 gcc_assert (new_expr);
2435 if (dump_file)
2436 {
2437 fprintf (dump_file,
2438 "[codegen] scev analyzeable, new_expr: ");
2439 print_generic_expr (dump_file, new_expr, 0);
2440 fprintf (dump_file, "\n");
2441 }
2442 gsi_insert_earliest (stmts);
2443 new_phi_args[i] = new_expr;
2444 continue;
2445 }
2446
2447 /* Postpone code gen for later for back-edges. */
2448 region->incomplete_phis.safe_push (std::make_pair (phi, new_phi));
2449
2450 if (dump_file)
2451 {
2452 fprintf (dump_file, "[codegen] postpone cond phi nodes: ");
2453 print_gimple_stmt (dump_file, new_phi, 0, 0);
2454 }
2455
2456 new_phi_args [i] = NULL_TREE;
2457 continue;
2458 }
2459 else
2460 /* Either we should add the arg to phi or, we should postpone. */
2461 return false;
2462 }
2463
2464 /* If none of the args have been determined in the first stage then wait until
2465 later. */
2466 if (postpone && !new_phi_args[0] && !new_phi_args[1])
2467 return true;
2468
2469 return add_phi_arg_for_new_expr (old_phi_args, new_phi_args,
2470 old_bb_dominating_edge,
2471 old_bb_non_dominating_edge,
2472 phi, new_phi, new_bb);
2473 }
2474
2475 /* Copy cond phi nodes from BB to NEW_BB. A cond-phi node is a basic block
2476 containing phi nodes coming from two predecessors, and none of them are back
2477 edges. */
2478
2479 bool translate_isl_ast_to_gimple::
copy_cond_phi_nodes(basic_block bb,basic_block new_bb,vec<tree> iv_map)2480 copy_cond_phi_nodes (basic_block bb, basic_block new_bb, vec<tree> iv_map)
2481 {
2482
2483 gcc_assert (!bb_contains_loop_close_phi_nodes (bb));
2484
2485 /* TODO: Handle cond phi nodes with more than 2 predecessors. */
2486 if (EDGE_COUNT (bb->preds) != 2)
2487 return false;
2488
2489 if (dump_file)
2490 fprintf (dump_file, "[codegen] copying cond phi nodes in bb_%d.\n",
2491 new_bb->index);
2492
2493 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
2494 gsi_next (&psi))
2495 {
2496 gphi *phi = psi.phi ();
2497 tree res = gimple_phi_result (phi);
2498 if (virtual_operand_p (res))
2499 continue;
2500
2501 gphi *new_phi = create_phi_node (NULL_TREE, new_bb);
2502 tree new_res = create_new_def_for (res, new_phi,
2503 gimple_phi_result_ptr (new_phi));
2504 set_rename (res, new_res);
2505
2506 if (!copy_cond_phi_args (phi, new_phi, iv_map, true))
2507 return false;
2508
2509 update_stmt (new_phi);
2510 }
2511
2512 return true;
2513 }
2514
2515 /* Return true if STMT should be copied from region to the new code-generated
2516 region. LABELs, CONDITIONS, induction-variables and region parameters need
2517 not be copied. */
2518
2519 static bool
should_copy_to_new_region(gimple * stmt,sese_info_p region)2520 should_copy_to_new_region (gimple *stmt, sese_info_p region)
2521 {
2522 /* Do not copy labels or conditions. */
2523 if (gimple_code (stmt) == GIMPLE_LABEL
2524 || gimple_code (stmt) == GIMPLE_COND)
2525 return false;
2526
2527 tree lhs;
2528 /* Do not copy induction variables. */
2529 if (is_gimple_assign (stmt)
2530 && (lhs = gimple_assign_lhs (stmt))
2531 && TREE_CODE (lhs) == SSA_NAME
2532 && is_gimple_reg (lhs)
2533 && scev_analyzable_p (lhs, region->region))
2534 return false;
2535
2536 /* Do not copy parameters that have been generated in the header of the
2537 scop. */
2538 if (is_gimple_assign (stmt)
2539 && (lhs = gimple_assign_lhs (stmt))
2540 && TREE_CODE (lhs) == SSA_NAME
2541 && region->parameter_rename_map->get(lhs))
2542 return false;
2543
2544 return true;
2545 }
2546
2547 /* Create new names for all the definitions created by COPY and add replacement
2548 mappings for each new name. */
2549
2550 void translate_isl_ast_to_gimple::
set_rename_for_each_def(gimple * stmt)2551 set_rename_for_each_def (gimple *stmt)
2552 {
2553 def_operand_p def_p;
2554 ssa_op_iter op_iter;
2555 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
2556 {
2557 tree old_name = DEF_FROM_PTR (def_p);
2558 tree new_name = create_new_def_for (old_name, stmt, def_p);
2559 set_rename (old_name, new_name);
2560 }
2561 }
2562
2563 /* Duplicates the statements of basic block BB into basic block NEW_BB
2564 and compute the new induction variables according to the IV_MAP. */
2565
2566 bool translate_isl_ast_to_gimple::
graphite_copy_stmts_from_block(basic_block bb,basic_block new_bb,vec<tree> iv_map)2567 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
2568 vec<tree> iv_map)
2569 {
2570 /* Iterator poining to the place where new statement (s) will be inserted. */
2571 gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
2572
2573 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
2574 gsi_next (&gsi))
2575 {
2576 gimple *stmt = gsi_stmt (gsi);
2577 if (!should_copy_to_new_region (stmt, region))
2578 continue;
2579
2580 /* Create a new copy of STMT and duplicate STMT's virtual
2581 operands. */
2582 gimple *copy = gimple_copy (stmt);
2583 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
2584
2585 if (dump_file)
2586 {
2587 fprintf (dump_file, "[codegen] inserting statement: ");
2588 print_gimple_stmt (dump_file, copy, 0, 0);
2589 }
2590
2591 maybe_duplicate_eh_stmt (copy, stmt);
2592 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
2593
2594 /* Crete new names for each def in the copied stmt. */
2595 set_rename_for_each_def (copy);
2596
2597 loop_p loop = bb->loop_father;
2598 if (rename_uses (copy, &gsi_tgt, bb, loop, iv_map))
2599 {
2600 fold_stmt_inplace (&gsi_tgt);
2601 gcc_assert (gsi_stmt (gsi_tgt) == copy);
2602 }
2603
2604 if (codegen_error_p ())
2605 return false;
2606
2607 /* For each SSA_NAME in the parameter_rename_map rename their usage. */
2608 ssa_op_iter iter;
2609 use_operand_p use_p;
2610 if (!is_gimple_debug (copy))
2611 FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
2612 {
2613 tree old_name = USE_FROM_PTR (use_p);
2614
2615 if (TREE_CODE (old_name) != SSA_NAME
2616 || SSA_NAME_IS_DEFAULT_DEF (old_name))
2617 continue;
2618
2619 tree *new_expr = region->parameter_rename_map->get (old_name);
2620 if (!new_expr)
2621 continue;
2622
2623 replace_exp (use_p, *new_expr);
2624 }
2625
2626 update_stmt (copy);
2627 }
2628
2629 return true;
2630 }
2631
2632
2633 /* Given a basic block containing close-phi it returns the new basic block where
2634 to insert a copy of the close-phi nodes. All the uses in close phis should
2635 come from a single loop otherwise it returns NULL. */
2636
2637 edge translate_isl_ast_to_gimple::
edge_for_new_close_phis(basic_block bb)2638 edge_for_new_close_phis (basic_block bb)
2639 {
2640 /* Make sure that NEW_BB is the new_loop->exit->dest. We find the definition
2641 of close phi in the original code and then find the mapping of basic block
2642 defining that variable. If there are multiple close-phis and they are
2643 defined in different loops (in the original or in the new code) because of
2644 loop splitting, then we bail out. */
2645 loop_p new_loop = NULL;
2646 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
2647 gsi_next (&psi))
2648 {
2649 gphi *phi = psi.phi ();
2650 tree name = gimple_phi_arg_def (phi, 0);
2651 basic_block old_loop_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
2652
2653 vec <basic_block> *bbs = region->copied_bb_map->get (old_loop_bb);
2654 if (!bbs || bbs->length () != 1)
2655 /* This is one of the places which shows preserving original structure
2656 is not always possible, as we may need to insert close PHI for a loop
2657 where the latch does not have any mapping, or the mapping is
2658 ambiguous. */
2659 return NULL;
2660
2661 if (!new_loop)
2662 new_loop = (*bbs)[0]->loop_father;
2663 else if (new_loop != (*bbs)[0]->loop_father)
2664 return NULL;
2665 }
2666
2667 if (!new_loop)
2668 return NULL;
2669
2670 return single_exit (new_loop);
2671 }
2672
2673 /* Copies BB and includes in the copied BB all the statements that can
2674 be reached following the use-def chains from the memory accesses,
2675 and returns the next edge following this new block. */
2676
2677 edge translate_isl_ast_to_gimple::
copy_bb_and_scalar_dependences(basic_block bb,edge next_e,vec<tree> iv_map)2678 copy_bb_and_scalar_dependences (basic_block bb, edge next_e, vec<tree> iv_map)
2679 {
2680 int num_phis = number_of_phi_nodes (bb);
2681
2682 if (region->copied_bb_map->get (bb))
2683 {
2684 /* FIXME: we should be able to handle phi nodes with args coming from
2685 outside the region. */
2686 if (num_phis)
2687 {
2688 codegen_error = true;
2689 return NULL;
2690 }
2691 }
2692
2693 basic_block new_bb = NULL;
2694 if (bb_contains_loop_close_phi_nodes (bb))
2695 {
2696 if (dump_file)
2697 fprintf (dump_file, "[codegen] bb_%d contains close phi nodes.\n",
2698 bb->index);
2699
2700 edge e = edge_for_new_close_phis (bb);
2701 if (!e)
2702 {
2703 codegen_error = true;
2704 return NULL;
2705 }
2706
2707 basic_block phi_bb = e->dest;
2708
2709 if (!bb_contains_loop_close_phi_nodes (phi_bb) || !single_succ_p (phi_bb))
2710 phi_bb = split_edge (e);
2711
2712 gcc_assert (single_pred_edge (phi_bb)->src->loop_father
2713 != single_pred_edge (phi_bb)->dest->loop_father);
2714
2715 if (!copy_loop_close_phi_nodes (bb, phi_bb))
2716 {
2717 codegen_error = true;
2718 return NULL;
2719 }
2720
2721 if (e == next_e)
2722 new_bb = phi_bb;
2723 else
2724 new_bb = split_edge (next_e);
2725 }
2726 else
2727 {
2728 new_bb = split_edge (next_e);
2729 if (num_phis > 0 && bb_contains_loop_phi_nodes (bb))
2730 {
2731 basic_block phi_bb = next_e->dest->loop_father->header;
2732
2733 /* At this point we are unable to codegenerate by still preserving the SSA
2734 structure because maybe the loop is completely unrolled and the PHIs
2735 and cross-bb scalar dependencies are untrackable w.r.t. the original
2736 code. See gfortran.dg/graphite/pr29832.f90. */
2737 if (EDGE_COUNT (bb->preds) != EDGE_COUNT (phi_bb->preds))
2738 {
2739 codegen_error = true;
2740 return NULL;
2741 }
2742
2743 /* In case isl did some loop peeling, like this:
2744
2745 S_8(0);
2746 for (int c1 = 1; c1 <= 5; c1 += 1) {
2747 S_8(c1);
2748 }
2749 S_8(6);
2750
2751 there should be no loop-phi nodes in S_8(0).
2752
2753 FIXME: We need to reason about dynamic instances of S_8, i.e., the
2754 values of all scalar variables: for the moment we instantiate only
2755 SCEV analyzable expressions on the iteration domain, and we need to
2756 extend that to reductions that cannot be analyzed by SCEV. */
2757 if (!bb_in_sese_p (phi_bb, region->if_region->true_region->region))
2758 {
2759 codegen_error = true;
2760 return NULL;
2761 }
2762
2763 if (dump_file)
2764 fprintf (dump_file, "[codegen] bb_%d contains loop phi nodes.\n",
2765 bb->index);
2766 if (!copy_loop_phi_nodes (bb, phi_bb))
2767 {
2768 codegen_error = true;
2769 return NULL;
2770 }
2771 }
2772 else if (num_phis > 0)
2773 {
2774 if (dump_file)
2775 fprintf (dump_file, "[codegen] bb_%d contains cond phi nodes.\n",
2776 bb->index);
2777
2778 basic_block phi_bb = single_pred (new_bb);
2779 loop_p loop_father = new_bb->loop_father;
2780
2781 /* Move back until we find the block with two predecessors. */
2782 while (single_pred_p (phi_bb))
2783 phi_bb = single_pred_edge (phi_bb)->src;
2784
2785 /* If a corresponding merge-point was not found, then abort codegen. */
2786 if (phi_bb->loop_father != loop_father
2787 || !bb_in_sese_p (phi_bb, region->if_region->true_region->region)
2788 || !copy_cond_phi_nodes (bb, phi_bb, iv_map))
2789 {
2790 codegen_error = true;
2791 return NULL;
2792 }
2793 }
2794 }
2795
2796 if (dump_file)
2797 fprintf (dump_file, "[codegen] copying from bb_%d to bb_%d.\n",
2798 bb->index, new_bb->index);
2799
2800 vec <basic_block> *copied_bbs = region->copied_bb_map->get (bb);
2801 if (copied_bbs)
2802 copied_bbs->safe_push (new_bb);
2803 else
2804 {
2805 vec<basic_block> bbs;
2806 bbs.create (2);
2807 bbs.safe_push (new_bb);
2808 region->copied_bb_map->put (bb, bbs);
2809 }
2810
2811 if (!graphite_copy_stmts_from_block (bb, new_bb, iv_map))
2812 {
2813 codegen_error = true;
2814 return NULL;
2815 }
2816
2817 return single_succ_edge (new_bb);
2818 }
2819
2820 /* Patch the missing arguments of the phi nodes. */
2821
2822 void translate_isl_ast_to_gimple::
translate_pending_phi_nodes()2823 translate_pending_phi_nodes ()
2824 {
2825 int i;
2826 phi_rename *rename;
2827 FOR_EACH_VEC_ELT (region->incomplete_phis, i, rename)
2828 {
2829 gphi *old_phi = rename->first;
2830 gphi *new_phi = rename->second;
2831 basic_block old_bb = gimple_bb (old_phi);
2832 basic_block new_bb = gimple_bb (new_phi);
2833
2834 /* First edge is the init edge and second is the back edge. */
2835 init_back_edge_pair_t ibp_old_bb = get_edges (old_bb);
2836 init_back_edge_pair_t ibp_new_bb = get_edges (new_bb);
2837
2838 if (dump_file)
2839 {
2840 fprintf (dump_file, "[codegen] translating pending old-phi: ");
2841 print_gimple_stmt (dump_file, old_phi, 0, 0);
2842 }
2843
2844 auto_vec <tree, 1> iv_map;
2845 if (bb_contains_loop_phi_nodes (new_bb))
2846 codegen_error = !copy_loop_phi_args (old_phi, ibp_old_bb, new_phi,
2847 ibp_new_bb, false);
2848 else if (bb_contains_loop_close_phi_nodes (new_bb))
2849 codegen_error = !copy_loop_close_phi_args (old_bb, new_bb, false);
2850 else
2851 codegen_error = !copy_cond_phi_args (old_phi, new_phi, iv_map, false);
2852
2853 if (dump_file)
2854 {
2855 fprintf (dump_file, "[codegen] to new-phi: ");
2856 print_gimple_stmt (dump_file, new_phi, 0, 0);
2857 }
2858 if (codegen_error_p ())
2859 return;
2860 }
2861 }
2862
2863 /* Add isl's parameter identifiers and corresponding trees to ivs_params. */
2864
2865 void translate_isl_ast_to_gimple::
add_parameters_to_ivs_params(scop_p scop,ivs_params & ip)2866 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
2867 {
2868 sese_info_p region = scop->scop_info;
2869 unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param);
2870 gcc_assert (nb_parameters == region->params.length ());
2871 unsigned i;
2872 for (i = 0; i < nb_parameters; i++)
2873 {
2874 isl_id *tmp_id = isl_set_get_dim_id (scop->param_context,
2875 isl_dim_param, i);
2876 ip[tmp_id] = region->params[i];
2877 }
2878 }
2879
2880
2881 /* Generates a build, which specifies the constraints on the parameters. */
2882
2883 __isl_give isl_ast_build *translate_isl_ast_to_gimple::
generate_isl_context(scop_p scop)2884 generate_isl_context (scop_p scop)
2885 {
2886 isl_set *context_isl = isl_set_params (isl_set_copy (scop->param_context));
2887 return isl_ast_build_from_context (context_isl);
2888 }
2889
2890 /* This method is executed before the construction of a for node. */
2891 __isl_give isl_id *
ast_build_before_for(__isl_keep isl_ast_build * build,void * user)2892 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
2893 {
2894 isl_union_map *dependences = (isl_union_map *) user;
2895 ast_build_info *for_info = XNEW (struct ast_build_info);
2896 isl_union_map *schedule = isl_ast_build_get_schedule (build);
2897 isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
2898 int dimension = isl_space_dim (schedule_space, isl_dim_out);
2899 for_info->is_parallelizable =
2900 !carries_deps (schedule, dependences, dimension);
2901 isl_union_map_free (schedule);
2902 isl_space_free (schedule_space);
2903 isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
2904 return id;
2905 }
2906
2907 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
2908
2909 /* Generate isl AST from schedule of SCOP. */
2910
2911 __isl_give isl_ast_node *translate_isl_ast_to_gimple::
scop_to_isl_ast(scop_p scop)2912 scop_to_isl_ast (scop_p scop)
2913 {
2914 gcc_assert (scop->transformed_schedule);
2915
2916 /* Set the separate option to reduce control flow overhead. */
2917 isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up
2918 (isl_schedule_copy (scop->transformed_schedule), set_separate_option, NULL);
2919 isl_ast_build *context_isl = generate_isl_context (scop);
2920
2921 if (flag_loop_parallelize_all)
2922 {
2923 scop_get_dependences (scop);
2924 context_isl =
2925 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
2926 scop->dependence);
2927 }
2928
2929 isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
2930 (context_isl, schedule);
2931 isl_ast_build_free (context_isl);
2932 return ast_isl;
2933 }
2934
2935 #else
2936 /* Get the maximal number of schedule dimensions in the scop SCOP. */
2937
2938 int translate_isl_ast_to_gimple::
get_max_schedule_dimensions(scop_p scop)2939 get_max_schedule_dimensions (scop_p scop)
2940 {
2941 int i;
2942 poly_bb_p pbb;
2943 int schedule_dims = 0;
2944
2945 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
2946 {
2947 int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
2948 if (pbb_schedule_dims > schedule_dims)
2949 schedule_dims = pbb_schedule_dims;
2950 }
2951
2952 return schedule_dims;
2953 }
2954
2955 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
2956
2957 For schedules with different dimensionality, the isl AST generator can not
2958 define an order and will just randomly choose an order. The solution to this
2959 problem is to extend all schedules to the maximal number of schedule
2960 dimensions (using '0's for the remaining values). */
2961
2962 __isl_give isl_map *translate_isl_ast_to_gimple::
extend_schedule(__isl_take isl_map * schedule,int nb_schedule_dims)2963 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
2964 {
2965 int tmp_dims = isl_map_dim (schedule, isl_dim_out);
2966 schedule =
2967 isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
2968 isl_val *zero =
2969 isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
2970 int i;
2971 for (i = tmp_dims; i < nb_schedule_dims; i++)
2972 {
2973 schedule
2974 = isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
2975 }
2976 isl_val_free (zero);
2977 return schedule;
2978 }
2979
2980 /* Generates a schedule, which specifies an order used to
2981 visit elements in a domain. */
2982
2983 __isl_give isl_union_map *translate_isl_ast_to_gimple::
generate_isl_schedule(scop_p scop)2984 generate_isl_schedule (scop_p scop)
2985 {
2986 int nb_schedule_dims = get_max_schedule_dimensions (scop);
2987 int i;
2988 poly_bb_p pbb;
2989 isl_union_map *schedule_isl =
2990 isl_union_map_empty (isl_set_get_space (scop->param_context));
2991
2992 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
2993 {
2994 /* Dead code elimination: when the domain of a PBB is empty,
2995 don't generate code for the PBB. */
2996 if (isl_set_is_empty (pbb->domain))
2997 continue;
2998
2999 isl_map *bb_schedule = isl_map_copy (pbb->transformed);
3000 bb_schedule = isl_map_intersect_domain (bb_schedule,
3001 isl_set_copy (pbb->domain));
3002 bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
3003 bb_schedule = isl_map_coalesce (bb_schedule);
3004 schedule_isl
3005 = isl_union_map_union (schedule_isl,
3006 isl_union_map_from_map (bb_schedule));
3007 schedule_isl = isl_union_map_coalesce (schedule_isl);
3008 }
3009 return schedule_isl;
3010 }
3011
3012 /* Set the separate option for all dimensions.
3013 This helps to reduce control overhead. */
3014
3015 __isl_give isl_ast_build *translate_isl_ast_to_gimple::
set_options(__isl_take isl_ast_build * control,__isl_keep isl_union_map * schedule)3016 set_options (__isl_take isl_ast_build *control,
3017 __isl_keep isl_union_map *schedule)
3018 {
3019 isl_ctx *ctx = isl_union_map_get_ctx (schedule);
3020 isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
3021 range_space =
3022 isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
3023 isl_union_set *range =
3024 isl_union_set_from_set (isl_set_universe (range_space));
3025 isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
3026 domain = isl_union_set_universe (domain);
3027 isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
3028 return isl_ast_build_set_options (control, options);
3029 }
3030
3031 /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */
3032
3033 __isl_give isl_ast_node *translate_isl_ast_to_gimple::
scop_to_isl_ast(scop_p scop,ivs_params & ip)3034 scop_to_isl_ast (scop_p scop, ivs_params &ip)
3035 {
3036 /* Generate loop upper bounds that consist of the current loop iterator, an
3037 operator (< or <=) and an expression not involving the iterator. If this
3038 option is not set, then the current loop iterator may appear several times
3039 in the upper bound. See the isl manual for more details. */
3040 isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, true);
3041
3042 add_parameters_to_ivs_params (scop, ip);
3043 isl_union_map *schedule_isl = generate_isl_schedule (scop);
3044 isl_ast_build *context_isl = generate_isl_context (scop);
3045 context_isl = set_options (context_isl, schedule_isl);
3046 if (flag_loop_parallelize_all)
3047 {
3048 isl_union_map *dependence = scop_get_dependences (scop);
3049 context_isl =
3050 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
3051 dependence);
3052 }
3053
3054 isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
3055 schedule_isl);
3056 if (scop->schedule)
3057 {
3058 isl_schedule_free (scop->schedule);
3059 scop->schedule = NULL;
3060 }
3061
3062 isl_ast_build_free (context_isl);
3063 return ast_isl;
3064 }
3065 #endif
3066
3067 /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by
3068 DEF_STMT. GSI points to entry basic block of the TO_REGION. */
3069
3070 static void
copy_def(tree tr,gimple * def_stmt,sese_info_p region,sese_info_p to_region,gimple_stmt_iterator * gsi)3071 copy_def (tree tr, gimple *def_stmt, sese_info_p region, sese_info_p to_region,
3072 gimple_stmt_iterator *gsi)
3073 {
3074 if (!defined_in_sese_p (tr, region->region))
3075 return;
3076
3077 ssa_op_iter iter;
3078 use_operand_p use_p;
3079 FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
3080 {
3081 tree use_tr = USE_FROM_PTR (use_p);
3082
3083 /* Do not copy parameters that have been generated in the header of the
3084 scop. */
3085 if (region->parameter_rename_map->get(use_tr))
3086 continue;
3087
3088 gimple *def_of_use = SSA_NAME_DEF_STMT (use_tr);
3089 if (!def_of_use)
3090 continue;
3091
3092 copy_def (use_tr, def_of_use, region, to_region, gsi);
3093 }
3094
3095 gimple *copy = gimple_copy (def_stmt);
3096 gsi_insert_after (gsi, copy, GSI_NEW_STMT);
3097
3098 /* Create new names for all the definitions created by COPY and
3099 add replacement mappings for each new name. */
3100 def_operand_p def_p;
3101 ssa_op_iter op_iter;
3102 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
3103 {
3104 tree old_name = DEF_FROM_PTR (def_p);
3105 tree new_name = create_new_def_for (old_name, copy, def_p);
3106 region->parameter_rename_map->put(old_name, new_name);
3107 }
3108
3109 update_stmt (copy);
3110 }
3111
3112 static void
copy_internal_parameters(sese_info_p region,sese_info_p to_region)3113 copy_internal_parameters (sese_info_p region, sese_info_p to_region)
3114 {
3115 /* For all the parameters which definitino is in the if_region->false_region,
3116 insert code on true_region (if_region->true_region->entry). */
3117
3118 int i;
3119 tree tr;
3120 gimple_stmt_iterator gsi = gsi_start_bb(to_region->region.entry->dest);
3121
3122 FOR_EACH_VEC_ELT (region->params, i, tr)
3123 {
3124 // If def is not in region.
3125 gimple *def_stmt = SSA_NAME_DEF_STMT (tr);
3126 if (def_stmt)
3127 copy_def (tr, def_stmt, region, to_region, &gsi);
3128 }
3129 }
3130
3131 /* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
3132 Return true if code generation succeeded. */
3133
3134 bool
graphite_regenerate_ast_isl(scop_p scop)3135 graphite_regenerate_ast_isl (scop_p scop)
3136 {
3137 sese_info_p region = scop->scop_info;
3138 translate_isl_ast_to_gimple t (region);
3139
3140 ifsese if_region = NULL;
3141 isl_ast_node *root_node;
3142 ivs_params ip;
3143
3144 timevar_push (TV_GRAPHITE_CODE_GEN);
3145 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3146 t.add_parameters_to_ivs_params (scop, ip);
3147 root_node = t.scop_to_isl_ast (scop);
3148 #else
3149 root_node = t.scop_to_isl_ast (scop, ip);
3150 #endif
3151
3152 if (dump_file && (dump_flags & TDF_DETAILS))
3153 {
3154 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
3155 fprintf (dump_file, "[scheduler] original schedule:\n");
3156 print_isl_schedule (dump_file, scop->original_schedule);
3157 fprintf (dump_file, "[scheduler] isl transformed schedule:\n");
3158 print_isl_schedule (dump_file, scop->transformed_schedule);
3159
3160 fprintf (dump_file, "[scheduler] original ast:\n");
3161 print_schedule_ast (dump_file, scop->original_schedule, scop);
3162 #endif
3163 fprintf (dump_file, "[scheduler] AST generated by isl:\n");
3164 print_isl_ast (dump_file, root_node);
3165 }
3166
3167 recompute_all_dominators ();
3168 graphite_verify ();
3169
3170 if_region = move_sese_in_condition (region);
3171 region->if_region = if_region;
3172 recompute_all_dominators ();
3173
3174 loop_p context_loop = region->region.entry->src->loop_father;
3175
3176 /* Copy all the parameters which are defined in the region. */
3177 copy_internal_parameters(if_region->false_region, if_region->true_region);
3178
3179 edge e = single_succ_edge (if_region->true_region->region.entry->dest);
3180 basic_block bb = split_edge (e);
3181
3182 /* Update the true_region exit edge. */
3183 region->if_region->true_region->region.exit = single_succ_edge (bb);
3184
3185 t.translate_isl_ast (context_loop, root_node, e, ip);
3186 if (t.codegen_error_p ())
3187 {
3188 if (dump_file)
3189 fprintf (dump_file, "codegen error: "
3190 "reverting back to the original code.\n");
3191 set_ifsese_condition (if_region, integer_zero_node);
3192 }
3193 else
3194 {
3195 t.translate_pending_phi_nodes ();
3196 if (!t.codegen_error_p ())
3197 {
3198 sese_insert_phis_for_liveouts (region,
3199 if_region->region->region.exit->src,
3200 if_region->false_region->region.exit,
3201 if_region->true_region->region.exit);
3202 mark_virtual_operands_for_renaming (cfun);
3203 update_ssa (TODO_update_ssa);
3204
3205
3206 graphite_verify ();
3207 scev_reset ();
3208 recompute_all_dominators ();
3209 graphite_verify ();
3210
3211 if (dump_file)
3212 fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
3213 }
3214 else
3215 {
3216 if (dump_file)
3217 fprintf (dump_file, "[codegen] unsuccessful in translating"
3218 " pending phis, reverting back to the original code.\n");
3219 set_ifsese_condition (if_region, integer_zero_node);
3220 }
3221 }
3222
3223 free (if_region->true_region);
3224 free (if_region->region);
3225 free (if_region);
3226
3227 ivs_params_clear (ip);
3228 isl_ast_node_free (root_node);
3229 timevar_pop (TV_GRAPHITE_CODE_GEN);
3230
3231 if (dump_file && (dump_flags & TDF_DETAILS))
3232 {
3233 loop_p loop;
3234 int num_no_dependency = 0;
3235
3236 FOR_EACH_LOOP (loop, 0)
3237 if (loop->can_be_parallel)
3238 num_no_dependency++;
3239
3240 fprintf (dump_file, "%d loops carried no dependency.\n",
3241 num_no_dependency);
3242 }
3243
3244 return !t.codegen_error_p ();
3245 }
3246
3247 #endif /* HAVE_isl */
3248