tree2scop.c: scop_from_non_affine_if: delay construction of body pet_scop(s)
[pet.git] / nest.c
blob2cc975c9cd2013ac970887e382153277895c8551
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 "expr.h"
38 #include "expr_arg.h"
39 #include "nest.h"
40 #include "scop.h"
42 /* A wrapper around pet_expr_free to be used as an isl_id free user function.
44 static void pet_expr_free_wrap(void *user)
46 pet_expr_free((pet_expr *) user);
49 /* Create an isl_id that refers to the nested access "expr".
51 __isl_give isl_id *pet_nested_pet_expr(__isl_take pet_expr *expr)
53 isl_id *id;
55 id = isl_id_alloc(pet_expr_get_ctx(expr), "__pet_expr", expr);
56 id = isl_id_set_free_user(id, &pet_expr_free_wrap);
58 return id;
61 /* Extract a pet_expr from an isl_id created by pet_nested_pet_expr.
62 * Such an isl_id has name "__pet_expr" and
63 * the user pointer points to a pet_expr object.
65 __isl_give pet_expr *pet_nested_extract_expr(__isl_keep isl_id *id)
67 return pet_expr_copy((pet_expr *) isl_id_get_user(id));
70 /* Does "id" refer to a nested access created by pet_nested_pet_expr?
72 int pet_nested_in_id(__isl_keep isl_id *id)
74 const char *name;
76 if (!id)
77 return 0;
78 if (!isl_id_get_user(id))
79 return 0;
81 name = isl_id_get_name(id);
82 return !strcmp(name, "__pet_expr");
85 /* Does parameter "pos" of "space" refer to a nested access?
87 static int pet_nested_in_space(__isl_keep isl_space *space, int pos)
89 int nested;
90 isl_id *id;
92 id = isl_space_get_dim_id(space, isl_dim_param, pos);
93 nested = pet_nested_in_id(id);
94 isl_id_free(id);
96 return nested;
99 /* Does parameter "pos" of "set" refer to a nested access?
101 int pet_nested_in_set(__isl_keep isl_set *set, int pos)
103 int nested;
104 isl_id *id;
106 id = isl_set_get_dim_id(set, isl_dim_param, pos);
107 nested = pet_nested_in_id(id);
108 isl_id_free(id);
110 return nested;
113 /* Does parameter "pos" of "map" refer to a nested access?
115 int pet_nested_in_map(__isl_keep isl_map *map, int pos)
117 int nested;
118 isl_id *id;
120 id = isl_map_get_dim_id(map, isl_dim_param, pos);
121 nested = pet_nested_in_id(id);
122 isl_id_free(id);
124 return nested;
127 /* Does "space" involve any parameters that refer to nested accesses?
129 int pet_nested_any_in_space(__isl_keep isl_space *space)
131 int i;
132 int nparam;
134 nparam = isl_space_dim(space, isl_dim_param);
135 for (i = 0; i < nparam; ++i)
136 if (pet_nested_in_space(space, i))
137 return 1;
139 return 0;
142 /* Does "pa" involve any parameters that refer to nested accesses?
144 int pet_nested_any_in_pw_aff(__isl_keep isl_pw_aff *pa)
146 isl_space *space;
147 int nested;
149 space = isl_pw_aff_get_space(pa);
150 nested = pet_nested_any_in_space(space);
151 isl_space_free(space);
153 return nested;
156 /* How many parameters of "space" refer to nested accesses?
158 int pet_nested_n_in_space(__isl_keep isl_space *space)
160 int i, n = 0;
161 int nparam;
163 nparam = isl_space_dim(space, isl_dim_param);
164 for (i = 0; i < nparam; ++i)
165 if (pet_nested_in_space(space, i))
166 ++n;
168 return n;
171 /* How many parameters of "map" refer to nested accesses?
173 int pet_nested_n_in_map(__isl_keep isl_map *map)
175 isl_space *space;
176 int n;
178 space = isl_map_get_space(map);
179 n = pet_nested_n_in_space(space);
180 isl_space_free(space);
182 return n;
185 /* How many parameters of "set" refer to nested accesses?
187 int pet_nested_n_in_set(__isl_keep isl_set *set)
189 isl_space *space;
190 int n;
192 space = isl_set_get_space(set);
193 n = pet_nested_n_in_space(space);
194 isl_space_free(space);
196 return n;
199 /* Remove all parameters from "set" that refer to nested accesses.
201 __isl_give isl_set *pet_nested_remove_from_set(__isl_take isl_set *set)
203 int i;
204 int nparam;
206 nparam = isl_set_dim(set, isl_dim_param);
207 for (i = nparam - 1; i >= 0; --i)
208 if (pet_nested_in_set(set, i))
209 set = isl_set_project_out(set, isl_dim_param, i, 1);
211 return set;
214 /* Remove all parameters from "map" that refer to nested accesses.
216 static __isl_give isl_map *pet_nested_remove_from_map(__isl_take isl_map *map)
218 int i;
219 int nparam;
221 nparam = isl_map_dim(map, isl_dim_param);
222 for (i = nparam - 1; i >= 0; --i)
223 if (pet_nested_in_map(map, i))
224 map = isl_map_project_out(map, isl_dim_param, i, 1);
226 return map;
229 /* Remove all parameters from "mpa" that refer to nested accesses.
231 static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff(
232 __isl_take isl_multi_pw_aff *mpa)
234 int i;
235 int nparam;
236 isl_space *space;
238 space = isl_multi_pw_aff_get_space(mpa);
239 nparam = isl_space_dim(space, isl_dim_param);
240 for (i = nparam - 1; i >= 0; --i) {
241 if (!pet_nested_in_space(space, i))
242 continue;
243 mpa = isl_multi_pw_aff_drop_dims(mpa, isl_dim_param, i, 1);
245 isl_space_free(space);
247 return mpa;
250 /* Remove all parameters from the index expression and access relation of "expr"
251 * that refer to nested accesses.
253 static __isl_give pet_expr *expr_remove_nested_parameters(
254 __isl_take pet_expr *expr, void *user)
256 expr = pet_expr_cow(expr);
257 if (!expr)
258 return NULL;
260 expr->acc.access = pet_nested_remove_from_map(expr->acc.access);
261 expr->acc.index = pet_nested_remove_from_multi_pw_aff(expr->acc.index);
262 if (!expr->acc.access || !expr->acc.index)
263 return pet_expr_free(expr);
265 return expr;
268 /* Remove all nested access parameters from the schedule and all
269 * accesses of "stmt".
270 * There is no need to remove them from the domain as these parameters
271 * have already been removed from the domain when this function is called.
273 struct pet_stmt *pet_stmt_remove_nested_parameters(struct pet_stmt *stmt)
275 int i;
277 if (!stmt)
278 return NULL;
279 stmt->schedule = pet_nested_remove_from_map(stmt->schedule);
280 stmt->body = pet_expr_map_access(stmt->body,
281 &expr_remove_nested_parameters, NULL);
282 if (!stmt->schedule || !stmt->body)
283 goto error;
284 for (i = 0; i < stmt->n_arg; ++i) {
285 stmt->args[i] = pet_expr_map_access(stmt->args[i],
286 &expr_remove_nested_parameters, NULL);
287 if (!stmt->args[i])
288 goto error;
291 return stmt;
292 error:
293 pet_stmt_free(stmt);
294 return NULL;
297 /* For each nested access parameter in "space",
298 * construct a corresponding pet_expr, place it in args and
299 * record its position in "param2pos".
300 * "n_arg" is the number of elements that are already in args.
301 * The position recorded in "param2pos" takes this number into account.
302 * If the pet_expr corresponding to a parameter is identical to
303 * the pet_expr corresponding to an earlier parameter, then these two
304 * parameters are made to refer to the same element in args.
306 * Return the final number of elements in args or -1 if an error has occurred.
308 int pet_extract_nested_from_space(__isl_keep isl_space *space,
309 int n_arg, __isl_give pet_expr **args, int *param2pos)
311 int i, nparam;
313 nparam = isl_space_dim(space, isl_dim_param);
314 for (i = 0; i < nparam; ++i) {
315 int j;
316 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
318 if (!pet_nested_in_id(id)) {
319 isl_id_free(id);
320 continue;
323 args[n_arg] = pet_nested_extract_expr(id);
324 isl_id_free(id);
325 if (!args[n_arg])
326 return -1;
328 for (j = 0; j < n_arg; ++j)
329 if (pet_expr_is_equal(args[j], args[n_arg]))
330 break;
332 if (j < n_arg) {
333 pet_expr_free(args[n_arg]);
334 args[n_arg] = NULL;
335 param2pos[i] = j;
336 } else
337 param2pos[i] = n_arg++;
340 return n_arg;
343 /* For each nested access parameter in the access relations in "expr",
344 * construct a corresponding pet_expr, append it to the arguments of "expr"
345 * and record its position in "param2pos" (relative to the initial
346 * number of arguments).
347 * n is the number of nested access parameters.
349 __isl_give pet_expr *pet_expr_extract_nested(__isl_take pet_expr *expr, int n,
350 int *param2pos)
352 isl_ctx *ctx;
353 isl_space *space;
354 int i, n_arg;
355 pet_expr **args;
357 ctx = pet_expr_get_ctx(expr);
358 args = isl_calloc_array(ctx, pet_expr *, n);
359 if (!args)
360 return pet_expr_free(expr);
362 n_arg = pet_expr_get_n_arg(expr);
363 space = pet_expr_access_get_parameter_space(expr);
364 n = pet_extract_nested_from_space(space, 0, args, param2pos);
365 isl_space_free(space);
367 if (n < 0)
368 expr = pet_expr_free(expr);
369 else
370 expr = pet_expr_set_n_arg(expr, n_arg + n);
372 for (i = 0; i < n; ++i)
373 expr = pet_expr_set_arg(expr, n_arg + i, args[i]);
374 free(args);
376 return expr;
379 /* Are "expr1" and "expr2" both array accesses such that
380 * the access relation of "expr1" is a subset of that of "expr2"?
381 * Only take into account the first "n_arg" arguments.
383 static int is_sub_access(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2,
384 int n_arg)
386 isl_id *id1, *id2;
387 isl_map *access1, *access2;
388 int is_subset;
389 int i, n1, n2;
391 if (!expr1 || !expr2)
392 return 0;
393 if (pet_expr_get_type(expr1) != pet_expr_access)
394 return 0;
395 if (pet_expr_get_type(expr2) != pet_expr_access)
396 return 0;
397 if (pet_expr_is_affine(expr1))
398 return 0;
399 if (pet_expr_is_affine(expr2))
400 return 0;
401 n1 = pet_expr_get_n_arg(expr1);
402 if (n1 > n_arg)
403 n1 = n_arg;
404 n2 = pet_expr_get_n_arg(expr2);
405 if (n2 > n_arg)
406 n2 = n_arg;
407 if (n1 != n2)
408 return 0;
409 for (i = 0; i < n1; ++i) {
410 pet_expr *arg1, *arg2;
411 int equal;
412 arg1 = pet_expr_get_arg(expr1, i);
413 arg2 = pet_expr_get_arg(expr2, i);
414 equal = pet_expr_is_equal(arg1, arg2);
415 pet_expr_free(arg1);
416 pet_expr_free(arg2);
417 if (equal < 0 || !equal)
418 return equal;
420 id1 = pet_expr_access_get_id(expr1);
421 id2 = pet_expr_access_get_id(expr2);
422 isl_id_free(id1);
423 isl_id_free(id2);
424 if (!id1 || !id2)
425 return 0;
426 if (id1 != id2)
427 return 0;
429 access1 = pet_expr_access_get_access(expr1);
430 access2 = pet_expr_access_get_access(expr2);
431 is_subset = isl_map_is_subset(access1, access2);
432 isl_map_free(access1);
433 isl_map_free(access2);
435 return is_subset;
438 /* Mark self dependences among the arguments of "expr" starting at "first".
439 * These arguments have already been added to the list of arguments
440 * but are not yet referenced directly from the index expression.
441 * Instead, they are still referenced through parameters encoding
442 * nested accesses.
444 * In particular, if "expr" is a read access, then check the arguments
445 * starting at "first" to see if "expr" accesses a subset of
446 * the elements accessed by the argument, or under more restrictive conditions.
447 * If so, then this nested access can be removed from the constraints
448 * governing the outer access. There is no point in restricting
449 * accesses to an array if in order to evaluate the restriction,
450 * we have to access the same elements (or more).
452 * Rather than removing the argument at this point (which would
453 * complicate the resolution of the other nested accesses), we simply
454 * mark it here by replacing it by a NaN pet_expr.
455 * These NaNs are then later removed in remove_marked_self_dependences.
457 static __isl_give pet_expr *mark_self_dependences(__isl_take pet_expr *expr,
458 int first)
460 int i, n;
462 if (pet_expr_access_is_write(expr))
463 return expr;
465 n = pet_expr_get_n_arg(expr);
466 for (i = first; i < n; ++i) {
467 int mark;
468 pet_expr *arg;
470 arg = pet_expr_get_arg(expr, i);
471 mark = is_sub_access(expr, arg, first);
472 pet_expr_free(arg);
473 if (mark < 0)
474 return pet_expr_free(expr);
475 if (!mark)
476 continue;
478 arg = pet_expr_new_int(isl_val_nan(pet_expr_get_ctx(expr)));
479 expr = pet_expr_set_arg(expr, i, arg);
482 return expr;
485 /* Is "expr" a NaN integer expression?
487 static int expr_is_nan(__isl_keep pet_expr *expr)
489 isl_val *v;
490 int is_nan;
492 if (pet_expr_get_type(expr) != pet_expr_int)
493 return 0;
495 v = pet_expr_int_get_val(expr);
496 is_nan = isl_val_is_nan(v);
497 isl_val_free(v);
499 return is_nan;
502 /* Check if we have marked any self dependences (as NaNs)
503 * in mark_self_dependences and remove them here.
504 * It is safe to project them out since these arguments
505 * can at most be referenced from the condition of the access relation,
506 * but do not appear in the index expression.
507 * "dim" is the dimension of the iteration domain.
509 static __isl_give pet_expr *remove_marked_self_dependences(
510 __isl_take pet_expr *expr, int dim, int first)
512 int i, n;
514 n = pet_expr_get_n_arg(expr);
515 for (i = n - 1; i >= first; --i) {
516 int is_nan;
517 pet_expr *arg;
519 arg = pet_expr_get_arg(expr, i);
520 is_nan = expr_is_nan(arg);
521 pet_expr_free(arg);
522 if (!is_nan)
523 continue;
524 expr = pet_expr_access_project_out_arg(expr, dim, i);
527 return expr;
530 /* Look for parameters in any access relation in "expr" that
531 * refer to nested accesses. In particular, these are
532 * parameters with name "__pet_expr".
534 * If there are any such parameters, then the domain of the index
535 * expression and the access relation, which is either [] or
536 * [[] -> [a_1,...,a_m]] at this point, is replaced by [[] -> [t_1,...,t_n]] or
537 * [[] -> [a_1,...,a_m,t_1,...,t_n]], with m the original number of arguments
538 * (n_arg) and n the number of these parameters
539 * (after identifying identical nested accesses).
541 * This transformation is performed in several steps.
542 * We first extract the arguments in pet_expr_extract_nested.
543 * param2pos maps the original parameter position to the position
544 * of the argument beyond the initial (n_arg) number of arguments.
545 * Then we move these parameters to input dimensions.
546 * t2pos maps the positions of these temporary input dimensions
547 * to the positions of the corresponding arguments.
548 * Finally, we express these temporary dimensions in terms of the domain
549 * [[] -> [a_1,...,a_m,t_1,...,t_n]] and precompose index expression and access
550 * relations with this function.
552 __isl_give pet_expr *pet_expr_resolve_nested(__isl_take pet_expr *expr)
554 int i, n, n_arg;
555 int nparam;
556 isl_ctx *ctx;
557 isl_space *space;
558 isl_local_space *ls;
559 isl_aff *aff;
560 isl_multi_aff *ma;
561 int *param2pos;
562 int *t2pos;
564 if (!expr)
565 return expr;
567 n_arg = pet_expr_get_n_arg(expr);
568 for (i = 0; i < n_arg; ++i) {
569 pet_expr *arg;
570 arg = pet_expr_get_arg(expr, i);
571 arg = pet_expr_resolve_nested(arg);
572 expr = pet_expr_set_arg(expr, i, arg);
575 if (pet_expr_get_type(expr) != pet_expr_access)
576 return expr;
578 space = pet_expr_access_get_parameter_space(expr);
579 n = pet_nested_n_in_space(space);
580 isl_space_free(space);
581 if (n == 0)
582 return expr;
584 expr = pet_expr_access_align_params(expr);
585 if (!expr)
586 return NULL;
588 space = pet_expr_access_get_parameter_space(expr);
589 nparam = isl_space_dim(space, isl_dim_param);
590 isl_space_free(space);
592 ctx = pet_expr_get_ctx(expr);
594 param2pos = isl_alloc_array(ctx, int, nparam);
595 t2pos = isl_alloc_array(ctx, int, n);
596 if (!param2pos)
597 goto error;
598 expr = pet_expr_extract_nested(expr, n, param2pos);
599 expr = mark_self_dependences(expr, n_arg);
600 if (!expr)
601 goto error;
603 n = 0;
604 space = pet_expr_access_get_parameter_space(expr);
605 nparam = isl_space_dim(space, isl_dim_param);
606 for (i = nparam - 1; i >= 0; --i) {
607 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
608 if (!pet_nested_in_id(id)) {
609 isl_id_free(id);
610 continue;
613 expr = pet_expr_access_move_dims(expr,
614 isl_dim_in, n_arg + n, isl_dim_param, i, 1);
615 t2pos[n] = n_arg + param2pos[i];
616 n++;
618 isl_id_free(id);
620 isl_space_free(space);
622 space = pet_expr_access_get_parameter_space(expr);
623 space = isl_space_set_from_params(space);
624 space = isl_space_add_dims(space, isl_dim_set,
625 pet_expr_get_n_arg(expr));
626 space = isl_space_wrap(isl_space_from_range(space));
627 ls = isl_local_space_from_space(isl_space_copy(space));
628 space = isl_space_from_domain(space);
629 space = isl_space_add_dims(space, isl_dim_out, n_arg + n);
630 ma = isl_multi_aff_zero(space);
632 for (i = 0; i < n_arg; ++i) {
633 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
634 isl_dim_set, i);
635 ma = isl_multi_aff_set_aff(ma, i, aff);
637 for (i = 0; i < n; ++i) {
638 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
639 isl_dim_set, t2pos[i]);
640 ma = isl_multi_aff_set_aff(ma, n_arg + i, aff);
642 isl_local_space_free(ls);
644 expr = pet_expr_access_pullback_multi_aff(expr, ma);
646 expr = remove_marked_self_dependences(expr, 0, n_arg);
648 free(t2pos);
649 free(param2pos);
650 return expr;
651 error:
652 free(t2pos);
653 free(param2pos);
654 return pet_expr_free(expr);
657 /* Precompose the access relation and the index expression associated
658 * to "expr" with the function pointed to by "user",
659 * thereby embedding the access relation in the domain of this function.
660 * The initial domain of the access relation and the index expression
661 * is the zero-dimensional domain.
663 static __isl_give pet_expr *embed_access(__isl_take pet_expr *expr, void *user)
665 isl_multi_aff *ma = (isl_multi_aff *) user;
667 return pet_expr_access_pullback_multi_aff(expr, isl_multi_aff_copy(ma));
670 /* Precompose all access relations in "expr" with "ma", thereby
671 * embedding them in the domain of "ma".
673 static __isl_give pet_expr *embed(__isl_take pet_expr *expr,
674 __isl_keep isl_multi_aff *ma)
676 return pet_expr_map_access(expr, &embed_access, ma);
679 /* For each nested access parameter in the domain of "stmt",
680 * construct a corresponding pet_expr, place it before the original
681 * elements in stmt->args and record its position in "param2pos".
682 * n is the number of nested access parameters.
684 struct pet_stmt *pet_stmt_extract_nested(struct pet_stmt *stmt, int n,
685 int *param2pos)
687 int i;
688 isl_ctx *ctx;
689 isl_space *space;
690 int n_arg;
691 pet_expr **args;
693 ctx = isl_set_get_ctx(stmt->domain);
695 n_arg = stmt->n_arg;
696 args = isl_calloc_array(ctx, pet_expr *, n + n_arg);
697 if (!args)
698 goto error;
700 space = isl_set_get_space(stmt->domain);
701 n_arg = pet_extract_nested_from_space(space, 0, args, param2pos);
702 isl_space_free(space);
704 if (n_arg < 0)
705 goto error;
707 for (i = 0; i < stmt->n_arg; ++i)
708 args[n_arg + i] = stmt->args[i];
709 free(stmt->args);
710 stmt->args = args;
711 stmt->n_arg += n_arg;
713 return stmt;
714 error:
715 if (args) {
716 for (i = 0; i < n; ++i)
717 pet_expr_free(args[i]);
718 free(args);
720 pet_stmt_free(stmt);
721 return NULL;
724 /* Check whether any of the arguments i of "stmt" starting at position "n"
725 * is equal to one of the first "n" arguments j.
726 * If so, combine the constraints on arguments i and j and remove
727 * argument i.
729 static struct pet_stmt *remove_duplicate_arguments(struct pet_stmt *stmt, int n)
731 int i, j;
732 isl_map *map;
734 if (!stmt)
735 return NULL;
736 if (n == 0)
737 return stmt;
738 if (n == stmt->n_arg)
739 return stmt;
741 map = isl_set_unwrap(stmt->domain);
743 for (i = stmt->n_arg - 1; i >= n; --i) {
744 for (j = 0; j < n; ++j)
745 if (pet_expr_is_equal(stmt->args[i], stmt->args[j]))
746 break;
747 if (j >= n)
748 continue;
750 map = isl_map_equate(map, isl_dim_out, i, isl_dim_out, j);
751 map = isl_map_project_out(map, isl_dim_out, i, 1);
753 pet_expr_free(stmt->args[i]);
754 for (j = i; j + 1 < stmt->n_arg; ++j)
755 stmt->args[j] = stmt->args[j + 1];
756 stmt->n_arg--;
759 stmt->domain = isl_map_wrap(map);
760 if (!stmt->domain)
761 goto error;
762 return stmt;
763 error:
764 pet_stmt_free(stmt);
765 return NULL;
768 /* Look for parameters in the iteration domain of "stmt" that
769 * refer to nested accesses. In particular, these are
770 * parameters with name "__pet_expr".
772 * If there are any such parameters, then as many extra variables
773 * (after identifying identical nested accesses) are inserted in the
774 * range of the map wrapped inside the domain, before the original variables.
775 * If the original domain is not a wrapped map, then a new wrapped
776 * map is created with zero output dimensions.
777 * The parameters are then equated to the corresponding output dimensions
778 * and subsequently projected out, from the iteration domain,
779 * the schedule and the access relations.
780 * For each of the output dimensions, a corresponding argument
781 * expression is inserted. Initially they are created with
782 * a zero-dimensional domain, so they have to be embedded
783 * in the current iteration domain.
784 * param2pos maps the position of the parameter to the position
785 * of the corresponding output dimension in the wrapped map.
787 struct pet_stmt *pet_stmt_resolve_nested(struct pet_stmt *stmt)
789 int i, n;
790 int pos;
791 int nparam;
792 unsigned n_arg;
793 isl_ctx *ctx;
794 isl_map *map;
795 isl_space *space;
796 isl_multi_aff *ma;
797 int *param2pos;
799 if (!stmt)
800 return NULL;
802 n = pet_nested_n_in_set(stmt->domain);
803 if (n == 0)
804 return stmt;
806 ctx = isl_set_get_ctx(stmt->domain);
808 n_arg = stmt->n_arg;
809 nparam = isl_set_dim(stmt->domain, isl_dim_param);
810 param2pos = isl_alloc_array(ctx, int, nparam);
811 stmt = pet_stmt_extract_nested(stmt, n, param2pos);
812 if (!stmt) {
813 free(param2pos);
814 return NULL;
817 n = stmt->n_arg - n_arg;
818 if (isl_set_is_wrapping(stmt->domain))
819 map = isl_set_unwrap(stmt->domain);
820 else
821 map = isl_map_from_domain(stmt->domain);
822 map = isl_map_insert_dims(map, isl_dim_out, 0, n);
824 for (i = nparam - 1; i >= 0; --i) {
825 isl_id *id;
827 if (!pet_nested_in_map(map, i))
828 continue;
830 id = pet_expr_access_get_id(stmt->args[param2pos[i]]);
831 map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id);
832 map = isl_map_equate(map, isl_dim_param, i, isl_dim_out,
833 param2pos[i]);
834 map = isl_map_project_out(map, isl_dim_param, i, 1);
837 stmt->domain = isl_map_wrap(map);
839 space = isl_space_unwrap(isl_set_get_space(stmt->domain));
840 space = isl_space_from_domain(isl_space_domain(space));
841 ma = isl_multi_aff_zero(space);
842 for (pos = 0; pos < n; ++pos)
843 stmt->args[pos] = embed(stmt->args[pos], ma);
844 isl_multi_aff_free(ma);
846 stmt = pet_stmt_remove_nested_parameters(stmt);
847 stmt = remove_duplicate_arguments(stmt, n);
849 free(param2pos);
850 return stmt;
853 /* For each statement in "scop", move the parameters that correspond
854 * to nested access into the ranges of the domains and create
855 * corresponding argument expressions.
857 struct pet_scop *pet_scop_resolve_nested(struct pet_scop *scop)
859 int i;
861 if (!scop)
862 return NULL;
864 for (i = 0; i < scop->n_stmt; ++i) {
865 scop->stmts[i] = pet_stmt_resolve_nested(scop->stmts[i]);
866 if (!scop->stmts[i])
867 return pet_scop_free(scop);
870 return scop;