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
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/options.h>
41 #include <isl/union_map.h>
42 #include <isl/id_to_pw_aff.h>
46 struct isl_options
*isl
;
47 struct pet_options
*pet
;
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
)
59 ISL_ARG_DEF(options
, struct options
, options_args
)
61 static __isl_give isl_pw_aff
*expr_extract_pw_aff(__isl_keep pet_expr
*expr
,
62 __isl_keep isl_space
*space
, __isl_keep isl_id_to_pw_aff
*assignments
);
64 /* Extract an affine expression from the call to floord in "expr",
65 * possibly exploiting "assignments".
67 * "space" is the iteration space of the statement containing the expression.
69 static __isl_give isl_pw_aff
*expr_extract_floord(__isl_keep pet_expr
*expr
,
70 __isl_keep isl_space
*space
, __isl_keep isl_id_to_pw_aff
*assignments
)
72 isl_pw_aff
*lhs
, *rhs
;
75 arg
= pet_expr_get_arg(expr
, 0);
76 lhs
= expr_extract_pw_aff(arg
, space
, assignments
);
78 arg
= pet_expr_get_arg(expr
, 1);
79 rhs
= expr_extract_pw_aff(arg
, space
, assignments
);
81 return isl_pw_aff_floor(isl_pw_aff_div(lhs
, rhs
));
84 /* Extract an affine expression from the call in "expr",
85 * possibly exploiting "assignments".
87 * "space" is the iteration space of the statement containing the expression.
89 * We only support calls to the "floord" function for now.
91 static __isl_give isl_pw_aff
*call_expr_extract_pw_aff(
92 __isl_keep pet_expr
*expr
, __isl_keep isl_space
*space
,
93 __isl_keep isl_id_to_pw_aff
*assignments
)
97 name
= pet_expr_call_get_name(expr
);
100 if (!strcmp(name
, "floord"))
101 return expr_extract_floord(expr
, space
, assignments
);
103 isl_die(isl_id_to_pw_aff_get_ctx(assignments
), isl_error_unsupported
,
104 "unsupported expression", return NULL
);
107 /* Is the variable accessed by "index" assigned in "assignments"?
109 * The assignments map variable identifiers to functions of the form
111 * { domain -> value }
113 static int is_assigned(__isl_keep isl_multi_pw_aff
*index
,
114 __isl_keep isl_id_to_pw_aff
*assignments
)
119 var
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
120 assigned
= isl_id_to_pw_aff_has(assignments
, var
);
126 /* Apply the appropriate assignment in "assignments"
127 * to the index expression "index".
129 * "index" is of the form
131 * { access_domain -> variable }
133 * "assignments" maps variable identifiers to functions of the form
135 * { assignment_domain -> value }
137 * We assume the assignment precedes the access in the code.
138 * In particular, we assume that the loops around the assignment
139 * are the same as the first loops around the access.
143 * { access_domain -> assignment_domain }
145 * equating the iterators of assignment_domain to the corresponding iterators
146 * in access_domain and then plug that into the assigned value, obtaining
148 * { access_domain -> value }
150 static __isl_give isl_pw_aff
*apply_assignment(
151 __isl_take isl_multi_pw_aff
*index
,
152 __isl_keep isl_id_to_pw_aff
*assignments
)
158 isl_space
*space
, *dom_space
;
162 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
163 dom
= isl_multi_pw_aff_domain(index
);
164 val
= isl_id_to_pw_aff_get(assignments
, id
);
165 space
= isl_pw_aff_get_domain_space(val
);
166 dom_space
= isl_set_get_space(dom
);
167 space
= isl_space_map_from_domain_and_range(dom_space
, space
);
168 ma
= isl_multi_aff_zero(space
);
169 ls
= isl_local_space_from_space(isl_set_get_space(dom
));
170 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
171 for (i
= 0; i
< n
; ++i
) {
174 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
176 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
178 isl_local_space_free(ls
);
180 val
= isl_pw_aff_pullback_multi_aff(val
, ma
);
181 val
= isl_pw_aff_intersect_domain(val
, dom
);
186 /* Extract an affine expression from the access to a named space in "index",
187 * possibly exploiting "assignments".
189 * If the variable has been assigned a value, we return the corresponding
190 * assignment. Otherwise, we assume we are accessing a 0D space and
191 * we turn that into an expression equal to a parameter of the same name.
193 static __isl_give isl_pw_aff
*resolve_access(__isl_take isl_multi_pw_aff
*index
,
194 __isl_keep isl_id_to_pw_aff
*assignments
)
202 if (is_assigned(index
, assignments
))
203 return apply_assignment(index
, assignments
);
205 id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
206 dom
= isl_multi_pw_aff_domain(index
);
207 dom
= isl_set_insert_dims(dom
, isl_dim_param
, 0, 1);
208 dom
= isl_set_set_dim_id(dom
, isl_dim_param
, 0, id
);
209 ls
= isl_local_space_from_space(isl_set_get_space(dom
));
210 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
211 pa
= isl_pw_aff_alloc(dom
, aff
);
216 /* Extract an affine expression from the access expression "expr",
217 * possibly exploiting "assignments".
219 * If we are accessing a (1D) anonymous space, then we are actually
220 * computing an affine expression and we simply return that expression.
221 * Otherwise, we try and convert the access to an affine expression in
224 static __isl_give isl_pw_aff
*access_expr_extract_pw_aff(
225 __isl_keep pet_expr
*expr
, __isl_keep isl_id_to_pw_aff
*assignments
)
228 isl_multi_pw_aff
*index
;
230 index
= pet_expr_access_get_index(expr
);
231 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
232 pa
= resolve_access(index
, assignments
);
234 pa
= isl_multi_pw_aff_get_pw_aff(index
, 0);
235 isl_multi_pw_aff_free(index
);
240 /* Extract an affine expression defined over iteration space "space"
241 * from the integer expression "expr".
243 static __isl_give isl_pw_aff
*int_expr_extract_pw_aff(
244 __isl_keep pet_expr
*expr
, __isl_keep isl_space
*space
)
249 ls
= isl_local_space_from_space(isl_space_copy(space
));
250 aff
= isl_aff_zero_on_domain(ls
);
251 aff
= isl_aff_add_constant_val(aff
, pet_expr_int_get_val(expr
));
252 return isl_pw_aff_from_aff(aff
);
255 /* Extract an affine expression from the operation in "expr",
256 * possibly exploiting "assignments".
258 * "space" is the iteration space of the statement containing the expression.
260 * We only handle the kinds of expressions that we would expect
261 * as arguments to a function call in code generated by isl.
263 static __isl_give isl_pw_aff
*op_expr_extract_pw_aff(__isl_keep pet_expr
*expr
,
264 __isl_keep isl_space
*space
, __isl_keep isl_id_to_pw_aff
*assignments
)
266 isl_pw_aff
*pa
, *pa1
, *pa2
;
269 switch (pet_expr_get_n_arg(expr
)) {
271 if (pet_expr_op_get_type(expr
) == pet_op_minus
) {
272 arg
= pet_expr_get_arg(expr
, 0);
273 pa
= expr_extract_pw_aff(arg
, space
, assignments
);
275 return isl_pw_aff_neg(pa
);
279 arg
= pet_expr_get_arg(expr
, 0);
280 pa1
= expr_extract_pw_aff(arg
, space
, assignments
);
282 arg
= pet_expr_get_arg(expr
, 1);
283 pa2
= expr_extract_pw_aff(arg
, space
, assignments
);
285 switch (pet_expr_op_get_type(expr
)) {
287 pa
= isl_pw_aff_mul(pa1
, pa2
);
290 pa
= isl_pw_aff_add(pa1
, pa2
);
293 pa
= isl_pw_aff_sub(pa1
, pa2
);
296 pa
= isl_pw_aff_tdiv_q(pa1
, pa2
);
299 pa
= isl_pw_aff_tdiv_r(pa1
, pa2
);
306 arg
= pet_expr_get_arg(expr
, 0);
307 pa
= expr_extract_pw_aff(arg
, space
, assignments
);
309 arg
= pet_expr_get_arg(expr
, 1);
310 pa1
= expr_extract_pw_aff(arg
, space
, assignments
);
312 arg
= pet_expr_get_arg(expr
, 2);
313 pa2
= expr_extract_pw_aff(arg
, space
, assignments
);
315 return isl_pw_aff_cond(pa
, pa1
, pa2
);
321 /* Extract an affine expression from "expr", possibly exploiting "assignments",
322 * in the form of an isl_pw_aff.
324 * "space" is the iteration space of the statement containing the expression.
326 * We only handle the kinds of expressions that we would expect
327 * as arguments to a function call in code generated by isl.
329 static __isl_give isl_pw_aff
*expr_extract_pw_aff(__isl_keep pet_expr
*expr
,
330 __isl_keep isl_space
*space
, __isl_keep isl_id_to_pw_aff
*assignments
)
332 switch (pet_expr_get_type(expr
)) {
334 return int_expr_extract_pw_aff(expr
, space
);
335 case pet_expr_access
:
336 return access_expr_extract_pw_aff(expr
, assignments
);
338 return op_expr_extract_pw_aff(expr
, space
, assignments
);
340 return call_expr_extract_pw_aff(expr
, space
, assignments
);
342 case pet_expr_double
:
348 /* Extract an affine expression from "expr", possibly exploiting "assignments",
349 * in the form of an isl_map.
351 * "space" is the iteration space of the statement containing the expression.
353 static __isl_give isl_map
*expr_extract_map(__isl_keep pet_expr
*expr
,
354 __isl_keep isl_space
*space
, __isl_keep isl_id_to_pw_aff
*assignments
)
358 pa
= expr_extract_pw_aff(expr
, space
, assignments
);
359 return isl_map_from_pw_aff(pa
);
362 /* Extract a call from "stmt", possibly exploiting "assignments".
364 * The returned map is of the form
366 * { domain -> function[arguments] }
368 static __isl_give isl_map
*stmt_extract_call(struct pet_stmt
*stmt
,
369 __isl_keep isl_id_to_pw_aff
*assignments
)
376 domain
= isl_set_copy(stmt
->domain
);
377 call
= isl_map_from_domain(domain
);
379 assert(pet_expr_get_type(stmt
->body
) == pet_expr_call
);
381 n
= pet_expr_get_n_arg(stmt
->body
);
382 for (i
= 0; i
< n
; ++i
) {
387 arg
= pet_expr_get_arg(stmt
->body
, i
);
388 space
= pet_stmt_get_space(stmt
);
389 map_i
= expr_extract_map(arg
, space
, assignments
);
390 isl_space_free(space
);
392 call
= isl_map_flat_range_product(call
, map_i
);
395 name
= pet_expr_call_get_name(stmt
->body
);
396 call
= isl_map_set_tuple_name(call
, isl_dim_out
, name
);
401 /* Add the assignment in "stmt" to "assignments".
403 * We extract the accessed variable identifier "var"
404 * and the assigned value
406 * { domain -> value }
408 * and map "var" to this value in "assignments", replacing
409 * any possible previously assigned value to the same variable.
411 static __isl_give isl_id_to_pw_aff
*add_assignment(
412 __isl_take isl_id_to_pw_aff
*assignments
, struct pet_stmt
*stmt
)
419 assert(pet_stmt_is_assign(stmt
));
420 arg
= pet_expr_get_arg(stmt
->body
, 0);
421 assert(pet_expr_get_type(arg
) == pet_expr_access
);
422 var
= pet_expr_access_get_id(arg
);
424 arg
= pet_expr_get_arg(stmt
->body
, 1);
425 space
= pet_stmt_get_space(stmt
);
426 val
= expr_extract_pw_aff(arg
, space
, assignments
);
427 isl_space_free(space
);
430 assignments
= isl_id_to_pw_aff_set(assignments
, var
, val
);
435 /* Extract a mapping from the iterations domains of "scop" to
436 * the calls in the corresponding statements.
438 * While scanning "scop", we keep track of assignments to variables
439 * so that we can plug them in in the arguments of the calls.
440 * Note that we do not perform any dependence analysis on the assigned
441 * variables. In code generated by isl, such assignments should only
442 * appear immediately before they are used.
444 * The assignments are kept as an associative array between
445 * variable identifiers and assignments of the form
447 * { domain -> value }
449 * We skip kill statements.
450 * Other than assignments and kill statements, all statements are assumed
451 * to be function calls.
453 static __isl_give isl_union_map
*scop_collect_calls(struct pet_scop
*scop
)
458 isl_id_to_pw_aff
*assignments
;
464 call
= isl_union_map_empty(isl_set_get_space(scop
->context
));
465 ctx
= isl_set_get_ctx(scop
->context
);
466 assignments
= isl_id_to_pw_aff_alloc(ctx
, 0);
468 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
469 struct pet_stmt
*stmt
;
471 stmt
= scop
->stmts
[i
];
472 if (pet_stmt_is_assign(stmt
)) {
473 assignments
= add_assignment(assignments
, stmt
);
476 if (pet_stmt_is_kill(stmt
))
478 call_i
= stmt_extract_call(scop
->stmts
[i
], assignments
);
479 call
= isl_union_map_add_map(call
, call_i
);
482 isl_id_to_pw_aff_free(assignments
);
487 /* Extract a schedule on the original domains from "scop".
488 * The original domain elements appear as calls in "scop".
490 * We first extract a schedule on the code iteration domains
491 * and a mapping from the code iteration domains to the calls
492 * (i.e., the original domain) and then combine the two.
494 static __isl_give isl_union_map
*extract_code_schedule(struct pet_scop
*scop
)
496 isl_union_map
*schedule
;
497 isl_union_map
*calls
;
499 schedule
= pet_scop_collect_schedule(scop
);
501 calls
= scop_collect_calls(scop
);
503 schedule
= isl_union_map_apply_domain(schedule
, calls
);
508 /* Check that schedule and code_schedule have the same domain,
509 * i.e., that they execute the same statement instances.
511 static int check_domain(__isl_keep isl_union_map
*schedule
,
512 __isl_keep isl_union_map
*code_schedule
)
514 isl_union_set
*dom1
, *dom2
;
520 dom1
= isl_union_map_domain(isl_union_map_copy(schedule
));
521 dom2
= isl_union_map_domain(isl_union_map_copy(code_schedule
));
522 equal
= isl_union_set_is_equal(dom1
, dom2
);
527 isl_union_set_dump(dom1
);
528 isl_union_set_dump(dom2
);
529 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
530 "domains not identical", r
= -1);
533 isl_union_set_free(dom1
);
534 isl_union_set_free(dom2
);
539 /* Check that the relative order specified by the input schedule is respected
540 * by the schedule extracted from the code, in case the original schedule
543 * In particular, check that there is no pair of statement instances
544 * such that the first should be scheduled _before_ the second,
545 * but is actually scheduled _after_ the second in the code.
547 static int check_order_sv(__isl_keep isl_union_map
*schedule
,
548 __isl_keep isl_union_map
*code_schedule
)
554 t1
= isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule
),
555 isl_union_map_copy(schedule
));
556 t2
= isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule
),
557 isl_union_map_copy(code_schedule
));
558 t1
= isl_union_map_intersect(t1
, t2
);
559 empty
= isl_union_map_is_empty(t1
);
560 isl_union_map_free(t1
);
565 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
566 "order not respected", return -1);
571 /* Check that the relative order specified by the input schedule is respected
572 * by the schedule extracted from the code, in case the original schedule
573 * is not single valued.
575 * In particular, check that the order imposed by the schedules on pairs
576 * of statement instances is the same.
578 static int check_order_not_sv(__isl_keep isl_union_map
*schedule
,
579 __isl_keep isl_union_map
*code_schedule
)
585 t1
= isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule
),
586 isl_union_map_copy(schedule
));
587 t2
= isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule
),
588 isl_union_map_copy(code_schedule
));
589 equal
= isl_union_map_is_equal(t1
, t2
);
590 isl_union_map_free(t1
);
591 isl_union_map_free(t2
);
596 isl_die(isl_union_map_get_ctx(schedule
), isl_error_unknown
,
597 "order not respected", return -1);
602 /* Check that the relative order specified by the input schedule is respected
603 * by the schedule extracted from the code.
605 * "sv" indicated whether the original schedule is single valued.
606 * If so, we use a cheaper test. Otherwise, we fall back on a more
609 static int check_order(__isl_keep isl_union_map
*schedule
,
610 __isl_keep isl_union_map
*code_schedule
, int sv
)
613 return check_order_sv(schedule
, code_schedule
);
615 return check_order_not_sv(schedule
, code_schedule
);
618 /* If the original schedule was single valued ("sv" is set),
619 * then the schedule extracted from the code should be single valued as well.
621 static int check_single_valued(__isl_keep isl_union_map
*code_schedule
, int sv
)
626 sv
= isl_union_map_is_single_valued(code_schedule
);
631 isl_die(isl_union_map_get_ctx(code_schedule
), isl_error_unknown
,
632 "schedule not single valued", return -1);
637 /* Read a schedule and a context from the first argument and
638 * C code from the second argument and check that the C code
639 * corresponds to the schedule on the context.
641 * In particular, check that
642 * - the domains are identical, i.e., the calls in the C code
643 * correspond to the domain elements of the schedule
644 * - no function is called twice with the same arguments, provided
645 * the schedule is single-valued
646 * - the calls are performed in an order that is compatible
649 * If the schedule is not single-valued then we would have to check
650 * that each function with a given set of arguments is called
651 * the same number of times as there are images in the schedule,
652 * but this is considerably more difficult.
654 int main(int argc
, char **argv
)
658 isl_union_map
*schedule
, *code_schedule
;
659 struct pet_scop
*scop
;
660 struct options
*options
;
665 options
= options_new_with_defaults();
667 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
668 pet_options_set_signed_overflow(ctx
, PET_OVERFLOW_IGNORE
);
669 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
671 file
= fopen(options
->schedule
, "r");
673 schedule
= isl_union_map_read_from_file(ctx
, file
);
674 context
= isl_set_read_from_file(ctx
, file
);
677 scop
= pet_scop_extract_from_C_source(ctx
, options
->code
, NULL
);
679 schedule
= isl_union_map_intersect_params(schedule
,
680 isl_set_copy(context
));
681 code_schedule
= extract_code_schedule(scop
);
682 code_schedule
= isl_union_map_intersect_params(code_schedule
, context
);
684 sv
= isl_union_map_is_single_valued(schedule
);
686 check_domain(schedule
, code_schedule
) ||
687 check_single_valued(code_schedule
, sv
) ||
688 check_order(schedule
, code_schedule
, sv
);
691 isl_union_map_free(schedule
);
692 isl_union_map_free(code_schedule
);