pet_expr_filter: avoid introduction of constraints in index expression
[pet.git] / print.c
blob01dfd15f03c3e4f8fe992a36d98d0c4a12e220b6
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
32 * Leiden University.
35 #include <isl/aff.h>
36 #include <isl/ast.h>
37 #include <isl/ast_build.h>
38 #include <pet.h>
39 #include "expr.h"
40 #include "print.h"
41 #include "scop.h"
43 /* Given an access expression, check if any of its arguments
44 * are not themselves access expressions.
45 * If so, set *found and abort the search.
47 static int depends_on_expressions(__isl_keep pet_expr *expr, void *user)
49 int i;
50 int *found = user;
52 for (i = 0; i < expr->n_arg; ++i)
53 if (expr->args[i]->type != pet_expr_access) {
54 *found = 1;
55 return -1;
58 return 0;
61 /* pet_stmt_build_ast_exprs is currently limited to only handle
62 * some forms of data dependent accesses.
63 * If pet_stmt_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
64 * can safely be called on "stmt".
66 int pet_stmt_can_build_ast_exprs(struct pet_stmt *stmt)
68 int r;
69 int found = 0;
71 if (!stmt)
72 return -1;
74 r = pet_expr_foreach_access_expr(stmt->body,
75 &depends_on_expressions, &found);
76 if (r < 0 && !found)
77 return -1;
79 return !found;
82 /* pet_stmt_build_ast_exprs is currently limited to only handle
83 * some forms of data dependent accesses.
84 * If pet_scop_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
85 * can safely be called on all statements in the scop.
87 int pet_scop_can_build_ast_exprs(struct pet_scop *scop)
89 int i;
91 if (!scop)
92 return -1;
94 for (i = 0; i < scop->n_stmt; ++i) {
95 int ok = pet_stmt_can_build_ast_exprs(scop->stmts[i]);
96 if (ok < 0 || !ok)
97 return ok;
100 return 1;
103 /* Internal data structure for pet_stmt_build_ast_exprs.
105 * "build" is used to construct an AST expression from an index expression.
106 * "fn_index" is used to transform the index expression prior to
107 * the construction of the AST expression.
108 * "fn_expr" is used to transform the constructed AST expression.
109 * "ref2expr" collects the results.
111 struct pet_build_ast_expr_data {
112 isl_ast_build *build;
113 __isl_give isl_multi_pw_aff *(*fn_index)(
114 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
115 void *user);
116 void *user_index;
117 __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
118 __isl_keep isl_id *id, void *user);
119 void *user_expr;
120 isl_id_to_ast_expr *ref2expr;
123 /* Given an index expression "index" with nested expressions, replace
124 * those nested expressions by parameters. The identifiers
125 * of those parameters reference the corresponding arguments
126 * of "expr". The same identifiers are used in
127 * pet_expr_build_nested_ast_exprs.
129 * In particular, if "index" is of the form
131 * { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
133 * then we construct the expression
135 * [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
138 static __isl_give isl_multi_pw_aff *parametrize_nested_exprs(
139 __isl_take isl_multi_pw_aff *index, __isl_keep pet_expr *expr)
141 int i;
142 isl_ctx *ctx;
143 isl_space *space, *space2;
144 isl_local_space *ls;
145 isl_multi_aff *ma, *ma2;
147 ctx = isl_multi_pw_aff_get_ctx(index);
148 space = isl_multi_pw_aff_get_domain_space(index);
149 space = isl_space_unwrap(space);
151 space2 = isl_space_domain(isl_space_copy(space));
152 ma = isl_multi_aff_identity(isl_space_map_from_set(space2));
154 space = isl_space_insert_dims(space, isl_dim_param, 0,
155 expr->n_arg);
156 for (i = 0; i < expr->n_arg; ++i) {
157 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
159 space = isl_space_set_dim_id(space, isl_dim_param, i, id);
161 space2 = isl_space_domain(isl_space_copy(space));
162 ls = isl_local_space_from_space(space2);
163 ma2 = isl_multi_aff_zero(space);
164 for (i = 0; i < expr->n_arg; ++i) {
165 isl_aff *aff;
166 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
167 isl_dim_param, i);
168 ma2 = isl_multi_aff_set_aff(ma2, i, aff);
170 isl_local_space_free(ls);
172 ma = isl_multi_aff_range_product(ma, ma2);
174 return isl_multi_pw_aff_pullback_multi_aff(index, ma);
177 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
178 __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data);
180 /* Construct an associative array from identifiers for the nested
181 * expressions of "expr" to the corresponding isl_ast_expr.
182 * The identifiers reference the corresponding arguments of "expr".
183 * The same identifiers are used in parametrize_nested_exprs.
185 static __isl_give isl_id_to_ast_expr *pet_expr_build_nested_ast_exprs(
186 __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
188 int i;
189 isl_ctx *ctx = isl_ast_build_get_ctx(data->build);
190 isl_id_to_ast_expr *id2expr;
192 id2expr = isl_id_to_ast_expr_alloc(ctx, expr->n_arg);
194 for (i = 0; i < expr->n_arg; ++i) {
195 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
196 isl_ast_expr *ast_expr;
198 ast_expr = pet_expr_build_ast_expr(expr->args[i], data);
199 id2expr = isl_id_to_ast_expr_set(id2expr, id, ast_expr);
202 return id2expr;
205 /* Construct an AST expression from an access expression.
207 * If the expression has any arguments, we first convert those
208 * to AST expressions and replace the references to those arguments
209 * in the index expression by parameters.
211 * Then we apply the index transformation if any was provided by the user.
213 * If the "access" is actually an affine expression, we print is as such.
214 * Otherwise, we print a proper access.
216 * If the original expression had any arguments, then they are plugged in now.
218 * Finally, we apply an AST transformation on the result, if any was provided
219 * by the user.
221 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
222 __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
224 isl_pw_aff *pa;
225 isl_multi_pw_aff *mpa;
226 isl_ast_expr *ast_expr;
227 isl_id_to_ast_expr *id2expr;
228 isl_ast_build *build = data->build;
230 if (!expr)
231 return NULL;
232 if (expr->type != pet_expr_access)
233 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
234 "not an access expression", return NULL);
236 mpa = isl_multi_pw_aff_copy(expr->acc.index);
238 if (expr->n_arg > 0) {
239 mpa = parametrize_nested_exprs(mpa, expr);
240 id2expr = pet_expr_build_nested_ast_exprs(expr, data);
243 if (data->fn_index)
244 mpa = data->fn_index(mpa, expr->acc.ref_id, data->user_index);
245 mpa = isl_multi_pw_aff_coalesce(mpa);
247 if (!pet_expr_is_affine(expr)) {
248 ast_expr = isl_ast_build_access_from_multi_pw_aff(build, mpa);
249 } else {
250 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
251 ast_expr = isl_ast_build_expr_from_pw_aff(build, pa);
252 isl_multi_pw_aff_free(mpa);
254 if (expr->n_arg > 0)
255 ast_expr = isl_ast_expr_substitute_ids(ast_expr, id2expr);
256 if (data->fn_expr)
257 ast_expr = data->fn_expr(ast_expr, expr->acc.ref_id,
258 data->user_index);
260 return ast_expr;
263 /* Construct an AST expression from the access expression "expr" and
264 * add the mapping from reference identifier to AST expression to
265 * data->ref2expr.
267 static int add_access(__isl_keep pet_expr *expr, void *user)
269 struct pet_build_ast_expr_data *data = user;
270 isl_id *id;
271 isl_ast_expr *ast_expr;
273 ast_expr = pet_expr_build_ast_expr(expr, data);
275 id = isl_id_copy(expr->acc.ref_id);
276 data->ref2expr = isl_id_to_ast_expr_set(data->ref2expr, id, ast_expr);
278 return 0;
281 /* Construct an associative array from reference identifiers of
282 * access expressions in "stmt" to the corresponding isl_ast_expr.
283 * Each index expression is first transformed through "fn_index"
284 * (if not NULL). Then an AST expression is generated using "build".
285 * Finally, the AST expression is transformed using "fn_expr"
286 * (if not NULL).
288 __isl_give isl_id_to_ast_expr *pet_stmt_build_ast_exprs(struct pet_stmt *stmt,
289 __isl_keep isl_ast_build *build,
290 __isl_give isl_multi_pw_aff *(*fn_index)(
291 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
292 void *user), void *user_index,
293 __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
294 __isl_keep isl_id *id, void *user), void *user_expr)
296 struct pet_build_ast_expr_data data =
297 { build, fn_index, user_index, fn_expr, user_expr };
298 isl_ctx *ctx;
300 if (!stmt || !build)
301 return NULL;
303 ctx = isl_ast_build_get_ctx(build);
304 data.ref2expr = isl_id_to_ast_expr_alloc(ctx, 0);
305 if (pet_expr_foreach_access_expr(stmt->body, &add_access, &data) < 0)
306 data.ref2expr = isl_id_to_ast_expr_free(data.ref2expr);
308 return data.ref2expr;
311 /* Print the access expression "expr" to "p".
313 * We look up the corresponding isl_ast_expr in "ref2expr"
314 * and print that to "p".
316 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
317 __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
319 isl_ast_expr *ast_expr;
320 int is_access;
322 if (!isl_id_to_ast_expr_has(ref2expr, expr->acc.ref_id))
323 isl_die(isl_printer_get_ctx(p), isl_error_internal,
324 "missing expression", return isl_printer_free(p));
326 ast_expr = isl_id_to_ast_expr_get(ref2expr,
327 isl_id_copy(expr->acc.ref_id));
328 is_access = isl_ast_expr_get_type(ast_expr) == isl_ast_expr_op &&
329 isl_ast_expr_get_op_type(ast_expr) == isl_ast_op_access;
330 if (!is_access)
331 p = isl_printer_print_str(p, "(");
332 p = isl_printer_print_ast_expr(p, ast_expr);
333 if (!is_access)
334 p = isl_printer_print_str(p, ")");
335 isl_ast_expr_free(ast_expr);
337 return p;
340 /* Is "op" a postfix operator?
342 static int is_postfix(enum pet_op_type op)
344 switch (op) {
345 case pet_op_post_inc:
346 case pet_op_post_dec:
347 return 1;
348 default:
349 return 0;
353 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
354 __isl_keep pet_expr *expr, int outer,
355 __isl_keep isl_id_to_ast_expr *ref2expr);
357 /* Print operation expression "expr" to "p".
359 * The access subexpressions are replaced by the isl_ast_expr
360 * associated to its reference identifier in "ref2expr".
362 static __isl_give isl_printer *print_op(__isl_take isl_printer *p,
363 __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
365 switch (expr->n_arg) {
366 case 1:
367 if (!is_postfix(expr->op))
368 p = isl_printer_print_str(p, pet_op_str(expr->op));
369 p = print_pet_expr(p, expr->args[pet_un_arg], 0, ref2expr);
370 if (is_postfix(expr->op))
371 p = isl_printer_print_str(p, pet_op_str(expr->op));
372 break;
373 case 2:
374 p = print_pet_expr(p, expr->args[pet_bin_lhs], 0,
375 ref2expr);
376 p = isl_printer_print_str(p, " ");
377 p = isl_printer_print_str(p, pet_op_str(expr->op));
378 p = isl_printer_print_str(p, " ");
379 p = print_pet_expr(p, expr->args[pet_bin_rhs], 0,
380 ref2expr);
381 break;
382 case 3:
383 p = print_pet_expr(p, expr->args[pet_ter_cond], 0,
384 ref2expr);
385 p = isl_printer_print_str(p, " ? ");
386 p = print_pet_expr(p, expr->args[pet_ter_true], 0,
387 ref2expr);
388 p = isl_printer_print_str(p, " : ");
389 p = print_pet_expr(p, expr->args[pet_ter_false], 0,
390 ref2expr);
391 break;
394 return p;
397 /* Print "expr" to "p".
399 * If "outer" is set, then we are printing the outer expression statement.
401 * The access subexpressions are replaced by the isl_ast_expr
402 * associated to its reference identifier in "ref2expr".
404 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
405 __isl_keep pet_expr *expr, int outer,
406 __isl_keep isl_id_to_ast_expr *ref2expr)
408 int i;
410 switch (expr->type) {
411 case pet_expr_error:
412 p = isl_printer_free(p);
413 break;
414 case pet_expr_int:
415 p = isl_printer_print_val(p, expr->i);
416 break;
417 case pet_expr_double:
418 p = isl_printer_print_str(p, expr->d.s);
419 break;
420 case pet_expr_access:
421 p = print_access(p, expr, ref2expr);
422 break;
423 case pet_expr_op:
424 if (!outer)
425 p = isl_printer_print_str(p, "(");
426 p = print_op(p, expr, ref2expr);
427 if (!outer)
428 p = isl_printer_print_str(p, ")");
429 break;
430 case pet_expr_call:
431 p = isl_printer_print_str(p, expr->name);
432 p = isl_printer_print_str(p, "(");
433 for (i = 0; i < expr->n_arg; ++i) {
434 if (i)
435 p = isl_printer_print_str(p, ", ");
436 p = print_pet_expr(p, expr->args[i], 1, ref2expr);
438 p = isl_printer_print_str(p, ")");
439 break;
440 case pet_expr_cast:
441 if (!outer)
442 p = isl_printer_print_str(p, "(");
443 p = isl_printer_print_str(p, "(");
444 p = isl_printer_print_str(p, expr->type_name);
445 p = isl_printer_print_str(p, ") ");
446 p = print_pet_expr(p, expr->args[0], 0, ref2expr);
447 if (!outer)
448 p = isl_printer_print_str(p, ")");
449 break;
452 return p;
455 /* Print "stmt" to "p".
457 * The access expressions in "stmt" are replaced by the isl_ast_expr
458 * associated to its reference identifier in "ref2expr".
460 * If the statement is an assume statement, then we print nothing.
462 __isl_give isl_printer *pet_stmt_print_body(struct pet_stmt *stmt,
463 __isl_take isl_printer *p, __isl_keep isl_id_to_ast_expr *ref2expr)
465 if (!stmt)
466 return isl_printer_free(p);
467 if (pet_stmt_is_assume(stmt))
468 return p;
469 p = isl_printer_start_line(p);
470 p = print_pet_expr(p, stmt->body, 1, ref2expr);
471 p = isl_printer_print_str(p, ";");
472 p = isl_printer_end_line(p);
474 return p;
477 /* Copy the contents of "input" from offset "start" to "end" to "output".
479 int copy(FILE *input, FILE *output, long start, long end)
481 char buffer[1024];
482 size_t n, m;
484 if (end < 0) {
485 fseek(input, 0, SEEK_END);
486 end = ftell(input);
489 fseek(input, start, SEEK_SET);
491 while (start < end) {
492 n = end - start;
493 if (n > 1024)
494 n = 1024;
495 n = fread(buffer, 1, n, input);
496 if (n <= 0)
497 return -1;
498 m = fwrite(buffer, 1, n, output);
499 if (n != m)
500 return -1;
501 start += n;
504 return 0;