add pet_expr_foreach_access_expr
[pet.git] / pet_check_code.c
blobb080ca02983f80c3d08d7a095cbb62eb1a7a4fb1
1 /*
2 * Copyright 2012 Ecole Normale Superieure. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials provided
14 * with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY ECOLE NORMALE SUPERIEURE ''AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ECOLE NORMALE SUPERIEURE OR
20 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
23 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 * The views and conclusions contained in the software and documentation
29 * are those of the authors and should not be interpreted as
30 * representing official policies, either expressed or implied, of
31 * Ecole Normale Superieure.
34 #include <assert.h>
35 #include <stdio.h>
36 #include <string.h>
37 #include <isl/arg.h>
38 #include <isl/aff.h>
39 #include <isl/set.h>
40 #include <isl/union_map.h>
41 #include <pet.h>
43 struct options {
44 struct pet_options *pet;
45 char *schedule;
46 char *code;
49 ISL_ARGS_START(struct options, options_args)
50 ISL_ARG_CHILD(struct options, pet, NULL, &pet_options_args, "pet options")
51 ISL_ARG_ARG(struct options, schedule, "schedule", NULL)
52 ISL_ARG_ARG(struct options, code, "code", NULL)
53 ISL_ARGS_END
55 ISL_ARG_DEF(options, struct options, options_args)
57 static __isl_give isl_pw_aff *expr_extract_pw_aff(struct pet_expr *expr,
58 __isl_keep isl_union_map *assignments);
60 /* Extract an affine expression from the call to floord in "expr",
61 * possibly exploiting "assignments".
63 static __isl_give isl_pw_aff *expr_extract_floord(struct pet_expr *expr,
64 __isl_keep isl_union_map *assignments)
66 isl_pw_aff *lhs, *rhs;
68 lhs = expr_extract_pw_aff(expr->args[0], assignments);
69 rhs = expr_extract_pw_aff(expr->args[1], assignments);
70 return isl_pw_aff_floor(isl_pw_aff_div(lhs, rhs));
73 /* Extract an affine expression from the call in "expr",
74 * possibly exploiting "assignments".
76 * We only support calls to the "floord" function for now.
78 static __isl_give isl_pw_aff *call_expr_extract_pw_aff(struct pet_expr *expr,
79 __isl_keep isl_union_map *assignments)
81 assert(!strcmp(expr->name, "floord"));
83 return expr_extract_floord(expr, assignments);
86 /* Is the variable accessed by "access" assigned in "assignments"?
88 * The assignments are of the form
90 * { variable -> [domain -> value] }
92 static int is_assigned(__isl_keep isl_map *access,
93 __isl_keep isl_union_map *assignments)
95 isl_union_set *var;
96 isl_union_map *test;
97 int empty;
99 var = isl_union_set_from_set(isl_map_range(isl_map_copy(access)));
100 test = isl_union_map_copy(assignments);
101 test = isl_union_map_intersect_domain(test, var);
102 empty = isl_union_map_is_empty(test);
103 isl_union_map_free(test);
105 return !empty;
108 /* Apply the appropriate assignment in "assignments" to the access "map".
110 * "map" is of the form
112 * { access_domain -> variable }
114 * "assignments" are of the form
116 * { variable -> [assignment_domain -> value] }
118 * We assume the assignment precedes the access in the code.
119 * In particular, we assume that the loops around the assignment
120 * are the same as the first loops around the access.
122 * We compute
124 * { access_domain -> [assignment_domain -> value] }
126 * equate the iterators of assignment_domain to the corresponding iterators
127 * in access_domain and then project out assignment_domain, obtaining
129 * { access_domain -> value }
131 static __isl_give isl_map *apply_assignment(__isl_take isl_map *map,
132 __isl_keep isl_union_map *assignments)
134 isl_union_map *umap;
135 isl_space *space;
136 int i, n;
138 umap = isl_union_map_from_map(map);
139 umap = isl_union_map_apply_range(umap, isl_union_map_copy(assignments));
140 map = isl_map_from_union_map(umap);
141 space = isl_space_unwrap(isl_space_range(isl_map_get_space(map)));
142 n = isl_space_dim(space, isl_dim_in);
143 for (i = 0; i < n; ++i)
144 map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
145 map = isl_map_apply_range(map,
146 isl_map_range_map(isl_map_universe(space)));
148 return map;
151 /* Extract an affine expression from the access to a named space in "access",
152 * possibly exploiting "assignments".
154 * If the variable has been assigned a value, we return the corresponding
155 * assignment. Otherwise, we assume we are accessing a 0D space and
156 * we turn that into an expression equal to a parameter of the same name.
158 static __isl_give isl_map *resolve_access(__isl_take isl_map *access,
159 __isl_keep isl_union_map *assignments)
161 isl_id *id;
163 if (is_assigned(access, assignments))
164 return apply_assignment(access, assignments);
166 id = isl_map_get_tuple_id(access, isl_dim_out);
167 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
168 access = isl_map_set_dim_id(access, isl_dim_param, 0, id);
169 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
170 access = isl_map_equate(access, isl_dim_param, 0, isl_dim_out, 0);
172 return access;
175 /* Extract an affine expression from the access expression "expr",
176 * possibly exploiting "assignments".
178 * If we are accessing a (1D) anonymous space, then we are actually
179 * computing an affine expression and we simply return that expression.
180 * Otherwise, we try and convert the access to an affine expression in
181 * resolve_access().
183 static __isl_give isl_pw_aff *access_expr_extract_pw_aff(struct pet_expr *expr,
184 __isl_keep isl_union_map *assignments)
186 isl_map *map;
187 isl_pw_aff *pa;
188 isl_pw_multi_aff *pma;
190 map = isl_map_copy(expr->acc.access);
191 if (isl_map_has_tuple_id(map, isl_dim_out))
192 map = resolve_access(map, assignments);
193 pma = isl_pw_multi_aff_from_map(map);
194 pa = isl_pw_multi_aff_get_pw_aff(pma, 0);
195 isl_pw_multi_aff_free(pma);
196 return pa;
199 /* Extract an affine expression from "expr", possibly exploiting "assignments",
200 * in the form of an isl_pw_aff.
202 * We only handle the kinds of expressions that we would expect
203 * as arguments to a function call in code generated by isl.
205 static __isl_give isl_pw_aff *expr_extract_pw_aff(struct pet_expr *expr,
206 __isl_keep isl_union_map *assignments)
208 isl_pw_aff *pa, *pa1, *pa2;
210 switch (expr->type) {
211 case pet_expr_access:
212 return access_expr_extract_pw_aff(expr, assignments);
213 case pet_expr_unary:
214 if (expr->op == pet_op_minus) {
215 pa = expr_extract_pw_aff(expr->args[0], assignments);
216 return isl_pw_aff_neg(pa);
218 assert(0);
219 case pet_expr_binary:
220 pa1 = expr_extract_pw_aff(expr->args[0], assignments);
221 pa2 = expr_extract_pw_aff(expr->args[1], assignments);
222 switch (expr->op) {
223 case pet_op_mul:
224 pa = isl_pw_aff_mul(pa1, pa2);
225 break;
226 case pet_op_add:
227 pa = isl_pw_aff_add(pa1, pa2);
228 break;
229 case pet_op_sub:
230 pa = isl_pw_aff_sub(pa1, pa2);
231 break;
232 case pet_op_div:
233 pa = isl_pw_aff_tdiv_q(pa1, pa2);
234 break;
235 case pet_op_mod:
236 pa = isl_pw_aff_tdiv_r(pa1, pa2);
237 break;
238 default:
239 assert(0);
241 return pa;
242 case pet_expr_call:
243 return call_expr_extract_pw_aff(expr, assignments);
244 case pet_expr_ternary:
245 pa = expr_extract_pw_aff(expr->args[0], assignments);
246 pa1 = expr_extract_pw_aff(expr->args[1], assignments);
247 pa2 = expr_extract_pw_aff(expr->args[2], assignments);
248 return isl_pw_aff_cond(pa, pa1, pa2);
249 case pet_expr_cast:
250 case pet_expr_double:
251 assert(0);
255 /* Extract an affine expression from "expr", possibly exploiting "assignments",
256 * in the form of an isl_map.
258 static __isl_give isl_map *expr_extract_map(struct pet_expr *expr,
259 __isl_keep isl_union_map *assignments)
261 return isl_map_from_pw_aff(expr_extract_pw_aff(expr, assignments));
264 /* Extract a call from "stmt", possibly exploiting "assignments".
266 * The returned map is of the form
268 * { domain -> function[arguments] }
270 static __isl_give isl_map *stmt_extract_call(struct pet_stmt *stmt,
271 __isl_keep isl_union_map *assignments)
273 int i;
274 isl_set *domain;
275 isl_map *call;
277 domain = isl_set_copy(stmt->domain);
278 call = isl_map_from_domain(domain);
280 assert(stmt->body->type == pet_expr_call);
282 for (i = 0; i < stmt->body->n_arg; ++i) {
283 isl_map *arg;
285 arg = expr_extract_map(stmt->body->args[i], assignments);
286 call = isl_map_flat_range_product(call, arg);
289 call = isl_map_set_tuple_name(call, isl_dim_out, stmt->body->name);
291 return call;
294 /* Add the assignment in "stmt" to "assignments".
296 * We extract the variable access
298 * { domain -> variable }
300 * and the assigned value
302 * { domain -> value }
304 * and combined them into
306 * { variable -> [domain -> value] }
308 * We add this to "assignments" after having removed any
309 * previously assigned value to the same variable.
311 static __isl_give isl_union_map *add_assignment(
312 __isl_take isl_union_map *assignments, struct pet_stmt *stmt)
314 isl_map *var;
315 isl_map *val;
316 isl_set *dom;
318 assert(stmt->body->op == pet_op_assign);
319 assert(stmt->body->args[0]->type == pet_expr_access);
320 var = isl_map_copy(stmt->body->args[0]->acc.access);
321 val = expr_extract_map(stmt->body->args[1], assignments);
323 val = isl_map_range_product(val, var);
324 val = isl_map_uncurry(val);
325 val = isl_map_reverse(val);
327 dom = isl_set_universe(isl_space_domain(isl_map_get_space(val)));
328 assignments = isl_union_map_subtract_domain(assignments,
329 isl_union_set_from_set(dom));
330 assignments = isl_union_map_add_map(assignments, val);
332 return assignments;
335 /* Is "stmt" a kill statement?
337 static int is_kill(struct pet_stmt *stmt)
339 if (stmt->body->type != pet_expr_unary)
340 return 0;
341 return stmt->body->op == pet_op_kill;
344 /* Extract a mapping from the iterations domains of "scop" to
345 * the calls in the corresponding statements.
347 * While scanning "scop", we keep track of assignments to variables
348 * so that we can plug them in in the arguments of the calls.
349 * Note that we do not perform any dependence analysis on the assigned
350 * variables. In code generated by isl, such assignments should only
351 * appear immediately before they are used.
353 * The assignments are kept in the form
355 * { variable -> [domain -> value] }
357 * We skip kill statements.
358 * Other than assignments and kill statements, all statements are assumed
359 * to be function calls.
361 static __isl_give isl_union_map *scop_collect_calls(struct pet_scop *scop)
363 int i;
364 isl_map *call_i;
365 isl_union_map *assignments;
366 isl_union_map *call;
368 if (!scop)
369 return NULL;
371 call = isl_union_map_empty(isl_set_get_space(scop->context));
372 assignments = isl_union_map_empty(isl_set_get_space(scop->context));
374 for (i = 0; i < scop->n_stmt; ++i) {
375 struct pet_stmt *stmt;
377 stmt = scop->stmts[i];
378 if (stmt->body->type == pet_expr_binary) {
379 assignments = add_assignment(assignments, stmt);
380 continue;
382 if (is_kill(stmt))
383 continue;
384 call_i = stmt_extract_call(scop->stmts[i], assignments);
385 call = isl_union_map_add_map(call, call_i);
388 isl_union_map_free(assignments);
390 return call;
393 /* Extract a schedule on the original domains from "scop".
394 * The original domain elements appear as calls in "scop".
396 * We first extract a schedule on the code iteration domains
397 * and a mapping from the code iteration domains to the calls
398 * (i.e., the original domain) and then combine the two.
400 static __isl_give isl_union_map *extract_code_schedule(struct pet_scop *scop)
402 isl_union_map *schedule;
403 isl_union_map *calls;
405 schedule = pet_scop_collect_schedule(scop);
407 calls = scop_collect_calls(scop);
409 schedule = isl_union_map_apply_domain(schedule, calls);
411 return schedule;
414 /* Check that schedule and code_schedule have the same domain,
415 * i.e., that they execute the same statement instances.
417 static int check_domain(__isl_keep isl_union_map *schedule,
418 __isl_keep isl_union_map *code_schedule)
420 isl_union_set *dom1, *dom2;
421 int equal;
422 isl_set *s1, *s2;;
423 isl_id *id1, *id2;
425 dom1 = isl_union_map_domain(isl_union_map_copy(schedule));
426 dom2 = isl_union_map_domain(isl_union_map_copy(code_schedule));
427 equal = isl_union_set_is_equal(dom1, dom2);
428 isl_union_set_free(dom1);
429 isl_union_set_free(dom2);
431 if (equal < 0)
432 return -1;
433 if (!equal)
434 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
435 "domains not identical", return -1);
437 return 0;
440 /* Check that the relative order specified by the input schedule is respected
441 * by the schedule extracted from the code, in case the original schedule
442 * is single valued.
444 * In particular, check that there is no pair of statement instances
445 * such that the first should be scheduled _before_ the second,
446 * but is actually scheduled _after_ the second in the code.
448 static int check_order_sv(__isl_keep isl_union_map *schedule,
449 __isl_keep isl_union_map *code_schedule)
451 isl_union_map *t1;
452 isl_union_map *t2;
453 int empty;
455 t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
456 isl_union_map_copy(schedule));
457 t2 = isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule),
458 isl_union_map_copy(code_schedule));
459 t1 = isl_union_map_intersect(t1, t2);
460 empty = isl_union_map_is_empty(t1);
461 isl_union_map_free(t1);
463 if (empty < 0)
464 return -1;
465 if (!empty)
466 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
467 "order not respected", return -1);
469 return 0;
472 /* Check that the relative order specified by the input schedule is respected
473 * by the schedule extracted from the code, in case the original schedule
474 * is not single valued.
476 * In particular, check that the order imposed by the schedules on pairs
477 * of statement instances is the same.
479 static int check_order_not_sv(__isl_keep isl_union_map *schedule,
480 __isl_keep isl_union_map *code_schedule)
482 isl_union_map *t1;
483 isl_union_map *t2;
484 int equal;
486 t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
487 isl_union_map_copy(schedule));
488 t2 = isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule),
489 isl_union_map_copy(code_schedule));
490 equal = isl_union_map_is_equal(t1, t2);
491 isl_union_map_free(t1);
492 isl_union_map_free(t2);
494 if (equal < 0)
495 return -1;
496 if (!equal)
497 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
498 "order not respected", return -1);
500 return 0;
503 /* Check that the relative order specified by the input schedule is respected
504 * by the schedule extracted from the code.
506 * "sv" indicated whether the original schedule is single valued.
507 * If so, we use a cheaper test. Otherwise, we fall back on a more
508 * expensive test.
510 static int check_order(__isl_keep isl_union_map *schedule,
511 __isl_keep isl_union_map *code_schedule, int sv)
513 if (sv)
514 return check_order_sv(schedule, code_schedule);
515 else
516 return check_order_not_sv(schedule, code_schedule);
519 /* If the original schedule was single valued ("sv" is set),
520 * then the schedule extracted from the code should be single valued as well.
522 static int check_single_valued(__isl_keep isl_union_map *code_schedule, int sv)
524 if (!sv)
525 return 0;
527 sv = isl_union_map_is_single_valued(code_schedule);
528 if (sv < 0)
529 return -1;
531 if (!sv)
532 isl_die(isl_union_map_get_ctx(code_schedule), isl_error_unknown,
533 "schedule not single valued", return -1);
535 return 0;
538 /* Read a schedule and a context from the first argument and
539 * C code from the second argument and check that the C code
540 * corresponds to the schedule on the context.
542 * In particular, check that
543 * - the domains are identical, i.e., the calls in the C code
544 * correspond to the domain elements of the schedule
545 * - no function is called twice with the same arguments, provided
546 * the schedule is single-valued
547 * - the calls are performed in an order that is compatible
548 * with the schedule
550 * If the schedule is not single-valued then we would have to check
551 * that each function with a given set of arguments is called
552 * the same number of times as there are images in the schedule,
553 * but this is considerably more difficult.
555 int main(int argc, char **argv)
557 isl_ctx *ctx;
558 isl_set *context;
559 isl_union_map *schedule, *code_schedule;
560 struct pet_scop *scop;
561 struct options *options;
562 FILE *file;
563 int r;
564 int sv;
566 options = options_new_with_defaults();
567 assert(options);
568 ctx = isl_ctx_alloc_with_options(&options_args, options);
569 pet_options_set_signed_overflow(ctx, PET_OVERFLOW_IGNORE);
570 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
572 file = fopen(options->schedule, "r");
573 assert(file);
574 schedule = isl_union_map_read_from_file(ctx, file);
575 context = isl_set_read_from_file(ctx, file);
576 fclose(file);
578 scop = pet_scop_extract_from_C_source(ctx, options->code, NULL);
580 schedule = isl_union_map_intersect_params(schedule,
581 isl_set_copy(context));
582 code_schedule = extract_code_schedule(scop);
583 code_schedule = isl_union_map_intersect_params(code_schedule, context);
585 sv = isl_union_map_is_single_valued(schedule);
586 r = sv < 0 ||
587 check_domain(schedule, code_schedule) ||
588 check_single_valued(code_schedule, sv) ||
589 check_order(schedule, code_schedule, sv);
591 pet_scop_free(scop);
592 isl_union_map_free(schedule);
593 isl_union_map_free(code_schedule);
594 isl_ctx_free(ctx);
596 return r;