scop.c: implies_filter: avoid using access relation
[pet.git] / pet_check_code.c
blobda186c1fc2518decc1dc5db2ba6c957d12c6af39
1 /*
2 * Copyright 2012-2014 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/options.h>
40 #include <isl/set.h>
41 #include <isl/union_map.h>
42 #include <isl/id_to_pw_aff.h>
43 #include <pet.h>
45 struct options {
46 struct isl_options *isl;
47 struct pet_options *pet;
48 char *schedule;
49 char *code;
52 ISL_ARGS_START(struct options, options_args)
53 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
54 ISL_ARG_CHILD(struct options, pet, NULL, &pet_options_args, "pet options")
55 ISL_ARG_ARG(struct options, schedule, "schedule", NULL)
56 ISL_ARG_ARG(struct options, code, "code", NULL)
57 ISL_ARGS_END
59 ISL_ARG_DEF(options, struct options, options_args)
61 /* Extract an affine expression from "expr" in the form of an isl_map.
63 * The domain of the created expression is that of "pc".
65 static __isl_give isl_map *expr_extract_map(__isl_keep pet_expr *expr,
66 __isl_keep pet_context *pc)
68 isl_pw_aff *pa;
70 pa = pet_expr_extract_affine(expr, pc);
71 return isl_map_from_pw_aff(pa);
74 /* Extract a call from "stmt".
76 * The returned map is of the form
78 * { domain -> function[arguments] }
80 static __isl_give isl_map *stmt_extract_call(struct pet_stmt *stmt)
82 int i, n;
83 isl_set *domain;
84 isl_map *call;
85 const char *name;
86 pet_context *pc;
87 pet_expr *expr;
89 expr = pet_tree_expr_get_expr(stmt->body);
90 if (!expr)
91 return NULL;
92 if (pet_expr_get_type(expr) != pet_expr_call)
93 isl_die(pet_expr_get_ctx(expr),
94 isl_error_invalid, "expecting call statement",
95 goto error);
97 domain = isl_set_copy(stmt->domain);
98 call = isl_map_from_domain(domain);
100 pc = pet_context_alloc(isl_set_copy(stmt->domain));
101 n = pet_expr_get_n_arg(expr);
102 for (i = 0; i < n; ++i) {
103 isl_map *map_i;
104 pet_expr *arg;
106 arg = pet_expr_get_arg(expr, i);
107 map_i = expr_extract_map(arg, pc);
108 pet_expr_free(arg);
109 call = isl_map_flat_range_product(call, map_i);
111 pet_context_free(pc);
113 name = pet_expr_call_get_name(expr);
114 call = isl_map_set_tuple_name(call, isl_dim_out, name);
116 pet_expr_free(expr);
117 return call;
118 error:
119 pet_expr_free(expr);
120 return NULL;
123 /* Extract a mapping from the iterations domains of "scop" to
124 * the calls in the corresponding statements.
126 * We skip assignment and kill statements.
127 * Other than assignments and kill statements, all statements are assumed
128 * to be function calls.
130 static __isl_give isl_union_map *scop_collect_calls(struct pet_scop *scop)
132 int i;
133 isl_ctx *ctx;
134 isl_map *call_i;
135 isl_union_map *call;
137 if (!scop)
138 return NULL;
140 call = isl_union_map_empty(isl_set_get_space(scop->context));
141 ctx = isl_set_get_ctx(scop->context);
143 for (i = 0; i < scop->n_stmt; ++i) {
144 struct pet_stmt *stmt;
146 stmt = scop->stmts[i];
147 if (pet_stmt_is_assign(stmt))
148 continue;
149 if (pet_stmt_is_kill(stmt))
150 continue;
151 call_i = stmt_extract_call(scop->stmts[i]);
152 call = isl_union_map_add_map(call, call_i);
155 return call;
158 /* Extract a schedule on the original domains from "scop".
159 * The original domain elements appear as calls in "scop".
161 * We first extract a schedule on the code iteration domains
162 * and a mapping from the code iteration domains to the calls
163 * (i.e., the original domain) and then combine the two.
165 static __isl_give isl_union_map *extract_code_schedule(struct pet_scop *scop)
167 isl_union_map *schedule;
168 isl_union_map *calls;
170 schedule = pet_scop_collect_schedule(scop);
172 calls = scop_collect_calls(scop);
174 schedule = isl_union_map_apply_domain(schedule, calls);
176 return schedule;
179 /* Check that schedule and code_schedule have the same domain,
180 * i.e., that they execute the same statement instances.
182 static int check_domain(__isl_keep isl_union_map *schedule,
183 __isl_keep isl_union_map *code_schedule)
185 isl_union_set *dom1, *dom2;
186 int equal;
187 isl_set *s1, *s2;;
188 isl_id *id1, *id2;
189 int r = 0;
191 dom1 = isl_union_map_domain(isl_union_map_copy(schedule));
192 dom2 = isl_union_map_domain(isl_union_map_copy(code_schedule));
193 equal = isl_union_set_is_equal(dom1, dom2);
195 if (equal < 0)
196 r = -1;
197 else if (!equal) {
198 isl_union_set_dump(dom1);
199 isl_union_set_dump(dom2);
200 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
201 "domains not identical", r = -1);
204 isl_union_set_free(dom1);
205 isl_union_set_free(dom2);
207 return r;
210 /* Check that the relative order specified by the input schedule is respected
211 * by the schedule extracted from the code, in case the original schedule
212 * is single valued.
214 * In particular, check that there is no pair of statement instances
215 * such that the first should be scheduled _before_ the second,
216 * but is actually scheduled _after_ the second in the code.
218 static int check_order_sv(__isl_keep isl_union_map *schedule,
219 __isl_keep isl_union_map *code_schedule)
221 isl_union_map *t1;
222 isl_union_map *t2;
223 int empty;
225 t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
226 isl_union_map_copy(schedule));
227 t2 = isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule),
228 isl_union_map_copy(code_schedule));
229 t1 = isl_union_map_intersect(t1, t2);
230 empty = isl_union_map_is_empty(t1);
231 isl_union_map_free(t1);
233 if (empty < 0)
234 return -1;
235 if (!empty)
236 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
237 "order not respected", return -1);
239 return 0;
242 /* Check that the relative order specified by the input schedule is respected
243 * by the schedule extracted from the code, in case the original schedule
244 * is not single valued.
246 * In particular, check that the order imposed by the schedules on pairs
247 * of statement instances is the same.
249 static int check_order_not_sv(__isl_keep isl_union_map *schedule,
250 __isl_keep isl_union_map *code_schedule)
252 isl_union_map *t1;
253 isl_union_map *t2;
254 int equal;
256 t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
257 isl_union_map_copy(schedule));
258 t2 = isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule),
259 isl_union_map_copy(code_schedule));
260 equal = isl_union_map_is_equal(t1, t2);
261 isl_union_map_free(t1);
262 isl_union_map_free(t2);
264 if (equal < 0)
265 return -1;
266 if (!equal)
267 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
268 "order not respected", return -1);
270 return 0;
273 /* Check that the relative order specified by the input schedule is respected
274 * by the schedule extracted from the code.
276 * "sv" indicated whether the original schedule is single valued.
277 * If so, we use a cheaper test. Otherwise, we fall back on a more
278 * expensive test.
280 static int check_order(__isl_keep isl_union_map *schedule,
281 __isl_keep isl_union_map *code_schedule, int sv)
283 if (sv)
284 return check_order_sv(schedule, code_schedule);
285 else
286 return check_order_not_sv(schedule, code_schedule);
289 /* If the original schedule was single valued ("sv" is set),
290 * then the schedule extracted from the code should be single valued as well.
292 static int check_single_valued(__isl_keep isl_union_map *code_schedule, int sv)
294 if (!sv)
295 return 0;
297 sv = isl_union_map_is_single_valued(code_schedule);
298 if (sv < 0)
299 return -1;
301 if (!sv)
302 isl_die(isl_union_map_get_ctx(code_schedule), isl_error_unknown,
303 "schedule not single valued", return -1);
305 return 0;
308 /* Read a schedule and a context from the first argument and
309 * C code from the second argument and check that the C code
310 * corresponds to the schedule on the context.
312 * In particular, check that
313 * - the domains are identical, i.e., the calls in the C code
314 * correspond to the domain elements of the schedule
315 * - no function is called twice with the same arguments, provided
316 * the schedule is single-valued
317 * - the calls are performed in an order that is compatible
318 * with the schedule
320 * If the schedule is not single-valued then we would have to check
321 * that each function with a given set of arguments is called
322 * the same number of times as there are images in the schedule,
323 * but this is considerably more difficult.
325 int main(int argc, char **argv)
327 isl_ctx *ctx;
328 isl_set *context;
329 isl_union_map *schedule, *code_schedule;
330 struct pet_scop *scop;
331 struct options *options;
332 FILE *file;
333 int r;
334 int sv;
336 options = options_new_with_defaults();
337 assert(options);
338 ctx = isl_ctx_alloc_with_options(&options_args, options);
339 pet_options_set_signed_overflow(ctx, PET_OVERFLOW_IGNORE);
340 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
342 file = fopen(options->schedule, "r");
343 assert(file);
344 schedule = isl_union_map_read_from_file(ctx, file);
345 context = isl_set_read_from_file(ctx, file);
346 fclose(file);
348 scop = pet_scop_extract_from_C_source(ctx, options->code, NULL);
350 schedule = isl_union_map_intersect_params(schedule,
351 isl_set_copy(context));
352 code_schedule = extract_code_schedule(scop);
353 code_schedule = isl_union_map_intersect_params(code_schedule, context);
355 sv = isl_union_map_is_single_valued(schedule);
356 r = sv < 0 ||
357 check_domain(schedule, code_schedule) ||
358 check_single_valued(code_schedule, sv) ||
359 check_order(schedule, code_schedule, sv);
361 pet_scop_free(scop);
362 isl_union_map_free(schedule);
363 isl_union_map_free(code_schedule);
364 isl_ctx_free(ctx);
366 return r;