add pet_expr_access_get_domain_space
[pet.git] / expr.c
blobd04ceb315bbed76f9524b0e5592e008269b49b34
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 "array.h"
39 #include "expr.h"
40 #include "expr_arg.h"
41 #include "filter.h"
42 #include "nest.h"
43 #include "options.h"
44 #include "value_bounds.h"
46 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
48 static char *type_str[] = {
49 [pet_expr_access] = "access",
50 [pet_expr_call] = "call",
51 [pet_expr_cast] = "cast",
52 [pet_expr_double] = "double",
53 [pet_expr_int] = "int",
54 [pet_expr_op] = "op",
57 static char *op_str[] = {
58 [pet_op_add_assign] = "+=",
59 [pet_op_sub_assign] = "-=",
60 [pet_op_mul_assign] = "*=",
61 [pet_op_div_assign] = "/=",
62 [pet_op_assign] = "=",
63 [pet_op_add] = "+",
64 [pet_op_sub] = "-",
65 [pet_op_mul] = "*",
66 [pet_op_div] = "/",
67 [pet_op_mod] = "%",
68 [pet_op_shl] = "<<",
69 [pet_op_shr] = ">>",
70 [pet_op_eq] = "==",
71 [pet_op_ne] = "!=",
72 [pet_op_le] = "<=",
73 [pet_op_ge] = ">=",
74 [pet_op_lt] = "<",
75 [pet_op_gt] = ">",
76 [pet_op_minus] = "-",
77 [pet_op_post_inc] = "++",
78 [pet_op_post_dec] = "--",
79 [pet_op_pre_inc] = "++",
80 [pet_op_pre_dec] = "--",
81 [pet_op_address_of] = "&",
82 [pet_op_and] = "&",
83 [pet_op_xor] = "^",
84 [pet_op_or] = "|",
85 [pet_op_not] = "~",
86 [pet_op_land] = "&&",
87 [pet_op_lor] = "||",
88 [pet_op_lnot] = "!",
89 [pet_op_cond] = "?:",
90 [pet_op_assume] = "assume",
91 [pet_op_kill] = "kill"
94 const char *pet_op_str(enum pet_op_type op)
96 return op_str[op];
99 int pet_op_is_inc_dec(enum pet_op_type op)
101 return op == pet_op_post_inc || op == pet_op_post_dec ||
102 op == pet_op_pre_inc || op == pet_op_pre_dec;
105 const char *pet_type_str(enum pet_expr_type type)
107 return type_str[type];
110 enum pet_op_type pet_str_op(const char *str)
112 int i;
114 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
115 if (!strcmp(op_str[i], str))
116 return i;
118 return -1;
121 enum pet_expr_type pet_str_type(const char *str)
123 int i;
125 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
126 if (!strcmp(type_str[i], str))
127 return i;
129 return -1;
132 /* Construct a pet_expr of the given type.
134 __isl_give pet_expr *pet_expr_alloc(isl_ctx *ctx, enum pet_expr_type type)
136 pet_expr *expr;
138 expr = isl_calloc_type(ctx, struct pet_expr);
139 if (!expr)
140 return NULL;
142 expr->ctx = ctx;
143 isl_ctx_ref(ctx);
144 expr->type = type;
145 expr->ref = 1;
147 return expr;
150 /* Construct an access pet_expr from an access relation and an index expression.
151 * By default, it is considered to be a read access.
153 __isl_give pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
154 __isl_take isl_multi_pw_aff *index)
156 isl_ctx *ctx = isl_map_get_ctx(access);
157 pet_expr *expr;
159 if (!index || !access)
160 goto error;
161 expr = pet_expr_alloc(ctx, pet_expr_access);
162 if (!expr)
163 goto error;
165 expr->acc.access = access;
166 expr->acc.index = index;
167 expr->acc.read = 1;
168 expr->acc.write = 0;
170 return expr;
171 error:
172 isl_map_free(access);
173 isl_multi_pw_aff_free(index);
174 return NULL;
177 /* Construct an access pet_expr from an index expression.
178 * By default, the access is considered to be a read access.
180 __isl_give pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
182 isl_map *access;
184 access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
185 return pet_expr_from_access_and_index(access, index);
188 /* Extend the range of "access" with "n" dimensions, retaining
189 * the tuple identifier on this range.
191 * If "access" represents a member access, then extend the range
192 * of the member.
194 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
196 isl_id *id;
198 id = isl_map_get_tuple_id(access, isl_dim_out);
200 if (!isl_map_range_is_wrapping(access)) {
201 access = isl_map_add_dims(access, isl_dim_out, n);
202 } else {
203 isl_map *domain;
205 domain = isl_map_copy(access);
206 domain = isl_map_range_factor_domain(domain);
207 access = isl_map_range_factor_range(access);
208 access = extend_range(access, n);
209 access = isl_map_range_product(domain, access);
212 access = isl_map_set_tuple_id(access, isl_dim_out, id);
214 return access;
217 /* Finalize the construction of an access expression by setting
218 * the depth of the accessed array.
220 * The index expression may have been updated by
221 * pet_expr_access_subscript and/or pet_expr_access_member
222 * without the access relation having been updated accordingly.
223 * We perform this update here, taking into account the depth
224 * of the accessed array.
226 * If the number of indices is smaller than the depth of the array,
227 * then we assume that all elements of the remaining dimensions
228 * are accessed.
230 __isl_give pet_expr *pet_expr_access_set_depth(__isl_take pet_expr *expr,
231 int depth)
233 isl_map *access;
234 int dim;
236 expr = pet_expr_cow(expr);
237 if (!expr)
238 return NULL;
240 access = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
241 if (!access)
242 return pet_expr_free(expr);
244 dim = isl_map_dim(access, isl_dim_out);
245 if (dim > depth)
246 isl_die(isl_map_get_ctx(access), isl_error_internal,
247 "number of indices greater than depth",
248 access = isl_map_free(access));
250 if (dim != depth)
251 access = extend_range(access, depth - dim);
253 return pet_expr_access_set_access(expr, access);
256 /* Construct a pet_expr that kills the elements specified by
257 * the index expression "index" and the access relation "access".
259 __isl_give pet_expr *pet_expr_kill_from_access_and_index(
260 __isl_take isl_map *access, __isl_take isl_multi_pw_aff *index)
262 pet_expr *expr;
264 if (!access || !index)
265 goto error;
267 expr = pet_expr_from_access_and_index(access, index);
268 expr = pet_expr_access_set_read(expr, 0);
269 return pet_expr_new_unary(pet_op_kill, expr);
270 error:
271 isl_map_free(access);
272 isl_multi_pw_aff_free(index);
273 return NULL;
276 /* Construct a unary pet_expr that performs "op" on "arg".
278 __isl_give pet_expr *pet_expr_new_unary(enum pet_op_type op,
279 __isl_take pet_expr *arg)
281 isl_ctx *ctx;
282 pet_expr *expr;
284 if (!arg)
285 return NULL;
286 ctx = pet_expr_get_ctx(arg);
287 expr = pet_expr_alloc(ctx, pet_expr_op);
288 expr = pet_expr_set_n_arg(expr, 1);
289 if (!expr)
290 goto error;
292 expr->op = op;
293 expr->args[pet_un_arg] = arg;
295 return expr;
296 error:
297 pet_expr_free(arg);
298 return NULL;
301 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
302 * where the result is represented using a type of "type_size" bits
303 * (may be zero if unknown or if the type is not an integer).
305 __isl_give pet_expr *pet_expr_new_binary(int type_size, enum pet_op_type op,
306 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
308 isl_ctx *ctx;
309 pet_expr *expr;
311 if (!lhs || !rhs)
312 goto error;
313 ctx = pet_expr_get_ctx(lhs);
314 expr = pet_expr_alloc(ctx, pet_expr_op);
315 expr = pet_expr_set_n_arg(expr, 2);
316 if (!expr)
317 goto error;
319 expr->op = op;
320 expr->type_size = type_size;
321 expr->args[pet_bin_lhs] = lhs;
322 expr->args[pet_bin_rhs] = rhs;
324 return expr;
325 error:
326 pet_expr_free(lhs);
327 pet_expr_free(rhs);
328 return NULL;
331 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
333 __isl_give pet_expr *pet_expr_new_ternary(__isl_take pet_expr *cond,
334 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
336 isl_ctx *ctx;
337 pet_expr *expr;
339 if (!cond || !lhs || !rhs)
340 goto error;
341 ctx = pet_expr_get_ctx(cond);
342 expr = pet_expr_alloc(ctx, pet_expr_op);
343 expr = pet_expr_set_n_arg(expr, 3);
344 if (!expr)
345 goto error;
347 expr->op = pet_op_cond;
348 expr->args[pet_ter_cond] = cond;
349 expr->args[pet_ter_true] = lhs;
350 expr->args[pet_ter_false] = rhs;
352 return expr;
353 error:
354 pet_expr_free(cond);
355 pet_expr_free(lhs);
356 pet_expr_free(rhs);
357 return NULL;
360 /* Construct a call pet_expr that calls function "name" with "n_arg"
361 * arguments. The caller is responsible for filling in the arguments.
363 __isl_give pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
364 unsigned n_arg)
366 pet_expr *expr;
368 expr = pet_expr_alloc(ctx, pet_expr_call);
369 expr = pet_expr_set_n_arg(expr, n_arg);
370 if (!expr)
371 return NULL;
373 expr->name = strdup(name);
374 if (!expr->name)
375 return pet_expr_free(expr);
377 return expr;
380 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
382 __isl_give pet_expr *pet_expr_new_cast(const char *type_name,
383 __isl_take pet_expr *arg)
385 isl_ctx *ctx;
386 pet_expr *expr;
388 if (!arg)
389 return NULL;
391 ctx = pet_expr_get_ctx(arg);
392 expr = pet_expr_alloc(ctx, pet_expr_cast);
393 expr = pet_expr_set_n_arg(expr, 1);
394 if (!expr)
395 goto error;
397 expr->type_name = strdup(type_name);
398 if (!expr->type_name)
399 goto error;
401 expr->args[0] = arg;
403 return expr;
404 error:
405 pet_expr_free(arg);
406 pet_expr_free(expr);
407 return NULL;
410 /* Construct a pet_expr that represents the double "d".
412 __isl_give pet_expr *pet_expr_new_double(isl_ctx *ctx,
413 double val, const char *s)
415 pet_expr *expr;
417 expr = pet_expr_alloc(ctx, pet_expr_double);
418 if (!expr)
419 return NULL;
421 expr->d.val = val;
422 expr->d.s = strdup(s);
423 if (!expr->d.s)
424 return pet_expr_free(expr);
426 return expr;
429 /* Construct a pet_expr that represents the integer value "v".
431 __isl_give pet_expr *pet_expr_new_int(__isl_take isl_val *v)
433 isl_ctx *ctx;
434 pet_expr *expr;
436 if (!v)
437 return NULL;
439 ctx = isl_val_get_ctx(v);
440 expr = pet_expr_alloc(ctx, pet_expr_int);
441 if (!expr)
442 goto error;
444 expr->i = v;
446 return expr;
447 error:
448 isl_val_free(v);
449 return NULL;
452 static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr)
454 int i;
455 pet_expr *dup;
457 if (!expr)
458 return NULL;
460 dup = pet_expr_alloc(expr->ctx, expr->type);
461 dup = pet_expr_set_type_size(dup, expr->type_size);
462 dup = pet_expr_set_n_arg(dup, expr->n_arg);
463 for (i = 0; i < expr->n_arg; ++i)
464 dup = pet_expr_set_arg(dup, i, pet_expr_copy(expr->args[i]));
466 switch (expr->type) {
467 case pet_expr_access:
468 if (expr->acc.ref_id)
469 dup = pet_expr_access_set_ref_id(dup,
470 isl_id_copy(expr->acc.ref_id));
471 dup = pet_expr_access_set_access(dup,
472 isl_map_copy(expr->acc.access));
473 dup = pet_expr_access_set_index(dup,
474 isl_multi_pw_aff_copy(expr->acc.index));
475 dup = pet_expr_access_set_read(dup, expr->acc.read);
476 dup = pet_expr_access_set_write(dup, expr->acc.write);
477 break;
478 case pet_expr_call:
479 dup = pet_expr_call_set_name(dup, expr->name);
480 break;
481 case pet_expr_cast:
482 dup = pet_expr_cast_set_type_name(dup, expr->type_name);
483 break;
484 case pet_expr_double:
485 dup = pet_expr_double_set(dup, expr->d.val, expr->d.s);
486 break;
487 case pet_expr_int:
488 dup = pet_expr_int_set_val(dup, isl_val_copy(expr->i));
489 break;
490 case pet_expr_op:
491 dup = pet_expr_op_set_type(dup, expr->op);
492 break;
493 case pet_expr_error:
494 dup = pet_expr_free(dup);
495 break;
498 return dup;
501 __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr)
503 if (!expr)
504 return NULL;
506 if (expr->ref == 1)
507 return expr;
508 expr->ref--;
509 return pet_expr_dup(expr);
512 __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr)
514 int i;
516 if (!expr)
517 return NULL;
518 if (--expr->ref > 0)
519 return NULL;
521 for (i = 0; i < expr->n_arg; ++i)
522 pet_expr_free(expr->args[i]);
523 free(expr->args);
525 switch (expr->type) {
526 case pet_expr_access:
527 isl_id_free(expr->acc.ref_id);
528 isl_map_free(expr->acc.access);
529 isl_multi_pw_aff_free(expr->acc.index);
530 break;
531 case pet_expr_call:
532 free(expr->name);
533 break;
534 case pet_expr_cast:
535 free(expr->type_name);
536 break;
537 case pet_expr_double:
538 free(expr->d.s);
539 break;
540 case pet_expr_int:
541 isl_val_free(expr->i);
542 break;
543 case pet_expr_op:
544 case pet_expr_error:
545 break;
548 isl_ctx_deref(expr->ctx);
549 free(expr);
550 return NULL;
553 /* Return an additional reference to "expr".
555 __isl_give pet_expr *pet_expr_copy(__isl_keep pet_expr *expr)
557 if (!expr)
558 return NULL;
560 expr->ref++;
561 return expr;
564 /* Return the isl_ctx in which "expr" was created.
566 isl_ctx *pet_expr_get_ctx(__isl_keep pet_expr *expr)
568 return expr ? expr->ctx : NULL;
571 /* Return the type of "expr".
573 enum pet_expr_type pet_expr_get_type(__isl_keep pet_expr *expr)
575 if (!expr)
576 return pet_expr_error;
577 return expr->type;
580 /* Return the number of arguments of "expr".
582 int pet_expr_get_n_arg(__isl_keep pet_expr *expr)
584 if (!expr)
585 return -1;
587 return expr->n_arg;
590 /* Set the number of arguments of "expr" to "n".
592 * If "expr" originally had more arguments, then remove the extra arguments.
593 * If "expr" originally had fewer arguments, then create space for
594 * the extra arguments ans initialize them to NULL.
596 __isl_give pet_expr *pet_expr_set_n_arg(__isl_take pet_expr *expr, int n)
598 int i;
599 pet_expr **args;
601 if (!expr)
602 return NULL;
603 if (expr->n_arg == n)
604 return expr;
605 expr = pet_expr_cow(expr);
606 if (!expr)
607 return NULL;
609 if (n < expr->n_arg) {
610 for (i = n; i < expr->n_arg; ++i)
611 pet_expr_free(expr->args[i]);
612 expr->n_arg = n;
613 return expr;
616 args = isl_realloc_array(expr->ctx, expr->args, pet_expr *, n);
617 if (!args)
618 return pet_expr_free(expr);
619 expr->args = args;
620 for (i = expr->n_arg; i < n; ++i)
621 expr->args[i] = NULL;
622 expr->n_arg = n;
624 return expr;
627 /* Return the argument of "expr" at position "pos".
629 __isl_give pet_expr *pet_expr_get_arg(__isl_keep pet_expr *expr, int pos)
631 if (!expr)
632 return NULL;
633 if (pos < 0 || pos >= expr->n_arg)
634 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
635 "position out of bounds", return NULL);
637 return pet_expr_copy(expr->args[pos]);
640 /* Replace the argument of "expr" at position "pos" by "arg".
642 __isl_give pet_expr *pet_expr_set_arg(__isl_take pet_expr *expr, int pos,
643 __isl_take pet_expr *arg)
645 if (!expr || !arg)
646 goto error;
647 if (pos < 0 || pos >= expr->n_arg)
648 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
649 "position out of bounds", goto error);
650 if (expr->args[pos] == arg) {
651 pet_expr_free(arg);
652 return expr;
655 expr = pet_expr_cow(expr);
656 if (!expr)
657 goto error;
659 pet_expr_free(expr->args[pos]);
660 expr->args[pos] = arg;
662 return expr;
663 error:
664 pet_expr_free(expr);
665 pet_expr_free(arg);
666 return NULL;
669 /* Does "expr" perform a comparison operation?
671 int pet_expr_is_comparison(__isl_keep pet_expr *expr)
673 if (!expr)
674 return -1;
675 if (expr->type != pet_expr_op)
676 return 0;
677 switch (expr->op) {
678 case pet_op_eq:
679 case pet_op_ne:
680 case pet_op_le:
681 case pet_op_ge:
682 case pet_op_lt:
683 case pet_op_gt:
684 return 1;
685 default:
686 return 0;
690 /* Does "expr" perform a boolean operation?
692 int pet_expr_is_boolean(__isl_keep pet_expr *expr)
694 if (!expr)
695 return -1;
696 if (expr->type != pet_expr_op)
697 return 0;
698 switch (expr->op) {
699 case pet_op_land:
700 case pet_op_lor:
701 case pet_op_lnot:
702 return 1;
703 default:
704 return 0;
708 /* Is "expr" an assume statement?
710 int pet_expr_is_assume(__isl_keep pet_expr *expr)
712 if (!expr)
713 return -1;
714 if (expr->type != pet_expr_op)
715 return 0;
716 return expr->op == pet_op_assume;
719 /* Does "expr" perform a min operation?
721 int pet_expr_is_min(__isl_keep pet_expr *expr)
723 if (!expr)
724 return -1;
725 if (expr->type != pet_expr_call)
726 return 0;
727 if (expr->n_arg != 2)
728 return 0;
729 if (strcmp(expr->name, "min") != 0)
730 return 0;
731 return 1;
734 /* Does "expr" perform a max operation?
736 int pet_expr_is_max(__isl_keep pet_expr *expr)
738 if (!expr)
739 return -1;
740 if (expr->type != pet_expr_call)
741 return 0;
742 if (expr->n_arg != 2)
743 return 0;
744 if (strcmp(expr->name, "max") != 0)
745 return 0;
746 return 1;
749 /* Does "expr" represent an access to an unnamed space, i.e.,
750 * does it represent an affine expression?
752 int pet_expr_is_affine(__isl_keep pet_expr *expr)
754 int has_id;
756 if (!expr)
757 return -1;
758 if (expr->type != pet_expr_access)
759 return 0;
761 has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
762 if (has_id < 0)
763 return -1;
765 return !has_id;
768 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
769 * not part of any struct?
771 int pet_expr_is_scalar_access(__isl_keep pet_expr *expr)
773 if (!expr)
774 return -1;
775 if (expr->type != pet_expr_access)
776 return 0;
777 if (isl_map_range_is_wrapping(expr->acc.access))
778 return 0;
780 return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
783 /* Return 1 if the two pet_exprs are equivalent.
785 int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2)
787 int i;
789 if (!expr1 || !expr2)
790 return 0;
792 if (expr1->type != expr2->type)
793 return 0;
794 if (expr1->n_arg != expr2->n_arg)
795 return 0;
796 for (i = 0; i < expr1->n_arg; ++i)
797 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
798 return 0;
799 switch (expr1->type) {
800 case pet_expr_error:
801 return -1;
802 case pet_expr_double:
803 if (strcmp(expr1->d.s, expr2->d.s))
804 return 0;
805 if (expr1->d.val != expr2->d.val)
806 return 0;
807 break;
808 case pet_expr_int:
809 if (!isl_val_eq(expr1->i, expr2->i))
810 return 0;
811 break;
812 case pet_expr_access:
813 if (expr1->acc.read != expr2->acc.read)
814 return 0;
815 if (expr1->acc.write != expr2->acc.write)
816 return 0;
817 if (expr1->acc.ref_id != expr2->acc.ref_id)
818 return 0;
819 if (!expr1->acc.access || !expr2->acc.access)
820 return 0;
821 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
822 return 0;
823 if (!expr1->acc.index || !expr2->acc.index)
824 return 0;
825 if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
826 expr2->acc.index))
827 return 0;
828 break;
829 case pet_expr_op:
830 if (expr1->op != expr2->op)
831 return 0;
832 break;
833 case pet_expr_call:
834 if (strcmp(expr1->name, expr2->name))
835 return 0;
836 break;
837 case pet_expr_cast:
838 if (strcmp(expr1->type_name, expr2->type_name))
839 return 0;
840 break;
843 return 1;
846 /* Does the access expression "expr" read the accessed elements?
848 int pet_expr_access_is_read(__isl_keep pet_expr *expr)
850 if (!expr)
851 return -1;
852 if (expr->type != pet_expr_access)
853 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
854 "not an access expression", return -1);
856 return expr->acc.read;
859 /* Does the access expression "expr" write to the accessed elements?
861 int pet_expr_access_is_write(__isl_keep pet_expr *expr)
863 if (!expr)
864 return -1;
865 if (expr->type != pet_expr_access)
866 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
867 "not an access expression", return -1);
869 return expr->acc.write;
872 /* Return the identifier of the array accessed by "expr".
874 * If "expr" represents a member access, then return the identifier
875 * of the outer structure array.
877 __isl_give isl_id *pet_expr_access_get_id(__isl_keep pet_expr *expr)
879 if (!expr)
880 return NULL;
881 if (expr->type != pet_expr_access)
882 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
883 "not an access expression", return NULL);
885 if (isl_map_range_is_wrapping(expr->acc.access)) {
886 isl_space *space;
887 isl_id *id;
889 space = isl_map_get_space(expr->acc.access);
890 space = isl_space_range(space);
891 while (space && isl_space_is_wrapping(space))
892 space = isl_space_domain(isl_space_unwrap(space));
893 id = isl_space_get_tuple_id(space, isl_dim_set);
894 isl_space_free(space);
896 return id;
899 return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
902 /* Return the parameter space of "expr".
904 __isl_give isl_space *pet_expr_access_get_parameter_space(
905 __isl_keep pet_expr *expr)
907 isl_space *space;
909 if (!expr)
910 return NULL;
911 if (expr->type != pet_expr_access)
912 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
913 "not an access expression", return NULL);
915 space = isl_multi_pw_aff_get_space(expr->acc.index);
916 space = isl_space_params(space);
918 return space;
921 /* Return the domain space of "expr", without the arguments (if any).
923 __isl_give isl_space *pet_expr_access_get_domain_space(
924 __isl_keep pet_expr *expr)
926 isl_space *space;
928 if (!expr)
929 return NULL;
930 if (expr->type != pet_expr_access)
931 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
932 "not an access expression", return NULL);
934 space = isl_multi_pw_aff_get_space(expr->acc.index);
935 space = isl_space_domain(space);
936 if (isl_space_is_wrapping(space))
937 space = isl_space_domain(isl_space_unwrap(space));
939 return space;
942 /* Return the space of the data accessed by "expr".
944 __isl_give isl_space *pet_expr_access_get_data_space(__isl_keep pet_expr *expr)
946 isl_space *space;
948 if (!expr)
949 return NULL;
950 if (expr->type != pet_expr_access)
951 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
952 "not an access expression", return NULL);
954 space = isl_multi_pw_aff_get_space(expr->acc.index);
955 space = isl_space_range(space);
957 return space;
960 /* Modify all expressions of type pet_expr_access in "expr"
961 * by calling "fn" on them.
963 __isl_give pet_expr *pet_expr_map_access(__isl_take pet_expr *expr,
964 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
965 void *user)
967 int i, n;
969 n = pet_expr_get_n_arg(expr);
970 for (i = 0; i < n; ++i) {
971 pet_expr *arg = pet_expr_get_arg(expr, i);
972 arg = pet_expr_map_access(arg, fn, user);
973 expr = pet_expr_set_arg(expr, i, arg);
976 if (!expr)
977 return NULL;
979 if (expr->type == pet_expr_access)
980 expr = fn(expr, user);
982 return expr;
985 /* Call "fn" on each of the subexpressions of "expr" of type "type".
987 * Return -1 on error (where fn returning a negative value is treated as
988 * an error).
989 * Otherwise return 0.
991 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr *expr,
992 enum pet_expr_type type,
993 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
995 int i;
997 if (!expr)
998 return -1;
1000 for (i = 0; i < expr->n_arg; ++i)
1001 if (pet_expr_foreach_expr_of_type(expr->args[i],
1002 type, fn, user) < 0)
1003 return -1;
1005 if (expr->type == type)
1006 return fn(expr, user);
1008 return 0;
1011 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1013 * Return -1 on error (where fn returning a negative value is treated as
1014 * an error).
1015 * Otherwise return 0.
1017 int pet_expr_foreach_access_expr(__isl_keep pet_expr *expr,
1018 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1020 return pet_expr_foreach_expr_of_type(expr, pet_expr_access, fn, user);
1023 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1025 * Return -1 on error (where fn returning a negative value is treated as
1026 * an error).
1027 * Otherwise return 0.
1029 int pet_expr_foreach_call_expr(__isl_keep pet_expr *expr,
1030 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1032 return pet_expr_foreach_expr_of_type(expr, pet_expr_call, fn, user);
1035 /* Internal data structure for pet_expr_writes.
1036 * "id" is the identifier that we are looking for.
1037 * "found" is set if we have found the identifier being written to.
1039 struct pet_expr_writes_data {
1040 isl_id *id;
1041 int found;
1044 /* Given an access expression, check if it writes to data->id.
1045 * If so, set data->found and abort the search.
1047 static int writes(__isl_keep pet_expr *expr, void *user)
1049 struct pet_expr_writes_data *data = user;
1050 isl_id *write_id;
1052 if (!expr->acc.write)
1053 return 0;
1054 if (pet_expr_is_affine(expr))
1055 return 0;
1057 write_id = pet_expr_access_get_id(expr);
1058 isl_id_free(write_id);
1060 if (!write_id)
1061 return -1;
1063 if (write_id != data->id)
1064 return 0;
1066 data->found = 1;
1067 return -1;
1070 /* Does expression "expr" write to "id"?
1072 int pet_expr_writes(__isl_keep pet_expr *expr, __isl_keep isl_id *id)
1074 struct pet_expr_writes_data data;
1076 data.id = id;
1077 data.found = 0;
1078 if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
1079 !data.found)
1080 return -1;
1082 return data.found;
1085 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1086 * index expression and access relation of "expr"
1087 * to dimensions of "dst_type" at "dst_pos".
1089 __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr,
1090 enum isl_dim_type dst_type, unsigned dst_pos,
1091 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1093 expr = pet_expr_cow(expr);
1094 if (!expr)
1095 return NULL;
1096 if (expr->type != pet_expr_access)
1097 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1098 "not an access pet_expr", return pet_expr_free(expr));
1100 expr->acc.access = isl_map_move_dims(expr->acc.access,
1101 dst_type, dst_pos, src_type, src_pos, n);
1102 expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index,
1103 dst_type, dst_pos, src_type, src_pos, n);
1104 if (!expr->acc.access || !expr->acc.index)
1105 return pet_expr_free(expr);
1107 return expr;
1110 /* Replace the index expression and access relation of "expr"
1111 * by their preimages under the function represented by "ma".
1113 __isl_give pet_expr *pet_expr_access_pullback_multi_aff(
1114 __isl_take pet_expr *expr, __isl_take isl_multi_aff *ma)
1116 expr = pet_expr_cow(expr);
1117 if (!expr || !ma)
1118 goto error;
1119 if (expr->type != pet_expr_access)
1120 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1121 "not an access pet_expr", goto error);
1123 expr->acc.access = isl_map_preimage_domain_multi_aff(expr->acc.access,
1124 isl_multi_aff_copy(ma));
1125 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
1126 ma);
1127 if (!expr->acc.access || !expr->acc.index)
1128 return pet_expr_free(expr);
1130 return expr;
1131 error:
1132 isl_multi_aff_free(ma);
1133 pet_expr_free(expr);
1134 return NULL;
1137 /* Replace the index expression and access relation of "expr"
1138 * by their preimages under the function represented by "mpa".
1140 __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff(
1141 __isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *mpa)
1143 expr = pet_expr_cow(expr);
1144 if (!expr || !mpa)
1145 goto error;
1146 if (expr->type != pet_expr_access)
1147 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1148 "not an access pet_expr", goto error);
1150 expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
1151 expr->acc.access, isl_multi_pw_aff_copy(mpa));
1152 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1153 expr->acc.index, mpa);
1154 if (!expr->acc.access || !expr->acc.index)
1155 return pet_expr_free(expr);
1157 return expr;
1158 error:
1159 isl_multi_pw_aff_free(mpa);
1160 pet_expr_free(expr);
1161 return NULL;
1164 /* Return the access relation of access expression "expr".
1166 __isl_give isl_map *pet_expr_access_get_access(__isl_keep pet_expr *expr)
1168 if (!expr)
1169 return NULL;
1170 if (expr->type != pet_expr_access)
1171 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1172 "not an access expression", return NULL);
1174 return isl_map_copy(expr->acc.access);
1177 /* Return the index expression of access expression "expr".
1179 __isl_give isl_multi_pw_aff *pet_expr_access_get_index(
1180 __isl_keep pet_expr *expr)
1182 if (!expr)
1183 return NULL;
1184 if (expr->type != pet_expr_access)
1185 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1186 "not an access expression", return NULL);
1188 return isl_multi_pw_aff_copy(expr->acc.index);
1191 /* Align the parameters of expr->acc.index and expr->acc.access.
1193 __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr)
1195 expr = pet_expr_cow(expr);
1196 if (!expr)
1197 return NULL;
1198 if (expr->type != pet_expr_access)
1199 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1200 "not an access expression", return pet_expr_free(expr));
1202 expr->acc.access = isl_map_align_params(expr->acc.access,
1203 isl_multi_pw_aff_get_space(expr->acc.index));
1204 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1205 isl_map_get_space(expr->acc.access));
1206 if (!expr->acc.access || !expr->acc.index)
1207 return pet_expr_free(expr);
1209 return expr;
1212 /* Add extra conditions on the parameters to all access relations in "expr".
1214 * The conditions are not added to the index expression. Instead, they
1215 * are used to try and simplify the index expression.
1217 __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr,
1218 __isl_take isl_set *cond)
1220 int i;
1222 expr = pet_expr_cow(expr);
1223 if (!expr)
1224 goto error;
1226 for (i = 0; i < expr->n_arg; ++i) {
1227 expr->args[i] = pet_expr_restrict(expr->args[i],
1228 isl_set_copy(cond));
1229 if (!expr->args[i])
1230 goto error;
1233 if (expr->type == pet_expr_access) {
1234 expr->acc.access = isl_map_intersect_params(expr->acc.access,
1235 isl_set_copy(cond));
1236 expr->acc.index = isl_multi_pw_aff_gist_params(
1237 expr->acc.index, isl_set_copy(cond));
1238 if (!expr->acc.access || !expr->acc.index)
1239 goto error;
1242 isl_set_free(cond);
1243 return expr;
1244 error:
1245 isl_set_free(cond);
1246 return pet_expr_free(expr);
1249 /* Modify the access relation and index expression
1250 * of the given access expression
1251 * based on the given iteration space transformation.
1252 * In particular, precompose the access relation and index expression
1253 * with the update function.
1255 * If the access has any arguments then the domain of the access relation
1256 * is a wrapped mapping from the iteration space to the space of
1257 * argument values. We only need to change the domain of this wrapped
1258 * mapping, so we extend the input transformation with an identity mapping
1259 * on the space of argument values.
1261 __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr,
1262 __isl_keep isl_multi_pw_aff *update)
1264 isl_space *space;
1266 expr = pet_expr_cow(expr);
1267 if (!expr)
1268 return NULL;
1269 if (expr->type != pet_expr_access)
1270 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1271 "not an access expression", return pet_expr_free(expr));
1273 update = isl_multi_pw_aff_copy(update);
1275 space = isl_map_get_space(expr->acc.access);
1276 space = isl_space_domain(space);
1277 if (!isl_space_is_wrapping(space))
1278 isl_space_free(space);
1279 else {
1280 isl_multi_pw_aff *id;
1281 space = isl_space_unwrap(space);
1282 space = isl_space_range(space);
1283 space = isl_space_map_from_set(space);
1284 id = isl_multi_pw_aff_identity(space);
1285 update = isl_multi_pw_aff_product(update, id);
1288 expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
1289 expr->acc.access,
1290 isl_multi_pw_aff_copy(update));
1291 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1292 expr->acc.index, update);
1293 if (!expr->acc.access || !expr->acc.index)
1294 return pet_expr_free(expr);
1296 return expr;
1299 static __isl_give pet_expr *update_domain(__isl_take pet_expr *expr, void *user)
1301 isl_multi_pw_aff *update = user;
1303 return pet_expr_access_update_domain(expr, update);
1306 /* Modify all access relations in "expr" by precomposing them with
1307 * the given iteration space transformation.
1309 __isl_give pet_expr *pet_expr_update_domain(__isl_take pet_expr *expr,
1310 __isl_take isl_multi_pw_aff *update)
1312 expr = pet_expr_map_access(expr, &update_domain, update);
1313 isl_multi_pw_aff_free(update);
1314 return expr;
1317 /* Add all parameters in "space" to the access relation and index expression
1318 * of "expr".
1320 static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user)
1322 isl_space *space = user;
1324 expr = pet_expr_cow(expr);
1325 if (!expr)
1326 return NULL;
1327 if (expr->type != pet_expr_access)
1328 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1329 "not an access expression", return pet_expr_free(expr));
1331 expr->acc.access = isl_map_align_params(expr->acc.access,
1332 isl_space_copy(space));
1333 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1334 isl_space_copy(space));
1335 if (!expr->acc.access || !expr->acc.index)
1336 return pet_expr_free(expr);
1338 return expr;
1341 /* Add all parameters in "space" to all access relations and index expressions
1342 * in "expr".
1344 __isl_give pet_expr *pet_expr_align_params(__isl_take pet_expr *expr,
1345 __isl_take isl_space *space)
1347 expr = pet_expr_map_access(expr, &align_params, space);
1348 isl_space_free(space);
1349 return expr;
1352 /* Insert an argument expression corresponding to "test" in front
1353 * of the list of arguments described by *n_arg and *args.
1355 static __isl_give pet_expr *insert_access_arg(__isl_take pet_expr *expr,
1356 __isl_keep isl_multi_pw_aff *test)
1358 int i;
1359 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1361 if (!test)
1362 return pet_expr_free(expr);
1363 expr = pet_expr_cow(expr);
1364 if (!expr)
1365 return NULL;
1367 if (!expr->args) {
1368 expr->args = isl_calloc_array(ctx, pet_expr *, 1);
1369 if (!expr->args)
1370 return pet_expr_free(expr);
1371 } else {
1372 pet_expr **ext;
1373 ext = isl_calloc_array(ctx, pet_expr *, 1 + expr->n_arg);
1374 if (!ext)
1375 return pet_expr_free(expr);
1376 for (i = 0; i < expr->n_arg; ++i)
1377 ext[1 + i] = expr->args[i];
1378 free(expr->args);
1379 expr->args = ext;
1381 expr->n_arg++;
1382 expr->args[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1383 if (!expr->args[0])
1384 return pet_expr_free(expr);
1386 return expr;
1389 /* Make the expression "expr" depend on the value of "test"
1390 * being equal to "satisfied".
1392 * If "test" is an affine expression, we simply add the conditions
1393 * on the expression having the value "satisfied" to all access relations
1394 * and index expressions.
1396 * Otherwise, we add a filter to "expr" (which is then assumed to be
1397 * an access expression) corresponding to "test" being equal to "satisfied".
1399 __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr,
1400 __isl_take isl_multi_pw_aff *test, int satisfied)
1402 isl_id *id;
1403 isl_ctx *ctx;
1404 isl_space *space;
1405 isl_pw_multi_aff *pma;
1407 expr = pet_expr_cow(expr);
1408 if (!expr || !test)
1409 goto error;
1411 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
1412 isl_pw_aff *pa;
1413 isl_set *cond;
1415 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
1416 isl_multi_pw_aff_free(test);
1417 if (satisfied)
1418 cond = isl_pw_aff_non_zero_set(pa);
1419 else
1420 cond = isl_pw_aff_zero_set(pa);
1421 return pet_expr_restrict(expr, isl_set_params(cond));
1424 ctx = isl_multi_pw_aff_get_ctx(test);
1425 if (expr->type != pet_expr_access)
1426 isl_die(ctx, isl_error_invalid,
1427 "can only filter access expressions", goto error);
1429 space = isl_space_domain(isl_map_get_space(expr->acc.access));
1430 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1431 pma = pet_filter_insert_pma(space, id, satisfied);
1433 expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
1434 expr->acc.access,
1435 isl_pw_multi_aff_copy(pma));
1436 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
1437 expr->acc.index, pma);
1438 if (!expr->acc.access || !expr->acc.index)
1439 goto error;
1441 expr = insert_access_arg(expr, test);
1443 isl_multi_pw_aff_free(test);
1444 return expr;
1445 error:
1446 isl_multi_pw_aff_free(test);
1447 return pet_expr_free(expr);
1450 /* Check if the given index expression accesses a (0D) array that corresponds
1451 * to one of the parameters in "space". If so, replace the array access
1452 * by an access to the set of integers with as index (and value)
1453 * that parameter.
1455 static __isl_give isl_multi_pw_aff *index_detect_parameter(
1456 __isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
1458 isl_local_space *ls;
1459 isl_id *array_id = NULL;
1460 isl_aff *aff;
1461 int pos = -1;
1463 if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
1464 array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
1465 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
1467 isl_space_free(space);
1469 if (pos < 0) {
1470 isl_id_free(array_id);
1471 return index;
1474 space = isl_multi_pw_aff_get_domain_space(index);
1475 isl_multi_pw_aff_free(index);
1477 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
1478 if (pos < 0) {
1479 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
1480 space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
1481 pos = 0;
1482 } else
1483 isl_id_free(array_id);
1485 ls = isl_local_space_from_space(space);
1486 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
1487 index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
1489 return index;
1492 /* Check if the given access relation accesses a (0D) array that corresponds
1493 * to one of the parameters in "space". If so, replace the array access
1494 * by an access to the set of integers with as index (and value)
1495 * that parameter.
1497 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
1498 __isl_take isl_space *space)
1500 isl_id *array_id = NULL;
1501 int pos = -1;
1503 if (isl_map_has_tuple_id(access, isl_dim_out)) {
1504 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1505 pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
1507 isl_space_free(space);
1509 if (pos < 0) {
1510 isl_id_free(array_id);
1511 return access;
1514 pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
1515 if (pos < 0) {
1516 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
1517 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
1518 pos = 0;
1519 } else
1520 isl_id_free(array_id);
1522 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1523 access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
1525 return access;
1528 /* If "expr" accesses a (0D) array that corresponds to one of the parameters
1529 * in "space" then replace it by a value equal to the corresponding parameter.
1531 static __isl_give pet_expr *detect_parameter_accesses(__isl_take pet_expr *expr,
1532 void *user)
1534 isl_space *space = user;
1536 expr = pet_expr_cow(expr);
1537 if (!expr)
1538 return NULL;
1539 if (expr->type != pet_expr_access)
1540 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1541 "not an access expression", return pet_expr_free(expr));
1543 expr->acc.access = access_detect_parameter(expr->acc.access,
1544 isl_space_copy(space));
1545 expr->acc.index = index_detect_parameter(expr->acc.index,
1546 isl_space_copy(space));
1547 if (!expr->acc.access || !expr->acc.index)
1548 return pet_expr_free(expr);
1550 return expr;
1553 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1554 * in "space" by a value equal to the corresponding parameter.
1556 __isl_give pet_expr *pet_expr_detect_parameter_accesses(
1557 __isl_take pet_expr *expr, __isl_take isl_space *space)
1559 expr = pet_expr_map_access(expr, &detect_parameter_accesses, space);
1560 isl_space_free(space);
1561 return expr;
1564 /* Add a reference identifier to access expression "expr".
1565 * "user" points to an integer that contains the sequence number
1566 * of the next reference.
1568 static __isl_give pet_expr *access_add_ref_id(__isl_take pet_expr *expr,
1569 void *user)
1571 isl_ctx *ctx;
1572 char name[50];
1573 int *n_ref = user;
1575 expr = pet_expr_cow(expr);
1576 if (!expr)
1577 return expr;
1578 if (expr->type != pet_expr_access)
1579 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1580 "not an access expression", return pet_expr_free(expr));
1582 ctx = isl_map_get_ctx(expr->acc.access);
1583 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
1584 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
1585 if (!expr->acc.ref_id)
1586 return pet_expr_free(expr);
1588 return expr;
1591 __isl_give pet_expr *pet_expr_add_ref_ids(__isl_take pet_expr *expr, int *n_ref)
1593 return pet_expr_map_access(expr, &access_add_ref_id, n_ref);
1596 /* Reset the user pointer on all parameter and tuple ids in
1597 * the access relation and the index expressions
1598 * of the access expression "expr".
1600 static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr,
1601 void *user)
1603 expr = pet_expr_cow(expr);
1604 if (!expr)
1605 return expr;
1606 if (expr->type != pet_expr_access)
1607 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1608 "not an access expression", return pet_expr_free(expr));
1610 expr->acc.access = isl_map_reset_user(expr->acc.access);
1611 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
1612 if (!expr->acc.access || !expr->acc.index)
1613 return pet_expr_free(expr);
1615 return expr;
1618 __isl_give pet_expr *pet_expr_anonymize(__isl_take pet_expr *expr)
1620 return pet_expr_map_access(expr, &access_anonymize, NULL);
1623 /* Data used in access_gist() callback.
1625 struct pet_access_gist_data {
1626 isl_set *domain;
1627 isl_union_map *value_bounds;
1630 /* Given an expression "expr" of type pet_expr_access, compute
1631 * the gist of the associated access relation and index expression
1632 * with respect to data->domain and the bounds on the values of the arguments
1633 * of the expression.
1635 * The arguments of "expr" have been gisted right before "expr" itself
1636 * is gisted. The gisted arguments may have become equal where before
1637 * they may not have been (obviously) equal. We therefore take
1638 * the opportunity to remove duplicate arguments here.
1640 static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user)
1642 struct pet_access_gist_data *data = user;
1643 isl_set *domain;
1645 expr = pet_expr_remove_duplicate_args(expr);
1646 expr = pet_expr_cow(expr);
1647 if (!expr)
1648 return expr;
1649 if (expr->type != pet_expr_access)
1650 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1651 "not an access expression", return pet_expr_free(expr));
1653 domain = isl_set_copy(data->domain);
1654 if (expr->n_arg > 0)
1655 domain = pet_value_bounds_apply(domain, expr->n_arg, expr->args,
1656 data->value_bounds);
1658 expr->acc.access = isl_map_gist_domain(expr->acc.access,
1659 isl_set_copy(domain));
1660 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
1661 if (!expr->acc.access || !expr->acc.index)
1662 return pet_expr_free(expr);
1664 return expr;
1667 __isl_give pet_expr *pet_expr_gist(__isl_take pet_expr *expr,
1668 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
1670 struct pet_access_gist_data data = { context, value_bounds };
1672 return pet_expr_map_access(expr, &access_gist, &data);
1675 /* Mark "expr" as a read dependening on "read".
1677 __isl_give pet_expr *pet_expr_access_set_read(__isl_take pet_expr *expr,
1678 int read)
1680 if (!expr)
1681 return pet_expr_free(expr);
1682 if (expr->type != pet_expr_access)
1683 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1684 "not an access expression", return pet_expr_free(expr));
1685 if (expr->acc.read == read)
1686 return expr;
1687 expr = pet_expr_cow(expr);
1688 if (!expr)
1689 return NULL;
1690 expr->acc.read = read;
1692 return expr;
1695 /* Mark "expr" as a write dependening on "write".
1697 __isl_give pet_expr *pet_expr_access_set_write(__isl_take pet_expr *expr,
1698 int write)
1700 if (!expr)
1701 return pet_expr_free(expr);
1702 if (expr->type != pet_expr_access)
1703 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1704 "not an access expression", return pet_expr_free(expr));
1705 if (expr->acc.write == write)
1706 return expr;
1707 expr = pet_expr_cow(expr);
1708 if (!expr)
1709 return NULL;
1710 expr->acc.write = write;
1712 return expr;
1715 /* Replace the access relation of "expr" by "access".
1717 __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr,
1718 __isl_take isl_map *access)
1720 expr = pet_expr_cow(expr);
1721 if (!expr || !access)
1722 goto error;
1723 if (expr->type != pet_expr_access)
1724 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1725 "not an access expression", goto error);
1726 isl_map_free(expr->acc.access);
1727 expr->acc.access = access;
1729 return expr;
1730 error:
1731 isl_map_free(access);
1732 pet_expr_free(expr);
1733 return NULL;
1736 /* Replace the index expression of "expr" by "index".
1738 __isl_give pet_expr *pet_expr_access_set_index(__isl_take pet_expr *expr,
1739 __isl_take isl_multi_pw_aff *index)
1741 expr = pet_expr_cow(expr);
1742 if (!expr || !index)
1743 goto error;
1744 if (expr->type != pet_expr_access)
1745 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1746 "not an access expression", goto error);
1747 isl_multi_pw_aff_free(expr->acc.index);
1748 expr->acc.index = index;
1750 return expr;
1751 error:
1752 isl_multi_pw_aff_free(index);
1753 pet_expr_free(expr);
1754 return NULL;
1757 /* Return the reference identifier of access expression "expr".
1759 __isl_give isl_id *pet_expr_access_get_ref_id(__isl_keep pet_expr *expr)
1761 if (!expr)
1762 return NULL;
1763 if (expr->type != pet_expr_access)
1764 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1765 "not an access expression", return NULL);
1767 return isl_id_copy(expr->acc.ref_id);
1770 /* Replace the reference identifier of access expression "expr" by "ref_id".
1772 __isl_give pet_expr *pet_expr_access_set_ref_id(__isl_take pet_expr *expr,
1773 __isl_take isl_id *ref_id)
1775 expr = pet_expr_cow(expr);
1776 if (!expr || !ref_id)
1777 goto error;
1778 if (expr->type != pet_expr_access)
1779 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1780 "not an access expression", goto error);
1781 isl_id_free(expr->acc.ref_id);
1782 expr->acc.ref_id = ref_id;
1784 return expr;
1785 error:
1786 isl_id_free(ref_id);
1787 pet_expr_free(expr);
1788 return NULL;
1791 /* Tag the access relation "access" with "id".
1792 * That is, insert the id as the range of a wrapped relation
1793 * in the domain of "access".
1795 * If "access" is of the form
1797 * D[i] -> A[a]
1799 * then the result is of the form
1801 * [D[i] -> id[]] -> A[a]
1803 __isl_give isl_map *pet_expr_tag_access(__isl_keep pet_expr *expr,
1804 __isl_take isl_map *access)
1806 isl_space *space;
1807 isl_map *add_tag;
1808 isl_id *id;
1810 if (expr->type != pet_expr_access)
1811 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1812 "not an access expression",
1813 return isl_map_free(access));
1815 id = isl_id_copy(expr->acc.ref_id);
1816 space = isl_space_range(isl_map_get_space(access));
1817 space = isl_space_from_range(space);
1818 space = isl_space_set_tuple_id(space, isl_dim_in, id);
1819 add_tag = isl_map_universe(space);
1820 access = isl_map_domain_product(access, add_tag);
1822 return access;
1825 /* Return the relation mapping pairs of domain iterations and argument
1826 * values to the corresponding accessed data elements.
1828 __isl_give isl_map *pet_expr_access_get_dependent_access(
1829 __isl_keep pet_expr *expr)
1831 if (!expr)
1832 return NULL;
1833 if (expr->type != pet_expr_access)
1834 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1835 "not an access expression", return NULL);
1837 return isl_map_copy(expr->acc.access);
1840 /* Return the relation mapping domain iterations to all possibly
1841 * accessed data elements.
1842 * In particular, take the access relation and project out the values
1843 * of the arguments, if any.
1845 __isl_give isl_map *pet_expr_access_get_may_access(__isl_keep pet_expr *expr)
1847 isl_map *access;
1848 isl_space *space;
1849 isl_map *map;
1851 if (!expr)
1852 return NULL;
1853 if (expr->type != pet_expr_access)
1854 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1855 "not an access expression", return NULL);
1857 access = pet_expr_access_get_dependent_access(expr);
1858 if (expr->n_arg == 0)
1859 return access;
1861 space = isl_space_domain(isl_map_get_space(access));
1862 map = isl_map_universe(isl_space_unwrap(space));
1863 map = isl_map_domain_map(map);
1864 access = isl_map_apply_domain(access, map);
1866 return access;
1869 /* Return a relation mapping domain iterations to definitely
1870 * accessed data elements, assuming the statement containing
1871 * the expression is executed.
1873 * If there are no arguments, then all elements are accessed.
1874 * Otherwise, we conservatively return an empty relation.
1876 __isl_give isl_map *pet_expr_access_get_must_access(__isl_keep pet_expr *expr)
1878 isl_space *space;
1880 if (!expr)
1881 return NULL;
1882 if (expr->type != pet_expr_access)
1883 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1884 "not an access expression", return NULL);
1886 if (expr->n_arg == 0)
1887 return pet_expr_access_get_dependent_access(expr);
1889 space = isl_map_get_space(expr->acc.access);
1890 space = isl_space_domain_factor_domain(space);
1892 return isl_map_empty(space);
1895 /* Return the relation mapping domain iterations to all possibly
1896 * accessed data elements, with its domain tagged with the reference
1897 * identifier.
1899 __isl_give isl_map *pet_expr_access_get_tagged_may_access(
1900 __isl_keep pet_expr *expr)
1902 isl_map *access;
1904 if (!expr)
1905 return NULL;
1907 access = pet_expr_access_get_may_access(expr);
1908 access = pet_expr_tag_access(expr, access);
1910 return access;
1913 /* Return the operation type of operation expression "expr".
1915 enum pet_op_type pet_expr_op_get_type(__isl_keep pet_expr *expr)
1917 if (!expr)
1918 return pet_op_last;
1919 if (expr->type != pet_expr_op)
1920 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1921 "not an operation expression", return pet_op_last);
1923 return expr->op;
1926 /* Replace the operation type of operation expression "expr" by "type".
1928 __isl_give pet_expr *pet_expr_op_set_type(__isl_take pet_expr *expr,
1929 enum pet_op_type type)
1931 if (!expr)
1932 return pet_expr_free(expr);
1933 if (expr->type != pet_expr_op)
1934 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1935 "not an operation expression",
1936 return pet_expr_free(expr));
1937 if (expr->op == type)
1938 return expr;
1939 expr = pet_expr_cow(expr);
1940 if (!expr)
1941 return NULL;
1942 expr->op = type;
1944 return expr;
1947 /* Return the name of the function called by "expr".
1949 __isl_keep const char *pet_expr_call_get_name(__isl_keep pet_expr *expr)
1951 if (!expr)
1952 return NULL;
1953 if (expr->type != pet_expr_call)
1954 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1955 "not a call expression", return NULL);
1956 return expr->name;
1959 /* Replace the name of the function called by "expr" by "name".
1961 __isl_give pet_expr *pet_expr_call_set_name(__isl_take pet_expr *expr,
1962 __isl_keep const char *name)
1964 expr = pet_expr_cow(expr);
1965 if (!expr || !name)
1966 return pet_expr_free(expr);
1967 if (expr->type != pet_expr_call)
1968 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1969 "not a call expression", return pet_expr_free(expr));
1970 free(expr->name);
1971 expr->name = strdup(name);
1972 if (!expr->name)
1973 return pet_expr_free(expr);
1974 return expr;
1977 /* Replace the type of the cast performed by "expr" by "name".
1979 __isl_give pet_expr *pet_expr_cast_set_type_name(__isl_take pet_expr *expr,
1980 __isl_keep const char *name)
1982 expr = pet_expr_cow(expr);
1983 if (!expr || !name)
1984 return pet_expr_free(expr);
1985 if (expr->type != pet_expr_cast)
1986 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1987 "not a cast expression", return pet_expr_free(expr));
1988 free(expr->type_name);
1989 expr->type_name = strdup(name);
1990 if (!expr->type_name)
1991 return pet_expr_free(expr);
1992 return expr;
1995 /* Return the value of the integer represented by "expr".
1997 __isl_give isl_val *pet_expr_int_get_val(__isl_keep pet_expr *expr)
1999 if (!expr)
2000 return NULL;
2001 if (expr->type != pet_expr_int)
2002 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2003 "not an int expression", return NULL);
2005 return isl_val_copy(expr->i);
2008 /* Replace the value of the integer represented by "expr" by "v".
2010 __isl_give pet_expr *pet_expr_int_set_val(__isl_take pet_expr *expr,
2011 __isl_take isl_val *v)
2013 expr = pet_expr_cow(expr);
2014 if (!expr || !v)
2015 goto error;
2016 if (expr->type != pet_expr_int)
2017 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2018 "not an int expression", goto error);
2019 isl_val_free(expr->i);
2020 expr->i = v;
2022 return expr;
2023 error:
2024 isl_val_free(v);
2025 pet_expr_free(expr);
2026 return NULL;
2029 /* Replace the value and string representation of the double
2030 * represented by "expr" by "d" and "s".
2032 __isl_give pet_expr *pet_expr_double_set(__isl_take pet_expr *expr,
2033 double d, __isl_keep const char *s)
2035 expr = pet_expr_cow(expr);
2036 if (!expr || !s)
2037 return pet_expr_free(expr);
2038 if (expr->type != pet_expr_double)
2039 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2040 "not a double expression", return pet_expr_free(expr));
2041 expr->d.val = d;
2042 free(expr->d.s);
2043 expr->d.s = strdup(s);
2044 if (!expr->d.s)
2045 return pet_expr_free(expr);
2046 return expr;
2049 /* Return a string representation of the double expression "expr".
2051 __isl_give char *pet_expr_double_get_str(__isl_keep pet_expr *expr)
2053 if (!expr)
2054 return NULL;
2055 if (expr->type != pet_expr_double)
2056 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2057 "not a double expression", return NULL);
2058 return strdup(expr->d.s);
2061 /* Return a piecewise affine expression defined on the specified domain
2062 * that represents NaN.
2064 static __isl_give isl_pw_aff *non_affine(__isl_take isl_space *space)
2066 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space));
2069 /* This function is called when we come across an access that is
2070 * nested in what is supposed to be an affine expression.
2071 * "pc" is the context in which the affine expression is created.
2072 * If nesting is allowed in "pc", we return an affine expression that is
2073 * equal to a new parameter corresponding to this nested access.
2074 * Otherwise, we return NaN.
2076 * Note that we currently don't allow nested accesses themselves
2077 * to contain any nested accesses, so we check if "expr" itself
2078 * involves any nested accesses (either explicitly as arguments
2079 * or implicitly through parameters) and return NaN if it does.
2081 * The new parameter is resolved in resolve_nested.
2083 static __isl_give isl_pw_aff *nested_access(__isl_keep pet_expr *expr,
2084 __isl_keep pet_context *pc)
2086 isl_ctx *ctx;
2087 isl_id *id;
2088 isl_space *space;
2089 isl_local_space *ls;
2090 isl_aff *aff;
2091 int nested;
2093 if (!expr || !pc)
2094 return NULL;
2095 if (!pet_context_allow_nesting(pc))
2096 return non_affine(pet_context_get_space(pc));
2098 if (pet_expr_get_type(expr) != pet_expr_access)
2099 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2100 "not an access expression", return NULL);
2102 if (expr->n_arg > 0)
2103 return non_affine(pet_context_get_space(pc));
2105 space = pet_expr_access_get_parameter_space(expr);
2106 nested = pet_nested_any_in_space(space);
2107 isl_space_free(space);
2108 if (nested)
2109 return non_affine(pet_context_get_space(pc));
2111 ctx = pet_expr_get_ctx(expr);
2112 id = pet_nested_pet_expr(pet_expr_copy(expr));
2113 space = pet_context_get_space(pc);
2114 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2116 space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
2117 ls = isl_local_space_from_space(space);
2118 aff = isl_aff_var_on_domain(ls, isl_dim_param, 0);
2120 return isl_pw_aff_from_aff(aff);
2123 /* Extract an affine expression from the access pet_expr "expr".
2124 * "pc" is the context in which the affine expression is created.
2126 * If "expr" is actually an affine expression rather than
2127 * a real access, then we return that expression.
2128 * Otherwise, we require that "expr" is of an integral type.
2129 * If not, we return NaN.
2131 * If we are accessing a scalar (i.e., not an array and not a member)
2132 * and if that scalar can be treated as a parameter (because it is
2133 * not assigned a known or unknown value in the relevant part of the AST),
2134 * then we return an affine expression equal to that parameter.
2136 * If the variable has been assigned a known affine expression,
2137 * then we return that expression.
2139 * Otherwise, we return an expression that is equal to a parameter
2140 * representing "expr" (if "allow_nested" is set).
2142 static __isl_give isl_pw_aff *extract_affine_from_access(
2143 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2145 int pos;
2146 isl_id *id;
2147 isl_space *space;
2148 isl_local_space *ls;
2149 isl_aff *aff;
2151 if (pet_expr_is_affine(expr)) {
2152 isl_pw_aff *pa;
2153 isl_multi_pw_aff *mpa;
2155 mpa = pet_expr_access_get_index(expr);
2156 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
2157 isl_multi_pw_aff_free(mpa);
2158 return pa;
2161 if (pet_expr_get_type_size(expr) == 0)
2162 return non_affine(pet_context_get_space(pc));
2164 if (!pet_expr_is_scalar_access(expr))
2165 return nested_access(expr, pc);
2167 id = pet_expr_access_get_id(expr);
2168 if (pet_context_is_assigned(pc, id)) {
2169 isl_pw_aff *pa;
2171 pa = pet_context_get_value(pc, id);
2172 if (!pa)
2173 return NULL;
2174 if (!isl_pw_aff_involves_nan(pa))
2175 return pa;
2176 isl_pw_aff_free(pa);
2177 return nested_access(expr, pc);
2180 space = pet_context_get_space(pc);
2182 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
2183 if (pos >= 0) {
2184 isl_id_free(id);
2185 } else {
2186 pos = isl_space_dim(space, isl_dim_param);
2187 space = isl_space_add_dims(space, isl_dim_param, 1);
2188 space = isl_space_set_dim_id(space, isl_dim_param, pos, id);
2191 ls = isl_local_space_from_space(space);
2192 aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
2194 return isl_pw_aff_from_aff(aff);
2197 /* Construct an affine expression from the integer constant "expr".
2198 * "pc" is the context in which the affine expression is created.
2200 static __isl_give isl_pw_aff *extract_affine_from_int(__isl_keep pet_expr *expr,
2201 __isl_keep pet_context *pc)
2203 isl_local_space *ls;
2204 isl_aff *aff;
2206 if (!expr)
2207 return NULL;
2209 ls = isl_local_space_from_space(pet_context_get_space(pc));
2210 aff = isl_aff_val_on_domain(ls, pet_expr_int_get_val(expr));
2212 return isl_pw_aff_from_aff(aff);
2215 /* Extract an affine expression from an addition or subtraction operation.
2216 * Return NaN if we are unable to extract an affine expression.
2218 * "pc" is the context in which the affine expression is created.
2220 static __isl_give isl_pw_aff *extract_affine_add_sub(__isl_keep pet_expr *expr,
2221 __isl_keep pet_context *pc)
2223 isl_pw_aff *lhs;
2224 isl_pw_aff *rhs;
2226 if (!expr)
2227 return NULL;
2228 if (expr->n_arg != 2)
2229 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2230 "expecting two arguments", return NULL);
2232 lhs = pet_expr_extract_affine(expr->args[0], pc);
2233 rhs = pet_expr_extract_affine(expr->args[1], pc);
2235 switch (pet_expr_op_get_type(expr)) {
2236 case pet_op_add:
2237 return isl_pw_aff_add(lhs, rhs);
2238 case pet_op_sub:
2239 return isl_pw_aff_sub(lhs, rhs);
2240 default:
2241 isl_pw_aff_free(lhs);
2242 isl_pw_aff_free(rhs);
2243 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2244 "not an addition or subtraction operation",
2245 return NULL);
2250 /* Extract an affine expression from an integer division or a modulo operation.
2251 * Return NaN if we are unable to extract an affine expression.
2253 * "pc" is the context in which the affine expression is created.
2255 * In particular, if "expr" is lhs/rhs, then return
2257 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2259 * If "expr" is lhs%rhs, then return
2261 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2263 * If the second argument (rhs) is not a (positive) integer constant,
2264 * then we fail to extract an affine expression.
2266 static __isl_give isl_pw_aff *extract_affine_div_mod(__isl_keep pet_expr *expr,
2267 __isl_keep pet_context *pc)
2269 int is_cst;
2270 isl_pw_aff *lhs;
2271 isl_pw_aff *rhs;
2273 if (!expr)
2274 return NULL;
2275 if (expr->n_arg != 2)
2276 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2277 "expecting two arguments", return NULL);
2279 rhs = pet_expr_extract_affine(expr->args[1], pc);
2281 is_cst = isl_pw_aff_is_cst(rhs);
2282 if (is_cst < 0 || !is_cst) {
2283 isl_pw_aff_free(rhs);
2284 return non_affine(pet_context_get_space(pc));
2287 lhs = pet_expr_extract_affine(expr->args[0], pc);
2289 switch (pet_expr_op_get_type(expr)) {
2290 case pet_op_div:
2291 return isl_pw_aff_tdiv_q(lhs, rhs);
2292 case pet_op_mod:
2293 return isl_pw_aff_tdiv_r(lhs, rhs);
2294 default:
2295 isl_pw_aff_free(lhs);
2296 isl_pw_aff_free(rhs);
2297 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2298 "not a div or mod operator", return NULL);
2303 /* Extract an affine expression from a multiplication operation.
2304 * Return NaN if we are unable to extract an affine expression.
2305 * In particular, if neither of the arguments is a (piecewise) constant
2306 * then we return NaN.
2308 * "pc" is the context in which the affine expression is created.
2310 static __isl_give isl_pw_aff *extract_affine_mul(__isl_keep pet_expr *expr,
2311 __isl_keep pet_context *pc)
2313 int lhs_cst, rhs_cst;
2314 isl_pw_aff *lhs;
2315 isl_pw_aff *rhs;
2317 if (!expr)
2318 return NULL;
2319 if (expr->n_arg != 2)
2320 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2321 "expecting two arguments", return NULL);
2323 lhs = pet_expr_extract_affine(expr->args[0], pc);
2324 rhs = pet_expr_extract_affine(expr->args[1], pc);
2326 lhs_cst = isl_pw_aff_is_cst(lhs);
2327 rhs_cst = isl_pw_aff_is_cst(rhs);
2328 if (lhs_cst < 0 || rhs_cst < 0 || (!lhs_cst && !rhs_cst)) {
2329 isl_pw_aff_free(lhs);
2330 isl_pw_aff_free(rhs);
2331 return non_affine(pet_context_get_space(pc));
2334 return isl_pw_aff_mul(lhs, rhs);
2337 /* Extract an affine expression from a negation operation.
2338 * Return NaN if we are unable to extract an affine expression.
2340 * "pc" is the context in which the affine expression is created.
2342 static __isl_give isl_pw_aff *extract_affine_neg(__isl_keep pet_expr *expr,
2343 __isl_keep pet_context *pc)
2345 isl_pw_aff *res;
2347 if (!expr)
2348 return NULL;
2349 if (expr->n_arg != 1)
2350 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2351 "expecting one argument", return NULL);
2353 res = pet_expr_extract_affine(expr->args[0], pc);
2354 return isl_pw_aff_neg(res);
2357 /* Extract an affine expression from a conditional operation.
2358 * Return NaN if we are unable to extract an affine expression.
2360 * "pc" is the context in which the affine expression is created.
2362 static __isl_give isl_pw_aff *extract_affine_cond(__isl_keep pet_expr *expr,
2363 __isl_keep pet_context *pc)
2365 isl_pw_aff *cond, *lhs, *rhs;
2367 if (!expr)
2368 return NULL;
2369 if (expr->n_arg != 3)
2370 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2371 "expecting three arguments", return NULL);
2373 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
2374 lhs = pet_expr_extract_affine(expr->args[1], pc);
2375 rhs = pet_expr_extract_affine(expr->args[2], pc);
2377 return isl_pw_aff_cond(cond, lhs, rhs);
2380 /* Compute
2382 * pwaff mod 2^width
2384 static __isl_give isl_pw_aff *wrap(__isl_take isl_pw_aff *pwaff, unsigned width)
2386 isl_ctx *ctx;
2387 isl_val *mod;
2389 ctx = isl_pw_aff_get_ctx(pwaff);
2390 mod = isl_val_int_from_ui(ctx, width);
2391 mod = isl_val_2exp(mod);
2393 pwaff = isl_pw_aff_mod_val(pwaff, mod);
2395 return pwaff;
2398 /* Limit the domain of "pwaff" to those elements where the function
2399 * value satisfies
2401 * 2^{width-1} <= pwaff < 2^{width-1}
2403 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
2404 unsigned width)
2406 isl_ctx *ctx;
2407 isl_val *v;
2408 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
2409 isl_local_space *ls = isl_local_space_from_space(space);
2410 isl_aff *bound;
2411 isl_set *dom;
2412 isl_pw_aff *b;
2414 ctx = isl_pw_aff_get_ctx(pwaff);
2415 v = isl_val_int_from_ui(ctx, width - 1);
2416 v = isl_val_2exp(v);
2418 bound = isl_aff_zero_on_domain(ls);
2419 bound = isl_aff_add_constant_val(bound, v);
2420 b = isl_pw_aff_from_aff(bound);
2422 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
2423 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2425 b = isl_pw_aff_neg(b);
2426 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
2427 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2429 return pwaff;
2432 /* Handle potential overflows on signed computations.
2434 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2435 * then we adjust the domain of "pa" to avoid overflows.
2437 static __isl_give isl_pw_aff *signed_overflow(__isl_take isl_pw_aff *pa,
2438 unsigned width)
2440 isl_ctx *ctx;
2441 struct pet_options *options;
2443 if (!pa)
2444 return NULL;
2446 ctx = isl_pw_aff_get_ctx(pa);
2447 options = isl_ctx_peek_pet_options(ctx);
2448 if (!options || options->signed_overflow == PET_OVERFLOW_AVOID)
2449 pa = avoid_overflow(pa, width);
2451 return pa;
2454 /* Extract an affine expression from some an operation.
2455 * Return NaN if we are unable to extract an affine expression.
2456 * If the result of a binary (non boolean) operation is unsigned,
2457 * then we wrap it based on the size of the type. If the result is signed,
2458 * then we ensure that no overflow occurs.
2460 * "pc" is the context in which the affine expression is created.
2462 static __isl_give isl_pw_aff *extract_affine_from_op(__isl_keep pet_expr *expr,
2463 __isl_keep pet_context *pc)
2465 isl_pw_aff *res;
2466 int type_size;
2468 switch (pet_expr_op_get_type(expr)) {
2469 case pet_op_add:
2470 case pet_op_sub:
2471 res = extract_affine_add_sub(expr, pc);
2472 break;
2473 case pet_op_div:
2474 case pet_op_mod:
2475 res = extract_affine_div_mod(expr, pc);
2476 break;
2477 case pet_op_mul:
2478 res = extract_affine_mul(expr, pc);
2479 break;
2480 case pet_op_minus:
2481 return extract_affine_neg(expr, pc);
2482 case pet_op_cond:
2483 return extract_affine_cond(expr, pc);
2484 case pet_op_eq:
2485 case pet_op_ne:
2486 case pet_op_le:
2487 case pet_op_ge:
2488 case pet_op_lt:
2489 case pet_op_gt:
2490 case pet_op_land:
2491 case pet_op_lor:
2492 case pet_op_lnot:
2493 return pet_expr_extract_affine_condition(expr, pc);
2494 default:
2495 return non_affine(pet_context_get_space(pc));
2498 if (!res)
2499 return NULL;
2500 if (isl_pw_aff_involves_nan(res)) {
2501 isl_space *space = isl_pw_aff_get_domain_space(res);
2502 isl_pw_aff_free(res);
2503 return non_affine(space);
2506 type_size = pet_expr_get_type_size(expr);
2507 if (type_size > 0)
2508 res = wrap(res, type_size);
2509 else
2510 res = signed_overflow(res, -type_size);
2512 return res;
2515 /* Extract an affine expression from some special function calls.
2516 * Return NaN if we are unable to extract an affine expression.
2517 * In particular, we handle "min", "max", "ceild", "floord",
2518 * "intMod", "intFloor" and "intCeil".
2519 * In case of the latter five, the second argument needs to be
2520 * a (positive) integer constant.
2522 * "pc" is the context in which the affine expression is created.
2524 static __isl_give isl_pw_aff *extract_affine_from_call(
2525 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2527 isl_pw_aff *aff1, *aff2;
2528 int n;
2529 const char *name;
2531 n = pet_expr_get_n_arg(expr);
2532 name = pet_expr_call_get_name(expr);
2533 if (!(n == 2 && !strcmp(name, "min")) &&
2534 !(n == 2 && !strcmp(name, "max")) &&
2535 !(n == 2 && !strcmp(name, "intMod")) &&
2536 !(n == 2 && !strcmp(name, "intFloor")) &&
2537 !(n == 2 && !strcmp(name, "intCeil")) &&
2538 !(n == 2 && !strcmp(name, "floord")) &&
2539 !(n == 2 && !strcmp(name, "ceild")))
2540 return non_affine(pet_context_get_space(pc));
2542 if (!strcmp(name, "min") || !strcmp(name, "max")) {
2543 aff1 = pet_expr_extract_affine(expr->args[0], pc);
2544 aff2 = pet_expr_extract_affine(expr->args[1], pc);
2546 if (!strcmp(name, "min"))
2547 aff1 = isl_pw_aff_min(aff1, aff2);
2548 else
2549 aff1 = isl_pw_aff_max(aff1, aff2);
2550 } else if (!strcmp(name, "intMod")) {
2551 isl_val *v;
2553 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
2554 return non_affine(pet_context_get_space(pc));
2555 v = pet_expr_int_get_val(expr->args[1]);
2556 aff1 = pet_expr_extract_affine(expr->args[0], pc);
2557 aff1 = isl_pw_aff_mod_val(aff1, v);
2558 } else {
2559 isl_val *v;
2561 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
2562 return non_affine(pet_context_get_space(pc));
2563 v = pet_expr_int_get_val(expr->args[1]);
2564 aff1 = pet_expr_extract_affine(expr->args[0], pc);
2565 aff1 = isl_pw_aff_scale_down_val(aff1, v);
2566 if (!strcmp(name, "floord") || !strcmp(name, "intFloor"))
2567 aff1 = isl_pw_aff_floor(aff1);
2568 else
2569 aff1 = isl_pw_aff_ceil(aff1);
2572 return aff1;
2575 /* Extract an affine expression from "expr", if possible.
2576 * Otherwise return NaN.
2578 * "pc" is the context in which the affine expression is created.
2580 __isl_give isl_pw_aff *pet_expr_extract_affine(__isl_keep pet_expr *expr,
2581 __isl_keep pet_context *pc)
2583 if (!expr)
2584 return NULL;
2586 switch (pet_expr_get_type(expr)) {
2587 case pet_expr_access:
2588 return extract_affine_from_access(expr, pc);
2589 case pet_expr_int:
2590 return extract_affine_from_int(expr, pc);
2591 case pet_expr_op:
2592 return extract_affine_from_op(expr, pc);
2593 case pet_expr_call:
2594 return extract_affine_from_call(expr, pc);
2595 case pet_expr_cast:
2596 case pet_expr_double:
2597 case pet_expr_error:
2598 return non_affine(pet_context_get_space(pc));
2602 /* Extract an affine expressions representing the comparison "LHS op RHS"
2603 * Return NaN if we are unable to extract such an affine expression.
2605 * "pc" is the context in which the affine expression is created.
2607 * If the comparison is of the form
2609 * a <= min(b,c)
2611 * then the expression is constructed as the conjunction of
2612 * the comparisons
2614 * a <= b and a <= c
2616 * A similar optimization is performed for max(a,b) <= c.
2617 * We do this because that will lead to simpler representations
2618 * of the expression.
2619 * If isl is ever enhanced to explicitly deal with min and max expressions,
2620 * this optimization can be removed.
2622 __isl_give isl_pw_aff *pet_expr_extract_comparison(enum pet_op_type op,
2623 __isl_keep pet_expr *lhs, __isl_keep pet_expr *rhs,
2624 __isl_keep pet_context *pc)
2626 isl_pw_aff *lhs_pa, *rhs_pa;
2628 if (op == pet_op_gt)
2629 return pet_expr_extract_comparison(pet_op_lt, rhs, lhs, pc);
2630 if (op == pet_op_ge)
2631 return pet_expr_extract_comparison(pet_op_le, rhs, lhs, pc);
2633 if (op == pet_op_lt || op == pet_op_le) {
2634 if (pet_expr_is_min(rhs)) {
2635 lhs_pa = pet_expr_extract_comparison(op, lhs,
2636 rhs->args[0], pc);
2637 rhs_pa = pet_expr_extract_comparison(op, lhs,
2638 rhs->args[1], pc);
2639 return pet_and(lhs_pa, rhs_pa);
2641 if (pet_expr_is_max(lhs)) {
2642 lhs_pa = pet_expr_extract_comparison(op, lhs->args[0],
2643 rhs, pc);
2644 rhs_pa = pet_expr_extract_comparison(op, lhs->args[1],
2645 rhs, pc);
2646 return pet_and(lhs_pa, rhs_pa);
2650 lhs_pa = pet_expr_extract_affine(lhs, pc);
2651 rhs_pa = pet_expr_extract_affine(rhs, pc);
2653 return pet_comparison(op, lhs_pa, rhs_pa);
2656 /* Extract an affine expressions from the comparison "expr".
2657 * Return NaN if we are unable to extract such an affine expression.
2659 * "pc" is the context in which the affine expression is created.
2661 static __isl_give isl_pw_aff *extract_comparison(__isl_keep pet_expr *expr,
2662 __isl_keep pet_context *pc)
2664 enum pet_op_type type;
2666 if (!expr)
2667 return NULL;
2668 if (expr->n_arg != 2)
2669 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2670 "expecting two arguments", return NULL);
2672 type = pet_expr_op_get_type(expr);
2673 return pet_expr_extract_comparison(type, expr->args[0], expr->args[1],
2674 pc);
2677 /* Extract an affine expression representing the boolean operation
2678 * expressed by "expr".
2679 * Return NaN if we are unable to extract an affine expression.
2681 * "pc" is the context in which the affine expression is created.
2683 static __isl_give isl_pw_aff *extract_boolean(__isl_keep pet_expr *expr,
2684 __isl_keep pet_context *pc)
2686 isl_pw_aff *lhs, *rhs;
2687 int n;
2689 if (!expr)
2690 return NULL;
2692 n = pet_expr_get_n_arg(expr);
2693 lhs = pet_expr_extract_affine_condition(expr->args[0], pc);
2694 if (n == 1)
2695 return pet_not(lhs);
2697 rhs = pet_expr_extract_affine_condition(expr->args[1], pc);
2698 return pet_boolean(pet_expr_op_get_type(expr), lhs, rhs);
2701 /* Extract the affine expression "expr != 0 ? 1 : 0".
2702 * Return NaN if we are unable to extract an affine expression.
2704 * "pc" is the context in which the affine expression is created.
2706 static __isl_give isl_pw_aff *extract_implicit_condition(
2707 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2709 isl_pw_aff *res;
2711 res = pet_expr_extract_affine(expr, pc);
2712 return pet_to_bool(res);
2715 /* Extract a boolean affine expression from "expr".
2716 * Return NaN if we are unable to extract an affine expression.
2718 * "pc" is the context in which the affine expression is created.
2720 * If "expr" is neither a comparison nor a boolean operation,
2721 * then we assume it is an affine expression and return the
2722 * boolean expression "expr != 0 ? 1 : 0".
2724 __isl_give isl_pw_aff *pet_expr_extract_affine_condition(
2725 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2727 if (!expr)
2728 return NULL;
2730 if (pet_expr_is_comparison(expr))
2731 return extract_comparison(expr, pc);
2732 if (pet_expr_is_boolean(expr))
2733 return extract_boolean(expr, pc);
2735 return extract_implicit_condition(expr, pc);
2738 /* Check if "expr" is an assume expression and if its single argument
2739 * can be converted to an affine expression in the context of "pc".
2740 * If so, replace the argument by the affine expression.
2742 __isl_give pet_expr *pet_expr_resolve_assume(__isl_take pet_expr *expr,
2743 __isl_keep pet_context *pc)
2745 isl_pw_aff *cond;
2746 isl_multi_pw_aff *index;
2748 if (!expr)
2749 return NULL;
2750 if (!pet_expr_is_assume(expr))
2751 return expr;
2752 if (expr->n_arg != 1)
2753 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2754 "expecting one argument", return pet_expr_free(expr));
2756 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
2757 if (!cond)
2758 return pet_expr_free(expr);
2759 if (isl_pw_aff_involves_nan(cond)) {
2760 isl_pw_aff_free(cond);
2761 return expr;
2764 index = isl_multi_pw_aff_from_pw_aff(cond);
2765 expr = pet_expr_set_arg(expr, 0, pet_expr_from_index(index));
2767 return expr;
2770 /* Return the number of bits needed to represent the type of "expr".
2771 * See the description of the type_size field of pet_expr.
2773 int pet_expr_get_type_size(__isl_keep pet_expr *expr)
2775 return expr ? expr->type_size : 0;
2778 /* Replace the number of bits needed to represent the type of "expr"
2779 * by "type_size".
2780 * See the description of the type_size field of pet_expr.
2782 __isl_give pet_expr *pet_expr_set_type_size(__isl_take pet_expr *expr,
2783 int type_size)
2785 expr = pet_expr_cow(expr);
2786 if (!expr)
2787 return NULL;
2789 expr->type_size = type_size;
2791 return expr;
2794 /* Extend an access expression "expr" with an additional index "index".
2795 * In particular, add "index" as an extra argument to "expr" and
2796 * adjust the index expression of "expr" to refer to this extra argument.
2797 * The caller is responsible for calling pet_expr_access_set_depth
2798 * to update the corresponding access relation.
2800 * Note that we only collect the individual index expressions as
2801 * arguments of "expr" here.
2802 * An attempt to integrate them into the index expression of "expr"
2803 * is performed in pet_expr_access_plug_in_args.
2805 __isl_give pet_expr *pet_expr_access_subscript(__isl_take pet_expr *expr,
2806 __isl_take pet_expr *index)
2808 int n;
2809 isl_space *space;
2810 isl_local_space *ls;
2811 isl_pw_aff *pa;
2813 expr = pet_expr_cow(expr);
2814 if (!expr || !index)
2815 goto error;
2816 if (expr->type != pet_expr_access)
2817 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2818 "not an access pet_expr", goto error);
2820 n = pet_expr_get_n_arg(expr);
2821 expr = pet_expr_insert_arg(expr, n, index);
2822 if (!expr)
2823 return NULL;
2825 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
2826 ls = isl_local_space_from_space(space);
2827 pa = isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, isl_dim_set, n));
2828 expr->acc.index = pet_array_subscript(expr->acc.index, pa);
2829 if (!expr->acc.index)
2830 return pet_expr_free(expr);
2832 return expr;
2833 error:
2834 pet_expr_free(expr);
2835 pet_expr_free(index);
2836 return NULL;
2839 /* Extend an access expression "expr" with an additional member acces to "id".
2840 * In particular, extend the index expression of "expr" to include
2841 * the additional member access.
2842 * The caller is responsible for calling pet_expr_access_set_depth
2843 * to update the corresponding access relation.
2845 __isl_give pet_expr *pet_expr_access_member(__isl_take pet_expr *expr,
2846 __isl_take isl_id *id)
2848 isl_space *space;
2849 isl_multi_pw_aff *field_access;
2851 expr = pet_expr_cow(expr);
2852 if (!expr || !id)
2853 goto error;
2854 if (expr->type != pet_expr_access)
2855 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2856 "not an access pet_expr", goto error);
2858 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
2859 space = isl_space_from_domain(space);
2860 space = isl_space_set_tuple_id(space, isl_dim_out, id);
2861 field_access = isl_multi_pw_aff_zero(space);
2862 expr->acc.index = pet_array_member(expr->acc.index, field_access);
2863 if (!expr->acc.index)
2864 return pet_expr_free(expr);
2866 return expr;
2867 error:
2868 pet_expr_free(expr);
2869 isl_id_free(id);
2870 return NULL;
2873 void pet_expr_dump_with_indent(__isl_keep pet_expr *expr, int indent)
2875 int i;
2877 if (!expr)
2878 return;
2880 fprintf(stderr, "%*s", indent, "");
2882 switch (expr->type) {
2883 case pet_expr_double:
2884 fprintf(stderr, "%s\n", expr->d.s);
2885 break;
2886 case pet_expr_int:
2887 isl_val_dump(expr->i);
2888 break;
2889 case pet_expr_access:
2890 if (expr->acc.ref_id) {
2891 isl_id_dump(expr->acc.ref_id);
2892 fprintf(stderr, "%*s", indent, "");
2894 isl_map_dump(expr->acc.access);
2895 fprintf(stderr, "%*s", indent, "");
2896 isl_multi_pw_aff_dump(expr->acc.index);
2897 fprintf(stderr, "%*sread: %d\n", indent + 2,
2898 "", expr->acc.read);
2899 fprintf(stderr, "%*swrite: %d\n", indent + 2,
2900 "", expr->acc.write);
2901 for (i = 0; i < expr->n_arg; ++i)
2902 pet_expr_dump_with_indent(expr->args[i], indent + 2);
2903 break;
2904 case pet_expr_op:
2905 fprintf(stderr, "%s\n", op_str[expr->op]);
2906 for (i = 0; i < expr->n_arg; ++i)
2907 pet_expr_dump_with_indent(expr->args[i], indent + 2);
2908 break;
2909 case pet_expr_call:
2910 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
2911 for (i = 0; i < expr->n_arg; ++i)
2912 pet_expr_dump_with_indent(expr->args[i], indent + 2);
2913 break;
2914 case pet_expr_cast:
2915 fprintf(stderr, "(%s)\n", expr->type_name);
2916 for (i = 0; i < expr->n_arg; ++i)
2917 pet_expr_dump_with_indent(expr->args[i], indent + 2);
2918 break;
2919 case pet_expr_error:
2920 fprintf(stderr, "ERROR\n");
2921 break;
2925 void pet_expr_dump(__isl_keep pet_expr *expr)
2927 pet_expr_dump_with_indent(expr, 0);