PetScan::extract_expr: improve error message
[pet.git] / nest.c
blobbde49a6fb878369bb531dcc939f586f9883cede9
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"
42 #include "tree.h"
44 /* A wrapper around pet_expr_free to be used as an isl_id free user function.
46 static void pet_expr_free_wrap(void *user)
48 pet_expr_free((pet_expr *) user);
51 /* Create an isl_id that refers to the nested access "expr".
53 __isl_give isl_id *pet_nested_pet_expr(__isl_take pet_expr *expr)
55 isl_id *id;
57 id = isl_id_alloc(pet_expr_get_ctx(expr), "__pet_expr", expr);
58 id = isl_id_set_free_user(id, &pet_expr_free_wrap);
60 return id;
63 /* Extract a pet_expr from an isl_id created by pet_nested_pet_expr.
64 * Such an isl_id has name "__pet_expr" and
65 * the user pointer points to a pet_expr object.
67 __isl_give pet_expr *pet_nested_extract_expr(__isl_keep isl_id *id)
69 return pet_expr_copy((pet_expr *) isl_id_get_user(id));
72 /* Does "id" refer to a nested access created by pet_nested_pet_expr?
74 int pet_nested_in_id(__isl_keep isl_id *id)
76 const char *name;
78 if (!id)
79 return 0;
80 if (!isl_id_get_user(id))
81 return 0;
83 name = isl_id_get_name(id);
84 return !strcmp(name, "__pet_expr");
87 /* Does parameter "pos" of "space" refer to a nested access?
89 static int pet_nested_in_space(__isl_keep isl_space *space, int pos)
91 int nested;
92 isl_id *id;
94 id = isl_space_get_dim_id(space, isl_dim_param, pos);
95 nested = pet_nested_in_id(id);
96 isl_id_free(id);
98 return nested;
101 /* Does parameter "pos" of "set" refer to a nested access?
103 int pet_nested_in_set(__isl_keep isl_set *set, int pos)
105 int nested;
106 isl_id *id;
108 id = isl_set_get_dim_id(set, isl_dim_param, pos);
109 nested = pet_nested_in_id(id);
110 isl_id_free(id);
112 return nested;
115 /* Does parameter "pos" of "map" refer to a nested access?
117 int pet_nested_in_map(__isl_keep isl_map *map, int pos)
119 int nested;
120 isl_id *id;
122 id = isl_map_get_dim_id(map, isl_dim_param, pos);
123 nested = pet_nested_in_id(id);
124 isl_id_free(id);
126 return nested;
129 /* Does parameter "pos" of "umap" refer to a nested access?
131 static int pet_nested_in_union_map(__isl_keep isl_union_map *umap, int pos)
133 int nested;
134 isl_id *id;
136 id = isl_union_map_get_dim_id(umap, isl_dim_param, pos);
137 nested = pet_nested_in_id(id);
138 isl_id_free(id);
140 return nested;
143 /* Does "space" involve any parameters that refer to nested accesses?
145 int pet_nested_any_in_space(__isl_keep isl_space *space)
147 int i;
148 int nparam;
150 nparam = isl_space_dim(space, isl_dim_param);
151 for (i = 0; i < nparam; ++i)
152 if (pet_nested_in_space(space, i))
153 return 1;
155 return 0;
158 /* Does "pa" involve any parameters that refer to nested accesses?
160 int pet_nested_any_in_pw_aff(__isl_keep isl_pw_aff *pa)
162 isl_space *space;
163 int nested;
165 space = isl_pw_aff_get_space(pa);
166 nested = pet_nested_any_in_space(space);
167 isl_space_free(space);
169 return nested;
172 /* How many parameters of "space" refer to nested accesses?
174 int pet_nested_n_in_space(__isl_keep isl_space *space)
176 int i, n = 0;
177 int nparam;
179 nparam = isl_space_dim(space, isl_dim_param);
180 for (i = 0; i < nparam; ++i)
181 if (pet_nested_in_space(space, i))
182 ++n;
184 return n;
187 /* How many parameters of "map" refer to nested accesses?
189 int pet_nested_n_in_map(__isl_keep isl_map *map)
191 isl_space *space;
192 int n;
194 space = isl_map_get_space(map);
195 n = pet_nested_n_in_space(space);
196 isl_space_free(space);
198 return n;
201 /* How many parameters of "set" refer to nested accesses?
203 int pet_nested_n_in_set(__isl_keep isl_set *set)
205 isl_space *space;
206 int n;
208 space = isl_set_get_space(set);
209 n = pet_nested_n_in_space(space);
210 isl_space_free(space);
212 return n;
215 /* Remove all parameters from "space" that refer to nested accesses.
217 __isl_give isl_space *pet_nested_remove_from_space(__isl_take isl_space *space)
219 int i;
220 int nparam;
222 nparam = isl_space_dim(space, isl_dim_param);
223 for (i = nparam - 1; i >= 0; --i)
224 if (pet_nested_in_space(space, i))
225 space = isl_space_drop_dims(space, isl_dim_param, i, 1);
227 return space;
230 /* Remove all parameters from "set" that refer to nested accesses.
232 __isl_give isl_set *pet_nested_remove_from_set(__isl_take isl_set *set)
234 int i;
235 int nparam;
237 nparam = isl_set_dim(set, isl_dim_param);
238 for (i = nparam - 1; i >= 0; --i)
239 if (pet_nested_in_set(set, i))
240 set = isl_set_project_out(set, isl_dim_param, i, 1);
242 return set;
245 /* Remove all parameters from "map" that refer to nested accesses.
247 static __isl_give isl_map *pet_nested_remove_from_map(__isl_take isl_map *map)
249 int i;
250 int nparam;
252 nparam = isl_map_dim(map, isl_dim_param);
253 for (i = nparam - 1; i >= 0; --i)
254 if (pet_nested_in_map(map, i))
255 map = isl_map_project_out(map, isl_dim_param, i, 1);
257 return map;
260 /* Remove all parameters from "umap" that refer to nested accesses.
262 static __isl_give isl_union_map *pet_nested_remove_from_union_map(
263 __isl_take isl_union_map *umap)
265 int i;
266 int nparam;
268 nparam = isl_union_map_dim(umap, isl_dim_param);
269 for (i = nparam - 1; i >= 0; --i)
270 if (pet_nested_in_union_map(umap, i))
271 umap = isl_union_map_project_out(umap,
272 isl_dim_param, i, 1);
274 return umap;
277 /* Remove all parameters from "mpa" that refer to nested accesses.
279 static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff(
280 __isl_take isl_multi_pw_aff *mpa)
282 int i;
283 int nparam;
284 isl_space *space;
286 space = isl_multi_pw_aff_get_space(mpa);
287 nparam = isl_space_dim(space, isl_dim_param);
288 for (i = nparam - 1; i >= 0; --i) {
289 if (!pet_nested_in_space(space, i))
290 continue;
291 mpa = isl_multi_pw_aff_drop_dims(mpa, isl_dim_param, i, 1);
293 isl_space_free(space);
295 return mpa;
298 /* Remove all parameters from the index expression and
299 * access relations of "expr" that refer to nested accesses.
301 static __isl_give pet_expr *expr_remove_nested_parameters(
302 __isl_take pet_expr *expr, void *user)
304 enum pet_expr_access_type type;
306 expr = pet_expr_cow(expr);
307 if (!expr)
308 return NULL;
310 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
311 if (!expr->acc.access[type])
312 continue;
313 expr->acc.access[type] =
314 pet_nested_remove_from_union_map(expr->acc.access[type]);
315 if (!expr->acc.access[type])
316 break;
318 expr->acc.index = pet_nested_remove_from_multi_pw_aff(expr->acc.index);
319 if (type < pet_expr_access_end || !expr->acc.index)
320 return pet_expr_free(expr);
322 return expr;
325 /* Remove all nested access parameters from the schedule and all
326 * accesses of "stmt".
327 * There is no need to remove them from the domain as these parameters
328 * have already been removed from the domain when this function is called.
330 struct pet_stmt *pet_stmt_remove_nested_parameters(struct pet_stmt *stmt)
332 int i;
334 if (!stmt)
335 return NULL;
336 stmt->body = pet_tree_map_access_expr(stmt->body,
337 &expr_remove_nested_parameters, NULL);
338 if (!stmt->body)
339 goto error;
340 for (i = 0; i < stmt->n_arg; ++i) {
341 stmt->args[i] = pet_expr_map_access(stmt->args[i],
342 &expr_remove_nested_parameters, NULL);
343 if (!stmt->args[i])
344 goto error;
347 return stmt;
348 error:
349 pet_stmt_free(stmt);
350 return NULL;
353 /* Set *dim to the dimension of the domain of the access expression "expr" and
354 * abort the search.
356 static int set_dim(__isl_keep pet_expr *expr, void *user)
358 int *dim = user;
359 isl_space *space;
361 space = pet_expr_access_get_domain_space(expr);
362 *dim = isl_space_dim(space, isl_dim_set);
363 isl_space_free(space);
365 return -1;
368 /* Determine the dimension of the domain of the access expressions in "expr".
370 * In particular, return the dimension of the domain of the first access
371 * expression in "expr" as all access expressions should have the same
372 * domain.
374 * If "expr" does not contain any access expressions, then we return 0.
376 static int pet_expr_domain_dim(__isl_keep pet_expr *expr)
378 int dim = -1;
380 if (pet_expr_foreach_access_expr(expr, &set_dim, &dim) >= 0)
381 return 0;
383 return dim;
386 /* Embed all access expressions in "expr" in the domain "space".
387 * The initial domain of the access expressions
388 * is an anonymous domain of a dimension that may be lower
389 * than the dimension of "space".
390 * We may therefore need to introduce extra dimensions as well as
391 * (potentially) the name of "space".
393 static __isl_give pet_expr *embed(__isl_take pet_expr *expr,
394 __isl_keep isl_space *space)
396 int n;
397 isl_multi_pw_aff *mpa;
399 n = pet_expr_domain_dim(expr);
400 if (n < 0)
401 return pet_expr_free(expr);
403 space = isl_space_copy(space);
404 mpa = isl_multi_pw_aff_from_multi_aff(pet_prefix_projection(space, n));
405 expr = pet_expr_update_domain(expr, mpa);
407 return expr;
410 /* For each nested access parameter in "space",
411 * construct a corresponding pet_expr, place it in args and
412 * record its position in "param2pos".
413 * The constructed pet_expr objects are embedded in "space"
414 * (with the nested access parameters removed).
415 * "n_arg" is the number of elements that are already in args.
416 * The position recorded in "param2pos" takes this number into account.
417 * If the pet_expr corresponding to a parameter is identical to
418 * the pet_expr corresponding to an earlier parameter, then these two
419 * parameters are made to refer to the same element in args.
421 * Return the final number of elements in args or -1 if an error has occurred.
423 int pet_extract_nested_from_space(__isl_keep isl_space *space,
424 int n_arg, __isl_give pet_expr **args, int *param2pos)
426 int i, nparam;
427 isl_space *domain;
429 domain = isl_space_copy(space);
430 domain = pet_nested_remove_from_space(domain);
431 nparam = isl_space_dim(space, isl_dim_param);
432 for (i = 0; i < nparam; ++i) {
433 int j;
434 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
436 if (!pet_nested_in_id(id)) {
437 isl_id_free(id);
438 continue;
441 args[n_arg] = embed(pet_nested_extract_expr(id), domain);
442 isl_id_free(id);
443 if (!args[n_arg])
444 return -1;
446 for (j = 0; j < n_arg; ++j)
447 if (pet_expr_is_equal(args[j], args[n_arg]))
448 break;
450 if (j < n_arg) {
451 pet_expr_free(args[n_arg]);
452 args[n_arg] = NULL;
453 param2pos[i] = j;
454 } else
455 param2pos[i] = n_arg++;
457 isl_space_free(domain);
459 return n_arg;
462 /* For each nested access parameter in the access relations in "expr",
463 * construct a corresponding pet_expr, append it to the arguments of "expr"
464 * and record its position in "param2pos" (relative to the initial
465 * number of arguments).
466 * n is the number of nested access parameters.
468 __isl_give pet_expr *pet_expr_extract_nested(__isl_take pet_expr *expr, int n,
469 int *param2pos)
471 isl_ctx *ctx;
472 isl_space *space;
473 int i, n_arg;
474 pet_expr **args;
476 ctx = pet_expr_get_ctx(expr);
477 args = isl_calloc_array(ctx, pet_expr *, n);
478 if (!args)
479 return pet_expr_free(expr);
481 n_arg = pet_expr_get_n_arg(expr);
482 space = pet_expr_access_get_domain_space(expr);
483 n = pet_extract_nested_from_space(space, 0, args, param2pos);
484 isl_space_free(space);
486 if (n < 0)
487 expr = pet_expr_free(expr);
488 else
489 expr = pet_expr_set_n_arg(expr, n_arg + n);
491 for (i = 0; i < n; ++i)
492 expr = pet_expr_set_arg(expr, n_arg + i, args[i]);
493 free(args);
495 return expr;
498 /* Mark self dependences among the arguments of "expr" starting at "first".
499 * These arguments have already been added to the list of arguments
500 * but are not yet referenced directly from the index expression.
501 * Instead, they are still referenced through parameters encoding
502 * nested accesses.
504 * In particular, if "expr" is a read access, then check the arguments
505 * starting at "first" to see if "expr" accesses a subset of
506 * the elements accessed by the argument, or under more restrictive conditions.
507 * If so, then this nested access can be removed from the constraints
508 * governing the outer access. There is no point in restricting
509 * accesses to an array if in order to evaluate the restriction,
510 * we have to access the same elements (or more).
512 * Rather than removing the argument at this point (which would
513 * complicate the resolution of the other nested accesses), we simply
514 * mark it here by replacing it by a NaN pet_expr.
515 * These NaNs are then later removed in remove_marked_self_dependences.
517 static __isl_give pet_expr *mark_self_dependences(__isl_take pet_expr *expr,
518 int first)
520 int i, n;
522 if (pet_expr_access_is_write(expr))
523 return expr;
525 n = pet_expr_get_n_arg(expr);
526 for (i = first; i < n; ++i) {
527 int mark;
528 pet_expr *arg;
530 arg = pet_expr_get_arg(expr, i);
531 mark = pet_expr_is_sub_access(expr, arg, first);
532 pet_expr_free(arg);
533 if (mark < 0)
534 return pet_expr_free(expr);
535 if (!mark)
536 continue;
538 arg = pet_expr_new_int(isl_val_nan(pet_expr_get_ctx(expr)));
539 expr = pet_expr_set_arg(expr, i, arg);
542 return expr;
545 /* Is "expr" a NaN integer expression?
547 static int expr_is_nan(__isl_keep pet_expr *expr)
549 isl_val *v;
550 int is_nan;
552 if (pet_expr_get_type(expr) != pet_expr_int)
553 return 0;
555 v = pet_expr_int_get_val(expr);
556 is_nan = isl_val_is_nan(v);
557 isl_val_free(v);
559 return is_nan;
562 /* Check if we have marked any self dependences (as NaNs)
563 * in mark_self_dependences and remove them here.
564 * It is safe to project them out since these arguments
565 * can at most be referenced from the condition of the access relation,
566 * but do not appear in the index expression.
567 * "dim" is the dimension of the iteration domain.
569 static __isl_give pet_expr *remove_marked_self_dependences(
570 __isl_take pet_expr *expr, int dim, int first)
572 int i, n;
574 n = pet_expr_get_n_arg(expr);
575 for (i = n - 1; i >= first; --i) {
576 int is_nan;
577 pet_expr *arg;
579 arg = pet_expr_get_arg(expr, i);
580 is_nan = expr_is_nan(arg);
581 pet_expr_free(arg);
582 if (!is_nan)
583 continue;
584 expr = pet_expr_access_project_out_arg(expr, dim, i);
587 return expr;
590 /* Look for parameters in any access relation in "expr" that
591 * refer to nested accesses. In particular, these are
592 * parameters with name "__pet_expr".
594 * If there are any such parameters, then the domain of the index
595 * expression and the access relation, which is either "domain" or
596 * [domain -> [a_1,...,a_m]] at this point, is replaced by
597 * [domain -> [t_1,...,t_n]] or [domain -> [a_1,...,a_m,t_1,...,t_n]],
598 * with m the original number of arguments (n_arg) and
599 * n the number of these parameters
600 * (after identifying identical nested accesses).
602 * This transformation is performed in several steps.
603 * We first extract the arguments in pet_expr_extract_nested.
604 * param2pos maps the original parameter position to the position
605 * of the argument beyond the initial (n_arg) number of arguments.
606 * Then we move these parameters to input dimensions.
607 * t2pos maps the positions of these temporary input dimensions
608 * to the positions of the corresponding arguments inside the space
609 * [domain -> [t_1,...,t_n]].
610 * Finally, we express these temporary dimensions in terms of the domain
611 * [domain -> [a_1,...,a_m,t_1,...,t_n]] and precompose index expression and
612 * access relations with this function.
614 __isl_give pet_expr *pet_expr_resolve_nested(__isl_take pet_expr *expr,
615 __isl_keep isl_space *domain)
617 int i, n, n_arg, dim, n_in;
618 int nparam;
619 isl_ctx *ctx;
620 isl_space *space;
621 isl_local_space *ls;
622 isl_aff *aff;
623 isl_multi_aff *ma;
624 int *param2pos;
625 int *t2pos;
627 if (!expr)
628 return expr;
630 n_arg = pet_expr_get_n_arg(expr);
631 for (i = 0; i < n_arg; ++i) {
632 pet_expr *arg;
633 arg = pet_expr_get_arg(expr, i);
634 arg = pet_expr_resolve_nested(arg, domain);
635 expr = pet_expr_set_arg(expr, i, arg);
638 if (pet_expr_get_type(expr) != pet_expr_access)
639 return expr;
641 dim = isl_space_dim(domain, isl_dim_set);
642 n_in = dim + n_arg;
644 space = pet_expr_access_get_parameter_space(expr);
645 n = pet_nested_n_in_space(space);
646 isl_space_free(space);
647 if (n == 0)
648 return expr;
650 expr = pet_expr_access_align_params(expr);
651 if (!expr)
652 return NULL;
654 space = pet_expr_access_get_parameter_space(expr);
655 nparam = isl_space_dim(space, isl_dim_param);
656 isl_space_free(space);
658 ctx = pet_expr_get_ctx(expr);
660 param2pos = isl_alloc_array(ctx, int, nparam);
661 t2pos = isl_alloc_array(ctx, int, n);
662 if (!param2pos)
663 goto error;
664 expr = pet_expr_extract_nested(expr, n, param2pos);
665 expr = mark_self_dependences(expr, n_arg);
666 if (!expr)
667 goto error;
669 n = 0;
670 space = pet_expr_access_get_parameter_space(expr);
671 nparam = isl_space_dim(space, isl_dim_param);
672 for (i = nparam - 1; i >= 0; --i) {
673 isl_id *id = isl_space_get_dim_id(space, isl_dim_param, i);
674 if (!pet_nested_in_id(id)) {
675 isl_id_free(id);
676 continue;
679 expr = pet_expr_access_move_dims(expr,
680 isl_dim_in, n_in + n, isl_dim_param, i, 1);
681 t2pos[n] = n_in + param2pos[i];
682 n++;
684 isl_id_free(id);
686 isl_space_free(space);
688 space = isl_space_copy(domain);
689 space = isl_space_from_domain(space);
690 space = isl_space_add_dims(space, isl_dim_out,
691 pet_expr_get_n_arg(expr));
692 space = isl_space_wrap(space);
693 ls = isl_local_space_from_space(isl_space_copy(space));
694 space = isl_space_from_domain(space);
695 space = isl_space_add_dims(space, isl_dim_out, n_in + n);
696 ma = isl_multi_aff_zero(space);
698 for (i = 0; i < n_in; ++i) {
699 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
700 isl_dim_set, i);
701 ma = isl_multi_aff_set_aff(ma, i, aff);
703 for (i = 0; i < n; ++i) {
704 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
705 isl_dim_set, t2pos[i]);
706 ma = isl_multi_aff_set_aff(ma, n_in + i, aff);
708 isl_local_space_free(ls);
710 expr = pet_expr_access_pullback_multi_aff(expr, ma);
712 expr = remove_marked_self_dependences(expr, dim, n_arg);
714 free(t2pos);
715 free(param2pos);
716 return expr;
717 error:
718 free(t2pos);
719 free(param2pos);
720 return pet_expr_free(expr);
723 /* Wrapper around pet_expr_resolve_nested
724 * for use as a callback to pet_tree_map_expr.
726 static __isl_give pet_expr *resolve_nested(__isl_take pet_expr *expr,
727 void *user)
729 isl_space *space = user;
731 return pet_expr_resolve_nested(expr, space);
734 /* Call pet_expr_resolve_nested on each of the expressions in "tree".
736 __isl_give pet_tree *pet_tree_resolve_nested(__isl_take pet_tree *tree,
737 __isl_keep isl_space *space)
739 return pet_tree_map_expr(tree, &resolve_nested, space);
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;