1/* Translation of isl AST to Gimple.
2 Copyright (C) 2014-2023 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#define INCLUDE_ISL
22
23#include "config.h"
24
25#ifdef HAVE_isl
26
27#include "system.h"
28#include "coretypes.h"
29#include "backend.h"
30#include "cfghooks.h"
31#include "tree.h"
32#include "gimple.h"
33#include "ssa.h"
34#include "fold-const.h"
35#include "gimple-iterator.h"
36#include "gimple-fold.h"
37#include "gimplify.h"
38#include "gimplify-me.h"
39#include "tree-eh.h"
40#include "tree-ssa-loop.h"
41#include "tree-ssa-operands.h"
42#include "tree-ssa-propagate.h"
43#include "tree-pass.h"
44#include "cfgloop.h"
45#include "tree-data-ref.h"
46#include "tree-ssa-loop-manip.h"
47#include "tree-scalar-evolution.h"
48#include "gimple-ssa.h"
49#include "tree-phinodes.h"
50#include "tree-into-ssa.h"
51#include "ssa-iterators.h"
52#include "tree-cfg.h"
53#include "gimple-pretty-print.h"
54#include "cfganal.h"
55#include "value-prof.h"
56#include "tree-ssa.h"
57#include "tree-vectorizer.h"
58#include "graphite.h"
59
60struct ast_build_info
61{
62 ast_build_info()
63 : is_parallelizable(false)
64 { }
65 bool is_parallelizable;
66};
67
68/* IVS_PARAMS maps isl's scattering and parameter identifiers
69 to corresponding trees. */
70
71typedef hash_map<isl_id *, tree> ivs_params;
72
73/* Free all memory allocated for isl's identifiers. */
74
75static void ivs_params_clear (ivs_params &ip)
76{
77 for (auto it = ip.begin (); it != ip.end (); ++it)
78 isl_id_free ((*it).first);
79}
80
81/* Set the "separate" option for the schedule node. */
82
83static isl_schedule_node *
84set_separate_option (__isl_take isl_schedule_node *node, void *user)
85{
86 if (user)
87 return node;
88
89 if (isl_schedule_node_get_type (node) != isl_schedule_node_band)
90 return node;
91
92 /* Set the "separate" option unless it is set earlier to another option. */
93 if (isl_schedule_node_band_member_get_ast_loop_type (node, 0)
94 == isl_ast_loop_default)
95 return isl_schedule_node_band_member_set_ast_loop_type
96 (node, 0, isl_ast_loop_separate);
97
98 return node;
99}
100
101/* Print SCHEDULE under an AST form on file F. */
102
103void
104print_schedule_ast (FILE *f, __isl_keep isl_schedule *schedule, scop_p scop)
105{
106 isl_set *set = isl_set_params (isl_set_copy (scop->param_context));
107 isl_ast_build *context = isl_ast_build_from_context (set);
108 isl_ast_node *ast
109 = isl_ast_build_node_from_schedule (context, isl_schedule_copy (schedule));
110 isl_ast_build_free (context);
111 print_isl_ast (f, ast);
112 isl_ast_node_free (ast);
113}
114
115DEBUG_FUNCTION void
116debug_schedule_ast (__isl_keep isl_schedule *s, scop_p scop)
117{
118 print_schedule_ast (stderr, s, scop);
119}
120
121enum phi_node_kind
122{
123 unknown_phi,
124 loop_phi,
125 close_phi,
126 cond_phi
127};
128
129class translate_isl_ast_to_gimple
130{
131 public:
132 translate_isl_ast_to_gimple (sese_info_p r);
133 edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
134 edge next_e, ivs_params &ip);
135 edge translate_isl_ast_node_for (loop_p context_loop,
136 __isl_keep isl_ast_node *node,
137 edge next_e, ivs_params &ip);
138 edge translate_isl_ast_for_loop (loop_p context_loop,
139 __isl_keep isl_ast_node *node_for,
140 edge next_e,
141 tree type, tree lb, tree ub,
142 ivs_params &ip);
143 edge translate_isl_ast_node_if (loop_p context_loop,
144 __isl_keep isl_ast_node *node,
145 edge next_e, ivs_params &ip);
146 edge translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
147 edge next_e, ivs_params &ip);
148 edge translate_isl_ast_node_block (loop_p context_loop,
149 __isl_keep isl_ast_node *node,
150 edge next_e, ivs_params &ip);
151 tree unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
152 ivs_params &ip);
153 tree binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
154 ivs_params &ip);
155 tree ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
156 ivs_params &ip);
157 tree nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr,
158 ivs_params &ip);
159 tree gcc_expression_from_isl_expression (tree type,
160 __isl_take isl_ast_expr *,
161 ivs_params &ip);
162 tree gcc_expression_from_isl_ast_expr_id (tree type,
163 __isl_keep isl_ast_expr *expr_id,
164 ivs_params &ip);
165 widest_int widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr);
166 tree gcc_expression_from_isl_expr_int (tree type,
167 __isl_take isl_ast_expr *expr);
168 tree gcc_expression_from_isl_expr_op (tree type,
169 __isl_take isl_ast_expr *expr,
170 ivs_params &ip);
171 struct loop *graphite_create_new_loop (edge entry_edge,
172 __isl_keep isl_ast_node *node_for,
173 loop_p outer, tree type,
174 tree lb, tree ub, ivs_params &ip);
175 edge graphite_create_new_guard (edge entry_edge,
176 __isl_take isl_ast_expr *if_cond,
177 ivs_params &ip);
178 void build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
179 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
180 sese_l &region);
181 void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip);
182 __isl_give isl_ast_build *generate_isl_context (scop_p scop);
183
184 __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop);
185
186 tree get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
187 vec<tree> iv_map);
188 void graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
189 vec<tree> iv_map);
190 edge copy_bb_and_scalar_dependences (basic_block bb, edge next_e,
191 vec<tree> iv_map);
192 void set_rename (tree old_name, tree expr);
193 void gsi_insert_earliest (gimple_seq seq);
194 bool codegen_error_p () const { return codegen_error; }
195
196 void set_codegen_error ()
197 {
198 codegen_error = true;
199 gcc_assert (! flag_checking
200 || param_graphite_allow_codegen_errors);
201 }
202
203 bool is_constant (tree op) const
204 {
205 return TREE_CODE (op) == INTEGER_CST
206 || TREE_CODE (op) == REAL_CST
207 || TREE_CODE (op) == COMPLEX_CST
208 || TREE_CODE (op) == VECTOR_CST;
209 }
210
211private:
212 /* The region to be translated. */
213 sese_info_p region;
214
215 /* This flag is set when an error occurred during the translation of isl AST
216 to Gimple. */
217 bool codegen_error;
218
219 /* A vector of all the edges at if_condition merge points. */
220 auto_vec<edge, 2> merge_points;
221
222 tree graphite_expr_type;
223};
224
225translate_isl_ast_to_gimple::translate_isl_ast_to_gimple (sese_info_p r)
226 : region (r), codegen_error (false)
227{
228 /* We always try to use signed 128 bit types, but fall back to smaller types
229 in case a platform does not provide types of these sizes. In the future we
230 should use isl to derive the optimal type for each subexpression. */
231 int max_mode_int_precision
232 = GET_MODE_PRECISION (int_mode_for_size (MAX_FIXED_MODE_SIZE, 0).require ());
233 int graphite_expr_type_precision
234 = 128 <= max_mode_int_precision ? 128 : max_mode_int_precision;
235 graphite_expr_type
236 = build_nonstandard_integer_type (graphite_expr_type_precision, 0);
237}
238
239/* Return the tree variable that corresponds to the given isl ast identifier
240 expression (an isl_ast_expr of type isl_ast_expr_id).
241
242 FIXME: We should replace blind conversion of id's type with derivation
243 of the optimal type when we get the corresponding isl support. Blindly
244 converting type sizes may be problematic when we switch to smaller
245 types. */
246
247tree translate_isl_ast_to_gimple::
248gcc_expression_from_isl_ast_expr_id (tree type,
249 __isl_take isl_ast_expr *expr_id,
250 ivs_params &ip)
251{
252 gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
253 isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
254 tree *tp = ip.get (tmp_isl_id);
255 isl_id_free (tmp_isl_id);
256 gcc_assert (tp && "Could not map isl_id to tree expression");
257 isl_ast_expr_free (expr_id);
258 tree t = *tp;
259 if (useless_type_conversion_p (type, TREE_TYPE (t)))
260 return t;
261 if (POINTER_TYPE_P (TREE_TYPE (t))
262 && !POINTER_TYPE_P (type) && !ptrofftype_p (type))
263 t = fold_convert (sizetype, t);
264 return fold_convert (type, t);
265}
266
267/* Converts an isl_ast_expr_int expression E to a widest_int.
268 Raises a code generation error when the constant doesn't fit. */
269
270widest_int translate_isl_ast_to_gimple::
271widest_int_from_isl_expr_int (__isl_keep isl_ast_expr *expr)
272{
273 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
274 isl_val *val = isl_ast_expr_get_val (expr);
275 size_t n = isl_val_n_abs_num_chunks (val, sizeof (HOST_WIDE_INT));
276 HOST_WIDE_INT *chunks = XALLOCAVEC (HOST_WIDE_INT, n);
277 if (n > WIDEST_INT_MAX_ELTS
278 || isl_val_get_abs_num_chunks (val, sizeof (HOST_WIDE_INT), chunks) == -1)
279 {
280 isl_val_free (val);
281 set_codegen_error ();
282 return 0;
283 }
284 widest_int wi = widest_int::from_array (chunks, n, true);
285 if (isl_val_is_neg (val))
286 wi = -wi;
287 isl_val_free (val);
288 return wi;
289}
290
291/* Converts an isl_ast_expr_int expression E to a GCC expression tree of
292 type TYPE. Raises a code generation error when the constant doesn't fit. */
293
294tree translate_isl_ast_to_gimple::
295gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
296{
297 widest_int wi = widest_int_from_isl_expr_int (expr);
298 isl_ast_expr_free (expr);
299 if (codegen_error_p ())
300 return NULL_TREE;
301 if (wi::min_precision (wi, TYPE_SIGN (type)) > TYPE_PRECISION (type))
302 {
303 set_codegen_error ();
304 return NULL_TREE;
305 }
306 return wide_int_to_tree (type, wi);
307}
308
309/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
310 type TYPE. */
311
312tree translate_isl_ast_to_gimple::
313binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
314{
315 enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
316 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
317 tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
318 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
319 isl_ast_expr_free (expr);
320
321 /* From our constraint generation we may get modulo operations that
322 we cannot represent explicitely but that are no-ops for TYPE.
323 Elide those. */
324 if ((expr_type == isl_ast_op_pdiv_r
325 || expr_type == isl_ast_op_zdiv_r
326 || expr_type == isl_ast_op_add)
327 && isl_ast_expr_get_type (arg_expr) == isl_ast_expr_int
328 && (wi::exact_log2 (widest_int_from_isl_expr_int (arg_expr))
329 >= TYPE_PRECISION (type)))
330 {
331 isl_ast_expr_free (arg_expr);
332 return tree_lhs_expr;
333 }
334
335 tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
336 if (codegen_error_p ())
337 return NULL_TREE;
338
339 switch (expr_type)
340 {
341 case isl_ast_op_add:
342 return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
343
344 case isl_ast_op_sub:
345 return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
346
347 case isl_ast_op_mul:
348 return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
349
350 case isl_ast_op_div:
351 return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
352
353 case isl_ast_op_pdiv_q:
354 return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
355
356 case isl_ast_op_zdiv_r:
357 case isl_ast_op_pdiv_r:
358 return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
359
360 case isl_ast_op_fdiv_q:
361 return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
362
363 case isl_ast_op_and:
364 return fold_build2 (TRUTH_ANDIF_EXPR, type,
365 tree_lhs_expr, tree_rhs_expr);
366
367 case isl_ast_op_or:
368 return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
369
370 case isl_ast_op_eq:
371 return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
372
373 case isl_ast_op_le:
374 return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
375
376 case isl_ast_op_lt:
377 return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
378
379 case isl_ast_op_ge:
380 return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
381
382 case isl_ast_op_gt:
383 return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
384
385 default:
386 gcc_unreachable ();
387 }
388}
389
390/* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
391 type TYPE. */
392
393tree translate_isl_ast_to_gimple::
394ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
395{
396 enum isl_ast_op_type t = isl_ast_expr_get_op_type (expr);
397 gcc_assert (t == isl_ast_op_cond || t == isl_ast_op_select);
398 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
399 tree a = gcc_expression_from_isl_expression (type, arg_expr, ip);
400 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
401 tree b = gcc_expression_from_isl_expression (type, arg_expr, ip);
402 arg_expr = isl_ast_expr_get_op_arg (expr, 2);
403 tree c = gcc_expression_from_isl_expression (type, arg_expr, ip);
404 isl_ast_expr_free (expr);
405
406 if (codegen_error_p ())
407 return NULL_TREE;
408
409 return fold_build3 (COND_EXPR, type, a,
410 rewrite_to_non_trapping_overflow (b),
411 rewrite_to_non_trapping_overflow (c));
412}
413
414/* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
415 type TYPE. */
416
417tree translate_isl_ast_to_gimple::
418unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
419{
420 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
421 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
422 tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
423 isl_ast_expr_free (expr);
424 return codegen_error_p () ? NULL_TREE
425 : fold_build1 (NEGATE_EXPR, type, tree_expr);
426}
427
428/* Converts an isl_ast_expr_op expression E with unknown number of arguments
429 to a GCC expression tree of type TYPE. */
430
431tree translate_isl_ast_to_gimple::
432nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
433{
434 enum tree_code op_code;
435 switch (isl_ast_expr_get_op_type (expr))
436 {
437 case isl_ast_op_max:
438 op_code = MAX_EXPR;
439 break;
440
441 case isl_ast_op_min:
442 op_code = MIN_EXPR;
443 break;
444
445 default:
446 gcc_unreachable ();
447 }
448 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
449 tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
450
451 if (codegen_error_p ())
452 {
453 isl_ast_expr_free (expr);
454 return NULL_TREE;
455 }
456
457 int i;
458 for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
459 {
460 arg_expr = isl_ast_expr_get_op_arg (expr, i);
461 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
462
463 if (codegen_error_p ())
464 {
465 isl_ast_expr_free (expr);
466 return NULL_TREE;
467 }
468
469 res = fold_build2 (op_code, type, res, t);
470 }
471 isl_ast_expr_free (expr);
472 return res;
473}
474
475/* Converts an isl_ast_expr_op expression E to a GCC expression tree of
476 type TYPE. */
477
478tree translate_isl_ast_to_gimple::
479gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
480 ivs_params &ip)
481{
482 if (codegen_error_p ())
483 {
484 isl_ast_expr_free (expr);
485 return NULL_TREE;
486 }
487
488 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
489 switch (isl_ast_expr_get_op_type (expr))
490 {
491 /* These isl ast expressions are not supported yet. */
492 case isl_ast_op_error:
493 case isl_ast_op_call:
494 case isl_ast_op_and_then:
495 case isl_ast_op_or_else:
496 gcc_unreachable ();
497
498 case isl_ast_op_max:
499 case isl_ast_op_min:
500 return nary_op_to_tree (type, expr, ip);
501
502 case isl_ast_op_add:
503 case isl_ast_op_sub:
504 case isl_ast_op_mul:
505 case isl_ast_op_div:
506 case isl_ast_op_pdiv_q:
507 case isl_ast_op_pdiv_r:
508 case isl_ast_op_fdiv_q:
509 case isl_ast_op_zdiv_r:
510 case isl_ast_op_and:
511 case isl_ast_op_or:
512 case isl_ast_op_eq:
513 case isl_ast_op_le:
514 case isl_ast_op_lt:
515 case isl_ast_op_ge:
516 case isl_ast_op_gt:
517 return binary_op_to_tree (type, expr, ip);
518
519 case isl_ast_op_minus:
520 return unary_op_to_tree (type, expr, ip);
521
522 case isl_ast_op_cond:
523 case isl_ast_op_select:
524 return ternary_op_to_tree (type, expr, ip);
525
526 default:
527 gcc_unreachable ();
528 }
529}
530
531/* Converts an isl AST expression E back to a GCC expression tree of
532 type TYPE. */
533
534tree translate_isl_ast_to_gimple::
535gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
536 ivs_params &ip)
537{
538 if (codegen_error_p ())
539 {
540 isl_ast_expr_free (expr);
541 return NULL_TREE;
542 }
543
544 switch (isl_ast_expr_get_type (expr))
545 {
546 case isl_ast_expr_id:
547 return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
548
549 case isl_ast_expr_int:
550 return gcc_expression_from_isl_expr_int (type, expr);
551
552 case isl_ast_expr_op:
553 return gcc_expression_from_isl_expr_op (type, expr, ip);
554
555 default:
556 gcc_unreachable ();
557 }
558}
559
560/* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
561 induction variable for the new LOOP. New LOOP is attached to CFG
562 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
563 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
564 isl's scattering name to the induction variable created for the
565 loop of STMT. The new induction variable is inserted in the NEWIVS
566 vector and is of type TYPE. */
567
568struct loop *translate_isl_ast_to_gimple::
569graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
570 loop_p outer, tree type, tree lb, tree ub,
571 ivs_params &ip)
572{
573 isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
574 tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
575
576 /* To fail code generation, we generate wrong code until we discard it. */
577 if (codegen_error_p ())
578 stride = integer_zero_node;
579
580 tree ivvar = create_tmp_var (type, "graphite_IV");
581 tree iv, iv_after_increment;
582 loop_p loop = create_empty_loop_on_edge
583 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
584 outer ? outer : entry_edge->src->loop_father);
585
586 isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
587 isl_id *id = isl_ast_expr_get_id (for_iterator);
588 bool existed_p = ip.put (id, iv);
589 if (existed_p)
590 isl_id_free (id);
591 isl_ast_expr_free (for_iterator);
592 return loop;
593}
594
595/* Create the loop for a isl_ast_node_for.
596
597 - NEXT_E is the edge where new generated code should be attached. */
598
599edge translate_isl_ast_to_gimple::
600translate_isl_ast_for_loop (loop_p context_loop,
601 __isl_keep isl_ast_node *node_for, edge next_e,
602 tree type, tree lb, tree ub,
603 ivs_params &ip)
604{
605 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
606 struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
607 type, lb, ub, ip);
608 edge last_e = single_exit (loop);
609 edge to_body = single_succ_edge (loop->header);
610 basic_block after = to_body->dest;
611
612 /* Translate the body of the loop. */
613 isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
614 next_e = translate_isl_ast (loop, for_body, to_body, ip);
615 isl_ast_node_free (for_body);
616
617 /* Early return if we failed to translate loop body. */
618 if (!next_e || codegen_error_p ())
619 return NULL;
620
621 if (next_e->dest != after)
622 redirect_edge_succ_nodup (next_e, after);
623 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
624
625 if (flag_loop_parallelize_all)
626 {
627 isl_id *id = isl_ast_node_get_annotation (node_for);
628 gcc_assert (id);
629 ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
630 loop->can_be_parallel = for_info->is_parallelizable;
631 free (for_info);
632 isl_id_free (id);
633 }
634
635 return last_e;
636}
637
638/* We use this function to get the upper bound because of the form,
639 which is used by isl to represent loops:
640
641 for (iterator = init; cond; iterator += inc)
642
643 {
644
645 ...
646
647 }
648
649 The loop condition is an arbitrary expression, which contains the
650 current loop iterator.
651
652 (e.g. iterator + 3 < B && C > iterator + A)
653
654 We have to know the upper bound of the iterator to generate a loop
655 in Gimple form. It can be obtained from the special representation
656 of the loop condition, which is generated by isl,
657 if the ast_build_atomic_upper_bound option is set. In this case,
658 isl generates a loop condition that consists of the current loop
659 iterator, + an operator (< or <=) and an expression not involving
660 the iterator, which is processed and returned by this function.
661
662 (e.g iterator <= upper-bound-expression-without-iterator) */
663
664static __isl_give isl_ast_expr *
665get_upper_bound (__isl_keep isl_ast_node *node_for)
666{
667 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
668 isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
669 gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
670 isl_ast_expr *res;
671 switch (isl_ast_expr_get_op_type (for_cond))
672 {
673 case isl_ast_op_le:
674 res = isl_ast_expr_get_op_arg (for_cond, 1);
675 break;
676
677 case isl_ast_op_lt:
678 {
679 /* (iterator < ub) => (iterator <= ub - 1). */
680 isl_val *one =
681 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
682 isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
683 res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
684 break;
685 }
686
687 default:
688 gcc_unreachable ();
689 }
690 isl_ast_expr_free (for_cond);
691 return res;
692}
693
694/* Translates an isl_ast_node_for to Gimple. */
695
696edge translate_isl_ast_to_gimple::
697translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
698 edge next_e, ivs_params &ip)
699{
700 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
701 tree type = graphite_expr_type;
702
703 isl_ast_expr *for_init = isl_ast_node_for_get_init (node);
704 tree lb = gcc_expression_from_isl_expression (type, for_init, ip);
705 /* To fail code generation, we generate wrong code until we discard it. */
706 if (codegen_error_p ())
707 lb = integer_zero_node;
708
709 isl_ast_expr *upper_bound = get_upper_bound (node);
710 tree ub = gcc_expression_from_isl_expression (type, upper_bound, ip);
711 /* To fail code generation, we generate wrong code until we discard it. */
712 if (codegen_error_p ())
713 ub = integer_zero_node;
714
715 edge last_e = single_succ_edge (split_edge (next_e));
716
717 /* Compensate for the fact that we emit a do { } while loop from
718 a for ISL AST.
719 ??? We often miss constraints on niter because the SESE region
720 doesn't cover loop header copies. Ideally we'd add constraints
721 for all relevant dominating conditions. */
722 if (TREE_CODE (lb) == INTEGER_CST && TREE_CODE (ub) == INTEGER_CST
723 && tree_int_cst_compare (lb, ub) <= 0)
724 ;
725 else
726 {
727 tree one = build_one_cst (POINTER_TYPE_P (type) ? sizetype : type);
728 /* Adding +1 and using LT_EXPR helps with loop latches that have a
729 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
730 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
731 is true, even if we do not want this. However lb < ub + 1 is false,
732 as expected. */
733 tree ub_one = fold_build2 (POINTER_TYPE_P (type)
734 ? POINTER_PLUS_EXPR : PLUS_EXPR,
735 type, unshare_expr (ub), one);
736 create_empty_if_region_on_edge (next_e,
737 fold_build2 (LT_EXPR, boolean_type_node,
738 unshare_expr (lb), ub_one));
739 next_e = get_true_edge_from_guard_bb (next_e->dest);
740 }
741
742 translate_isl_ast_for_loop (context_loop, node, next_e,
743 type, lb, ub, ip);
744 return last_e;
745}
746
747/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
748 variables of the loops around GBB in SESE.
749
750 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
751 chrec, we could consider using a map<int, tree> that maps loop ids to the
752 corresponding tree expressions. */
753
754void translate_isl_ast_to_gimple::
755build_iv_mapping (vec<tree> iv_map, gimple_poly_bb_p gbb,
756 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
757 sese_l &region)
758{
759 gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
760 isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
761 int i;
762 isl_ast_expr *arg_expr;
763 for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
764 {
765 arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
766 tree type = graphite_expr_type;
767 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
768
769 /* To fail code generation, we generate wrong code until we discard it. */
770 if (codegen_error_p ())
771 t = integer_zero_node;
772
773 loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
774 iv_map[old_loop->num] = t;
775 }
776}
777
778/* Translates an isl_ast_node_user to Gimple.
779
780 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
781
782edge translate_isl_ast_to_gimple::
783translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
784 edge next_e, ivs_params &ip)
785{
786 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
787
788 isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
789 isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
790 gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
791
792 isl_id *name_id = isl_ast_expr_get_id (name_expr);
793 poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
794 gcc_assert (pbb);
795
796 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
797
798 isl_ast_expr_free (name_expr);
799 isl_id_free (name_id);
800
801 gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
802 "The entry block should not even appear within a scop");
803
804 const int nb_loops = number_of_loops (cfun);
805 vec<tree> iv_map;
806 iv_map.create (nb_loops);
807 iv_map.safe_grow_cleared (nb_loops, true);
808
809 build_iv_mapping (iv_map, gbb, user_expr, ip, pbb->scop->scop_info->region);
810 isl_ast_expr_free (user_expr);
811
812 basic_block old_bb = GBB_BB (gbb);
813 if (dump_file && (dump_flags & TDF_DETAILS))
814 {
815 fprintf (dump_file,
816 "[codegen] copying from bb_%d on edge (bb_%d, bb_%d)\n",
817 old_bb->index, next_e->src->index, next_e->dest->index);
818 print_loops_bb (dump_file, GBB_BB (gbb), 0, 3);
819 }
820
821 next_e = copy_bb_and_scalar_dependences (old_bb, next_e, iv_map);
822
823 iv_map.release ();
824
825 if (codegen_error_p ())
826 return NULL;
827
828 if (dump_file && (dump_flags & TDF_DETAILS))
829 {
830 fprintf (dump_file, "[codegen] (after copy) new basic block\n");
831 print_loops_bb (dump_file, next_e->src, 0, 3);
832 }
833
834 return next_e;
835}
836
837/* Translates an isl_ast_node_block to Gimple. */
838
839edge translate_isl_ast_to_gimple::
840translate_isl_ast_node_block (loop_p context_loop,
841 __isl_keep isl_ast_node *node,
842 edge next_e, ivs_params &ip)
843{
844 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
845 isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
846 int i;
847 for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
848 {
849 isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
850 next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
851 isl_ast_node_free (tmp_node);
852 }
853 isl_ast_node_list_free (node_list);
854 return next_e;
855}
856
857/* Creates a new if region corresponding to isl's cond. */
858
859edge translate_isl_ast_to_gimple::
860graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
861 ivs_params &ip)
862{
863 tree type = graphite_expr_type;
864 tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
865
866 /* To fail code generation, we generate wrong code until we discard it. */
867 if (codegen_error_p ())
868 cond_expr = integer_zero_node;
869
870 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
871 return exit_edge;
872}
873
874/* Translates an isl_ast_node_if to Gimple. */
875
876edge translate_isl_ast_to_gimple::
877translate_isl_ast_node_if (loop_p context_loop,
878 __isl_keep isl_ast_node *node,
879 edge next_e, ivs_params &ip)
880{
881 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
882 isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
883 edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
884 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
885 merge_points.safe_push (last_e);
886
887 isl_ast_node *then_node = isl_ast_node_if_get_then (node);
888 translate_isl_ast (context_loop, then_node, true_e, ip);
889 isl_ast_node_free (then_node);
890
891 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
892 isl_ast_node *else_node = isl_ast_node_if_get_else (node);
893 if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
894 translate_isl_ast (context_loop, else_node, false_e, ip);
895
896 isl_ast_node_free (else_node);
897 return last_e;
898}
899
900/* Translates an isl AST node NODE to GCC representation in the
901 context of a SESE. */
902
903edge translate_isl_ast_to_gimple::
904translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
905 edge next_e, ivs_params &ip)
906{
907 if (codegen_error_p ())
908 return NULL;
909
910 switch (isl_ast_node_get_type (node))
911 {
912 case isl_ast_node_error:
913 gcc_unreachable ();
914
915 case isl_ast_node_for:
916 return translate_isl_ast_node_for (context_loop, node,
917 next_e, ip);
918
919 case isl_ast_node_if:
920 return translate_isl_ast_node_if (context_loop, node,
921 next_e, ip);
922
923 case isl_ast_node_user:
924 return translate_isl_ast_node_user (node, next_e, ip);
925
926 case isl_ast_node_block:
927 return translate_isl_ast_node_block (context_loop, node,
928 next_e, ip);
929
930 case isl_ast_node_mark:
931 {
932 isl_ast_node *n = isl_ast_node_mark_get_node (node);
933 edge e = translate_isl_ast (context_loop, n, next_e, ip);
934 isl_ast_node_free (n);
935 return e;
936 }
937
938 default:
939 gcc_unreachable ();
940 }
941}
942
943/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR).
944 When OLD_NAME and EXPR are the same we assert. */
945
946void translate_isl_ast_to_gimple::
947set_rename (tree old_name, tree expr)
948{
949 if (dump_file)
950 {
951 fprintf (dump_file, "[codegen] setting rename: old_name = ");
952 print_generic_expr (dump_file, old_name);
953 fprintf (dump_file, ", new decl = ");
954 print_generic_expr (dump_file, expr);
955 fprintf (dump_file, "\n");
956 }
957 bool res = region->rename_map->put (old_name, expr);
958 gcc_assert (! res);
959}
960
961/* Return an iterator to the instructions comes last in the execution order.
962 Either GSI1 and GSI2 should belong to the same basic block or one of their
963 respective basic blocks should dominate the other. */
964
965gimple_stmt_iterator
966later_of_the_two (gimple_stmt_iterator gsi1, gimple_stmt_iterator gsi2)
967{
968 basic_block bb1 = gsi_bb (gsi1);
969 basic_block bb2 = gsi_bb (gsi2);
970
971 /* Find the iterator which is the latest. */
972 if (bb1 == bb2)
973 {
974 gimple *stmt1 = gsi_stmt (gsi1);
975 gimple *stmt2 = gsi_stmt (gsi2);
976
977 if (stmt1 != NULL && stmt2 != NULL)
978 {
979 bool is_phi1 = gimple_code (stmt1) == GIMPLE_PHI;
980 bool is_phi2 = gimple_code (stmt2) == GIMPLE_PHI;
981
982 if (is_phi1 != is_phi2)
983 return is_phi1 ? gsi2 : gsi1;
984 }
985
986 /* For empty basic blocks gsis point to the end of the sequence. Since
987 there is no operator== defined for gimple_stmt_iterator and for gsis
988 not pointing to a valid statement gsi_next would assert. */
989 gimple_stmt_iterator gsi = gsi1;
990 do {
991 if (gsi_stmt (gsi) == gsi_stmt (gsi2))
992 return gsi2;
993 gsi_next (&gsi);
994 } while (!gsi_end_p (gsi));
995
996 return gsi1;
997 }
998
999 /* Find the basic block closest to the basic block which defines stmt. */
1000 if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
1001 return gsi1;
1002
1003 gcc_assert (dominated_by_p (CDI_DOMINATORS, bb2, bb1));
1004 return gsi2;
1005}
1006
1007/* Insert each statement from SEQ at its earliest insertion p. */
1008
1009void translate_isl_ast_to_gimple::
1010gsi_insert_earliest (gimple_seq seq)
1011{
1012 update_modified_stmts (seq);
1013 sese_l &codegen_region = region->if_region->true_region->region;
1014 basic_block begin_bb = get_entry_bb (codegen_region);
1015
1016 /* Inserting the gimple statements in a vector because gimple_seq behave
1017 in strange ways when inserting the stmts from it into different basic
1018 blocks one at a time. */
1019 auto_vec<gimple *, 3> stmts;
1020 for (gimple_stmt_iterator gsi = gsi_start (seq); !gsi_end_p (gsi);
1021 gsi_next (&gsi))
1022 stmts.safe_push (gsi_stmt (gsi));
1023
1024 int i;
1025 gimple *use_stmt;
1026 FOR_EACH_VEC_ELT (stmts, i, use_stmt)
1027 {
1028 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
1029 gimple_stmt_iterator gsi_def_stmt = gsi_start_nondebug_bb (begin_bb);
1030
1031 use_operand_p use_p;
1032 ssa_op_iter op_iter;
1033 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, op_iter, SSA_OP_USE)
1034 {
1035 /* Iterator to the current def of use_p. For function parameters or
1036 anything where def is not found, insert at the beginning of the
1037 generated region. */
1038 gimple_stmt_iterator gsi_stmt = gsi_def_stmt;
1039
1040 tree op = USE_FROM_PTR (use_p);
1041 gimple *stmt = SSA_NAME_DEF_STMT (op);
1042 if (stmt && (gimple_code (stmt) != GIMPLE_NOP))
1043 gsi_stmt = gsi_for_stmt (stmt);
1044
1045 /* For region parameters, insert at the beginning of the generated
1046 region. */
1047 if (!bb_in_sese_p (gsi_bb (gsi_stmt), codegen_region))
1048 gsi_stmt = gsi_def_stmt;
1049
1050 gsi_def_stmt = later_of_the_two (gsi_stmt, gsi_def_stmt);
1051 }
1052
1053 if (!gsi_stmt (gsi_def_stmt))
1054 {
1055 gimple_stmt_iterator gsi = gsi_after_labels (gsi_bb (gsi_def_stmt));
1056 gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
1057 }
1058 else if (gimple_code (gsi_stmt (gsi_def_stmt)) == GIMPLE_PHI)
1059 {
1060 gimple_stmt_iterator bsi
1061 = gsi_start_nondebug_bb (gsi_bb (gsi_def_stmt));
1062 /* Insert right after the PHI statements. */
1063 gsi_insert_before (&bsi, use_stmt, GSI_NEW_STMT);
1064 }
1065 else
1066 gsi_insert_after (&gsi_def_stmt, use_stmt, GSI_NEW_STMT);
1067
1068 if (dump_file)
1069 {
1070 fprintf (dump_file, "[codegen] inserting statement in BB %d: ",
1071 gimple_bb (use_stmt)->index);
1072 print_gimple_stmt (dump_file, use_stmt, 0, TDF_VOPS | TDF_MEMSYMS);
1073 }
1074 }
1075}
1076
1077/* For ops which are scev_analyzeable, we can regenerate a new name from its
1078 scalar evolution around LOOP. */
1079
1080tree translate_isl_ast_to_gimple::
1081get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop,
1082 vec<tree> iv_map)
1083{
1084 tree scev = cached_scalar_evolution_in_region (region->region,
1085 loop, old_name);
1086
1087 /* At this point we should know the exact scev for each
1088 scalar SSA_NAME used in the scop: all the other scalar
1089 SSA_NAMEs should have been translated out of SSA using
1090 arrays with one element. */
1091 tree new_expr;
1092 if (chrec_contains_undetermined (scev))
1093 {
1094 set_codegen_error ();
1095 return build_zero_cst (TREE_TYPE (old_name));
1096 }
1097
1098 new_expr = chrec_apply_map (scev, iv_map);
1099
1100 /* The apply should produce an expression tree containing
1101 the uses of the new induction variables. We should be
1102 able to use new_expr instead of the old_name in the newly
1103 generated loop nest. */
1104 if (chrec_contains_undetermined (new_expr)
1105 || tree_contains_chrecs (new_expr, NULL))
1106 {
1107 set_codegen_error ();
1108 return build_zero_cst (TREE_TYPE (old_name));
1109 }
1110
1111 /* Replace the old_name with the new_expr. */
1112 return force_gimple_operand (unshare_expr (new_expr), stmts,
1113 true, NULL_TREE);
1114}
1115
1116
1117/* Return true if STMT should be copied from region to the new code-generated
1118 region. LABELs, CONDITIONS, induction-variables and region parameters need
1119 not be copied. */
1120
1121static bool
1122should_copy_to_new_region (gimple *stmt, sese_info_p region)
1123{
1124 /* Do not copy labels or conditions. */
1125 if (gimple_code (stmt) == GIMPLE_LABEL
1126 || gimple_code (stmt) == GIMPLE_COND)
1127 return false;
1128
1129 tree lhs;
1130 /* Do not copy induction variables. */
1131 if (is_gimple_assign (stmt)
1132 && (lhs = gimple_assign_lhs (stmt))
1133 && TREE_CODE (lhs) == SSA_NAME
1134 && scev_analyzable_p (lhs, region->region)
1135 /* But to code-generate liveouts - liveout PHI generation is
1136 in generic sese.cc code that cannot do code generation. */
1137 && ! bitmap_bit_p (region->liveout, SSA_NAME_VERSION (lhs)))
1138 return false;
1139
1140 return true;
1141}
1142
1143/* Duplicates the statements of basic block BB into basic block NEW_BB
1144 and compute the new induction variables according to the IV_MAP. */
1145
1146void translate_isl_ast_to_gimple::
1147graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
1148 vec<tree> iv_map)
1149{
1150 /* Iterator poining to the place where new statement (s) will be inserted. */
1151 gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
1152
1153 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1154 gsi_next (&gsi))
1155 {
1156 gimple *stmt = gsi_stmt (gsi);
1157 if (!should_copy_to_new_region (stmt, region))
1158 continue;
1159
1160 /* Create a new copy of STMT and duplicate STMT's virtual
1161 operands. */
1162 gimple *copy = gimple_copy (stmt);
1163
1164 /* Rather than not copying debug stmts we reset them.
1165 ??? Where we can rewrite uses without inserting new
1166 stmts we could simply do that. */
1167 if (is_gimple_debug (copy))
1168 {
1169 if (gimple_debug_bind_p (copy))
1170 gimple_debug_bind_reset_value (copy);
1171 else if (gimple_debug_source_bind_p (copy)
1172 || gimple_debug_nonbind_marker_p (copy))
1173 ;
1174 else
1175 gcc_unreachable ();
1176 }
1177
1178 maybe_duplicate_eh_stmt (copy, stmt);
1179 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1180
1181 /* Crete new names for each def in the copied stmt. */
1182 def_operand_p def_p;
1183 ssa_op_iter op_iter;
1184 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1185 {
1186 tree old_name = DEF_FROM_PTR (def_p);
1187 create_new_def_for (old_name, copy, def_p);
1188 }
1189
1190 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1191 if (dump_file)
1192 {
1193 fprintf (dump_file, "[codegen] inserting statement: ");
1194 print_gimple_stmt (dump_file, copy, 0);
1195 }
1196
1197 /* For each SCEV analyzable SSA_NAME, rename their usage. */
1198 ssa_op_iter iter;
1199 use_operand_p use_p;
1200 if (!is_gimple_debug (copy))
1201 {
1202 bool changed = false;
1203 FOR_EACH_SSA_USE_OPERAND (use_p, copy, iter, SSA_OP_USE)
1204 {
1205 tree old_name = USE_FROM_PTR (use_p);
1206
1207 if (TREE_CODE (old_name) != SSA_NAME
1208 || SSA_NAME_IS_DEFAULT_DEF (old_name)
1209 || ! scev_analyzable_p (old_name, region->region))
1210 continue;
1211
1212 gimple_seq stmts = NULL;
1213 tree new_name = get_rename_from_scev (old_name, &stmts,
1214 bb->loop_father, iv_map);
1215 if (! codegen_error_p ())
1216 gsi_insert_earliest (stmts);
1217 replace_exp (use_p, new_name);
1218 changed = true;
1219 }
1220 if (changed)
1221 fold_stmt_inplace (&gsi_tgt);
1222 }
1223
1224 update_stmt (copy);
1225 }
1226}
1227
1228
1229/* Copies BB and includes in the copied BB all the statements that can
1230 be reached following the use-def chains from the memory accesses,
1231 and returns the next edge following this new block. */
1232
1233edge translate_isl_ast_to_gimple::
1234copy_bb_and_scalar_dependences (basic_block bb, edge next_e, vec<tree> iv_map)
1235{
1236 basic_block new_bb = split_edge (next_e);
1237 gimple_stmt_iterator gsi_tgt = gsi_last_bb (new_bb);
1238 for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1239 gsi_next (&psi))
1240 {
1241 gphi *phi = psi.phi ();
1242 tree res = gimple_phi_result (phi);
1243 if (virtual_operand_p (res)
1244 || scev_analyzable_p (res, region->region))
1245 continue;
1246
1247 tree new_phi_def;
1248 tree *rename = region->rename_map->get (res);
1249 if (! rename)
1250 {
1251 new_phi_def = create_tmp_reg (TREE_TYPE (res));
1252 set_rename (res, new_phi_def);
1253 }
1254 else
1255 new_phi_def = *rename;
1256
1257 gassign *ass = gimple_build_assign (NULL_TREE, new_phi_def);
1258 create_new_def_for (res, ass, NULL);
1259 gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1260 }
1261
1262 graphite_copy_stmts_from_block (bb, new_bb, iv_map);
1263
1264 /* Insert out-of SSA copies on the original BB outgoing edges. */
1265 gsi_tgt = gsi_last_bb (new_bb);
1266 basic_block bb_for_succs = bb;
1267 if (bb_for_succs == bb_for_succs->loop_father->latch
1268 && bb_in_sese_p (bb_for_succs, region->region)
1269 && sese_trivially_empty_bb_p (bb_for_succs))
1270 bb_for_succs = NULL;
1271 while (bb_for_succs)
1272 {
1273 basic_block latch = NULL;
1274 edge_iterator ei;
1275 edge e;
1276 FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
1277 {
1278 for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
1279 gsi_next (&psi))
1280 {
1281 gphi *phi = psi.phi ();
1282 tree res = gimple_phi_result (phi);
1283 if (virtual_operand_p (res)
1284 || scev_analyzable_p (res, region->region))
1285 continue;
1286
1287 tree new_phi_def;
1288 tree *rename = region->rename_map->get (res);
1289 if (! rename)
1290 {
1291 new_phi_def = create_tmp_reg (TREE_TYPE (res));
1292 set_rename (res, new_phi_def);
1293 }
1294 else
1295 new_phi_def = *rename;
1296
1297 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
1298 if (TREE_CODE (arg) == SSA_NAME
1299 && scev_analyzable_p (arg, region->region))
1300 {
1301 gimple_seq stmts = NULL;
1302 tree new_name = get_rename_from_scev (arg, &stmts,
1303 bb->loop_father,
1304 iv_map);
1305 if (! codegen_error_p ())
1306 gsi_insert_earliest (stmts);
1307 arg = new_name;
1308 }
1309 gassign *ass = gimple_build_assign (new_phi_def, arg);
1310 gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1311 }
1312 if (e->dest == bb_for_succs->loop_father->latch
1313 && bb_in_sese_p (e->dest, region->region)
1314 && sese_trivially_empty_bb_p (e->dest))
1315 latch = e->dest;
1316 }
1317 bb_for_succs = latch;
1318 }
1319
1320 return single_succ_edge (new_bb);
1321}
1322
1323/* Add isl's parameter identifiers and corresponding trees to ivs_params. */
1324
1325void translate_isl_ast_to_gimple::
1326add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
1327{
1328 sese_info_p region = scop->scop_info;
1329 unsigned nb_parameters = isl_set_dim (scop->param_context, isl_dim_param);
1330 gcc_assert (nb_parameters == sese_nb_params (region));
1331 unsigned i;
1332 tree param;
1333 FOR_EACH_VEC_ELT (region->params, i, param)
1334 {
1335 isl_id *tmp_id = isl_set_get_dim_id (scop->param_context,
1336 isl_dim_param, i);
1337 bool existed_p = ip.put (tmp_id, param);
1338 gcc_assert (!existed_p);
1339 }
1340}
1341
1342
1343/* Generates a build, which specifies the constraints on the parameters. */
1344
1345__isl_give isl_ast_build *translate_isl_ast_to_gimple::
1346generate_isl_context (scop_p scop)
1347{
1348 isl_set *context_isl = isl_set_params (isl_set_copy (scop->param_context));
1349 return isl_ast_build_from_context (context_isl);
1350}
1351
1352/* This method is executed before the construction of a for node. */
1353__isl_give isl_id *
1354ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
1355{
1356 isl_union_map *dependences = (isl_union_map *) user;
1357 ast_build_info *for_info = XNEW (struct ast_build_info);
1358 isl_union_map *schedule = isl_ast_build_get_schedule (build);
1359 isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
1360 int dimension = isl_space_dim (schedule_space, isl_dim_out);
1361 for_info->is_parallelizable =
1362 !carries_deps (schedule, dependences, dimension);
1363 isl_union_map_free (schedule);
1364 isl_space_free (schedule_space);
1365 isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
1366 return id;
1367}
1368
1369/* Generate isl AST from schedule of SCOP. */
1370
1371__isl_give isl_ast_node *translate_isl_ast_to_gimple::
1372scop_to_isl_ast (scop_p scop)
1373{
1374 int old_err = isl_options_get_on_error (scop->isl_context);
1375 int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
1376 int max_operations = param_max_isl_operations;
1377 if (max_operations)
1378 isl_ctx_set_max_operations (scop->isl_context, max_operations);
1379 isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
1380
1381 gcc_assert (scop->transformed_schedule);
1382
1383 /* Set the separate option to reduce control flow overhead. */
1384 isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up
1385 (isl_schedule_copy (scop->transformed_schedule), set_separate_option, NULL);
1386 isl_ast_build *context_isl = generate_isl_context (scop);
1387
1388 if (flag_loop_parallelize_all)
1389 {
1390 scop_get_dependences (scop);
1391 context_isl =
1392 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
1393 scop->dependence);
1394 }
1395
1396 isl_ast_node *ast_isl = isl_ast_build_node_from_schedule
1397 (context_isl, schedule);
1398 isl_ast_build_free (context_isl);
1399
1400 isl_options_set_on_error (scop->isl_context, old_err);
1401 isl_ctx_reset_operations (scop->isl_context);
1402 isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
1403 if (isl_ctx_last_error (scop->isl_context) != isl_error_none)
1404 {
1405 if (dump_enabled_p ())
1406 {
1407 dump_user_location_t loc = find_loop_location
1408 (scop->scop_info->region.entry->dest->loop_father);
1409 if (isl_ctx_last_error (scop->isl_context) == isl_error_quota)
1410 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1411 "loop nest not optimized, AST generation timed out "
1412 "after %d operations [--param max-isl-operations]\n",
1413 max_operations);
1414 else
1415 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1416 "loop nest not optimized, ISL AST generation "
1417 "signalled an error\n");
1418 }
1419 isl_ast_node_free (ast_isl);
1420 return NULL;
1421 }
1422
1423 return ast_isl;
1424}
1425
1426/* Generate out-of-SSA copies for the entry edge FALSE_ENTRY/TRUE_ENTRY
1427 in REGION. */
1428
1429static void
1430generate_entry_out_of_ssa_copies (edge false_entry,
1431 edge true_entry,
1432 sese_info_p region)
1433{
1434 gimple_stmt_iterator gsi_tgt = gsi_start_bb (true_entry->dest);
1435 for (gphi_iterator psi = gsi_start_phis (false_entry->dest);
1436 !gsi_end_p (psi); gsi_next (&psi))
1437 {
1438 gphi *phi = psi.phi ();
1439 tree res = gimple_phi_result (phi);
1440 if (virtual_operand_p (res))
1441 continue;
1442 /* When there's no out-of-SSA var registered do not bother
1443 to create one. */
1444 tree *rename = region->rename_map->get (res);
1445 if (! rename)
1446 continue;
1447 tree new_phi_def = *rename;
1448 gassign *ass = gimple_build_assign (new_phi_def,
1449 PHI_ARG_DEF_FROM_EDGE (phi,
1450 false_entry));
1451 gsi_insert_after (&gsi_tgt, ass, GSI_NEW_STMT);
1452 }
1453}
1454
1455/* GIMPLE Loop Generator: generates loops in GIMPLE form for the given SCOP.
1456 Return true if code generation succeeded. */
1457
1458bool
1459graphite_regenerate_ast_isl (scop_p scop)
1460{
1461 sese_info_p region = scop->scop_info;
1462 translate_isl_ast_to_gimple t (region);
1463
1464 ifsese if_region = NULL;
1465 isl_ast_node *root_node;
1466 ivs_params ip;
1467
1468 timevar_push (TV_GRAPHITE_CODE_GEN);
1469 t.add_parameters_to_ivs_params (scop, ip);
1470 root_node = t.scop_to_isl_ast (scop);
1471 if (! root_node)
1472 {
1473 ivs_params_clear (ip);
1474 timevar_pop (TV_GRAPHITE_CODE_GEN);
1475 return false;
1476 }
1477
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1479 {
1480 fprintf (dump_file, "[scheduler] original schedule:\n");
1481 print_isl_schedule (dump_file, scop->original_schedule);
1482 fprintf (dump_file, "[scheduler] isl transformed schedule:\n");
1483 print_isl_schedule (dump_file, scop->transformed_schedule);
1484
1485 fprintf (dump_file, "[scheduler] original ast:\n");
1486 print_schedule_ast (dump_file, scop->original_schedule, scop);
1487 fprintf (dump_file, "[scheduler] AST generated by isl:\n");
1488 print_isl_ast (dump_file, root_node);
1489 }
1490
1491 if_region = move_sese_in_condition (region);
1492 region->if_region = if_region;
1493
1494 loop_p context_loop = region->region.entry->src->loop_father;
1495 edge e = single_succ_edge (if_region->true_region->region.entry->dest);
1496 basic_block bb = split_edge (e);
1497
1498 /* Update the true_region exit edge. */
1499 region->if_region->true_region->region.exit = single_succ_edge (bb);
1500
1501 t.translate_isl_ast (context_loop, root_node, e, ip);
1502 if (! t.codegen_error_p ())
1503 {
1504 generate_entry_out_of_ssa_copies (if_region->false_region->region.entry,
1505 if_region->true_region->region.entry,
1506 region);
1507 sese_insert_phis_for_liveouts (region,
1508 if_region->region->region.exit->src,
1509 if_region->false_region->region.exit,
1510 if_region->true_region->region.exit);
1511 if (dump_file)
1512 fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n");
1513 }
1514
1515 if (t.codegen_error_p ())
1516 {
1517 if (dump_enabled_p ())
1518 {
1519 dump_user_location_t loc = find_loop_location
1520 (scop->scop_info->region.entry->dest->loop_father);
1521 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1522 "loop nest not optimized, code generation error\n");
1523 }
1524
1525 /* Remove the unreachable region. */
1526 remove_edge_and_dominated_blocks (if_region->true_region->region.entry);
1527 basic_block ifb = if_region->false_region->region.entry->src;
1528 gimple_stmt_iterator gsi = gsi_last_bb (ifb);
1529 gsi_remove (&gsi, true);
1530 if_region->false_region->region.entry->flags &= ~EDGE_FALSE_VALUE;
1531 if_region->false_region->region.entry->flags |= EDGE_FALLTHRU;
1532 /* remove_edge_and_dominated_blocks marks loops for removal but
1533 doesn't actually remove them (fix that...). */
1534 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1535 if (!loop->header)
1536 delete_loop (loop);
1537 }
1538
1539 /* We are delaying SSA update to after code-generating all SCOPs.
1540 This is because we analyzed DRs and parameters on the unmodified
1541 IL and thus rely on SSA update to pick up new dominating definitions
1542 from for example SESE liveout PHIs. This is also for efficiency
1543 as SSA update does work depending on the size of the function. */
1544
1545 free (if_region->true_region);
1546 free (if_region->region);
1547 free (if_region);
1548
1549 ivs_params_clear (ip);
1550 isl_ast_node_free (root_node);
1551 timevar_pop (TV_GRAPHITE_CODE_GEN);
1552
1553 return !t.codegen_error_p ();
1554}
1555
1556#endif /* HAVE_isl */
1557

source code of gcc/graphite-isl-ast-to-gimple.cc