Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-isl-ast-to-gimple.c @ 111:04ced10e8804

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