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
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.
39 #include <isl/union_map.h>
43 struct pet_options
*pet
;
48 ISL_ARGS_START(struct options
, options_args
)
49 ISL_ARG_CHILD(struct options
, pet
, NULL
, &pet_options_args
, "pet options")
50 ISL_ARG_ARG(struct options
, schedule
, "schedule", NULL
)
51 ISL_ARG_ARG(struct options
, code
, "code", NULL
)
54 ISL_ARG_DEF(options
, struct options
, options_args
)
56 static __isl_give isl_pw_aff
*expr_extract_pw_aff(struct pet_expr
*expr
,
57 __isl_keep isl_union_map
*assignments
);
59 /* Extract an affine expression from the call to floord in "expr",
60 * possibly exploiting "assignments".
62 static __isl_give isl_pw_aff
*expr_extract_floord(struct pet_expr
*expr
,
63 __isl_keep isl_union_map
*assignments
)
65 isl_pw_aff
*lhs
, *rhs
;
67 lhs
= expr_extract_pw_aff(expr
->args
[0], assignments
);
68 rhs
= expr_extract_pw_aff(expr
->args
[1], assignments
);
69 return isl_pw_aff_floor(isl_pw_aff_div(lhs
, rhs
));
72 /* Extract an affine expression from the call in "expr",
73 * possibly exploiting "assignments".
75 * We only support calls to the "floord" function for now.
77 static __isl_give isl_pw_aff
*call_expr_extract_pw_aff(struct pet_expr
*expr
,
78 __isl_keep isl_union_map
*assignments
)
80 assert(!strcmp(expr
->name
, "floord"));
82 return expr_extract_floord(expr
, assignments
);
85 /* Is the variable accessed by "access" assigned in "assignments"?
87 * The assignments are of the form
89 * { variable -> [domain -> value] }
91 static int is_assigned(__isl_keep isl_map
*access
,
92 __isl_keep isl_union_map
*assignments
)
98 var
= isl_union_set_from_set(isl_map_range(isl_map_copy(access
)));
99 test
= isl_union_map_copy(assignments
);
100 test
= isl_union_map_intersect_domain(test
, var
);
101 empty
= isl_union_map_is_empty(test
);
102 isl_union_map_free(test
);
107 /* Apply the appropriate assignment in "assignments" to the access "map".
109 * "map" is of the form
111 * { access_domain -> variable }
113 * "assignments" are of the form
115 * { variable -> [assignment_domain -> value] }
117 * We assume the assignment precedes the access in the code.
118 * In particular, we assume that the loops around the assignment
119 * are the same as the first loops around the access.
123 * { access_domain -> [assignment_domain -> value] }
125 * equate the iterators of assignment_domain to the corresponding iterators
126 * in access_domain and then project out assignment_domain, obtaining
128 * { access_domain -> value }
130 static __isl_give isl_map
*apply_assignment(__isl_take isl_map
*map
,
131 __isl_keep isl_union_map
*assignments
)
137 umap
= isl_union_map_from_map(map
);
138 umap
= isl_union_map_apply_range(umap
, isl_union_map_copy(assignments
));
139 map
= isl_map_from_union_map(umap
);
140 space
= isl_space_unwrap(isl_space_range(isl_map_get_space(map
)));
141 n
= isl_space_dim(space
, isl_dim_in
);
142 for (i
= 0; i
< n
; ++i
)
143 map
= isl_map_equate(map
, isl_dim_in
, i
, isl_dim_out
, i
);
144 map
= isl_map_apply_range(map
,
145 isl_map_range_map(isl_map_universe(space
)));
150 /* Extract an affine expression from the access to a named space in "access",
151 * possibly exploiting "assignments".
153 * If the variable has been assigned a value, we return the corresponding
154 * assignment. Otherwise, we assume we are accessing a 0D space and
155 * we turn that into an expression equal to a parameter of the same name.
157 static __isl_give isl_map
*resolve_access(__isl_take isl_map
*access
,
158 __isl_keep isl_union_map
*assignments
)
162 if (is_assigned(access
, assignments
))
163 return apply_assignment(access
, assignments
);
165 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
166 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
167 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, id
);
168 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
169 access
= isl_map_equate(access
, isl_dim_param
, 0, isl_dim_out
, 0);
174 /* Extract an affine expression from the access expression "expr",
175 * possibly exploiting "assignments".
177 * If we are accessing a (1D) anonymous space, then we are actually
178 * computing an affine expression and we simply return that expression.
179 * Otherwise, we try and convert the access to an affine expression in
182 static __isl_give isl_pw_aff
*access_expr_extract_pw_aff(struct pet_expr
*expr
,
183 __isl_keep isl_union_map
*assignments
)
187 isl_pw_multi_aff
*pma
;
189 map
= isl_map_copy(expr
->acc
.access
);
190 if (isl_map_has_tuple_id(map
, isl_dim_out
))
191 map
= resolve_access(map
, assignments
);
192 pma
= isl_pw_multi_aff_from_map(map
);
193 pa
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
194 isl_pw_multi_aff_free(pma
);
198 /* Extract an affine expression from "expr", possibly exploiting "assignments",
199 * in the form of an isl_pw_aff.
201 * We only handle the kinds of expressions that we would expect
202 * as arguments to a function call in code generated by isl.
204 static __isl_give isl_pw_aff
*expr_extract_pw_aff(struct pet_expr
*expr
,
205 __isl_keep isl_union_map
*assignments
)
207 isl_pw_aff
*pa
, *pa1
, *pa2
;
209 switch (expr
->type
) {
210 case pet_expr_access
:
211 return access_expr_extract_pw_aff(expr
, assignments
);
213 if (expr
->op
== pet_op_minus
) {
214 pa
= expr_extract_pw_aff(expr
->args
[0], assignments
);
215 return isl_pw_aff_neg(pa
);
218 case pet_expr_binary
:
219 pa1
= expr_extract_pw_aff(expr
->args
[0], assignments
);
220 pa2
= expr_extract_pw_aff(expr
->args
[1], assignments
);
223 pa
= isl_pw_aff_mul(pa1
, pa2
);
226 pa
= isl_pw_aff_add(pa1
, pa2
);
229 pa
= isl_pw_aff_sub(pa1
, pa2
);
232 pa
= isl_pw_aff_tdiv_q(pa1
, pa2
);
235 pa
= isl_pw_aff_tdiv_r(pa1
, pa2
);
242 return call_expr_extract_pw_aff(expr
, assignments
);
243 case pet_expr_ternary
:
244 pa
= expr_extract_pw_aff(expr
->args
[0], assignments
);
245 pa1
= expr_extract_pw_aff(expr
->args
[1], assignments
);
246 pa2
= expr_extract_pw_aff(expr
->args
[2], assignments
);
247 return isl_pw_aff_cond(pa
, pa1
, pa2
);
248 case pet_expr_double
:
253 /* Extract an affine expression from "expr", possibly exploiting "assignments",
254 * in the form of an isl_map.
256 static __isl_give isl_map
*expr_extract_map(struct pet_expr
*expr
,
257 __isl_keep isl_union_map
*assignments
)
259 return isl_map_from_pw_aff(expr_extract_pw_aff(expr
, assignments
));
262 /* Extract a call from "stmt", possibly exploiting "assignments".
264 * The returned map is of the form
266 * { domain -> function[arguments] }
268 static __isl_give isl_map
*stmt_extract_call(struct pet_stmt
*stmt
,
269 __isl_keep isl_union_map
*assignments
)
275 domain
= isl_set_copy(stmt
->domain
);
276 call
= isl_map_from_domain(domain
);
278 assert(stmt
->body
->type
== pet_expr_call
);
280 for (i
= 0; i
< stmt
->body
->n_arg
; ++i
) {
283 arg
= expr_extract_map(stmt
->body
->args
[i
], assignments
);
284 call
= isl_map_flat_range_product(call
, arg
);
287 call
= isl_map_set_tuple_name(call
, isl_dim_out
, stmt
->body
->name
);
292 /* Add the assignment in "stmt" to "assignments".
294 * We extract the variable access
296 * { domain -> variable }
298 * and the assigned value
300 * { domain -> value }
302 * and combined them into
304 * { variable -> [domain -> value] }
306 * We add this to "assignments" after having removed any
307 * previously assigned value to the same variable.
309 static __isl_give isl_union_map
*add_assignment(
310 __isl_take isl_union_map
*assignments
, struct pet_stmt
*stmt
)
316 assert(stmt
->body
->op
== pet_op_assign
);
317 assert(stmt
->body
->args
[0]->type
== pet_expr_access
);
318 var
= isl_map_copy(stmt
->body
->args
[0]->acc
.access
);
319 val
= expr_extract_map(stmt
->body
->args
[1], assignments
);
321 val
= isl_map_range_product(val
, var
);
322 val
= isl_map_uncurry(val
);
323 val
= isl_map_reverse(val
);
325 dom
= isl_map_domain(isl_map_copy(val
));
326 assignments
= isl_union_map_subtract_domain(assignments
,
327 isl_union_set_from_set(dom
));
328 assignments
= isl_union_map_add_map(assignments
, val
);
333 /* Is "stmt" a kill statement?
335 static int is_kill(struct pet_stmt
*stmt
)
337 if (stmt
->body
->type
!= pet_expr_unary
)
339 return stmt
->body
->op
== pet_op_kill
;
342 /* Extract a mapping from the iterations domains of "scop" to
343 * the calls in the corresponding statements.
345 * While scanning "scop", we keep track of assignments to variables
346 * so that we can plug them in in the arguments of the calls.
347 * Note that we do not perform any dependence analysis on the assigned
348 * variables. In code generated by isl, such assignments should only
349 * appear immediately before they are used.
351 * The assignments are kept in the form
353 * { variable -> [domain -> value] }
355 * We skip kill statements.
356 * Other than assignments and kill statements, all statements are assumed
357 * to be function calls.
359 static __isl_give isl_union_map
*scop_collect_calls(struct pet_scop
*scop
)
363 isl_union_map
*assignments
;
369 call
= isl_union_map_empty(isl_set_get_space(scop
->context
));
370 assignments
= isl_union_map_empty(isl_set_get_space(scop
->context
));
372 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
373 struct pet_stmt
*stmt
;
375 stmt
= scop
->stmts
[i
];
376 if (stmt
->body
->type
== pet_expr_binary
) {
377 assignments
= add_assignment(assignments
, stmt
);
382 call_i
= stmt_extract_call(scop
->stmts
[i
], assignments
);
383 call
= isl_union_map_add_map(call
, call_i
);
386 isl_union_map_free(assignments
);
391 /* Extract a schedule on the original domains from "scop".
392 * The original domain elements appear as calls in "scop".
394 * We first extract a schedule on the code iteration domains
395 * and a mapping from the code iteration domains to the calls
396 * (i.e., the original domain) and then combine the two.
398 static __isl_give isl_union_map
*extract_code_schedule(struct pet_scop
*scop
)
400 isl_union_map
*schedule
;
401 isl_union_map
*calls
;
403 schedule
= pet_scop_collect_schedule(scop
);
405 calls
= scop_collect_calls(scop
);
407 schedule
= isl_union_map_apply_domain(schedule
, calls
);
412 /* Check that schedule and code_schedule have the same domain,
413 * i.e., that they execute the same statement instances.
415 static int check_domain(__isl_keep isl_union_map
*schedule
,
416 __isl_keep isl_union_map
*code_schedule
)
418 isl_union_set
*dom1
, *dom2
;
423 dom1
= isl_union_map_domain(isl_union_map_copy(schedule
));
424 dom2
= isl_union_map_domain(isl_union_map_copy(code_schedule
));
425 equal
= isl_union_set_is_equal(dom1
, dom2
);
426 isl_union_set_free(dom1
);
427 isl_union_set_free(dom2
);
432 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
433 "domains not identical", return -1);
438 /* Check that the relative order specified by the input schedule is respected
439 * by the schedule extracted from the code.
441 * In particular, check that there is no pair of statement instances
442 * such that the first should be scheduled _before_ the second,
443 * but is actually scheduled _after_ the second in the code.
445 static int check_order(__isl_keep isl_union_map
*schedule
,
446 __isl_keep isl_union_map
*code_schedule
)
452 t1
= isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule
),
453 isl_union_map_copy(schedule
));
454 t2
= isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule
),
455 isl_union_map_copy(code_schedule
));
456 t1
= isl_union_map_intersect(t1
, t2
);
457 empty
= isl_union_map_is_empty(t1
);
458 isl_union_map_free(t1
);
463 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
464 "order not respected", return -1);
469 /* If the original schedule was single valued, then the schedule extracted
470 * from the code should be single valued as well.
472 static int check_single_valued(__isl_keep isl_union_map
*schedule
,
473 __isl_keep isl_union_map
*code_schedule
)
477 sv
= isl_union_map_is_single_valued(schedule
);
483 sv
= isl_union_map_is_single_valued(code_schedule
);
488 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
489 "schedule not single valued", return -1);
494 /* Read a schedule and a context from the first argument and
495 * C code from the second argument and check that the C code
496 * corresponds to the schedule on the context.
498 * In particular, check that
499 * - the domains are identical, i.e., the calls in the C code
500 * correspond to the domain elements of the schedule
501 * - the calls are performed in an order that is compatible
503 * - no function is called twice with the same arguments, provided
504 * the schedule is single-valued
506 * If the schedule is not single-valued then we would have to check
507 * that each function with a given set of arguments is called
508 * the same number of times as there are images in the schedule,
509 * but this is considerably more difficult.
511 int main(int argc
, char **argv
)
515 isl_union_map
*schedule
, *code_schedule
;
516 struct pet_scop
*scop
;
517 struct options
*options
;
521 options
= options_new_with_defaults();
523 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
524 pet_options_set_signed_overflow(ctx
, PET_OVERFLOW_IGNORE
);
525 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
527 file
= fopen(options
->schedule
, "r");
529 schedule
= isl_union_map_read_from_file(ctx
, file
);
530 context
= isl_set_read_from_file(ctx
, file
);
533 scop
= pet_scop_extract_from_C_source(ctx
, options
->code
, NULL
);
535 schedule
= isl_union_map_intersect_params(schedule
,
536 isl_set_copy(context
));
537 code_schedule
= extract_code_schedule(scop
);
538 code_schedule
= isl_union_map_intersect_params(code_schedule
, context
);
540 r
= check_domain(schedule
, code_schedule
) ||
541 check_order(schedule
, code_schedule
) ||
542 check_single_valued(schedule
, code_schedule
);
545 isl_union_map_free(schedule
);
546 isl_union_map_free(code_schedule
);