gcc/
[official-gcc.git] / gcc / graphite-isl-ast-to-gimple.c
blobb6ef13d5b373a51c0280f4d5fbaee49d440b4740
1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
3 Contributed by Roman Gareev <gareevroman@gmail.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
23 #ifdef HAVE_isl
24 #include <isl/set.h>
25 #include <isl/map.h>
26 #include <isl/union_map.h>
27 #include <isl/ast_build.h>
29 /* Since ISL-0.13, the extern is in val_gmp.h. */
30 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
31 extern "C" {
32 #endif
33 #include <isl/val_gmp.h>
34 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
36 #endif
37 #endif
39 #include "system.h"
40 #include "coretypes.h"
41 #include "alias.h"
42 #include "symtab.h"
43 #include "options.h"
44 #include "tree.h"
45 #include "fold-const.h"
46 #include "predict.h"
47 #include "tm.h"
48 #include "hard-reg-set.h"
49 #include "function.h"
50 #include "dominance.h"
51 #include "cfg.h"
52 #include "basic-block.h"
53 #include "tree-ssa-alias.h"
54 #include "internal-fn.h"
55 #include "gimple-expr.h"
56 #include "gimple.h"
57 #include "gimple-iterator.h"
58 #include "tree-ssa-loop.h"
59 #include "tree-pass.h"
60 #include "cfgloop.h"
61 #include "tree-data-ref.h"
62 #include "sese.h"
63 #include "tree-ssa-loop-manip.h"
64 #include "tree-scalar-evolution.h"
65 #include "gimple-ssa.h"
66 #include "tree-into-ssa.h"
67 #include <map>
69 #ifdef HAVE_isl
70 #include "graphite-poly.h"
71 #include "graphite-isl-ast-to-gimple.h"
73 /* This flag is set when an error occurred during the translation of
74 ISL AST to Gimple. */
76 static bool graphite_regenerate_error;
78 /* We always try to use signed 128 bit types, but fall back to smaller types
79 in case a platform does not provide types of these sizes. In the future we
80 should use isl to derive the optimal type for each subexpression. */
82 static int max_mode_int_precision =
83 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
84 static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
85 128 : max_mode_int_precision;
87 struct ast_build_info
89 ast_build_info()
90 : is_parallelizable(false)
91 { };
92 bool is_parallelizable;
95 /* Converts a GMP constant VAL to a tree and returns it. */
97 static tree
98 gmp_cst_to_tree (tree type, mpz_t val)
100 tree t = type ? type : integer_type_node;
101 mpz_t tmp;
103 mpz_init (tmp);
104 mpz_set (tmp, val);
105 wide_int wi = wi::from_mpz (t, tmp, true);
106 mpz_clear (tmp);
108 return wide_int_to_tree (t, wi);
111 /* Verifies properties that GRAPHITE should maintain during translation. */
113 static inline void
114 graphite_verify (void)
116 #ifdef ENABLE_CHECKING
117 verify_loop_structure ();
118 verify_loop_closed_ssa (true);
119 #endif
122 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
123 to corresponding trees. */
125 typedef std::map<isl_id *, tree> ivs_params;
127 /* Free all memory allocated for ISL's identifiers. */
129 void ivs_params_clear (ivs_params &ip)
131 std::map<isl_id *, tree>::iterator it;
132 for (it = ip.begin ();
133 it != ip.end (); it++)
135 isl_id_free (it->first);
139 static tree
140 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
141 ivs_params &ip);
143 /* Return the tree variable that corresponds to the given isl ast identifier
144 expression (an isl_ast_expr of type isl_ast_expr_id).
146 FIXME: We should replace blind conversation of id's type with derivation
147 of the optimal type when we get the corresponding isl support. Blindly
148 converting type sizes may be problematic when we switch to smaller
149 types. */
151 static tree
152 gcc_expression_from_isl_ast_expr_id (tree type,
153 __isl_keep isl_ast_expr *expr_id,
154 ivs_params &ip)
156 gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
157 isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
158 std::map<isl_id *, tree>::iterator res;
159 res = ip.find (tmp_isl_id);
160 isl_id_free (tmp_isl_id);
161 gcc_assert (res != ip.end () &&
162 "Could not map isl_id to tree expression");
163 isl_ast_expr_free (expr_id);
164 return fold_convert (type, res->second);
167 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
168 type TYPE. */
170 static tree
171 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
173 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
174 isl_val *val = isl_ast_expr_get_val (expr);
175 mpz_t val_mpz_t;
176 mpz_init (val_mpz_t);
177 tree res;
178 if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
179 res = NULL_TREE;
180 else
181 res = gmp_cst_to_tree (type, val_mpz_t);
182 isl_val_free (val);
183 isl_ast_expr_free (expr);
184 mpz_clear (val_mpz_t);
185 return res;
188 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
189 type TYPE. */
191 static tree
192 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
194 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
195 tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
196 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
197 tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
198 enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
199 isl_ast_expr_free (expr);
200 switch (expr_type)
202 case isl_ast_op_add:
203 return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
205 case isl_ast_op_sub:
206 return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
208 case isl_ast_op_mul:
209 return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
211 case isl_ast_op_div:
212 return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
214 case isl_ast_op_pdiv_q:
215 return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
217 case isl_ast_op_pdiv_r:
218 return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
220 case isl_ast_op_fdiv_q:
221 return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
223 case isl_ast_op_and:
224 return fold_build2 (TRUTH_ANDIF_EXPR, type,
225 tree_lhs_expr, tree_rhs_expr);
227 case isl_ast_op_or:
228 return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
230 case isl_ast_op_eq:
231 return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
233 case isl_ast_op_le:
234 return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
236 case isl_ast_op_lt:
237 return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
239 case isl_ast_op_ge:
240 return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
242 case isl_ast_op_gt:
243 return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
245 default:
246 gcc_unreachable ();
250 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
251 type TYPE. */
253 static tree
254 ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
256 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
257 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
258 tree tree_first_expr
259 = gcc_expression_from_isl_expression (type, arg_expr, ip);
260 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
261 tree tree_second_expr
262 = gcc_expression_from_isl_expression (type, arg_expr, ip);
263 arg_expr = isl_ast_expr_get_op_arg (expr, 2);
264 tree tree_third_expr
265 = gcc_expression_from_isl_expression (type, arg_expr, ip);
266 isl_ast_expr_free (expr);
267 return fold_build3 (COND_EXPR, type, tree_first_expr,
268 tree_second_expr, tree_third_expr);
271 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
272 type TYPE. */
274 static tree
275 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
277 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
278 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
279 tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
280 isl_ast_expr_free (expr);
281 return fold_build1 (NEGATE_EXPR, type, tree_expr);
284 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
285 to a GCC expression tree of type TYPE. */
287 static tree
288 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
290 enum tree_code op_code;
291 switch (isl_ast_expr_get_op_type (expr))
293 case isl_ast_op_max:
294 op_code = MAX_EXPR;
295 break;
297 case isl_ast_op_min:
298 op_code = MIN_EXPR;
299 break;
301 default:
302 gcc_unreachable ();
304 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
305 tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
306 int i;
307 for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
309 arg_expr = isl_ast_expr_get_op_arg (expr, i);
310 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
311 res = fold_build2 (op_code, type, res, t);
313 isl_ast_expr_free (expr);
314 return res;
318 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
319 type TYPE. */
321 static tree
322 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
323 ivs_params &ip)
325 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
326 switch (isl_ast_expr_get_op_type (expr))
328 /* These isl ast expressions are not supported yet. */
329 case isl_ast_op_error:
330 case isl_ast_op_call:
331 case isl_ast_op_and_then:
332 case isl_ast_op_or_else:
333 case isl_ast_op_select:
334 gcc_unreachable ();
336 case isl_ast_op_max:
337 case isl_ast_op_min:
338 return nary_op_to_tree (type, expr, ip);
340 case isl_ast_op_add:
341 case isl_ast_op_sub:
342 case isl_ast_op_mul:
343 case isl_ast_op_div:
344 case isl_ast_op_pdiv_q:
345 case isl_ast_op_pdiv_r:
346 case isl_ast_op_fdiv_q:
347 case isl_ast_op_and:
348 case isl_ast_op_or:
349 case isl_ast_op_eq:
350 case isl_ast_op_le:
351 case isl_ast_op_lt:
352 case isl_ast_op_ge:
353 case isl_ast_op_gt:
354 return binary_op_to_tree (type, expr, ip);
356 case isl_ast_op_minus:
357 return unary_op_to_tree (type, expr, ip);
359 case isl_ast_op_cond:
360 return ternary_op_to_tree (type, expr, ip);
362 default:
363 gcc_unreachable ();
366 return NULL_TREE;
369 /* Converts an ISL AST expression E back to a GCC expression tree of
370 type TYPE. */
372 static tree
373 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
374 ivs_params &ip)
376 switch (isl_ast_expr_get_type (expr))
378 case isl_ast_expr_id:
379 return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
381 case isl_ast_expr_int:
382 return gcc_expression_from_isl_expr_int (type, expr);
384 case isl_ast_expr_op:
385 return gcc_expression_from_isl_expr_op (type, expr, ip);
387 default:
388 gcc_unreachable ();
391 return NULL_TREE;
394 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
395 induction variable for the new LOOP. New LOOP is attached to CFG
396 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
397 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
398 ISL's scattering name to the induction variable created for the
399 loop of STMT. The new induction variable is inserted in the NEWIVS
400 vector and is of type TYPE. */
402 static struct loop *
403 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
404 loop_p outer, tree type, tree lb, tree ub,
405 ivs_params &ip)
407 isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
408 tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
409 tree ivvar = create_tmp_var (type, "graphite_IV");
410 tree iv, iv_after_increment;
411 loop_p loop = create_empty_loop_on_edge
412 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
413 outer ? outer : entry_edge->src->loop_father);
415 isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
416 isl_id *id = isl_ast_expr_get_id (for_iterator);
417 std::map<isl_id *, tree>::iterator res;
418 res = ip.find (id);
419 if (ip.count (id))
420 isl_id_free (res->first);
421 ip[id] = iv;
422 isl_ast_expr_free (for_iterator);
423 return loop;
426 static edge
427 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
428 edge next_e, ivs_params &ip);
430 /* Create the loop for a isl_ast_node_for.
432 - NEXT_E is the edge where new generated code should be attached. */
434 static edge
435 translate_isl_ast_for_loop (loop_p context_loop,
436 __isl_keep isl_ast_node *node_for, edge next_e,
437 tree type, tree lb, tree ub,
438 ivs_params &ip)
440 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
441 struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
442 type, lb, ub, ip);
443 edge last_e = single_exit (loop);
444 edge to_body = single_succ_edge (loop->header);
445 basic_block after = to_body->dest;
447 /* Create a basic block for loop close phi nodes. */
448 last_e = single_succ_edge (split_edge (last_e));
450 /* Translate the body of the loop. */
451 isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
452 next_e = translate_isl_ast (loop, for_body, to_body, ip);
453 isl_ast_node_free (for_body);
454 redirect_edge_succ_nodup (next_e, after);
455 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
457 if (flag_loop_parallelize_all)
459 isl_id *id = isl_ast_node_get_annotation (node_for);
460 gcc_assert (id);
461 ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
462 loop->can_be_parallel = for_info->is_parallelizable;
463 free (for_info);
464 isl_id_free (id);
467 return last_e;
470 /* We use this function to get the upper bound because of the form,
471 which is used by isl to represent loops:
473 for (iterator = init; cond; iterator += inc)
481 The loop condition is an arbitrary expression, which contains the
482 current loop iterator.
484 (e.g. iterator + 3 < B && C > iterator + A)
486 We have to know the upper bound of the iterator to generate a loop
487 in Gimple form. It can be obtained from the special representation
488 of the loop condition, which is generated by isl,
489 if the ast_build_atomic_upper_bound option is set. In this case,
490 isl generates a loop condition that consists of the current loop
491 iterator, + an operator (< or <=) and an expression not involving
492 the iterator, which is processed and returned by this function.
494 (e.g iterator <= upper-bound-expression-without-iterator) */
496 static __isl_give isl_ast_expr *
497 get_upper_bound (__isl_keep isl_ast_node *node_for)
499 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
500 isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
501 gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
502 isl_ast_expr *res;
503 switch (isl_ast_expr_get_op_type (for_cond))
505 case isl_ast_op_le:
506 res = isl_ast_expr_get_op_arg (for_cond, 1);
507 break;
509 case isl_ast_op_lt:
511 // (iterator < ub) => (iterator <= ub - 1)
512 isl_val *one =
513 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
514 isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
515 res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
516 break;
519 default:
520 gcc_unreachable ();
522 isl_ast_expr_free (for_cond);
523 return res;
526 /* All loops generated by create_empty_loop_on_edge have the form of
527 a post-test loop:
532 body of the loop;
533 } while (lower bound < upper bound);
535 We create a new if region protecting the loop to be executed, if
536 the execution count is zero (lower bound > upper bound). */
538 static edge
539 graphite_create_new_loop_guard (edge entry_edge,
540 __isl_keep isl_ast_node *node_for, tree *type,
541 tree *lb, tree *ub, ivs_params &ip)
543 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
544 tree cond_expr;
545 edge exit_edge;
547 *type =
548 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
549 isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
550 *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
551 isl_ast_expr *upper_bound = get_upper_bound (node_for);
552 *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
554 /* When ub is simply a constant or a parameter, use lb <= ub. */
555 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
556 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
557 else
559 tree one = (POINTER_TYPE_P (*type)
560 ? convert_to_ptrofftype (integer_one_node)
561 : fold_convert (*type, integer_one_node));
562 /* Adding +1 and using LT_EXPR helps with loop latches that have a
563 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
564 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
565 is true, even if we do not want this. However lb < ub + 1 is false,
566 as expected. */
567 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
568 : PLUS_EXPR, *type, *ub, one);
570 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
573 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
575 return exit_edge;
578 /* Translates an isl_ast_node_for to Gimple. */
580 static edge
581 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
582 edge next_e, ivs_params &ip)
584 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
585 tree type, lb, ub;
586 edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
587 &lb, &ub, ip);
588 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
590 translate_isl_ast_for_loop (context_loop, node, true_e,
591 type, lb, ub, ip);
592 return last_e;
595 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
596 variables of the loops around GBB in SESE.
598 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
599 chrec, we could consider using a map<int, tree> that maps loop ids to the
600 corresponding tree expressions. */
602 static void
603 build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb,
604 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
605 sese region)
607 gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
608 isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
609 int i;
610 isl_ast_expr *arg_expr;
611 for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
613 arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
614 tree type =
615 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
616 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
617 loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
618 iv_map[old_loop->num] = t;
623 /* Translates an isl_ast_node_user to Gimple.
625 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
627 static edge
628 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
629 edge next_e, ivs_params &ip)
631 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
632 isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
633 isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
634 gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
635 isl_id *name_id = isl_ast_expr_get_id (name_expr);
636 poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
637 gcc_assert (pbb);
638 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
639 vec<tree> iv_map;
640 isl_ast_expr_free (name_expr);
641 isl_id_free (name_id);
643 gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
644 "The entry block should not even appear within a scop");
646 int nb_loops = number_of_loops (cfun);
647 iv_map.create (nb_loops);
648 iv_map.safe_grow_cleared (nb_loops);
650 build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop));
651 isl_ast_expr_free (user_expr);
652 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
653 SCOP_REGION (pbb->scop), next_e,
654 iv_map,
655 &graphite_regenerate_error);
656 iv_map.release ();
657 mark_virtual_operands_for_renaming (cfun);
658 update_ssa (TODO_update_ssa);
659 return next_e;
662 /* Translates an isl_ast_node_block to Gimple. */
664 static edge
665 translate_isl_ast_node_block (loop_p context_loop,
666 __isl_keep isl_ast_node *node,
667 edge next_e, ivs_params &ip)
669 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
670 isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
671 int i;
672 for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
674 isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
675 next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
676 isl_ast_node_free (tmp_node);
678 isl_ast_node_list_free (node_list);
679 return next_e;
682 /* Creates a new if region corresponding to ISL's cond. */
684 static edge
685 graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
686 ivs_params &ip)
688 tree type =
689 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
690 tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
691 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
692 return exit_edge;
695 /* Translates an isl_ast_node_if to Gimple. */
697 static edge
698 translate_isl_ast_node_if (loop_p context_loop,
699 __isl_keep isl_ast_node *node,
700 edge next_e, ivs_params &ip)
702 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
703 isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
704 edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
706 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
707 isl_ast_node *then_node = isl_ast_node_if_get_then (node);
708 translate_isl_ast (context_loop, then_node, true_e, ip);
709 isl_ast_node_free (then_node);
711 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
712 isl_ast_node *else_node = isl_ast_node_if_get_else (node);
713 if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
714 translate_isl_ast (context_loop, else_node, false_e, ip);
715 isl_ast_node_free (else_node);
716 return last_e;
719 /* Translates an ISL AST node NODE to GCC representation in the
720 context of a SESE. */
722 static edge
723 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
724 edge next_e, ivs_params &ip)
726 switch (isl_ast_node_get_type (node))
728 case isl_ast_node_error:
729 gcc_unreachable ();
731 case isl_ast_node_for:
732 return translate_isl_ast_node_for (context_loop, node,
733 next_e, ip);
735 case isl_ast_node_if:
736 return translate_isl_ast_node_if (context_loop, node,
737 next_e, ip);
739 case isl_ast_node_user:
740 return translate_isl_ast_node_user (node, next_e, ip);
742 case isl_ast_node_block:
743 return translate_isl_ast_node_block (context_loop, node,
744 next_e, ip);
746 default:
747 gcc_unreachable ();
751 /* Prints NODE to FILE. */
753 void
754 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
755 __isl_keep isl_ctx *ctx)
757 isl_printer *prn = isl_printer_to_file (ctx, file);
758 prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
759 prn = isl_printer_print_ast_node (prn, node);
760 prn = isl_printer_print_str (prn, "\n");
761 isl_printer_free (prn);
764 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
766 static void
767 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
769 sese region = SCOP_REGION (scop);
770 unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
771 gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
772 unsigned i;
773 for (i = 0; i < nb_parameters; i++)
775 isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
776 ip[tmp_id] = SESE_PARAMS (region)[i];
781 /* Generates a build, which specifies the constraints on the parameters. */
783 static __isl_give isl_ast_build *
784 generate_isl_context (scop_p scop)
786 isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
787 return isl_ast_build_from_context (context_isl);
790 /* Get the maximal number of schedule dimensions in the scop SCOP. */
792 static
793 int get_max_schedule_dimensions (scop_p scop)
795 int i;
796 poly_bb_p pbb;
797 int schedule_dims = 0;
799 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
801 int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
802 if (pbb_schedule_dims > schedule_dims)
803 schedule_dims = pbb_schedule_dims;
806 return schedule_dims;
809 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
811 For schedules with different dimensionality, the isl AST generator can not
812 define an order and will just randomly choose an order. The solution to this
813 problem is to extend all schedules to the maximal number of schedule
814 dimensions (using '0's for the remaining values). */
816 static __isl_give isl_map *
817 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
819 int tmp_dims = isl_map_dim (schedule, isl_dim_out);
820 schedule =
821 isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
822 isl_val *zero =
823 isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
824 int i;
825 for (i = tmp_dims; i < nb_schedule_dims; i++)
827 schedule =
828 isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
830 isl_val_free (zero);
831 return schedule;
834 /* Set the separation_class option for unroll and jam. */
836 static __isl_give isl_union_map *
837 generate_luj_sepclass_opt (scop_p scop, __isl_take isl_union_set *domain,
838 int dim, int cl)
840 isl_map *map;
841 isl_space *space, *space_sep;
842 isl_ctx *ctx;
843 isl_union_map *mapu;
844 int nsched = get_max_schedule_dimensions (scop);
846 ctx = scop->ctx;
847 space_sep = isl_space_alloc (ctx, 0, 1, 1);
848 space_sep = isl_space_wrap (space_sep);
849 space_sep = isl_space_set_tuple_name (space_sep, isl_dim_set,
850 "separation_class");
851 space = isl_set_get_space (scop->context);
852 space_sep = isl_space_align_params (space_sep, isl_space_copy(space));
853 space = isl_space_map_from_domain_and_range (space, space_sep);
854 space = isl_space_add_dims (space,isl_dim_in, nsched);
855 map = isl_map_universe (space);
856 isl_map_fix_si (map,isl_dim_out,0,dim);
857 isl_map_fix_si (map,isl_dim_out,1,cl);
859 mapu = isl_union_map_intersect_domain (isl_union_map_from_map (map),
860 domain);
861 return (mapu);
864 /* Compute the separation class for loop unroll and jam. */
866 static __isl_give isl_union_set *
867 generate_luj_sepclass (scop_p scop)
869 int i;
870 poly_bb_p pbb;
871 isl_union_set *domain_isl;
873 domain_isl = isl_union_set_empty (isl_set_get_space (scop->context));
875 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
877 isl_set *bb_domain;
878 isl_set *bb_domain_s;
880 if (pbb->map_sepclass == NULL)
881 continue;
883 if (isl_set_is_empty (pbb->domain))
884 continue;
886 bb_domain = isl_set_copy (pbb->domain);
887 bb_domain_s = isl_set_apply (bb_domain, pbb->map_sepclass);
888 pbb->map_sepclass = NULL;
890 domain_isl =
891 isl_union_set_union (domain_isl, isl_union_set_from_set (bb_domain_s));
894 return domain_isl;
897 /* Set the AST built options for loop unroll and jam. */
899 static __isl_give isl_union_map *
900 generate_luj_options (scop_p scop)
902 isl_union_set *domain_isl;
903 isl_union_map *options_isl_ss;
904 isl_union_map *options_isl =
905 isl_union_map_empty (isl_set_get_space (scop->context));
906 int dim = get_max_schedule_dimensions (scop) - 1;
907 int dim1 = dim - PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH);
909 if (!flag_loop_unroll_jam)
910 return options_isl;
912 domain_isl = generate_luj_sepclass (scop);
914 options_isl_ss = generate_luj_sepclass_opt (scop, domain_isl, dim1, 0);
915 options_isl = isl_union_map_union (options_isl, options_isl_ss);
917 return options_isl;
920 /* Generates a schedule, which specifies an order used to
921 visit elements in a domain. */
923 static __isl_give isl_union_map *
924 generate_isl_schedule (scop_p scop)
926 int nb_schedule_dims = get_max_schedule_dimensions (scop);
927 int i;
928 poly_bb_p pbb;
929 isl_union_map *schedule_isl =
930 isl_union_map_empty (isl_set_get_space (scop->context));
932 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
934 /* Dead code elimination: when the domain of a PBB is empty,
935 don't generate code for the PBB. */
936 if (isl_set_is_empty (pbb->domain))
937 continue;
939 isl_map *bb_schedule = isl_map_copy (pbb->transformed);
940 bb_schedule = isl_map_intersect_domain (bb_schedule,
941 isl_set_copy (pbb->domain));
942 bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
943 schedule_isl =
944 isl_union_map_union (schedule_isl,
945 isl_union_map_from_map (bb_schedule));
947 return schedule_isl;
950 /* This method is executed before the construction of a for node. */
951 static __isl_give isl_id *
952 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
954 isl_union_map *dependences = (isl_union_map *) user;
955 ast_build_info *for_info = XNEW (struct ast_build_info);
956 isl_union_map *schedule = isl_ast_build_get_schedule (build);
957 isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
958 int dimension = isl_space_dim (schedule_space, isl_dim_out);
959 for_info->is_parallelizable =
960 !carries_deps (schedule, dependences, dimension);
961 isl_union_map_free (schedule);
962 isl_space_free (schedule_space);
963 isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
964 return id;
967 /* Set the separate option for all dimensions.
968 This helps to reduce control overhead.
969 Set the options for unroll and jam. */
971 static __isl_give isl_ast_build *
972 set_options (__isl_take isl_ast_build *control,
973 __isl_keep isl_union_map *schedule,
974 __isl_take isl_union_map *opt_luj)
976 isl_ctx *ctx = isl_union_map_get_ctx (schedule);
977 isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
978 range_space =
979 isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
980 isl_union_set *range =
981 isl_union_set_from_set (isl_set_universe (range_space));
982 isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
983 domain = isl_union_set_universe (domain);
984 isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
986 options = isl_union_map_union (options, opt_luj);
988 return isl_ast_build_set_options (control, options);
991 static __isl_give isl_ast_node *
992 scop_to_isl_ast (scop_p scop, ivs_params &ip)
994 /* Generate loop upper bounds that consist of the current loop iterator,
995 an operator (< or <=) and an expression not involving the iterator.
996 If this option is not set, then the current loop iterator may appear several
997 times in the upper bound. See the isl manual for more details. */
998 isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
1000 add_parameters_to_ivs_params (scop, ip);
1002 isl_union_map *options_luj = generate_luj_options (scop);
1004 isl_union_map *schedule_isl = generate_isl_schedule (scop);
1005 isl_ast_build *context_isl = generate_isl_context (scop);
1007 context_isl = set_options (context_isl, schedule_isl, options_luj);
1009 isl_union_map *dependences = NULL;
1010 if (flag_loop_parallelize_all)
1012 dependences = scop_get_dependences (scop);
1013 context_isl =
1014 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
1015 dependences);
1017 isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
1018 schedule_isl);
1019 if(dependences)
1020 isl_union_map_free (dependences);
1021 isl_ast_build_free (context_isl);
1022 return ast_isl;
1025 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1026 the given SCOP. Return true if code generation succeeded.
1028 FIXME: This is not yet a full implementation of the code generator
1029 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1031 bool
1032 graphite_regenerate_ast_isl (scop_p scop)
1034 loop_p context_loop;
1035 sese region = SCOP_REGION (scop);
1036 ifsese if_region = NULL;
1037 isl_ast_node *root_node;
1038 ivs_params ip;
1040 timevar_push (TV_GRAPHITE_CODE_GEN);
1041 graphite_regenerate_error = false;
1042 root_node = scop_to_isl_ast (scop, ip);
1044 if (dump_file && (dump_flags & TDF_DETAILS))
1046 fprintf (dump_file, "\nISL AST generated by ISL: \n");
1047 print_isl_ast_node (dump_file, root_node, scop->ctx);
1048 fprintf (dump_file, "\n");
1051 recompute_all_dominators ();
1052 graphite_verify ();
1054 if_region = move_sese_in_condition (region);
1055 sese_insert_phis_for_liveouts (region,
1056 if_region->region->exit->src,
1057 if_region->false_region->exit,
1058 if_region->true_region->exit);
1059 recompute_all_dominators ();
1060 graphite_verify ();
1062 context_loop = SESE_ENTRY (region)->src->loop_father;
1064 translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
1065 ip);
1067 mark_virtual_operands_for_renaming (cfun);
1068 update_ssa (TODO_update_ssa);
1070 graphite_verify ();
1071 scev_reset ();
1072 recompute_all_dominators ();
1073 graphite_verify ();
1075 if (graphite_regenerate_error)
1076 set_ifsese_condition (if_region, integer_zero_node);
1078 free (if_region->true_region);
1079 free (if_region->region);
1080 free (if_region);
1082 ivs_params_clear (ip);
1083 isl_ast_node_free (root_node);
1084 timevar_pop (TV_GRAPHITE_CODE_GEN);
1086 if (dump_file && (dump_flags & TDF_DETAILS))
1088 loop_p loop;
1089 int num_no_dependency = 0;
1091 FOR_EACH_LOOP (loop, 0)
1092 if (loop->can_be_parallel)
1093 num_no_dependency++;
1095 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1096 num_no_dependency);
1099 return !graphite_regenerate_error;
1101 #endif