pet_expr_is_equal: compare index expressions up to reordering of parameters
[pet.git] / nest.c
blob8513242ba6ae7924e295cd4b4147e033d68b0e66
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 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 <string.h>
37 #include "aff.h"
38 #include "expr.h"
39 #include "expr_arg.h"
40 #include "nest.h"
41 #include "scop.h"
43 /* A wrapper around pet_expr_free to be used as an isl_id free user function.
45 static void pet_expr_free_wrap(void *user)
47 pet_expr_free((pet_expr *) user);
50 /* Create an isl_id that refers to the nested access "expr".
52 __isl_give isl_id *pet_nested_pet_expr(__isl_take pet_expr *expr)
54 isl_id *id;
56 id = isl_id_alloc(pet_expr_get_ctx(expr), "__pet_expr", expr);
57 id = isl_id_set_free_user(id, &pet_expr_free_wrap);
59 return id;
62 /* Extract a pet_expr from an isl_id created by pet_nested_pet_expr.
63 * Such an isl_id has name "__pet_expr" and
64 * the user pointer points to a pet_expr object.
66 __isl_give pet_expr *pet_nested_extract_expr(__isl_keep isl_id *id)
68 return pet_expr_copy((pet_expr *) isl_id_get_user(id));
71 /* Does "id" refer to a nested access created by pet_nested_pet_expr?
73 int pet_nested_in_id(__isl_keep isl_id *id)
75 const char *name;
77 if (!id)
78 return 0;
79 if (!isl_id_get_user(id))
80 return 0;
82 name = isl_id_get_name(id);
83 return !strcmp(name, "__pet_expr");
86 /* Does parameter "pos" of "space" refer to a nested access?
88 static int pet_nested_in_space(__isl_keep isl_space *space, int pos)
90 int nested;
91 isl_id *id;
93 id = isl_space_get_dim_id(space, isl_dim_param, pos);
94 nested = pet_nested_in_id(id);
95 isl_id_free(id);
97 return nested;
100 /* Does parameter "pos" of "set" refer to a nested access?
102 int pet_nested_in_set(__isl_keep isl_set *set, int pos)
104 int nested;
105 isl_id *id;
107 id = isl_set_get_dim_id(set, isl_dim_param, pos);
108 nested = pet_nested_in_id(id);
109 isl_id_free(id);
111 return nested;
114 /* Does parameter "pos" of "map" refer to a nested access?
116 int pet_nested_in_map(__isl_keep isl_map *map, int pos)
118 int nested;
119 isl_id *id;
121 id = isl_map_get_dim_id(map, isl_dim_param, pos);
122 nested = pet_nested_in_id(id);
123 isl_id_free(id);
125 return nested;
128 /* Does "space" involve any parameters that refer to nested accesses?
130 int pet_nested_any_in_space(__isl_keep isl_space *space)
132 int i;
133 int nparam;
135 nparam = isl_space_dim(space, isl_dim_param);
136 for (i = 0; i < nparam; ++i)
137 if (pet_nested_in_space(space, i))
138 return 1;
140 return 0;
143 /* Does "pa" involve any parameters that refer to nested accesses?
145 int pet_nested_any_in_pw_aff(__isl_keep isl_pw_aff *pa)
147 isl_space *space;
148 int nested;
150 space = isl_pw_aff_get_space(pa);
151 nested = pet_nested_any_in_space(space);
152 isl_space_free(space);
154 return nested;
157 /* How many parameters of "space" refer to nested accesses?
159 int pet_nested_n_in_space(__isl_keep isl_space *space)
161 int i, n = 0;
162 int nparam;
164 nparam = isl_space_dim(space, isl_dim_param);
165 for (i = 0; i < nparam; ++i)
166 if (pet_nested_in_space(space, i))
167 ++n;
169 return n;
172 /* How many parameters of "map" refer to nested accesses?
174 int pet_nested_n_in_map(__isl_keep isl_map *map)
176 isl_space *space;
177 int n;
179 space = isl_map_get_space(map);
180 n = pet_nested_n_in_space(space);
181 isl_space_free(space);
183 return n;
186 /* How many parameters of "set" refer to nested accesses?
188 int pet_nested_n_in_set(__isl_keep isl_set *set)
190 isl_space *space;
191 int n;
193 space = isl_set_get_space(set);
194 n = pet_nested_n_in_space(space);
195 isl_space_free(space);
197 return n;
200 /* Remove all parameters from "space" that refer to nested accesses.
202 __isl_give isl_space *pet_nested_remove_from_space(__isl_take isl_space *space)
204 int i;
205 int nparam;
207 nparam = isl_space_dim(space, isl_dim_param);
208 for (i = nparam - 1; i >= 0; --i)
209 if (pet_nested_in_space(space, i))
210 space = isl_space_drop_dims(space, isl_dim_param, i, 1);
212 return space;
215 /* Remove all parameters from "set" that refer to nested accesses.
217 __isl_give isl_set *pet_nested_remove_from_set(__isl_take isl_set *set)
219 int i;
220 int nparam;
222 nparam = isl_set_dim(set, isl_dim_param);
223 for (i = nparam - 1; i >= 0; --i)
224 if (pet_nested_in_set(set, i))
225 set = isl_set_project_out(set, isl_dim_param, i, 1);
227 return set;
230 /* Remove all parameters from "map" that refer to nested accesses.
232 static __isl_give isl_map *pet_nested_remove_from_map(__isl_take isl_map *map)
234 int i;
235 int nparam;
237 nparam = isl_map_dim(map, isl_dim_param);
238 for (i = nparam - 1; i >= 0; --i)
239 if (pet_nested_in_map(map, i))
240 map = isl_map_project_out(map, isl_dim_param, i, 1);
242 return map;
245 /* Remove all parameters from "mpa" that refer to nested accesses.
247 static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff(
248 __isl_take isl_multi_pw_aff *mpa)
250 int i;
251 int nparam;
252 isl_space *space;
254 space = isl_multi_pw_aff_get_space(mpa);
255 nparam = isl_space_dim(space, isl_dim_param);
256 for (i = nparam - 1; i >= 0; --i) {
257 if (!pet_nested_in_space(space, i))
258 continue;
259 mpa = isl_multi_pw_aff_drop_dims(mpa, isl_dim_param, i, 1);
261 isl_space_free(space);
263 return mpa;
266 /* Remove all parameters from the index expression and access relation of "expr"
267 * that refer to nested accesses.
269 static __isl_give pet_expr *expr_remove_nested_parameters(
270 __isl_take pet_expr *expr, void *user)
272 expr = pet_expr_cow(expr);
273 if (!expr)
274 return NULL;
276 expr->acc.access = pet_nested_remove_from_map(expr->acc.access);
277 expr->acc.index = pet_nested_remove_from_multi_pw_aff(expr->acc.index);
278 if (!expr->acc.access || !expr->acc.index)
279 return pet_expr_free(expr);
281 return expr;
284 /* Remove all nested access parameters from the schedule and all
285 * accesses of "stmt".
286 * There is no need to remove them from the domain as these parameters
287 * have already been removed from the domain when this function is called.
289 struct pet_stmt *pet_stmt_remove_nested_parameters(struct pet_stmt *stmt)
291 int i;
293 if (!stmt)
294 return NULL;
295 stmt->schedule = pet_nested_remove_from_map(stmt->schedule);
296 stmt->body = pet_expr_map_access(stmt->body,
297 &expr_remove_nested_parameters, NULL);
298 if (!stmt->schedule || !stmt->body)
299 goto error;
300 for (i = 0; i < stmt->n_arg; ++i) {
301 stmt->args[i] = pet_expr_map_access(stmt->args[i],
302 &expr_remove_nested_parameters, NULL);
303 if (!stmt->args[i])
304 goto error;
307 return stmt;
308 error:
309 pet_stmt_free(stmt);
310 return NULL;
313 /* Set *dim to the dimension of the domain of the access expression "expr" and
314 * abort the search.
316 static int set_dim(__isl_keep pet_expr *expr, void *user)
318 int *dim = user;
319 isl_space *space;
321 space = pet_expr_access_get_domain_space(expr);
322 *dim = isl_space_dim(space, isl_dim_set);
323 isl_space_free(space);
325 return -1;
328 /* Determine the dimension of the domain of the access expressions in "expr".
330 * In particular, return the dimension of the domain of the first access
331 * expression in "expr" as all access expressions should have the same
332 * domain.
334 * If "expr" does not contain any access expressions, then we return 0.
336 static int pet_expr_domain_dim(__isl_keep pet_expr *expr)
338 int dim = -1;
340 if (pet_expr_foreach_access_expr(expr, &set_dim, &dim) >= 0)
341 return 0;
343 return dim;
346 /* Embed all access expressions in "expr" in the domain "space".
347 * The initial domain of the access expressions
348 * is an anonymous domain of a dimension that may be lower
349 * than the dimension of "space".
350 * We may therefore need to introduce extra dimensions as well as
351 * (potentially) the name of "space".
353 static __isl_give pet_expr *embed(__isl_take pet_expr *expr,
354 __isl_keep isl_space *space)
356 int n;
357 isl_multi_pw_aff *mpa;
359 n = pet_expr_domain_dim(expr);
360 if (n < 0)
361 return pet_expr_free(expr);
363 space = isl_space_copy(space);
364 mpa = isl_multi_pw_aff_from_multi_aff(pet_prefix_projection(space, n));
365 expr = pet_expr_update_domain(expr, mpa);
367 return expr;
370 /* For each nested access parameter in "space",
371 * construct a corresponding pet_expr, place it in args and
372 * record its position in "param2pos".
373 * The constructed pet_expr objects are embedded in "space"
374 * (with the nested access parameters removed).
375 * "n_arg" is the number of elements that are already in args.
376 * The position recorded in "param2pos" takes this number into account.
377 * If the pet_expr corresponding to a parameter is identical to
378 * the pet_expr corresponding to an earlier parameter, then these two
379 * parameters are made to refer to the same element in args.
381 * Return the final number of elements in args or -1 if an error has occurred.
383 int pet_extract_nested_from_space(__isl_keep isl_space *space,
384 int n_arg, __isl_give pet_expr **args, int *param2pos)
386 int i, nparam;
387 isl_space *domain;
389 domain = isl_space_copy(space);
390 domain = pet_nested_remove_from_space(domain);
391 nparam = isl_space_dim(space, isl_dim_param);
392 for (i = 0; i < nparam; ++i) {
393 int j;
394 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
396 if (!pet_nested_in_id(id)) {
397 isl_id_free(id);
398 continue;
401 args[n_arg] = embed(pet_nested_extract_expr(id), domain);
402 isl_id_free(id);
403 if (!args[n_arg])
404 return -1;
406 for (j = 0; j < n_arg; ++j)
407 if (pet_expr_is_equal(args[j], args[n_arg]))
408 break;
410 if (j < n_arg) {
411 pet_expr_free(args[n_arg]);
412 args[n_arg] = NULL;
413 param2pos[i] = j;
414 } else
415 param2pos[i] = n_arg++;
417 isl_space_free(domain);
419 return n_arg;
422 /* For each nested access parameter in the access relations in "expr",
423 * construct a corresponding pet_expr, append it to the arguments of "expr"
424 * and record its position in "param2pos" (relative to the initial
425 * number of arguments).
426 * n is the number of nested access parameters.
428 __isl_give pet_expr *pet_expr_extract_nested(__isl_take pet_expr *expr, int n,
429 int *param2pos)
431 isl_ctx *ctx;
432 isl_space *space;
433 int i, n_arg;
434 pet_expr **args;
436 ctx = pet_expr_get_ctx(expr);
437 args = isl_calloc_array(ctx, pet_expr *, n);
438 if (!args)
439 return pet_expr_free(expr);
441 n_arg = pet_expr_get_n_arg(expr);
442 space = pet_expr_access_get_domain_space(expr);
443 n = pet_extract_nested_from_space(space, 0, args, param2pos);
444 isl_space_free(space);
446 if (n < 0)
447 expr = pet_expr_free(expr);
448 else
449 expr = pet_expr_set_n_arg(expr, n_arg + n);
451 for (i = 0; i < n; ++i)
452 expr = pet_expr_set_arg(expr, n_arg + i, args[i]);
453 free(args);
455 return expr;
458 /* Are "expr1" and "expr2" both array accesses such that
459 * the access relation of "expr1" is a subset of that of "expr2"?
460 * Only take into account the first "n_arg" arguments.
462 static int is_sub_access(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2,
463 int n_arg)
465 isl_id *id1, *id2;
466 isl_map *access1, *access2;
467 int is_subset;
468 int i, n1, n2;
470 if (!expr1 || !expr2)
471 return 0;
472 if (pet_expr_get_type(expr1) != pet_expr_access)
473 return 0;
474 if (pet_expr_get_type(expr2) != pet_expr_access)
475 return 0;
476 if (pet_expr_is_affine(expr1))
477 return 0;
478 if (pet_expr_is_affine(expr2))
479 return 0;
480 n1 = pet_expr_get_n_arg(expr1);
481 if (n1 > n_arg)
482 n1 = n_arg;
483 n2 = pet_expr_get_n_arg(expr2);
484 if (n2 > n_arg)
485 n2 = n_arg;
486 if (n1 != n2)
487 return 0;
488 for (i = 0; i < n1; ++i) {
489 pet_expr *arg1, *arg2;
490 int equal;
491 arg1 = pet_expr_get_arg(expr1, i);
492 arg2 = pet_expr_get_arg(expr2, i);
493 equal = pet_expr_is_equal(arg1, arg2);
494 pet_expr_free(arg1);
495 pet_expr_free(arg2);
496 if (equal < 0 || !equal)
497 return equal;
499 id1 = pet_expr_access_get_id(expr1);
500 id2 = pet_expr_access_get_id(expr2);
501 isl_id_free(id1);
502 isl_id_free(id2);
503 if (!id1 || !id2)
504 return 0;
505 if (id1 != id2)
506 return 0;
508 access1 = pet_expr_access_get_access(expr1);
509 access2 = pet_expr_access_get_access(expr2);
510 is_subset = isl_map_is_subset(access1, access2);
511 isl_map_free(access1);
512 isl_map_free(access2);
514 return is_subset;
517 /* Mark self dependences among the arguments of "expr" starting at "first".
518 * These arguments have already been added to the list of arguments
519 * but are not yet referenced directly from the index expression.
520 * Instead, they are still referenced through parameters encoding
521 * nested accesses.
523 * In particular, if "expr" is a read access, then check the arguments
524 * starting at "first" to see if "expr" accesses a subset of
525 * the elements accessed by the argument, or under more restrictive conditions.
526 * If so, then this nested access can be removed from the constraints
527 * governing the outer access. There is no point in restricting
528 * accesses to an array if in order to evaluate the restriction,
529 * we have to access the same elements (or more).
531 * Rather than removing the argument at this point (which would
532 * complicate the resolution of the other nested accesses), we simply
533 * mark it here by replacing it by a NaN pet_expr.
534 * These NaNs are then later removed in remove_marked_self_dependences.
536 static __isl_give pet_expr *mark_self_dependences(__isl_take pet_expr *expr,
537 int first)
539 int i, n;
541 if (pet_expr_access_is_write(expr))
542 return expr;
544 n = pet_expr_get_n_arg(expr);
545 for (i = first; i < n; ++i) {
546 int mark;
547 pet_expr *arg;
549 arg = pet_expr_get_arg(expr, i);
550 mark = is_sub_access(expr, arg, first);
551 pet_expr_free(arg);
552 if (mark < 0)
553 return pet_expr_free(expr);
554 if (!mark)
555 continue;
557 arg = pet_expr_new_int(isl_val_nan(pet_expr_get_ctx(expr)));
558 expr = pet_expr_set_arg(expr, i, arg);
561 return expr;
564 /* Is "expr" a NaN integer expression?
566 static int expr_is_nan(__isl_keep pet_expr *expr)
568 isl_val *v;
569 int is_nan;
571 if (pet_expr_get_type(expr) != pet_expr_int)
572 return 0;
574 v = pet_expr_int_get_val(expr);
575 is_nan = isl_val_is_nan(v);
576 isl_val_free(v);
578 return is_nan;
581 /* Check if we have marked any self dependences (as NaNs)
582 * in mark_self_dependences and remove them here.
583 * It is safe to project them out since these arguments
584 * can at most be referenced from the condition of the access relation,
585 * but do not appear in the index expression.
586 * "dim" is the dimension of the iteration domain.
588 static __isl_give pet_expr *remove_marked_self_dependences(
589 __isl_take pet_expr *expr, int dim, int first)
591 int i, n;
593 n = pet_expr_get_n_arg(expr);
594 for (i = n - 1; i >= first; --i) {
595 int is_nan;
596 pet_expr *arg;
598 arg = pet_expr_get_arg(expr, i);
599 is_nan = expr_is_nan(arg);
600 pet_expr_free(arg);
601 if (!is_nan)
602 continue;
603 expr = pet_expr_access_project_out_arg(expr, dim, i);
606 return expr;
609 /* Look for parameters in any access relation in "expr" that
610 * refer to nested accesses. In particular, these are
611 * parameters with name "__pet_expr".
613 * If there are any such parameters, then the domain of the index
614 * expression and the access relation, which is either "domain" or
615 * [domain -> [a_1,...,a_m]] at this point, is replaced by
616 * [domain -> [t_1,...,t_n]] or [domain -> [a_1,...,a_m,t_1,...,t_n]],
617 * with m the original number of arguments (n_arg) and
618 * n the number of these parameters
619 * (after identifying identical nested accesses).
621 * This transformation is performed in several steps.
622 * We first extract the arguments in pet_expr_extract_nested.
623 * param2pos maps the original parameter position to the position
624 * of the argument beyond the initial (n_arg) number of arguments.
625 * Then we move these parameters to input dimensions.
626 * t2pos maps the positions of these temporary input dimensions
627 * to the positions of the corresponding arguments inside the space
628 * [domain -> [t_1,...,t_n]].
629 * Finally, we express these temporary dimensions in terms of the domain
630 * [domain -> [a_1,...,a_m,t_1,...,t_n]] and precompose index expression and
631 * access relations with this function.
633 __isl_give pet_expr *pet_expr_resolve_nested(__isl_take pet_expr *expr,
634 __isl_keep isl_space *domain)
636 int i, n, n_arg, dim, n_in;
637 int nparam;
638 isl_ctx *ctx;
639 isl_space *space;
640 isl_local_space *ls;
641 isl_aff *aff;
642 isl_multi_aff *ma;
643 int *param2pos;
644 int *t2pos;
646 if (!expr)
647 return expr;
649 n_arg = pet_expr_get_n_arg(expr);
650 for (i = 0; i < n_arg; ++i) {
651 pet_expr *arg;
652 arg = pet_expr_get_arg(expr, i);
653 arg = pet_expr_resolve_nested(arg, domain);
654 expr = pet_expr_set_arg(expr, i, arg);
657 if (pet_expr_get_type(expr) != pet_expr_access)
658 return expr;
660 dim = isl_space_dim(domain, isl_dim_set);
661 n_in = dim + n_arg;
663 space = pet_expr_access_get_parameter_space(expr);
664 n = pet_nested_n_in_space(space);
665 isl_space_free(space);
666 if (n == 0)
667 return expr;
669 expr = pet_expr_access_align_params(expr);
670 if (!expr)
671 return NULL;
673 space = pet_expr_access_get_parameter_space(expr);
674 nparam = isl_space_dim(space, isl_dim_param);
675 isl_space_free(space);
677 ctx = pet_expr_get_ctx(expr);
679 param2pos = isl_alloc_array(ctx, int, nparam);
680 t2pos = isl_alloc_array(ctx, int, n);
681 if (!param2pos)
682 goto error;
683 expr = pet_expr_extract_nested(expr, n, param2pos);
684 expr = mark_self_dependences(expr, n_arg);
685 if (!expr)
686 goto error;
688 n = 0;
689 space = pet_expr_access_get_parameter_space(expr);
690 nparam = isl_space_dim(space, isl_dim_param);
691 for (i = nparam - 1; i >= 0; --i) {
692 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
693 if (!pet_nested_in_id(id)) {
694 isl_id_free(id);
695 continue;
698 expr = pet_expr_access_move_dims(expr,
699 isl_dim_in, n_in + n, isl_dim_param, i, 1);
700 t2pos[n] = n_in + param2pos[i];
701 n++;
703 isl_id_free(id);
705 isl_space_free(space);
707 space = isl_space_copy(domain);
708 space = isl_space_from_domain(space);
709 space = isl_space_add_dims(space, isl_dim_out,
710 pet_expr_get_n_arg(expr));
711 space = isl_space_wrap(space);
712 ls = isl_local_space_from_space(isl_space_copy(space));
713 space = isl_space_from_domain(space);
714 space = isl_space_add_dims(space, isl_dim_out, n_in + n);
715 ma = isl_multi_aff_zero(space);
717 for (i = 0; i < n_in; ++i) {
718 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
719 isl_dim_set, i);
720 ma = isl_multi_aff_set_aff(ma, i, aff);
722 for (i = 0; i < n; ++i) {
723 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
724 isl_dim_set, t2pos[i]);
725 ma = isl_multi_aff_set_aff(ma, n_in + i, aff);
727 isl_local_space_free(ls);
729 expr = pet_expr_access_pullback_multi_aff(expr, ma);
731 expr = remove_marked_self_dependences(expr, dim, n_arg);
733 free(t2pos);
734 free(param2pos);
735 return expr;
736 error:
737 free(t2pos);
738 free(param2pos);
739 return pet_expr_free(expr);
742 /* For each nested access parameter in the domain of "stmt",
743 * construct a corresponding pet_expr, place it before the original
744 * elements in stmt->args and record its position in "param2pos".
745 * n is the number of nested access parameters.
747 struct pet_stmt *pet_stmt_extract_nested(struct pet_stmt *stmt, int n,
748 int *param2pos)
750 int i;
751 isl_ctx *ctx;
752 isl_space *space;
753 int n_arg;
754 pet_expr **args;
756 ctx = isl_set_get_ctx(stmt->domain);
758 n_arg = stmt->n_arg;
759 args = isl_calloc_array(ctx, pet_expr *, n + n_arg);
760 if (!args)
761 goto error;
763 space = isl_set_get_space(stmt->domain);
764 if (isl_space_is_wrapping(space))
765 space = isl_space_domain(isl_space_unwrap(space));
766 n_arg = pet_extract_nested_from_space(space, 0, args, param2pos);
767 isl_space_free(space);
769 if (n_arg < 0)
770 goto error;
772 for (i = 0; i < stmt->n_arg; ++i)
773 args[n_arg + i] = stmt->args[i];
774 free(stmt->args);
775 stmt->args = args;
776 stmt->n_arg += n_arg;
778 return stmt;
779 error:
780 if (args) {
781 for (i = 0; i < n; ++i)
782 pet_expr_free(args[i]);
783 free(args);
785 pet_stmt_free(stmt);
786 return NULL;
789 /* Check whether any of the arguments i of "stmt" starting at position "n"
790 * is equal to one of the first "n" arguments j.
791 * If so, combine the constraints on arguments i and j and remove
792 * argument i.
794 static struct pet_stmt *remove_duplicate_arguments(struct pet_stmt *stmt, int n)
796 int i, j;
797 isl_map *map;
799 if (!stmt)
800 return NULL;
801 if (n == 0)
802 return stmt;
803 if (n == stmt->n_arg)
804 return stmt;
806 map = isl_set_unwrap(stmt->domain);
808 for (i = stmt->n_arg - 1; i >= n; --i) {
809 for (j = 0; j < n; ++j)
810 if (pet_expr_is_equal(stmt->args[i], stmt->args[j]))
811 break;
812 if (j >= n)
813 continue;
815 map = isl_map_equate(map, isl_dim_out, i, isl_dim_out, j);
816 map = isl_map_project_out(map, isl_dim_out, i, 1);
818 pet_expr_free(stmt->args[i]);
819 for (j = i; j + 1 < stmt->n_arg; ++j)
820 stmt->args[j] = stmt->args[j + 1];
821 stmt->n_arg--;
824 stmt->domain = isl_map_wrap(map);
825 if (!stmt->domain)
826 goto error;
827 return stmt;
828 error:
829 pet_stmt_free(stmt);
830 return NULL;
833 /* Look for parameters in the iteration domain of "stmt" that
834 * refer to nested accesses. In particular, these are
835 * parameters with name "__pet_expr".
837 * If there are any such parameters, then as many extra variables
838 * (after identifying identical nested accesses) are inserted in the
839 * range of the map wrapped inside the domain, before the original variables.
840 * If the original domain is not a wrapped map, then a new wrapped
841 * map is created with zero output dimensions.
842 * The parameters are then equated to the corresponding output dimensions
843 * and subsequently projected out, from the iteration domain,
844 * the schedule and the access relations.
845 * For each of the output dimensions, a corresponding argument
846 * expression is inserted, embedded in the current iteration domain.
847 * param2pos maps the position of the parameter to the position
848 * of the corresponding output dimension in the wrapped map.
850 struct pet_stmt *pet_stmt_resolve_nested(struct pet_stmt *stmt)
852 int i, n;
853 int pos;
854 int nparam;
855 unsigned n_arg;
856 isl_ctx *ctx;
857 isl_map *map;
858 isl_space *space;
859 isl_multi_aff *ma;
860 int *param2pos;
862 if (!stmt)
863 return NULL;
865 n = pet_nested_n_in_set(stmt->domain);
866 if (n == 0)
867 return stmt;
869 ctx = isl_set_get_ctx(stmt->domain);
871 n_arg = stmt->n_arg;
872 nparam = isl_set_dim(stmt->domain, isl_dim_param);
873 param2pos = isl_alloc_array(ctx, int, nparam);
874 stmt = pet_stmt_extract_nested(stmt, n, param2pos);
875 if (!stmt) {
876 free(param2pos);
877 return NULL;
880 n = stmt->n_arg - n_arg;
881 if (isl_set_is_wrapping(stmt->domain))
882 map = isl_set_unwrap(stmt->domain);
883 else
884 map = isl_map_from_domain(stmt->domain);
885 map = isl_map_insert_dims(map, isl_dim_out, 0, n);
887 for (i = nparam - 1; i >= 0; --i) {
888 isl_id *id;
890 if (!pet_nested_in_map(map, i))
891 continue;
893 id = pet_expr_access_get_id(stmt->args[param2pos[i]]);
894 map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id);
895 map = isl_map_equate(map, isl_dim_param, i, isl_dim_out,
896 param2pos[i]);
897 map = isl_map_project_out(map, isl_dim_param, i, 1);
900 stmt->domain = isl_map_wrap(map);
902 stmt = pet_stmt_remove_nested_parameters(stmt);
903 stmt = remove_duplicate_arguments(stmt, n);
905 free(param2pos);
906 return stmt;
909 /* For each statement in "scop", move the parameters that correspond
910 * to nested access into the ranges of the domains and create
911 * corresponding argument expressions.
913 struct pet_scop *pet_scop_resolve_nested(struct pet_scop *scop)
915 int i;
917 if (!scop)
918 return NULL;
920 for (i = 0; i < scop->n_stmt; ++i) {
921 scop->stmts[i] = pet_stmt_resolve_nested(scop->stmts[i]);
922 if (!scop->stmts[i])
923 return pet_scop_free(scop);
926 return scop;