]>
Commit | Line | Data |
---|---|---|
f6cc3103 RG |
1 | /* Translation of ISL AST to Gimple. |
2 | Copyright (C) 2014 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 | #include "config.h" | |
22 | ||
7d1ceb93 | 23 | #ifdef HAVE_cloog |
f6cc3103 RG |
24 | #include <isl/set.h> |
25 | #include <isl/map.h> | |
26 | #include <isl/union_map.h> | |
27 | #include <isl/ast_build.h> | |
a78cfa7f RG |
28 | #if defined(__cplusplus) |
29 | extern "C" { | |
30 | #endif | |
31 | #include <isl/val_gmp.h> | |
32 | #if defined(__cplusplus) | |
33 | } | |
34 | #endif | |
7d1ceb93 | 35 | #endif |
f6cc3103 RG |
36 | |
37 | #include "system.h" | |
38 | #include "coretypes.h" | |
39 | #include "tree.h" | |
40 | #include "basic-block.h" | |
41 | #include "tree-ssa-alias.h" | |
42 | #include "internal-fn.h" | |
43 | #include "gimple-expr.h" | |
44 | #include "is-a.h" | |
45 | #include "gimple.h" | |
46 | #include "gimple-iterator.h" | |
47 | #include "tree-ssa-loop.h" | |
48 | #include "tree-pass.h" | |
49 | #include "cfgloop.h" | |
50 | #include "tree-data-ref.h" | |
51 | #include "sese.h" | |
a78cfa7f RG |
52 | #include "tree-ssa-loop-manip.h" |
53 | #include "tree-scalar-evolution.h" | |
5493d313 RG |
54 | #include "gimple-ssa.h" |
55 | #include "tree-into-ssa.h" | |
a78cfa7f | 56 | #include <map> |
f6cc3103 | 57 | |
7d1ceb93 | 58 | #ifdef HAVE_cloog |
f6cc3103 RG |
59 | #include "graphite-poly.h" |
60 | #include "graphite-isl-ast-to-gimple.h" | |
61 | ||
62 | /* This flag is set when an error occurred during the translation of | |
63 | ISL AST to Gimple. */ | |
64 | ||
65 | static bool graphite_regenerate_error; | |
66 | ||
55d1bd59 RG |
67 | /* We always try to use signed 128 bit types, but fall back to smaller types |
68 | in case a platform does not provide types of these sizes. In the future we | |
69 | should use isl to derive the optimal type for each subexpression. */ | |
a78cfa7f | 70 | |
55d1bd59 RG |
71 | static int max_mode_int_precision = |
72 | GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0)); | |
73 | static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? | |
74 | 128 : max_mode_int_precision; | |
a78cfa7f RG |
75 | |
76 | /* Converts a GMP constant VAL to a tree and returns it. */ | |
77 | ||
78 | static tree | |
79 | gmp_cst_to_tree (tree type, mpz_t val) | |
80 | { | |
81 | tree t = type ? type : integer_type_node; | |
82 | mpz_t tmp; | |
83 | ||
84 | mpz_init (tmp); | |
85 | mpz_set (tmp, val); | |
86 | wide_int wi = wi::from_mpz (t, tmp, true); | |
87 | mpz_clear (tmp); | |
88 | ||
89 | return wide_int_to_tree (t, wi); | |
90 | } | |
91 | ||
92 | /* Verifies properties that GRAPHITE should maintain during translation. */ | |
93 | ||
94 | static inline void | |
95 | graphite_verify (void) | |
96 | { | |
97 | #ifdef ENABLE_CHECKING | |
98 | verify_loop_structure (); | |
99 | verify_loop_closed_ssa (true); | |
100 | #endif | |
101 | } | |
102 | ||
103 | /* IVS_PARAMS maps ISL's scattering and parameter identifiers | |
104 | to corresponding trees. */ | |
105 | ||
106 | typedef std::map<isl_id *, tree> ivs_params; | |
107 | ||
108 | /* Free all memory allocated for ISL's identifiers. */ | |
109 | ||
110 | void ivs_params_clear (ivs_params &ip) | |
111 | { | |
112 | std::map<isl_id *, tree>::iterator it; | |
113 | for (it = ip.begin (); | |
114 | it != ip.end (); it++) | |
115 | { | |
116 | isl_id_free (it->first); | |
117 | } | |
118 | } | |
119 | ||
120 | static tree | |
121 | gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, | |
122 | ivs_params &ip); | |
123 | ||
124 | /* Return the tree variable that corresponds to the given isl ast identifier | |
125 | expression (an isl_ast_expr of type isl_ast_expr_id). */ | |
126 | ||
127 | static tree | |
128 | gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, | |
129 | ivs_params &ip) | |
130 | { | |
131 | gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); | |
132 | isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); | |
133 | std::map<isl_id *, tree>::iterator res; | |
134 | res = ip.find (tmp_isl_id); | |
135 | isl_id_free (tmp_isl_id); | |
136 | gcc_assert (res != ip.end () && | |
137 | "Could not map isl_id to tree expression"); | |
138 | isl_ast_expr_free (expr_id); | |
139 | return res->second; | |
140 | } | |
141 | ||
142 | /* Converts an isl_ast_expr_int expression E to a GCC expression tree of | |
143 | type TYPE. */ | |
144 | ||
145 | static tree | |
146 | gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr) | |
147 | { | |
148 | gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int); | |
149 | isl_val *val = isl_ast_expr_get_val (expr); | |
150 | mpz_t val_mpz_t; | |
151 | mpz_init (val_mpz_t); | |
152 | tree res; | |
153 | if (isl_val_get_num_gmp (val, val_mpz_t) == -1) | |
154 | res = NULL_TREE; | |
155 | else | |
156 | res = gmp_cst_to_tree (type, val_mpz_t); | |
157 | isl_val_free (val); | |
158 | isl_ast_expr_free (expr); | |
159 | mpz_clear (val_mpz_t); | |
160 | return res; | |
161 | } | |
162 | ||
163 | /* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of | |
164 | type TYPE. */ | |
165 | ||
166 | static tree | |
167 | binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) | |
168 | { | |
169 | isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); | |
170 | tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
171 | arg_expr = isl_ast_expr_get_op_arg (expr, 1); | |
172 | tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
173 | enum isl_ast_op_type expr_type = isl_ast_expr_get_op_type (expr); | |
174 | isl_ast_expr_free (expr); | |
175 | switch (expr_type) | |
176 | { | |
177 | case isl_ast_op_add: | |
178 | return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
179 | ||
180 | case isl_ast_op_sub: | |
181 | return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
182 | ||
183 | case isl_ast_op_mul: | |
184 | return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
185 | ||
186 | case isl_ast_op_div: | |
187 | return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
188 | ||
189 | case isl_ast_op_fdiv_q: | |
190 | return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
191 | ||
192 | case isl_ast_op_and: | |
193 | return fold_build2 (TRUTH_ANDIF_EXPR, type, | |
194 | tree_lhs_expr, tree_rhs_expr); | |
195 | ||
196 | case isl_ast_op_or: | |
197 | return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
198 | ||
199 | case isl_ast_op_eq: | |
200 | return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
201 | ||
202 | case isl_ast_op_le: | |
203 | return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
204 | ||
205 | case isl_ast_op_lt: | |
206 | return fold_build2 (LT_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
207 | ||
208 | case isl_ast_op_ge: | |
209 | return fold_build2 (GE_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
210 | ||
211 | case isl_ast_op_gt: | |
212 | return fold_build2 (GT_EXPR, type, tree_lhs_expr, tree_rhs_expr); | |
213 | ||
214 | default: | |
215 | gcc_unreachable (); | |
216 | } | |
217 | } | |
218 | ||
219 | /* Converts a ternary isl_ast_expr_op expression E to a GCC expression tree of | |
220 | type TYPE. */ | |
221 | ||
222 | static tree | |
223 | ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) | |
224 | { | |
225 | gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); | |
226 | isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); | |
227 | tree tree_first_expr | |
228 | = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
229 | arg_expr = isl_ast_expr_get_op_arg (expr, 1); | |
230 | tree tree_second_expr | |
231 | = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
232 | arg_expr = isl_ast_expr_get_op_arg (expr, 2); | |
233 | tree tree_third_expr | |
234 | = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
235 | isl_ast_expr_free (expr); | |
236 | return fold_build3 (COND_EXPR, type, tree_first_expr, | |
237 | tree_second_expr, tree_third_expr); | |
238 | } | |
239 | ||
240 | /* Converts a unary isl_ast_expr_op expression E to a GCC expression tree of | |
241 | type TYPE. */ | |
242 | ||
243 | static tree | |
244 | unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) | |
245 | { | |
246 | gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); | |
247 | isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); | |
248 | tree tree_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
249 | isl_ast_expr_free (expr); | |
250 | return fold_build1 (NEGATE_EXPR, type, tree_expr); | |
251 | } | |
252 | ||
253 | /* Converts an isl_ast_expr_op expression E with unknown number of arguments | |
254 | to a GCC expression tree of type TYPE. */ | |
255 | ||
256 | static tree | |
257 | nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) | |
258 | { | |
259 | enum tree_code op_code; | |
260 | switch (isl_ast_expr_get_op_type (expr)) | |
261 | { | |
262 | case isl_ast_op_max: | |
263 | op_code = MAX_EXPR; | |
264 | break; | |
265 | ||
266 | case isl_ast_op_min: | |
267 | op_code = MIN_EXPR; | |
268 | break; | |
269 | ||
270 | default: | |
271 | gcc_unreachable (); | |
272 | } | |
273 | isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); | |
274 | tree res = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
275 | int i; | |
276 | for (i = 1; i < isl_ast_expr_get_op_n_arg (expr); i++) | |
277 | { | |
278 | arg_expr = isl_ast_expr_get_op_arg (expr, i); | |
279 | tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
280 | res = fold_build2 (op_code, type, res, t); | |
281 | } | |
282 | isl_ast_expr_free (expr); | |
283 | return res; | |
284 | } | |
285 | ||
286 | ||
287 | /* Converts an isl_ast_expr_op expression E to a GCC expression tree of | |
288 | type TYPE. */ | |
289 | ||
290 | static tree | |
291 | gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr, | |
292 | ivs_params &ip) | |
293 | { | |
294 | gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op); | |
295 | switch (isl_ast_expr_get_op_type (expr)) | |
296 | { | |
297 | /* These isl ast expressions are not supported yet. */ | |
298 | case isl_ast_op_error: | |
299 | case isl_ast_op_call: | |
300 | case isl_ast_op_and_then: | |
301 | case isl_ast_op_or_else: | |
302 | case isl_ast_op_pdiv_q: | |
303 | case isl_ast_op_pdiv_r: | |
304 | case isl_ast_op_select: | |
305 | gcc_unreachable (); | |
306 | ||
307 | case isl_ast_op_max: | |
308 | case isl_ast_op_min: | |
309 | return nary_op_to_tree (type, expr, ip); | |
310 | ||
311 | case isl_ast_op_add: | |
312 | case isl_ast_op_sub: | |
313 | case isl_ast_op_mul: | |
314 | case isl_ast_op_div: | |
315 | case isl_ast_op_fdiv_q: | |
316 | case isl_ast_op_and: | |
317 | case isl_ast_op_or: | |
318 | case isl_ast_op_eq: | |
319 | case isl_ast_op_le: | |
320 | case isl_ast_op_lt: | |
321 | case isl_ast_op_ge: | |
322 | case isl_ast_op_gt: | |
323 | return binary_op_to_tree (type, expr, ip); | |
324 | ||
325 | case isl_ast_op_minus: | |
326 | return unary_op_to_tree (type, expr, ip); | |
327 | ||
328 | case isl_ast_op_cond: | |
329 | return ternary_op_to_tree (type, expr, ip); | |
330 | ||
331 | default: | |
332 | gcc_unreachable (); | |
333 | } | |
334 | ||
335 | return NULL_TREE; | |
336 | } | |
337 | ||
338 | /* Converts an ISL AST expression E back to a GCC expression tree of | |
339 | type TYPE. */ | |
340 | ||
341 | static tree | |
342 | gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr, | |
343 | ivs_params &ip) | |
344 | { | |
345 | switch (isl_ast_expr_get_type (expr)) | |
346 | { | |
347 | case isl_ast_expr_id: | |
348 | return gcc_expression_from_isl_ast_expr_id (expr, ip); | |
349 | ||
350 | case isl_ast_expr_int: | |
351 | return gcc_expression_from_isl_expr_int (type, expr); | |
352 | ||
353 | case isl_ast_expr_op: | |
354 | return gcc_expression_from_isl_expr_op (type, expr, ip); | |
355 | ||
356 | default: | |
357 | gcc_unreachable (); | |
358 | } | |
359 | ||
360 | return NULL_TREE; | |
361 | } | |
362 | ||
363 | /* Creates a new LOOP corresponding to isl_ast_node_for. Inserts an | |
364 | induction variable for the new LOOP. New LOOP is attached to CFG | |
365 | starting at ENTRY_EDGE. LOOP is inserted into the loop tree and | |
366 | becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds | |
367 | ISL's scattering name to the induction variable created for the | |
368 | loop of STMT. The new induction variable is inserted in the NEWIVS | |
369 | vector and is of type TYPE. */ | |
370 | ||
371 | static struct loop * | |
372 | graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for, | |
373 | loop_p outer, tree type, tree lb, tree ub, | |
374 | ivs_params &ip) | |
375 | { | |
376 | isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for); | |
377 | tree stride = gcc_expression_from_isl_expression (type, for_inc, ip); | |
378 | tree ivvar = create_tmp_var (type, "graphite_IV"); | |
379 | tree iv, iv_after_increment; | |
380 | loop_p loop = create_empty_loop_on_edge | |
381 | (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, | |
382 | outer ? outer : entry_edge->src->loop_father); | |
383 | ||
384 | isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for); | |
385 | isl_id *id = isl_ast_expr_get_id (for_iterator); | |
386 | ip[id] = iv; | |
387 | isl_ast_expr_free (for_iterator); | |
388 | return loop; | |
389 | } | |
390 | ||
391 | static edge | |
392 | translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, | |
393 | edge next_e, ivs_params &ip); | |
394 | ||
395 | /* Create the loop for a isl_ast_node_for. | |
396 | ||
397 | - NEXT_E is the edge where new generated code should be attached. */ | |
398 | ||
399 | static edge | |
400 | translate_isl_ast_for_loop (loop_p context_loop, | |
401 | __isl_keep isl_ast_node *node_for, edge next_e, | |
402 | tree type, tree lb, tree ub, | |
403 | ivs_params &ip) | |
404 | { | |
405 | gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); | |
406 | struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop, | |
407 | type, lb, ub, ip); | |
408 | edge last_e = single_exit (loop); | |
409 | edge to_body = single_succ_edge (loop->header); | |
410 | basic_block after = to_body->dest; | |
411 | ||
412 | /* Create a basic block for loop close phi nodes. */ | |
413 | last_e = single_succ_edge (split_edge (last_e)); | |
414 | ||
415 | /* Translate the body of the loop. */ | |
416 | isl_ast_node *for_body = isl_ast_node_for_get_body (node_for); | |
417 | next_e = translate_isl_ast (loop, for_body, to_body, ip); | |
418 | isl_ast_node_free (for_body); | |
419 | redirect_edge_succ_nodup (next_e, after); | |
420 | set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); | |
421 | ||
422 | /* TODO: Add checking for the loop parallelism. */ | |
423 | ||
424 | return last_e; | |
425 | } | |
426 | ||
427 | /* We use this function to get the upper bound because of the form, | |
428 | which is used by isl to represent loops: | |
429 | ||
430 | for (iterator = init; cond; iterator += inc) | |
431 | ||
432 | { | |
433 | ||
434 | ... | |
435 | ||
436 | } | |
437 | ||
438 | The loop condition is an arbitrary expression, which contains the | |
439 | current loop iterator. | |
440 | ||
441 | (e.g. iterator + 3 < B && C > iterator + A) | |
442 | ||
443 | We have to know the upper bound of the iterator to generate a loop | |
444 | in Gimple form. It can be obtained from the special representation | |
445 | of the loop condition, which is generated by isl, | |
446 | if the ast_build_atomic_upper_bound option is set. In this case, | |
447 | isl generates a loop condition that consists of the current loop | |
448 | iterator, + an operator (< or <=) and an expression not involving | |
449 | the iterator, which is processed and returned by this function. | |
450 | ||
451 | (e.g iterator <= upper-bound-expression-without-iterator) */ | |
452 | ||
453 | static __isl_give isl_ast_expr * | |
454 | get_upper_bound (__isl_keep isl_ast_node *node_for) | |
455 | { | |
456 | gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); | |
457 | isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for); | |
458 | gcc_assert (isl_ast_expr_get_type (for_cond) == isl_ast_expr_op); | |
459 | isl_ast_expr *res; | |
460 | switch (isl_ast_expr_get_op_type (for_cond)) | |
461 | { | |
462 | case isl_ast_op_le: | |
463 | res = isl_ast_expr_get_op_arg (for_cond, 1); | |
464 | break; | |
465 | ||
466 | case isl_ast_op_lt: | |
467 | { | |
468 | // (iterator < ub) => (iterator <= ub - 1) | |
2a466686 RG |
469 | isl_val *one = |
470 | isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); | |
a78cfa7f RG |
471 | isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1); |
472 | res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one)); | |
473 | break; | |
474 | } | |
475 | ||
476 | default: | |
477 | gcc_unreachable (); | |
478 | } | |
479 | isl_ast_expr_free (for_cond); | |
480 | return res; | |
481 | } | |
482 | ||
483 | /* All loops generated by create_empty_loop_on_edge have the form of | |
484 | a post-test loop: | |
485 | ||
486 | do | |
487 | ||
488 | { | |
489 | body of the loop; | |
490 | } while (lower bound < upper bound); | |
491 | ||
492 | We create a new if region protecting the loop to be executed, if | |
493 | the execution count is zero (lower bound > upper bound). */ | |
494 | ||
495 | static edge | |
496 | graphite_create_new_loop_guard (edge entry_edge, | |
497 | __isl_keep isl_ast_node *node_for, tree *type, | |
498 | tree *lb, tree *ub, ivs_params &ip) | |
499 | { | |
500 | gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); | |
501 | tree cond_expr; | |
502 | edge exit_edge; | |
503 | ||
55d1bd59 RG |
504 | *type = |
505 | build_nonstandard_integer_type (graphite_expression_type_precision, 0); | |
a78cfa7f RG |
506 | isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for); |
507 | *lb = gcc_expression_from_isl_expression (*type, for_init, ip); | |
508 | isl_ast_expr *upper_bound = get_upper_bound (node_for); | |
509 | *ub = gcc_expression_from_isl_expression (*type, upper_bound, ip); | |
510 | ||
511 | /* When ub is simply a constant or a parameter, use lb <= ub. */ | |
512 | if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME) | |
513 | cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub); | |
514 | else | |
515 | { | |
516 | tree one = (POINTER_TYPE_P (*type) | |
517 | ? convert_to_ptrofftype (integer_one_node) | |
518 | : fold_convert (*type, integer_one_node)); | |
519 | /* Adding +1 and using LT_EXPR helps with loop latches that have a | |
520 | loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this | |
521 | becomes 2^k-1 due to integer overflow, and the condition lb <= ub | |
522 | is true, even if we do not want this. However lb < ub + 1 is false, | |
523 | as expected. */ | |
524 | tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR | |
525 | : PLUS_EXPR, *type, *ub, one); | |
526 | ||
527 | cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one); | |
528 | } | |
529 | ||
530 | exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); | |
531 | ||
532 | return exit_edge; | |
533 | } | |
534 | ||
535 | /* Translates an isl_ast_node_for to Gimple. */ | |
536 | ||
537 | static edge | |
538 | translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node, | |
539 | edge next_e, ivs_params &ip) | |
540 | { | |
541 | gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for); | |
542 | tree type, lb, ub; | |
543 | edge last_e = graphite_create_new_loop_guard (next_e, node, &type, | |
544 | &lb, &ub, ip); | |
545 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); | |
546 | ||
547 | translate_isl_ast_for_loop (context_loop, node, true_e, | |
548 | type, lb, ub, ip); | |
549 | return last_e; | |
550 | } | |
551 | ||
5493d313 RG |
552 | /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction |
553 | variables of the loops around GBB in SESE. | |
554 | ||
555 | FIXME: Instead of using a vec<tree> that maps each loop id to a possible | |
556 | chrec, we could consider using a map<int, tree> that maps loop ids to the | |
557 | corresponding tree expressions. */ | |
558 | ||
559 | static void | |
560 | build_iv_mapping (vec<tree> iv_map, gimple_bb_p gbb, | |
561 | __isl_keep isl_ast_expr *user_expr, ivs_params &ip, | |
562 | sese region) | |
563 | { | |
564 | gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && | |
565 | isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); | |
566 | int i; | |
567 | isl_ast_expr *arg_expr; | |
568 | for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) | |
569 | { | |
570 | arg_expr = isl_ast_expr_get_op_arg (user_expr, i); | |
571 | tree type = | |
572 | build_nonstandard_integer_type (graphite_expression_type_precision, 0); | |
573 | tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); | |
574 | loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1); | |
575 | iv_map[old_loop->num] = t; | |
576 | } | |
577 | ||
578 | } | |
579 | ||
580 | /* Translates an isl_ast_node_user to Gimple. | |
581 | ||
582 | FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */ | |
583 | ||
584 | static edge | |
585 | translate_isl_ast_node_user (__isl_keep isl_ast_node *node, | |
586 | edge next_e, ivs_params &ip) | |
587 | { | |
588 | gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); | |
589 | isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); | |
590 | isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); | |
591 | gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); | |
592 | isl_id *name_id = isl_ast_expr_get_id (name_expr); | |
593 | poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); | |
594 | gcc_assert (pbb); | |
595 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
596 | vec<tree> iv_map; | |
597 | isl_ast_expr_free (name_expr); | |
598 | isl_id_free (name_id); | |
599 | ||
600 | gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && | |
601 | "The entry block should not even appear within a scop"); | |
602 | ||
603 | loop_p loop = gbb_loop (gbb); | |
604 | iv_map.create (loop->num + 1); | |
605 | iv_map.safe_grow_cleared (loop->num + 1); | |
606 | ||
607 | build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); | |
608 | isl_ast_expr_free (user_expr); | |
609 | next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), | |
610 | SCOP_REGION (pbb->scop), next_e, | |
611 | iv_map, | |
612 | &graphite_regenerate_error); | |
613 | iv_map.release (); | |
614 | mark_virtual_operands_for_renaming (cfun); | |
615 | update_ssa (TODO_update_ssa); | |
616 | return next_e; | |
617 | } | |
618 | ||
a78cfa7f RG |
619 | /* Translates an ISL AST node NODE to GCC representation in the |
620 | context of a SESE. */ | |
621 | ||
622 | static edge | |
623 | translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, | |
624 | edge next_e, ivs_params &ip) | |
625 | { | |
626 | switch (isl_ast_node_get_type (node)) | |
627 | { | |
628 | case isl_ast_node_error: | |
629 | gcc_unreachable (); | |
630 | ||
631 | case isl_ast_node_for: | |
632 | return translate_isl_ast_node_for (context_loop, node, | |
633 | next_e, ip); | |
634 | ||
635 | case isl_ast_node_if: | |
636 | return next_e; | |
637 | ||
638 | case isl_ast_node_user: | |
5493d313 | 639 | return translate_isl_ast_node_user (node, next_e, ip); |
a78cfa7f RG |
640 | |
641 | case isl_ast_node_block: | |
642 | return next_e; | |
643 | ||
644 | default: | |
645 | gcc_unreachable (); | |
646 | } | |
647 | } | |
648 | ||
f6cc3103 RG |
649 | /* Prints NODE to FILE. */ |
650 | ||
651 | void | |
652 | print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, | |
653 | __isl_keep isl_ctx *ctx) | |
654 | { | |
655 | isl_printer *prn = isl_printer_to_file (ctx, file); | |
656 | prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); | |
657 | prn = isl_printer_print_ast_node (prn, node); | |
658 | prn = isl_printer_print_str (prn, "\n"); | |
659 | isl_printer_free (prn); | |
660 | } | |
661 | ||
a78cfa7f RG |
662 | /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */ |
663 | ||
664 | static void | |
665 | add_parameters_to_ivs_params (scop_p scop, ivs_params &ip) | |
666 | { | |
667 | sese region = SCOP_REGION (scop); | |
668 | unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param); | |
669 | gcc_assert (nb_parameters == SESE_PARAMS (region).length ()); | |
670 | unsigned i; | |
671 | for (i = 0; i < nb_parameters; i++) | |
672 | { | |
673 | isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i); | |
674 | ip[tmp_id] = SESE_PARAMS (region)[i]; | |
675 | } | |
676 | } | |
677 | ||
678 | ||
f6cc3103 RG |
679 | /* Generates a build, which specifies the constraints on the parameters. */ |
680 | ||
e4a452b2 | 681 | static __isl_give isl_ast_build * |
f6cc3103 RG |
682 | generate_isl_context (scop_p scop) |
683 | { | |
684 | isl_set *context_isl = isl_set_params (isl_set_copy (scop->context)); | |
685 | return isl_ast_build_from_context (context_isl); | |
686 | } | |
687 | ||
fb3764d1 RG |
688 | /* Get the maximal number of schedule dimensions in the scop SCOP. */ |
689 | ||
690 | static | |
691 | int get_max_schedule_dimensions (scop_p scop) | |
692 | { | |
693 | int i; | |
694 | poly_bb_p pbb; | |
695 | int schedule_dims = 0; | |
696 | ||
697 | FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) | |
698 | { | |
699 | int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); | |
700 | if (pbb_schedule_dims > schedule_dims) | |
701 | schedule_dims = pbb_schedule_dims; | |
702 | } | |
703 | ||
704 | return schedule_dims; | |
705 | } | |
706 | ||
707 | /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. | |
708 | ||
709 | For schedules with different dimensionality, the isl AST generator can not | |
710 | define an order and will just randomly choose an order. The solution to this | |
711 | problem is to extend all schedules to the maximal number of schedule | |
712 | dimensions (using '0's for the remaining values). */ | |
713 | ||
714 | static __isl_give isl_map * | |
715 | extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims) | |
716 | { | |
717 | int tmp_dims = isl_map_dim (schedule, isl_dim_out); | |
718 | schedule = | |
719 | isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); | |
720 | isl_val *zero = | |
721 | isl_val_int_from_si (isl_map_get_ctx (schedule), 0); | |
722 | int i; | |
723 | for (i = tmp_dims; i < nb_schedule_dims; i++) | |
724 | { | |
725 | schedule = | |
726 | isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); | |
727 | } | |
728 | isl_val_free (zero); | |
729 | return schedule; | |
730 | } | |
731 | ||
f6cc3103 RG |
732 | /* Generates a schedule, which specifies an order used to |
733 | visit elements in a domain. */ | |
734 | ||
e4a452b2 | 735 | static __isl_give isl_union_map * |
f6cc3103 RG |
736 | generate_isl_schedule (scop_p scop) |
737 | { | |
fb3764d1 | 738 | int nb_schedule_dims = get_max_schedule_dimensions (scop); |
f6cc3103 RG |
739 | int i; |
740 | poly_bb_p pbb; | |
741 | isl_union_map *schedule_isl = | |
742 | isl_union_map_empty (isl_set_get_space (scop->context)); | |
743 | ||
744 | FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) | |
745 | { | |
746 | /* Dead code elimination: when the domain of a PBB is empty, | |
747 | don't generate code for the PBB. */ | |
748 | if (isl_set_is_empty (pbb->domain)) | |
749 | continue; | |
750 | ||
751 | isl_map *bb_schedule = isl_map_copy (pbb->transformed); | |
752 | bb_schedule = isl_map_intersect_domain (bb_schedule, | |
753 | isl_set_copy (pbb->domain)); | |
fb3764d1 | 754 | bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); |
f6cc3103 RG |
755 | schedule_isl = |
756 | isl_union_map_union (schedule_isl, | |
757 | isl_union_map_from_map (bb_schedule)); | |
758 | } | |
759 | return schedule_isl; | |
760 | } | |
761 | ||
e4a452b2 | 762 | static __isl_give isl_ast_node * |
a78cfa7f | 763 | scop_to_isl_ast (scop_p scop, ivs_params &ip) |
f6cc3103 | 764 | { |
a78cfa7f RG |
765 | /* Generate loop upper bounds that consist of the current loop iterator, |
766 | an operator (< or <=) and an expression not involving the iterator. | |
767 | If this option is not set, then the current loop iterator may appear several | |
768 | times in the upper bound. See the isl manual for more details. */ | |
769 | isl_options_set_ast_build_atomic_upper_bound (scop->ctx, true); | |
770 | ||
771 | add_parameters_to_ivs_params (scop, ip); | |
f6cc3103 RG |
772 | isl_union_map *schedule_isl = generate_isl_schedule (scop); |
773 | isl_ast_build *context_isl = generate_isl_context (scop); | |
774 | isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, | |
775 | schedule_isl); | |
776 | isl_ast_build_free (context_isl); | |
777 | return ast_isl; | |
778 | } | |
779 | ||
780 | /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for | |
781 | the given SCOP. Return true if code generation succeeded. | |
782 | ||
783 | FIXME: This is not yet a full implementation of the code generator | |
a78cfa7f | 784 | with ISL ASTs. Generation of GIMPLE code has to be completed. */ |
f6cc3103 RG |
785 | |
786 | bool | |
787 | graphite_regenerate_ast_isl (scop_p scop) | |
788 | { | |
a78cfa7f RG |
789 | loop_p context_loop; |
790 | sese region = SCOP_REGION (scop); | |
791 | ifsese if_region = NULL; | |
792 | isl_ast_node *root_node; | |
793 | ivs_params ip; | |
794 | ||
f6cc3103 RG |
795 | timevar_push (TV_GRAPHITE_CODE_GEN); |
796 | graphite_regenerate_error = false; | |
a78cfa7f RG |
797 | root_node = scop_to_isl_ast (scop, ip); |
798 | ||
f6cc3103 RG |
799 | if (dump_file && (dump_flags & TDF_DETAILS)) |
800 | { | |
801 | fprintf (dump_file, "\nISL AST generated by ISL: \n"); | |
802 | print_isl_ast_node (dump_file, root_node, scop->ctx); | |
a78cfa7f | 803 | fprintf (dump_file, "\n"); |
f6cc3103 | 804 | } |
a78cfa7f RG |
805 | |
806 | recompute_all_dominators (); | |
807 | graphite_verify (); | |
808 | ||
809 | if_region = move_sese_in_condition (region); | |
810 | sese_insert_phis_for_liveouts (region, | |
811 | if_region->region->exit->src, | |
812 | if_region->false_region->exit, | |
813 | if_region->true_region->exit); | |
814 | recompute_all_dominators (); | |
815 | graphite_verify (); | |
816 | ||
817 | context_loop = SESE_ENTRY (region)->src->loop_father; | |
818 | ||
819 | translate_isl_ast (context_loop, root_node, if_region->true_region->entry, | |
820 | ip); | |
821 | graphite_verify (); | |
822 | scev_reset (); | |
823 | recompute_all_dominators (); | |
824 | graphite_verify (); | |
825 | ||
826 | if (graphite_regenerate_error) | |
827 | set_ifsese_condition (if_region, integer_zero_node); | |
828 | ||
829 | free (if_region->true_region); | |
830 | free (if_region->region); | |
831 | free (if_region); | |
832 | ||
833 | ivs_params_clear (ip); | |
f6cc3103 RG |
834 | isl_ast_node_free (root_node); |
835 | timevar_pop (TV_GRAPHITE_CODE_GEN); | |
a78cfa7f | 836 | /* TODO: Add dump */ |
f6cc3103 RG |
837 | return !graphite_regenerate_error; |
838 | } | |
7d1ceb93 | 839 | #endif |