2014-12-12 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / graphite-isl-ast-to-gimple.c
blob456b24e76511e8ea9b4ff57ea512a2a49a4e9865
1 /* Translation of ISL AST to Gimple.
2 Copyright (C) 2014 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 "tree.h"
42 #include "predict.h"
43 #include "vec.h"
44 #include "hashtab.h"
45 #include "hash-set.h"
46 #include "machmode.h"
47 #include "tm.h"
48 #include "hard-reg-set.h"
49 #include "input.h"
50 #include "function.h"
51 #include "dominance.h"
52 #include "cfg.h"
53 #include "basic-block.h"
54 #include "tree-ssa-alias.h"
55 #include "internal-fn.h"
56 #include "gimple-expr.h"
57 #include "is-a.h"
58 #include "gimple.h"
59 #include "gimple-iterator.h"
60 #include "tree-ssa-loop.h"
61 #include "tree-pass.h"
62 #include "cfgloop.h"
63 #include "tree-data-ref.h"
64 #include "sese.h"
65 #include "tree-ssa-loop-manip.h"
66 #include "tree-scalar-evolution.h"
67 #include "gimple-ssa.h"
68 #include "tree-into-ssa.h"
69 #include <map>
71 #ifdef HAVE_isl
72 #include "graphite-poly.h"
73 #include "graphite-isl-ast-to-gimple.h"
75 /* This flag is set when an error occurred during the translation of
76 ISL AST to Gimple. */
78 static bool graphite_regenerate_error;
80 /* We always try to use signed 128 bit types, but fall back to smaller types
81 in case a platform does not provide types of these sizes. In the future we
82 should use isl to derive the optimal type for each subexpression. */
84 static int max_mode_int_precision =
85 GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0));
86 static int graphite_expression_type_precision = 128 <= max_mode_int_precision ?
87 128 : max_mode_int_precision;
89 struct ast_build_info
91 ast_build_info()
92 : is_parallelizable(false)
93 { };
94 bool is_parallelizable;
97 /* Converts a GMP constant VAL to a tree and returns it. */
99 static tree
100 gmp_cst_to_tree (tree type, mpz_t val)
102 tree t = type ? type : integer_type_node;
103 mpz_t tmp;
105 mpz_init (tmp);
106 mpz_set (tmp, val);
107 wide_int wi = wi::from_mpz (t, tmp, true);
108 mpz_clear (tmp);
110 return wide_int_to_tree (t, wi);
113 /* Verifies properties that GRAPHITE should maintain during translation. */
115 static inline void
116 graphite_verify (void)
118 #ifdef ENABLE_CHECKING
119 verify_loop_structure ();
120 verify_loop_closed_ssa (true);
121 #endif
124 /* IVS_PARAMS maps ISL's scattering and parameter identifiers
125 to corresponding trees. */
127 typedef std::map<isl_id *, tree> ivs_params;
129 /* Free all memory allocated for ISL's identifiers. */
131 void ivs_params_clear (ivs_params &ip)
133 std::map<isl_id *, tree>::iterator it;
134 for (it = ip.begin ();
135 it != ip.end (); it++)
137 isl_id_free (it->first);
141 static tree
142 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *,
143 ivs_params &ip);
145 /* Return the tree variable that corresponds to the given isl ast identifier
146 expression (an isl_ast_expr of type isl_ast_expr_id).
148 FIXME: We should replace blind conversation of id's type with derivation
149 of the optimal type when we get the corresponding isl support. Blindly
150 converting type sizes may be problematic when we switch to smaller
151 types. */
153 static tree
154 gcc_expression_from_isl_ast_expr_id (tree type,
155 __isl_keep isl_ast_expr *expr_id,
156 ivs_params &ip)
158 gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id);
159 isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id);
160 std::map<isl_id *, tree>::iterator res;
161 res = ip.find (tmp_isl_id);
162 isl_id_free (tmp_isl_id);
163 gcc_assert (res != ip.end () &&
164 "Could not map isl_id to tree expression");
165 isl_ast_expr_free (expr_id);
166 return fold_convert (type, res->second);
169 /* Converts an isl_ast_expr_int expression E to a GCC expression tree of
170 type TYPE. */
172 static tree
173 gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr)
175 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int);
176 isl_val *val = isl_ast_expr_get_val (expr);
177 mpz_t val_mpz_t;
178 mpz_init (val_mpz_t);
179 tree res;
180 if (isl_val_get_num_gmp (val, val_mpz_t) == -1)
181 res = NULL_TREE;
182 else
183 res = gmp_cst_to_tree (type, val_mpz_t);
184 isl_val_free (val);
185 isl_ast_expr_free (expr);
186 mpz_clear (val_mpz_t);
187 return res;
190 /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of
191 type TYPE. */
193 static tree
194 binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
196 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
197 tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
198 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
199 tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
200 enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr);
201 isl_ast_expr_free (expr);
202 switch (expr_type)
204 case isl_ast_op_add:
205 return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
207 case isl_ast_op_sub:
208 return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr);
210 case isl_ast_op_mul:
211 return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
213 case isl_ast_op_div:
214 return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
216 case isl_ast_op_pdiv_q:
217 return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
219 case isl_ast_op_pdiv_r:
220 return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr);
222 case isl_ast_op_fdiv_q:
223 return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr);
225 case isl_ast_op_and:
226 return fold_build2 (TRUTH_ANDIF_EXPR, type,
227 tree_lhs_expr, tree_rhs_expr);
229 case isl_ast_op_or:
230 return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr);
232 case isl_ast_op_eq:
233 return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
235 case isl_ast_op_le:
236 return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
238 case isl_ast_op_lt:
239 return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
241 case isl_ast_op_ge:
242 return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
244 case isl_ast_op_gt:
245 return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr);
247 default:
248 gcc_unreachable ();
252 /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of
253 type TYPE. */
255 static tree
256 ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
258 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
259 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
260 tree tree_first_expr
261 = gcc_expression_from_isl_expression (type, arg_expr, ip);
262 arg_expr = isl_ast_expr_get_op_arg (expr, 1);
263 tree tree_second_expr
264 = gcc_expression_from_isl_expression (type, arg_expr, ip);
265 arg_expr = isl_ast_expr_get_op_arg (expr, 2);
266 tree tree_third_expr
267 = gcc_expression_from_isl_expression (type, arg_expr, ip);
268 isl_ast_expr_free (expr);
269 return fold_build3 (COND_EXPR, type, tree_first_expr,
270 tree_second_expr, tree_third_expr);
273 /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of
274 type TYPE. */
276 static tree
277 unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
279 gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus);
280 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
281 tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip);
282 isl_ast_expr_free (expr);
283 return fold_build1 (NEGATE_EXPR, type, tree_expr);
286 /* Converts an isl_ast_expr_op expression E with unknown number of arguments
287 to a GCC expression tree of type TYPE. */
289 static tree
290 nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip)
292 enum tree_code op_code;
293 switch (isl_ast_expr_get_op_type (expr))
295 case isl_ast_op_max:
296 op_code = MAX_EXPR;
297 break;
299 case isl_ast_op_min:
300 op_code = MIN_EXPR;
301 break;
303 default:
304 gcc_unreachable ();
306 isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0);
307 tree res = gcc_expression_from_isl_expression (type, arg_expr, ip);
308 int i;
309 for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++)
311 arg_expr = isl_ast_expr_get_op_arg (expr, i);
312 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
313 res = fold_build2 (op_code, type, res, t);
315 isl_ast_expr_free (expr);
316 return res;
320 /* Converts an isl_ast_expr_op expression E to a GCC expression tree of
321 type TYPE. */
323 static tree
324 gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr,
325 ivs_params &ip)
327 gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op);
328 switch (isl_ast_expr_get_op_type (expr))
330 /* These isl ast expressions are not supported yet. */
331 case isl_ast_op_error:
332 case isl_ast_op_call:
333 case isl_ast_op_and_then:
334 case isl_ast_op_or_else:
335 case isl_ast_op_select:
336 gcc_unreachable ();
338 case isl_ast_op_max:
339 case isl_ast_op_min:
340 return nary_op_to_tree (type, expr, ip);
342 case isl_ast_op_add:
343 case isl_ast_op_sub:
344 case isl_ast_op_mul:
345 case isl_ast_op_div:
346 case isl_ast_op_pdiv_q:
347 case isl_ast_op_pdiv_r:
348 case isl_ast_op_fdiv_q:
349 case isl_ast_op_and:
350 case isl_ast_op_or:
351 case isl_ast_op_eq:
352 case isl_ast_op_le:
353 case isl_ast_op_lt:
354 case isl_ast_op_ge:
355 case isl_ast_op_gt:
356 return binary_op_to_tree (type, expr, ip);
358 case isl_ast_op_minus:
359 return unary_op_to_tree (type, expr, ip);
361 case isl_ast_op_cond:
362 return ternary_op_to_tree (type, expr, ip);
364 default:
365 gcc_unreachable ();
368 return NULL_TREE;
371 /* Converts an ISL AST expression E back to a GCC expression tree of
372 type TYPE. */
374 static tree
375 gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr,
376 ivs_params &ip)
378 switch (isl_ast_expr_get_type (expr))
380 case isl_ast_expr_id:
381 return gcc_expression_from_isl_ast_expr_id (type, expr, ip);
383 case isl_ast_expr_int:
384 return gcc_expression_from_isl_expr_int (type, expr);
386 case isl_ast_expr_op:
387 return gcc_expression_from_isl_expr_op (type, expr, ip);
389 default:
390 gcc_unreachable ();
393 return NULL_TREE;
396 /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an
397 induction variable for the new LOOP. New LOOP is attached to CFG
398 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
399 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
400 ISL's scattering name to the induction variable created for the
401 loop of STMT. The new induction variable is inserted in the NEWIVS
402 vector and is of type TYPE. */
404 static struct loop *
405 graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for,
406 loop_p outer, tree type, tree lb, tree ub,
407 ivs_params &ip)
409 isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
410 tree stride = gcc_expression_from_isl_expression (type, for_inc, ip);
411 tree ivvar = create_tmp_var (type, "graphite_IV");
412 tree iv, iv_after_increment;
413 loop_p loop = create_empty_loop_on_edge
414 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
415 outer ? outer : entry_edge->src->loop_father);
417 isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
418 isl_id *id = isl_ast_expr_get_id (for_iterator);
419 std::map<isl_id *, tree>::iterator res;
420 res = ip.find (id);
421 if (ip.count (id))
422 isl_id_free (res->first);
423 ip[id] = iv;
424 isl_ast_expr_free (for_iterator);
425 return loop;
428 static edge
429 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
430 edge next_e, ivs_params &ip);
432 /* Create the loop for a isl_ast_node_for.
434 - NEXT_E is the edge where new generated code should be attached. */
436 static edge
437 translate_isl_ast_for_loop (loop_p context_loop,
438 __isl_keep isl_ast_node *node_for, edge next_e,
439 tree type, tree lb, tree ub,
440 ivs_params &ip)
442 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
443 struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop,
444 type, lb, ub, ip);
445 edge last_e = single_exit (loop);
446 edge to_body = single_succ_edge (loop->header);
447 basic_block after = to_body->dest;
449 /* Create a basic block for loop close phi nodes. */
450 last_e = single_succ_edge (split_edge (last_e));
452 /* Translate the body of the loop. */
453 isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
454 next_e = translate_isl_ast (loop, for_body, to_body, ip);
455 isl_ast_node_free (for_body);
456 redirect_edge_succ_nodup (next_e, after);
457 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
459 if (flag_loop_parallelize_all)
461 isl_id *id = isl_ast_node_get_annotation (node_for);
462 gcc_assert (id);
463 ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id);
464 loop->can_be_parallel = for_info->is_parallelizable;
465 free (for_info);
466 isl_id_free (id);
469 return last_e;
472 /* We use this function to get the upper bound because of the form,
473 which is used by isl to represent loops:
475 for (iterator = init; cond; iterator += inc)
483 The loop condition is an arbitrary expression, which contains the
484 current loop iterator.
486 (e.g. iterator + 3 < B && C > iterator + A)
488 We have to know the upper bound of the iterator to generate a loop
489 in Gimple form. It can be obtained from the special representation
490 of the loop condition, which is generated by isl,
491 if the ast_build_atomic_upper_bound option is set. In this case,
492 isl generates a loop condition that consists of the current loop
493 iterator, + an operator (< or <=) and an expression not involving
494 the iterator, which is processed and returned by this function.
496 (e.g iterator <= upper-bound-expression-without-iterator) */
498 static __isl_give isl_ast_expr *
499 get_upper_bound (__isl_keep isl_ast_node *node_for)
501 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
502 isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
503 gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op);
504 isl_ast_expr *res;
505 switch (isl_ast_expr_get_op_type (for_cond))
507 case isl_ast_op_le:
508 res = isl_ast_expr_get_op_arg (for_cond, 1);
509 break;
511 case isl_ast_op_lt:
513 // (iterator < ub) => (iterator <= ub - 1)
514 isl_val *one =
515 isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1);
516 isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1);
517 res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one));
518 break;
521 default:
522 gcc_unreachable ();
524 isl_ast_expr_free (for_cond);
525 return res;
528 /* All loops generated by create_empty_loop_on_edge have the form of
529 a post-test loop:
534 body of the loop;
535 } while (lower bound < upper bound);
537 We create a new if region protecting the loop to be executed, if
538 the execution count is zero (lower bound > upper bound). */
540 static edge
541 graphite_create_new_loop_guard (edge entry_edge,
542 __isl_keep isl_ast_node *node_for, tree *type,
543 tree *lb, tree *ub, ivs_params &ip)
545 gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for);
546 tree cond_expr;
547 edge exit_edge;
549 *type =
550 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
551 isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
552 *lb = gcc_expression_from_isl_expression (*type, for_init, ip);
553 isl_ast_expr *upper_bound = get_upper_bound (node_for);
554 *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip);
556 /* When ub is simply a constant or a parameter, use lb <= ub. */
557 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
558 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
559 else
561 tree one = (POINTER_TYPE_P (*type)
562 ? convert_to_ptrofftype (integer_one_node)
563 : fold_convert (*type, integer_one_node));
564 /* Adding +1 and using LT_EXPR helps with loop latches that have a
565 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this
566 becomes 2^k-1 due to integer overflow, and the condition lb <= ub
567 is true, even if we do not want this. However lb < ub + 1 is false,
568 as expected. */
569 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
570 : PLUS_EXPR, *type, *ub, one);
572 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
575 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
577 return exit_edge;
580 /* Translates an isl_ast_node_for to Gimple. */
582 static edge
583 translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node,
584 edge next_e, ivs_params &ip)
586 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for);
587 tree type, lb, ub;
588 edge last_e = graphite_create_new_loop_guard (next_e, node, &type,
589 &lb, &ub, ip);
590 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
592 translate_isl_ast_for_loop (context_loop, node, true_e,
593 type, lb, ub, ip);
594 return last_e;
597 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction
598 variables of the loops around GBB in SESE.
600 FIXME: Instead of using a vec<tree> that maps each loop id to a possible
601 chrec, we could consider using a map<int, tree> that maps loop ids to the
602 corresponding tree expressions. */
604 static void
605 build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb,
606 __isl_keep isl_ast_expr *user_expr, ivs_params &ip,
607 sese region)
609 gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op &&
610 isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call);
611 int i;
612 isl_ast_expr *arg_expr;
613 for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++)
615 arg_expr = isl_ast_expr_get_op_arg (user_expr, i);
616 tree type =
617 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
618 tree t = gcc_expression_from_isl_expression (type, arg_expr, ip);
619 loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1);
620 iv_map[old_loop->num] = t;
625 /* Translates an isl_ast_node_user to Gimple.
627 FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */
629 static edge
630 translate_isl_ast_node_user (__isl_keep isl_ast_node *node,
631 edge next_e, ivs_params &ip)
633 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user);
634 isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node);
635 isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0);
636 gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id);
637 isl_id *name_id = isl_ast_expr_get_id (name_expr);
638 poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id);
639 gcc_assert (pbb);
640 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
641 vec<tree> iv_map;
642 isl_ast_expr_free (name_expr);
643 isl_id_free (name_id);
645 gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
646 "The entry block should not even appear within a scop");
648 int nb_loops = number_of_loops (cfun);
649 iv_map.create (nb_loops);
650 iv_map.safe_grow_cleared (nb_loops);
652 build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop));
653 isl_ast_expr_free (user_expr);
654 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb),
655 SCOP_REGION (pbb->scop), next_e,
656 iv_map,
657 &graphite_regenerate_error);
658 iv_map.release ();
659 mark_virtual_operands_for_renaming (cfun);
660 update_ssa (TODO_update_ssa);
661 return next_e;
664 /* Translates an isl_ast_node_block to Gimple. */
666 static edge
667 translate_isl_ast_node_block (loop_p context_loop,
668 __isl_keep isl_ast_node *node,
669 edge next_e, ivs_params &ip)
671 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block);
672 isl_ast_node_list *node_list = isl_ast_node_block_get_children (node);
673 int i;
674 for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
676 isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i);
677 next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip);
678 isl_ast_node_free (tmp_node);
680 isl_ast_node_list_free (node_list);
681 return next_e;
684 /* Creates a new if region corresponding to ISL's cond. */
686 static edge
687 graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond,
688 ivs_params &ip)
690 tree type =
691 build_nonstandard_integer_type (graphite_expression_type_precision, 0);
692 tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip);
693 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
694 return exit_edge;
697 /* Translates an isl_ast_node_if to Gimple. */
699 static edge
700 translate_isl_ast_node_if (loop_p context_loop,
701 __isl_keep isl_ast_node *node,
702 edge next_e, ivs_params &ip)
704 gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if);
705 isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node);
706 edge last_e = graphite_create_new_guard (next_e, if_cond, ip);
708 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
709 isl_ast_node *then_node = isl_ast_node_if_get_then (node);
710 translate_isl_ast (context_loop, then_node, true_e, ip);
711 isl_ast_node_free (then_node);
713 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
714 isl_ast_node *else_node = isl_ast_node_if_get_else (node);
715 if (isl_ast_node_get_type (else_node) != isl_ast_node_error)
716 translate_isl_ast (context_loop, else_node, false_e, ip);
717 isl_ast_node_free (else_node);
718 return last_e;
721 /* Translates an ISL AST node NODE to GCC representation in the
722 context of a SESE. */
724 static edge
725 translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node,
726 edge next_e, ivs_params &ip)
728 switch (isl_ast_node_get_type (node))
730 case isl_ast_node_error:
731 gcc_unreachable ();
733 case isl_ast_node_for:
734 return translate_isl_ast_node_for (context_loop, node,
735 next_e, ip);
737 case isl_ast_node_if:
738 return translate_isl_ast_node_if (context_loop, node,
739 next_e, ip);
741 case isl_ast_node_user:
742 return translate_isl_ast_node_user (node, next_e, ip);
744 case isl_ast_node_block:
745 return translate_isl_ast_node_block (context_loop, node,
746 next_e, ip);
748 default:
749 gcc_unreachable ();
753 /* Prints NODE to FILE. */
755 void
756 print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
757 __isl_keep isl_ctx *ctx)
759 isl_printer *prn = isl_printer_to_file (ctx, file);
760 prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
761 prn = isl_printer_print_ast_node (prn, node);
762 prn = isl_printer_print_str (prn, "\n");
763 isl_printer_free (prn);
766 /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */
768 static void
769 add_parameters_to_ivs_params (scop_p scop, ivs_params &ip)
771 sese region = SCOP_REGION (scop);
772 unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param);
773 gcc_assert (nb_parameters == SESE_PARAMS (region).length ());
774 unsigned i;
775 for (i = 0; i < nb_parameters; i++)
777 isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i);
778 ip[tmp_id] = SESE_PARAMS (region)[i];
783 /* Generates a build, which specifies the constraints on the parameters. */
785 static __isl_give isl_ast_build *
786 generate_isl_context (scop_p scop)
788 isl_set *context_isl = isl_set_params (isl_set_copy (scop->context));
789 return isl_ast_build_from_context (context_isl);
792 /* Get the maximal number of schedule dimensions in the scop SCOP. */
794 static
795 int get_max_schedule_dimensions (scop_p scop)
797 int i;
798 poly_bb_p pbb;
799 int schedule_dims = 0;
801 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
803 int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out);
804 if (pbb_schedule_dims > schedule_dims)
805 schedule_dims = pbb_schedule_dims;
808 return schedule_dims;
811 /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions.
813 For schedules with different dimensionality, the isl AST generator can not
814 define an order and will just randomly choose an order. The solution to this
815 problem is to extend all schedules to the maximal number of schedule
816 dimensions (using '0's for the remaining values). */
818 static __isl_give isl_map *
819 extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims)
821 int tmp_dims = isl_map_dim (schedule, isl_dim_out);
822 schedule =
823 isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims);
824 isl_val *zero =
825 isl_val_int_from_si (isl_map_get_ctx (schedule), 0);
826 int i;
827 for (i = tmp_dims; i < nb_schedule_dims; i++)
829 schedule =
830 isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero));
832 isl_val_free (zero);
833 return schedule;
836 /* Set the separation_class option for unroll and jam. */
838 static __isl_give isl_union_map *
839 generate_luj_sepclass_opt (scop_p scop, __isl_take isl_union_set *domain,
840 int dim, int cl)
842 isl_map *map;
843 isl_space *space, *space_sep;
844 isl_ctx *ctx;
845 isl_union_map *mapu;
846 int nsched = get_max_schedule_dimensions (scop);
848 ctx = scop->ctx;
849 space_sep = isl_space_alloc (ctx, 0, 1, 1);
850 space_sep = isl_space_wrap (space_sep);
851 space_sep = isl_space_set_tuple_name (space_sep, isl_dim_set,
852 "separation_class");
853 space = isl_set_get_space (scop->context);
854 space_sep = isl_space_align_params (space_sep, isl_space_copy(space));
855 space = isl_space_map_from_domain_and_range (space, space_sep);
856 space = isl_space_add_dims (space,isl_dim_in, nsched);
857 map = isl_map_universe (space);
858 isl_map_fix_si (map,isl_dim_out,0,dim);
859 isl_map_fix_si (map,isl_dim_out,1,cl);
861 mapu = isl_union_map_intersect_domain (isl_union_map_from_map (map),
862 domain);
863 return (mapu);
866 /* Compute the separation class for loop unroll and jam. */
868 static __isl_give isl_union_set *
869 generate_luj_sepclass (scop_p scop)
871 int i;
872 poly_bb_p pbb;
873 isl_union_set *domain_isl;
875 domain_isl = isl_union_set_empty (isl_set_get_space (scop->context));
877 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
879 isl_set *bb_domain;
880 isl_set *bb_domain_s;
882 if (pbb->map_sepclass == NULL)
883 continue;
885 if (isl_set_is_empty (pbb->domain))
886 continue;
888 bb_domain = isl_set_copy (pbb->domain);
889 bb_domain_s = isl_set_apply (bb_domain, pbb->map_sepclass);
890 pbb->map_sepclass = NULL;
892 domain_isl =
893 isl_union_set_union (domain_isl, isl_union_set_from_set (bb_domain_s));
896 return domain_isl;
899 /* Set the AST built options for loop unroll and jam. */
901 static __isl_give isl_union_map *
902 generate_luj_options (scop_p scop)
904 isl_union_set *domain_isl;
905 isl_union_map *options_isl_ss;
906 isl_union_map *options_isl =
907 isl_union_map_empty (isl_set_get_space (scop->context));
908 int dim = get_max_schedule_dimensions (scop) - 1;
909 int dim1 = dim - PARAM_VALUE (PARAM_LOOP_UNROLL_JAM_DEPTH);
911 if (!flag_loop_unroll_jam)
912 return options_isl;
914 domain_isl = generate_luj_sepclass (scop);
916 options_isl_ss = generate_luj_sepclass_opt (scop, domain_isl, dim1, 0);
917 options_isl = isl_union_map_union (options_isl, options_isl_ss);
919 return options_isl;
922 /* Generates a schedule, which specifies an order used to
923 visit elements in a domain. */
925 static __isl_give isl_union_map *
926 generate_isl_schedule (scop_p scop)
928 int nb_schedule_dims = get_max_schedule_dimensions (scop);
929 int i;
930 poly_bb_p pbb;
931 isl_union_map *schedule_isl =
932 isl_union_map_empty (isl_set_get_space (scop->context));
934 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
936 /* Dead code elimination: when the domain of a PBB is empty,
937 don't generate code for the PBB. */
938 if (isl_set_is_empty (pbb->domain))
939 continue;
941 isl_map *bb_schedule = isl_map_copy (pbb->transformed);
942 bb_schedule = isl_map_intersect_domain (bb_schedule,
943 isl_set_copy (pbb->domain));
944 bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims);
945 schedule_isl =
946 isl_union_map_union (schedule_isl,
947 isl_union_map_from_map (bb_schedule));
949 return schedule_isl;
952 /* This method is executed before the construction of a for node. */
953 static __isl_give isl_id *
954 ast_build_before_for (__isl_keep isl_ast_build *build, void *user)
956 isl_union_map *dependences = (isl_union_map *) user;
957 ast_build_info *for_info = XNEW (struct ast_build_info);
958 isl_union_map *schedule = isl_ast_build_get_schedule (build);
959 isl_space *schedule_space = isl_ast_build_get_schedule_space (build);
960 int dimension = isl_space_dim (schedule_space, isl_dim_out);
961 for_info->is_parallelizable =
962 !carries_deps (schedule, dependences, dimension);
963 isl_union_map_free (schedule);
964 isl_space_free (schedule_space);
965 isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info);
966 return id;
969 /* Set the separate option for all dimensions.
970 This helps to reduce control overhead.
971 Set the options for unroll and jam. */
973 static __isl_give isl_ast_build *
974 set_options (__isl_take isl_ast_build *control,
975 __isl_keep isl_union_map *schedule,
976 __isl_take isl_union_map *opt_luj)
978 isl_ctx *ctx = isl_union_map_get_ctx (schedule);
979 isl_space *range_space = isl_space_set_alloc (ctx, 0, 1);
980 range_space =
981 isl_space_set_tuple_name (range_space, isl_dim_set, "separate");
982 isl_union_set *range =
983 isl_union_set_from_set (isl_set_universe (range_space));
984 isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule));
985 domain = isl_union_set_universe (domain);
986 isl_union_map *options = isl_union_map_from_domain_and_range (domain, range);
988 options = isl_union_map_union (options, opt_luj);
990 return isl_ast_build_set_options (control, options);
993 static __isl_give isl_ast_node *
994 scop_to_isl_ast (scop_p scop, ivs_params &ip)
996 /* Generate loop upper bounds that consist of the current loop iterator,
997 an operator (< or <=) and an expression not involving the iterator.
998 If this option is not set, then the current loop iterator may appear several
999 times in the upper bound. See the isl manual for more details. */
1000 isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true);
1002 add_parameters_to_ivs_params (scop, ip);
1004 isl_union_map *options_luj = generate_luj_options (scop);
1006 isl_union_map *schedule_isl = generate_isl_schedule (scop);
1007 isl_ast_build *context_isl = generate_isl_context (scop);
1009 context_isl = set_options (context_isl, schedule_isl, options_luj);
1011 isl_union_map *dependences = NULL;
1012 if (flag_loop_parallelize_all)
1014 dependences = scop_get_dependences (scop);
1015 context_isl =
1016 isl_ast_build_set_before_each_for (context_isl, ast_build_before_for,
1017 dependences);
1019 isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
1020 schedule_isl);
1021 if(dependences)
1022 isl_union_map_free (dependences);
1023 isl_ast_build_free (context_isl);
1024 return ast_isl;
1027 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1028 the given SCOP. Return true if code generation succeeded.
1030 FIXME: This is not yet a full implementation of the code generator
1031 with ISL ASTs. Generation of GIMPLE code has to be completed. */
1033 bool
1034 graphite_regenerate_ast_isl (scop_p scop)
1036 loop_p context_loop;
1037 sese region = SCOP_REGION (scop);
1038 ifsese if_region = NULL;
1039 isl_ast_node *root_node;
1040 ivs_params ip;
1042 timevar_push (TV_GRAPHITE_CODE_GEN);
1043 graphite_regenerate_error = false;
1044 root_node = scop_to_isl_ast (scop, ip);
1046 if (dump_file && (dump_flags & TDF_DETAILS))
1048 fprintf (dump_file, "\nISL AST generated by ISL: \n");
1049 print_isl_ast_node (dump_file, root_node, scop->ctx);
1050 fprintf (dump_file, "\n");
1053 recompute_all_dominators ();
1054 graphite_verify ();
1056 if_region = move_sese_in_condition (region);
1057 sese_insert_phis_for_liveouts (region,
1058 if_region->region->exit->src,
1059 if_region->false_region->exit,
1060 if_region->true_region->exit);
1061 recompute_all_dominators ();
1062 graphite_verify ();
1064 context_loop = SESE_ENTRY (region)->src->loop_father;
1066 translate_isl_ast (context_loop, root_node, if_region->true_region->entry,
1067 ip);
1068 graphite_verify ();
1069 scev_reset ();
1070 recompute_all_dominators ();
1071 graphite_verify ();
1073 if (graphite_regenerate_error)
1074 set_ifsese_condition (if_region, integer_zero_node);
1076 free (if_region->true_region);
1077 free (if_region->region);
1078 free (if_region);
1080 ivs_params_clear (ip);
1081 isl_ast_node_free (root_node);
1082 timevar_pop (TV_GRAPHITE_CODE_GEN);
1084 if (dump_file && (dump_flags & TDF_DETAILS))
1086 loop_p loop;
1087 int num_no_dependency = 0;
1089 FOR_EACH_LOOP (loop, 0)
1090 if (loop->can_be_parallel)
1091 num_no_dependency++;
1093 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1094 num_no_dependency);
1097 return !graphite_regenerate_error;
1099 #endif