expr.c: extract_affine_mul: abort on error rather than treating it as non-affine
[pet.git] / expr.c
blobc239b91b873412c1b4a4228e23bb461f26031eb0
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 index expression.
151 * By default, the access is considered to be a read access.
152 * The initial depth is set from the index expression and
153 * may still be updated by the caller before the access relation
154 * is created.
156 __isl_give pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
158 isl_ctx *ctx;
159 pet_expr *expr;
161 if (!index)
162 return NULL;
163 ctx = isl_multi_pw_aff_get_ctx(index);
164 expr = pet_expr_alloc(ctx, pet_expr_access);
165 if (!expr)
166 goto error;
168 expr->acc.read = 1;
169 expr->acc.write = 0;
171 expr = pet_expr_access_set_index(expr, index);
173 return expr;
174 error:
175 isl_multi_pw_aff_free(index);
176 return NULL;
179 /* Extend the range of "access" with "n" dimensions, retaining
180 * the tuple identifier on this range.
182 * If "access" represents a member access, then extend the range
183 * of the member.
185 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
187 isl_id *id;
189 id = isl_map_get_tuple_id(access, isl_dim_out);
191 if (!isl_map_range_is_wrapping(access)) {
192 access = isl_map_add_dims(access, isl_dim_out, n);
193 } else {
194 isl_map *domain;
196 domain = isl_map_copy(access);
197 domain = isl_map_range_factor_domain(domain);
198 access = isl_map_range_factor_range(access);
199 access = extend_range(access, n);
200 access = isl_map_range_product(domain, access);
203 access = isl_map_set_tuple_id(access, isl_dim_out, id);
205 return access;
208 /* Does the access expression "expr" have any explicit access relation?
210 static int has_any_access_relation(__isl_keep pet_expr *expr)
212 enum pet_expr_access_type type;
214 if (!expr)
215 return -1;
217 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type)
218 if (expr->acc.access[type])
219 return 1;
221 return 0;
224 /* Are all relevant access relations explicitly available in "expr"?
226 static int has_relevant_access_relations(__isl_keep pet_expr *expr)
228 enum pet_expr_access_type type;
230 if (!expr)
231 return -1;
233 if (expr->acc.kill && !expr->acc.access[pet_expr_access_fake_killed])
234 return 0;
235 if (expr->acc.read && !expr->acc.access[pet_expr_access_may_read])
236 return 0;
237 if (expr->acc.write &&
238 (!expr->acc.access[pet_expr_access_may_write] ||
239 !expr->acc.access[pet_expr_access_must_write]))
240 return 0;
242 return 1;
245 /* Replace the depth of the access expr "expr" by "depth".
247 * To avoid inconsistencies between the depth and the access relation,
248 * we currently do not allow the depth to change once the access relation
249 * has been set or computed.
251 __isl_give pet_expr *pet_expr_access_set_depth(__isl_take pet_expr *expr,
252 int depth)
254 isl_map *access;
255 int dim;
257 if (!expr)
258 return NULL;
259 if (expr->acc.depth == depth)
260 return expr;
261 if (has_any_access_relation(expr))
262 isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
263 "depth cannot be changed after access relation "
264 "has been set or computed", return pet_expr_free(expr));
266 expr = pet_expr_cow(expr);
267 if (!expr)
268 return NULL;
269 expr->acc.depth = depth;
271 return expr;
274 /* Construct a pet_expr that kills the elements specified by
275 * the index expression "index" and the access relation "access".
277 __isl_give pet_expr *pet_expr_kill_from_access_and_index(
278 __isl_take isl_map *access, __isl_take isl_multi_pw_aff *index)
280 int depth;
281 pet_expr *expr;
283 if (!access || !index)
284 goto error;
286 expr = pet_expr_from_index(index);
287 expr = pet_expr_access_set_read(expr, 0);
288 expr = pet_expr_access_set_kill(expr, 1);
289 depth = isl_map_dim(access, isl_dim_out);
290 expr = pet_expr_access_set_depth(expr, depth);
291 expr = pet_expr_access_set_access(expr, pet_expr_access_killed,
292 isl_union_map_from_map(access));
293 return pet_expr_new_unary(pet_op_kill, expr);
294 error:
295 isl_map_free(access);
296 isl_multi_pw_aff_free(index);
297 return NULL;
300 /* Construct a unary pet_expr that performs "op" on "arg".
302 __isl_give pet_expr *pet_expr_new_unary(enum pet_op_type op,
303 __isl_take pet_expr *arg)
305 isl_ctx *ctx;
306 pet_expr *expr;
308 if (!arg)
309 return NULL;
310 ctx = pet_expr_get_ctx(arg);
311 expr = pet_expr_alloc(ctx, pet_expr_op);
312 expr = pet_expr_set_n_arg(expr, 1);
313 if (!expr)
314 goto error;
316 expr->op = op;
317 expr->args[pet_un_arg] = arg;
319 return expr;
320 error:
321 pet_expr_free(arg);
322 return NULL;
325 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
326 * where the result is represented using a type of "type_size" bits
327 * (may be zero if unknown or if the type is not an integer).
329 __isl_give pet_expr *pet_expr_new_binary(int type_size, enum pet_op_type op,
330 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
332 isl_ctx *ctx;
333 pet_expr *expr;
335 if (!lhs || !rhs)
336 goto error;
337 ctx = pet_expr_get_ctx(lhs);
338 expr = pet_expr_alloc(ctx, pet_expr_op);
339 expr = pet_expr_set_n_arg(expr, 2);
340 if (!expr)
341 goto error;
343 expr->op = op;
344 expr->type_size = type_size;
345 expr->args[pet_bin_lhs] = lhs;
346 expr->args[pet_bin_rhs] = rhs;
348 return expr;
349 error:
350 pet_expr_free(lhs);
351 pet_expr_free(rhs);
352 return NULL;
355 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
357 __isl_give pet_expr *pet_expr_new_ternary(__isl_take pet_expr *cond,
358 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
360 isl_ctx *ctx;
361 pet_expr *expr;
363 if (!cond || !lhs || !rhs)
364 goto error;
365 ctx = pet_expr_get_ctx(cond);
366 expr = pet_expr_alloc(ctx, pet_expr_op);
367 expr = pet_expr_set_n_arg(expr, 3);
368 if (!expr)
369 goto error;
371 expr->op = pet_op_cond;
372 expr->args[pet_ter_cond] = cond;
373 expr->args[pet_ter_true] = lhs;
374 expr->args[pet_ter_false] = rhs;
376 return expr;
377 error:
378 pet_expr_free(cond);
379 pet_expr_free(lhs);
380 pet_expr_free(rhs);
381 return NULL;
384 /* Construct a call pet_expr that calls function "name" with "n_arg"
385 * arguments. The caller is responsible for filling in the arguments.
387 __isl_give pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
388 unsigned n_arg)
390 pet_expr *expr;
392 expr = pet_expr_alloc(ctx, pet_expr_call);
393 expr = pet_expr_set_n_arg(expr, n_arg);
394 if (!expr)
395 return NULL;
397 expr->c.name = strdup(name);
398 if (!expr->c.name)
399 return pet_expr_free(expr);
401 return expr;
404 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
406 __isl_give pet_expr *pet_expr_new_cast(const char *type_name,
407 __isl_take pet_expr *arg)
409 isl_ctx *ctx;
410 pet_expr *expr;
412 if (!arg)
413 return NULL;
415 ctx = pet_expr_get_ctx(arg);
416 expr = pet_expr_alloc(ctx, pet_expr_cast);
417 expr = pet_expr_set_n_arg(expr, 1);
418 if (!expr)
419 goto error;
421 expr->type_name = strdup(type_name);
422 if (!expr->type_name)
423 goto error;
425 expr->args[0] = arg;
427 return expr;
428 error:
429 pet_expr_free(arg);
430 pet_expr_free(expr);
431 return NULL;
434 /* Construct a pet_expr that represents the double "d".
436 __isl_give pet_expr *pet_expr_new_double(isl_ctx *ctx,
437 double val, const char *s)
439 pet_expr *expr;
441 expr = pet_expr_alloc(ctx, pet_expr_double);
442 if (!expr)
443 return NULL;
445 expr->d.val = val;
446 expr->d.s = strdup(s);
447 if (!expr->d.s)
448 return pet_expr_free(expr);
450 return expr;
453 /* Construct a pet_expr that represents the integer value "v".
455 __isl_give pet_expr *pet_expr_new_int(__isl_take isl_val *v)
457 isl_ctx *ctx;
458 pet_expr *expr;
460 if (!v)
461 return NULL;
463 ctx = isl_val_get_ctx(v);
464 expr = pet_expr_alloc(ctx, pet_expr_int);
465 if (!expr)
466 goto error;
468 expr->i = v;
470 return expr;
471 error:
472 isl_val_free(v);
473 return NULL;
476 /* Return an independent duplicate of "expr".
478 * In case of an access expression, make sure the depth of the duplicate is set
479 * before the access relation (if any) is set and after the index expression
480 * is set.
482 static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr)
484 int i;
485 pet_expr *dup;
486 enum pet_expr_access_type type;
488 if (!expr)
489 return NULL;
491 dup = pet_expr_alloc(expr->ctx, expr->type);
492 dup = pet_expr_set_type_size(dup, expr->type_size);
493 dup = pet_expr_set_n_arg(dup, expr->n_arg);
494 for (i = 0; i < expr->n_arg; ++i)
495 dup = pet_expr_set_arg(dup, i, pet_expr_copy(expr->args[i]));
497 switch (expr->type) {
498 case pet_expr_access:
499 if (expr->acc.ref_id)
500 dup = pet_expr_access_set_ref_id(dup,
501 isl_id_copy(expr->acc.ref_id));
502 dup = pet_expr_access_set_index(dup,
503 isl_multi_pw_aff_copy(expr->acc.index));
504 dup = pet_expr_access_set_depth(dup, expr->acc.depth);
505 for (type = pet_expr_access_begin;
506 type < pet_expr_access_end; ++type) {
507 if (!expr->acc.access[type])
508 continue;
509 dup = pet_expr_access_set_access(dup, type,
510 isl_union_map_copy(expr->acc.access[type]));
512 dup = pet_expr_access_set_read(dup, expr->acc.read);
513 dup = pet_expr_access_set_write(dup, expr->acc.write);
514 dup = pet_expr_access_set_kill(dup, expr->acc.kill);
515 break;
516 case pet_expr_call:
517 dup = pet_expr_call_set_name(dup, expr->c.name);
518 if (expr->c.summary)
519 dup = pet_expr_call_set_summary(dup,
520 pet_function_summary_copy(expr->c.summary));
521 break;
522 case pet_expr_cast:
523 dup = pet_expr_cast_set_type_name(dup, expr->type_name);
524 break;
525 case pet_expr_double:
526 dup = pet_expr_double_set(dup, expr->d.val, expr->d.s);
527 break;
528 case pet_expr_int:
529 dup = pet_expr_int_set_val(dup, isl_val_copy(expr->i));
530 break;
531 case pet_expr_op:
532 dup = pet_expr_op_set_type(dup, expr->op);
533 break;
534 case pet_expr_error:
535 dup = pet_expr_free(dup);
536 break;
539 return dup;
542 __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr)
544 if (!expr)
545 return NULL;
547 if (expr->ref == 1)
548 return expr;
549 expr->ref--;
550 return pet_expr_dup(expr);
553 __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr)
555 enum pet_expr_access_type type;
556 int i;
558 if (!expr)
559 return NULL;
560 if (--expr->ref > 0)
561 return NULL;
563 for (i = 0; i < expr->n_arg; ++i)
564 pet_expr_free(expr->args[i]);
565 free(expr->args);
567 switch (expr->type) {
568 case pet_expr_access:
569 isl_id_free(expr->acc.ref_id);
570 for (type = pet_expr_access_begin;
571 type < pet_expr_access_end; ++type)
572 isl_union_map_free(expr->acc.access[type]);
573 isl_multi_pw_aff_free(expr->acc.index);
574 break;
575 case pet_expr_call:
576 free(expr->c.name);
577 pet_function_summary_free(expr->c.summary);
578 break;
579 case pet_expr_cast:
580 free(expr->type_name);
581 break;
582 case pet_expr_double:
583 free(expr->d.s);
584 break;
585 case pet_expr_int:
586 isl_val_free(expr->i);
587 break;
588 case pet_expr_op:
589 case pet_expr_error:
590 break;
593 isl_ctx_deref(expr->ctx);
594 free(expr);
595 return NULL;
598 /* Return an additional reference to "expr".
600 __isl_give pet_expr *pet_expr_copy(__isl_keep pet_expr *expr)
602 if (!expr)
603 return NULL;
605 expr->ref++;
606 return expr;
609 /* Return the isl_ctx in which "expr" was created.
611 isl_ctx *pet_expr_get_ctx(__isl_keep pet_expr *expr)
613 return expr ? expr->ctx : NULL;
616 /* Return the type of "expr".
618 enum pet_expr_type pet_expr_get_type(__isl_keep pet_expr *expr)
620 if (!expr)
621 return pet_expr_error;
622 return expr->type;
625 /* Return the number of arguments of "expr".
627 int pet_expr_get_n_arg(__isl_keep pet_expr *expr)
629 if (!expr)
630 return -1;
632 return expr->n_arg;
635 /* Set the number of arguments of "expr" to "n".
637 * If "expr" originally had more arguments, then remove the extra arguments.
638 * If "expr" originally had fewer arguments, then create space for
639 * the extra arguments ans initialize them to NULL.
641 __isl_give pet_expr *pet_expr_set_n_arg(__isl_take pet_expr *expr, int n)
643 int i;
644 pet_expr **args;
646 if (!expr)
647 return NULL;
648 if (expr->n_arg == n)
649 return expr;
650 expr = pet_expr_cow(expr);
651 if (!expr)
652 return NULL;
654 if (n < expr->n_arg) {
655 for (i = n; i < expr->n_arg; ++i)
656 pet_expr_free(expr->args[i]);
657 expr->n_arg = n;
658 return expr;
661 args = isl_realloc_array(expr->ctx, expr->args, pet_expr *, n);
662 if (!args)
663 return pet_expr_free(expr);
664 expr->args = args;
665 for (i = expr->n_arg; i < n; ++i)
666 expr->args[i] = NULL;
667 expr->n_arg = n;
669 return expr;
672 /* Return the argument of "expr" at position "pos".
674 __isl_give pet_expr *pet_expr_get_arg(__isl_keep pet_expr *expr, int pos)
676 if (!expr)
677 return NULL;
678 if (pos < 0 || pos >= expr->n_arg)
679 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
680 "position out of bounds", return NULL);
682 return pet_expr_copy(expr->args[pos]);
685 /* Replace the argument of "expr" at position "pos" by "arg".
687 __isl_give pet_expr *pet_expr_set_arg(__isl_take pet_expr *expr, int pos,
688 __isl_take pet_expr *arg)
690 if (!expr || !arg)
691 goto error;
692 if (pos < 0 || pos >= expr->n_arg)
693 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
694 "position out of bounds", goto error);
695 if (expr->args[pos] == arg) {
696 pet_expr_free(arg);
697 return expr;
700 expr = pet_expr_cow(expr);
701 if (!expr)
702 goto error;
704 pet_expr_free(expr->args[pos]);
705 expr->args[pos] = arg;
707 return expr;
708 error:
709 pet_expr_free(expr);
710 pet_expr_free(arg);
711 return NULL;
714 /* Does "expr" perform a comparison operation?
716 int pet_expr_is_comparison(__isl_keep pet_expr *expr)
718 if (!expr)
719 return -1;
720 if (expr->type != pet_expr_op)
721 return 0;
722 switch (expr->op) {
723 case pet_op_eq:
724 case pet_op_ne:
725 case pet_op_le:
726 case pet_op_ge:
727 case pet_op_lt:
728 case pet_op_gt:
729 return 1;
730 default:
731 return 0;
735 /* Does "expr" perform a boolean operation?
737 int pet_expr_is_boolean(__isl_keep pet_expr *expr)
739 if (!expr)
740 return -1;
741 if (expr->type != pet_expr_op)
742 return 0;
743 switch (expr->op) {
744 case pet_op_land:
745 case pet_op_lor:
746 case pet_op_lnot:
747 return 1;
748 default:
749 return 0;
753 /* Is "expr" an assume statement?
755 int pet_expr_is_assume(__isl_keep pet_expr *expr)
757 if (!expr)
758 return -1;
759 if (expr->type != pet_expr_op)
760 return 0;
761 return expr->op == pet_op_assume;
764 /* Does "expr" perform a min operation?
766 int pet_expr_is_min(__isl_keep pet_expr *expr)
768 if (!expr)
769 return -1;
770 if (expr->type != pet_expr_call)
771 return 0;
772 if (expr->n_arg != 2)
773 return 0;
774 if (strcmp(expr->c.name, "min") != 0)
775 return 0;
776 return 1;
779 /* Does "expr" perform a max operation?
781 int pet_expr_is_max(__isl_keep pet_expr *expr)
783 if (!expr)
784 return -1;
785 if (expr->type != pet_expr_call)
786 return 0;
787 if (expr->n_arg != 2)
788 return 0;
789 if (strcmp(expr->c.name, "max") != 0)
790 return 0;
791 return 1;
794 /* Does "expr" represent an access to an unnamed space, i.e.,
795 * does it represent an affine expression?
797 int pet_expr_is_affine(__isl_keep pet_expr *expr)
799 int has_id;
801 if (!expr)
802 return -1;
803 if (expr->type != pet_expr_access)
804 return 0;
806 has_id = isl_multi_pw_aff_has_tuple_id(expr->acc.index, isl_dim_out);
807 if (has_id < 0)
808 return -1;
810 return !has_id;
813 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
814 * not part of any struct?
816 int pet_expr_is_scalar_access(__isl_keep pet_expr *expr)
818 if (!expr)
819 return -1;
820 if (expr->type != pet_expr_access)
821 return 0;
822 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index))
823 return 0;
825 return expr->acc.depth == 0;
828 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
829 * of parameters.
831 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1,
832 __isl_keep isl_multi_pw_aff *mpa2)
834 int equal;
836 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
837 if (equal < 0 || equal)
838 return equal;
839 mpa2 = isl_multi_pw_aff_copy(mpa2);
840 mpa2 = isl_multi_pw_aff_align_params(mpa2,
841 isl_multi_pw_aff_get_space(mpa1));
842 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
843 isl_multi_pw_aff_free(mpa2);
845 return equal;
848 /* Construct an access relation from the index expression and
849 * the array depth of the access expression "expr".
851 * If the number of indices is smaller than the depth of the array,
852 * then we assume that all elements of the remaining dimensions
853 * are accessed.
855 static __isl_give isl_union_map *construct_access_relation(
856 __isl_keep pet_expr *expr)
858 isl_map *access;
859 int dim;
860 int read, write;
862 if (!expr)
863 return NULL;
865 access = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
866 if (!access)
867 return NULL;
869 dim = isl_map_dim(access, isl_dim_out);
870 if (dim > expr->acc.depth)
871 isl_die(isl_map_get_ctx(access), isl_error_internal,
872 "number of indices greater than depth",
873 access = isl_map_free(access));
875 if (dim != expr->acc.depth)
876 access = extend_range(access, expr->acc.depth - dim);
878 return isl_union_map_from_map(access);
881 /* Ensure that all relevant access relations are explicitly
882 * available in "expr".
884 * If "expr" does not already have the relevant access relations, then create
885 * them based on the index expression and the array depth.
887 * We do not cow since adding an explicit access relation
888 * does not change the meaning of the expression.
890 static __isl_give pet_expr *introduce_access_relations(
891 __isl_take pet_expr *expr)
893 enum pet_expr_access_type type;
894 isl_union_map *access;
895 int dim;
896 int kill, read, write;
898 if (!expr)
899 return NULL;
900 if (has_relevant_access_relations(expr))
901 return expr;
903 access = construct_access_relation(expr);
904 if (!access)
905 return pet_expr_free(expr);
907 kill = expr->acc.kill;
908 read = expr->acc.read;
909 write = expr->acc.write;
910 if (kill && !expr->acc.access[pet_expr_access_fake_killed])
911 expr->acc.access[pet_expr_access_fake_killed] =
912 isl_union_map_copy(access);
913 if (read && !expr->acc.access[pet_expr_access_may_read])
914 expr->acc.access[pet_expr_access_may_read] =
915 isl_union_map_copy(access);
916 if (write && !expr->acc.access[pet_expr_access_may_write])
917 expr->acc.access[pet_expr_access_may_write] =
918 isl_union_map_copy(access);
919 if (write && !expr->acc.access[pet_expr_access_must_write])
920 expr->acc.access[pet_expr_access_must_write] =
921 isl_union_map_copy(access);
923 isl_union_map_free(access);
925 if (!has_relevant_access_relations(expr))
926 return pet_expr_free(expr);
928 return expr;
931 /* Return 1 if the two pet_exprs are equivalent.
933 int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2)
935 int i;
936 enum pet_expr_access_type type;
938 if (!expr1 || !expr2)
939 return 0;
941 if (expr1->type != expr2->type)
942 return 0;
943 if (expr1->n_arg != expr2->n_arg)
944 return 0;
945 for (i = 0; i < expr1->n_arg; ++i)
946 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
947 return 0;
948 switch (expr1->type) {
949 case pet_expr_error:
950 return -1;
951 case pet_expr_double:
952 if (strcmp(expr1->d.s, expr2->d.s))
953 return 0;
954 if (expr1->d.val != expr2->d.val)
955 return 0;
956 break;
957 case pet_expr_int:
958 if (!isl_val_eq(expr1->i, expr2->i))
959 return 0;
960 break;
961 case pet_expr_access:
962 if (expr1->acc.read != expr2->acc.read)
963 return 0;
964 if (expr1->acc.write != expr2->acc.write)
965 return 0;
966 if (expr1->acc.kill != expr2->acc.kill)
967 return 0;
968 if (expr1->acc.ref_id != expr2->acc.ref_id)
969 return 0;
970 if (!expr1->acc.index || !expr2->acc.index)
971 return 0;
972 if (!multi_pw_aff_is_equal(expr1->acc.index, expr2->acc.index))
973 return 0;
974 if (expr1->acc.depth != expr2->acc.depth)
975 return 0;
976 if (has_relevant_access_relations(expr1) !=
977 has_relevant_access_relations(expr2)) {
978 int equal;
979 expr1 = pet_expr_copy(expr1);
980 expr2 = pet_expr_copy(expr2);
981 expr1 = introduce_access_relations(expr1);
982 expr2 = introduce_access_relations(expr2);
983 equal = pet_expr_is_equal(expr1, expr2);
984 pet_expr_free(expr1);
985 pet_expr_free(expr2);
986 return equal;
988 for (type = pet_expr_access_begin;
989 type < pet_expr_access_end; ++type) {
990 if (!expr1->acc.access[type] !=
991 !expr2->acc.access[type])
992 return 0;
993 if (!expr1->acc.access[type])
994 continue;
995 if (!isl_union_map_is_equal(expr1->acc.access[type],
996 expr2->acc.access[type]))
997 return 0;
999 break;
1000 case pet_expr_op:
1001 if (expr1->op != expr2->op)
1002 return 0;
1003 break;
1004 case pet_expr_call:
1005 if (strcmp(expr1->c.name, expr2->c.name))
1006 return 0;
1007 break;
1008 case pet_expr_cast:
1009 if (strcmp(expr1->type_name, expr2->type_name))
1010 return 0;
1011 break;
1014 return 1;
1017 /* Does the access expression "expr" read the accessed elements?
1019 int pet_expr_access_is_read(__isl_keep pet_expr *expr)
1021 if (!expr)
1022 return -1;
1023 if (expr->type != pet_expr_access)
1024 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1025 "not an access expression", return -1);
1027 return expr->acc.read;
1030 /* Does the access expression "expr" write to the accessed elements?
1032 int pet_expr_access_is_write(__isl_keep pet_expr *expr)
1034 if (!expr)
1035 return -1;
1036 if (expr->type != pet_expr_access)
1037 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1038 "not an access expression", return -1);
1040 return expr->acc.write;
1043 /* Return the identifier of the array accessed by "expr".
1045 * If "expr" represents a member access, then return the identifier
1046 * of the outer structure array.
1048 __isl_give isl_id *pet_expr_access_get_id(__isl_keep pet_expr *expr)
1050 if (!expr)
1051 return NULL;
1052 if (expr->type != pet_expr_access)
1053 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1054 "not an access expression", return NULL);
1056 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index)) {
1057 isl_space *space;
1058 isl_id *id;
1060 space = isl_multi_pw_aff_get_space(expr->acc.index);
1061 space = isl_space_range(space);
1062 while (space && isl_space_is_wrapping(space))
1063 space = isl_space_domain(isl_space_unwrap(space));
1064 id = isl_space_get_tuple_id(space, isl_dim_set);
1065 isl_space_free(space);
1067 return id;
1070 return isl_multi_pw_aff_get_tuple_id(expr->acc.index, isl_dim_out);
1073 /* Return the parameter space of "expr".
1075 __isl_give isl_space *pet_expr_access_get_parameter_space(
1076 __isl_keep pet_expr *expr)
1078 isl_space *space;
1080 if (!expr)
1081 return NULL;
1082 if (expr->type != pet_expr_access)
1083 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1084 "not an access expression", return NULL);
1086 space = isl_multi_pw_aff_get_space(expr->acc.index);
1087 space = isl_space_params(space);
1089 return space;
1092 /* Return the domain space of "expr", including the arguments (if any).
1094 __isl_give isl_space *pet_expr_access_get_augmented_domain_space(
1095 __isl_keep pet_expr *expr)
1097 isl_space *space;
1099 if (!expr)
1100 return NULL;
1101 if (expr->type != pet_expr_access)
1102 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1103 "not an access expression", return NULL);
1105 space = isl_multi_pw_aff_get_space(expr->acc.index);
1106 space = isl_space_domain(space);
1108 return space;
1111 /* Return the domain space of "expr", without the arguments (if any).
1113 __isl_give isl_space *pet_expr_access_get_domain_space(
1114 __isl_keep pet_expr *expr)
1116 isl_space *space;
1118 space = pet_expr_access_get_augmented_domain_space(expr);
1119 if (isl_space_is_wrapping(space))
1120 space = isl_space_domain(isl_space_unwrap(space));
1122 return space;
1125 /* Return the space of the data accessed by "expr".
1127 __isl_give isl_space *pet_expr_access_get_data_space(__isl_keep pet_expr *expr)
1129 isl_space *space;
1131 if (!expr)
1132 return NULL;
1133 if (expr->type != pet_expr_access)
1134 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1135 "not an access expression", return NULL);
1137 space = isl_multi_pw_aff_get_space(expr->acc.index);
1138 space = isl_space_range(space);
1140 return space;
1143 /* Modify all expressions of type "type" in "expr" by calling "fn" on them.
1145 static __isl_give pet_expr *pet_expr_map_expr_of_type(__isl_take pet_expr *expr,
1146 enum pet_expr_type type,
1147 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1148 void *user)
1150 int i, n;
1152 n = pet_expr_get_n_arg(expr);
1153 for (i = 0; i < n; ++i) {
1154 pet_expr *arg = pet_expr_get_arg(expr, i);
1155 arg = pet_expr_map_expr_of_type(arg, type, fn, user);
1156 expr = pet_expr_set_arg(expr, i, arg);
1159 if (!expr)
1160 return NULL;
1162 if (expr->type == type)
1163 expr = fn(expr, user);
1165 return expr;
1168 /* Modify all expressions of type pet_expr_access in "expr"
1169 * by calling "fn" on them.
1171 __isl_give pet_expr *pet_expr_map_access(__isl_take pet_expr *expr,
1172 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1173 void *user)
1175 return pet_expr_map_expr_of_type(expr, pet_expr_access, fn, user);
1178 /* Modify all expressions of type pet_expr_call in "expr"
1179 * by calling "fn" on them.
1181 __isl_give pet_expr *pet_expr_map_call(__isl_take pet_expr *expr,
1182 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1183 void *user)
1185 return pet_expr_map_expr_of_type(expr, pet_expr_call, fn, user);
1188 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1190 * Return -1 on error (where fn returning a negative value is treated as
1191 * an error).
1192 * Otherwise return 0.
1194 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr *expr,
1195 enum pet_expr_type type,
1196 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1198 int i;
1200 if (!expr)
1201 return -1;
1203 for (i = 0; i < expr->n_arg; ++i)
1204 if (pet_expr_foreach_expr_of_type(expr->args[i],
1205 type, fn, user) < 0)
1206 return -1;
1208 if (expr->type == type)
1209 return fn(expr, user);
1211 return 0;
1214 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1216 * Return -1 on error (where fn returning a negative value is treated as
1217 * an error).
1218 * Otherwise return 0.
1220 int pet_expr_foreach_access_expr(__isl_keep pet_expr *expr,
1221 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1223 return pet_expr_foreach_expr_of_type(expr, pet_expr_access, fn, user);
1226 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1228 * Return -1 on error (where fn returning a negative value is treated as
1229 * an error).
1230 * Otherwise return 0.
1232 int pet_expr_foreach_call_expr(__isl_keep pet_expr *expr,
1233 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1235 return pet_expr_foreach_expr_of_type(expr, pet_expr_call, fn, user);
1238 /* Internal data structure for pet_expr_writes.
1239 * "id" is the identifier that we are looking for.
1240 * "found" is set if we have found the identifier being written to.
1242 struct pet_expr_writes_data {
1243 isl_id *id;
1244 int found;
1247 /* Given an access expression, check if it writes to data->id.
1248 * If so, set data->found and abort the search.
1250 static int writes(__isl_keep pet_expr *expr, void *user)
1252 struct pet_expr_writes_data *data = user;
1253 isl_id *write_id;
1255 if (!expr->acc.write)
1256 return 0;
1257 if (pet_expr_is_affine(expr))
1258 return 0;
1260 write_id = pet_expr_access_get_id(expr);
1261 isl_id_free(write_id);
1263 if (!write_id)
1264 return -1;
1266 if (write_id != data->id)
1267 return 0;
1269 data->found = 1;
1270 return -1;
1273 /* Does expression "expr" write to "id"?
1275 int pet_expr_writes(__isl_keep pet_expr *expr, __isl_keep isl_id *id)
1277 struct pet_expr_writes_data data;
1279 data.id = id;
1280 data.found = 0;
1281 if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
1282 !data.found)
1283 return -1;
1285 return data.found;
1288 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1289 * index expression and access relations of "expr" (if any)
1290 * to dimensions of "dst_type" at "dst_pos".
1292 __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr,
1293 enum isl_dim_type dst_type, unsigned dst_pos,
1294 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1296 enum pet_expr_access_type type;
1298 expr = pet_expr_cow(expr);
1299 if (!expr)
1300 return NULL;
1301 if (expr->type != pet_expr_access)
1302 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1303 "not an access pet_expr", return pet_expr_free(expr));
1305 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1306 if (!expr->acc.access[type])
1307 continue;
1308 expr->acc.access[type] =
1309 pet_union_map_move_dims(expr->acc.access[type],
1310 dst_type, dst_pos, src_type, src_pos, n);
1311 if (!expr->acc.access[type])
1312 break;
1314 expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index,
1315 dst_type, dst_pos, src_type, src_pos, n);
1316 if (!expr->acc.index || type < pet_expr_access_end)
1317 return pet_expr_free(expr);
1319 return expr;
1322 /* Replace the index expression and access relations (if any) of "expr"
1323 * by their preimages under the function represented by "ma".
1325 __isl_give pet_expr *pet_expr_access_pullback_multi_aff(
1326 __isl_take pet_expr *expr, __isl_take isl_multi_aff *ma)
1328 enum pet_expr_access_type type;
1330 expr = pet_expr_cow(expr);
1331 if (!expr || !ma)
1332 goto error;
1333 if (expr->type != pet_expr_access)
1334 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1335 "not an access pet_expr", goto error);
1337 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1338 if (!expr->acc.access[type])
1339 continue;
1340 expr->acc.access[type] =
1341 isl_union_map_preimage_domain_multi_aff(
1342 expr->acc.access[type], isl_multi_aff_copy(ma));
1343 if (!expr->acc.access[type])
1344 break;
1346 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
1347 ma);
1348 if (!expr->acc.index || type < pet_expr_access_end)
1349 return pet_expr_free(expr);
1351 return expr;
1352 error:
1353 isl_multi_aff_free(ma);
1354 pet_expr_free(expr);
1355 return NULL;
1358 /* Replace the index expression and access relations (if any) of "expr"
1359 * by their preimages under the function represented by "mpa".
1361 __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff(
1362 __isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *mpa)
1364 enum pet_expr_access_type type;
1366 expr = pet_expr_cow(expr);
1367 if (!expr || !mpa)
1368 goto error;
1369 if (expr->type != pet_expr_access)
1370 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1371 "not an access pet_expr", goto error);
1373 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1374 if (!expr->acc.access[type])
1375 continue;
1376 expr->acc.access[type] =
1377 isl_union_map_preimage_domain_multi_pw_aff(
1378 expr->acc.access[type], isl_multi_pw_aff_copy(mpa));
1379 if (!expr->acc.access[type])
1380 break;
1382 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1383 expr->acc.index, mpa);
1384 if (!expr->acc.index || type < pet_expr_access_end)
1385 return pet_expr_free(expr);
1387 return expr;
1388 error:
1389 isl_multi_pw_aff_free(mpa);
1390 pet_expr_free(expr);
1391 return NULL;
1394 /* Return the index expression of access expression "expr".
1396 __isl_give isl_multi_pw_aff *pet_expr_access_get_index(
1397 __isl_keep pet_expr *expr)
1399 if (!expr)
1400 return NULL;
1401 if (expr->type != pet_expr_access)
1402 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1403 "not an access expression", return NULL);
1405 return isl_multi_pw_aff_copy(expr->acc.index);
1408 /* Align the parameters of expr->acc.index and expr->acc.access[*] (if set).
1410 __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr)
1412 isl_space *space;
1413 enum pet_expr_access_type type;
1415 expr = pet_expr_cow(expr);
1416 if (!expr)
1417 return NULL;
1418 if (expr->type != pet_expr_access)
1419 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1420 "not an access expression", return pet_expr_free(expr));
1422 if (!has_any_access_relation(expr))
1423 return expr;
1425 space = isl_multi_pw_aff_get_space(expr->acc.index);
1426 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1427 if (!expr->acc.access[type])
1428 continue;
1429 space = isl_space_align_params(space,
1430 isl_union_map_get_space(expr->acc.access[type]));
1432 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1433 isl_space_copy(space));
1434 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1435 if (!expr->acc.access[type])
1436 continue;
1437 expr->acc.access[type] =
1438 isl_union_map_align_params(expr->acc.access[type],
1439 isl_space_copy(space));
1440 if (!expr->acc.access[type])
1441 break;
1443 isl_space_free(space);
1444 if (!expr->acc.index || type < pet_expr_access_end)
1445 return pet_expr_free(expr);
1447 return expr;
1450 /* Are "expr1" and "expr2" both array accesses such that
1451 * the access relation of "expr1" is a subset of that of "expr2"?
1452 * Only take into account the first "n_arg" arguments.
1454 * This function is tailored for use by mark_self_dependences in nest.c.
1455 * In particular, the input expressions may have more than "n_arg"
1456 * elements in their arguments arrays, while only the first "n_arg"
1457 * elements are referenced from the access relations.
1459 int pet_expr_is_sub_access(__isl_keep pet_expr *expr1,
1460 __isl_keep pet_expr *expr2, int n_arg)
1462 isl_id *id1, *id2;
1463 int i, n1, n2;
1464 int is_subset;
1466 if (!expr1 || !expr2)
1467 return 0;
1468 if (pet_expr_get_type(expr1) != pet_expr_access)
1469 return 0;
1470 if (pet_expr_get_type(expr2) != pet_expr_access)
1471 return 0;
1472 if (pet_expr_is_affine(expr1))
1473 return 0;
1474 if (pet_expr_is_affine(expr2))
1475 return 0;
1476 n1 = pet_expr_get_n_arg(expr1);
1477 if (n1 > n_arg)
1478 n1 = n_arg;
1479 n2 = pet_expr_get_n_arg(expr2);
1480 if (n2 > n_arg)
1481 n2 = n_arg;
1482 if (n1 != n2)
1483 return 0;
1484 for (i = 0; i < n1; ++i) {
1485 int equal;
1486 equal = pet_expr_is_equal(expr1->args[i], expr2->args[i]);
1487 if (equal < 0 || !equal)
1488 return equal;
1490 id1 = pet_expr_access_get_id(expr1);
1491 id2 = pet_expr_access_get_id(expr2);
1492 isl_id_free(id1);
1493 isl_id_free(id2);
1494 if (!id1 || !id2)
1495 return 0;
1496 if (id1 != id2)
1497 return 0;
1499 expr1 = pet_expr_copy(expr1);
1500 expr2 = pet_expr_copy(expr2);
1501 expr1 = introduce_access_relations(expr1);
1502 expr2 = introduce_access_relations(expr2);
1503 if (!expr1 || !expr2)
1504 goto error;
1506 is_subset = isl_union_map_is_subset(
1507 expr1->acc.access[pet_expr_access_may_read],
1508 expr2->acc.access[pet_expr_access_may_read]);
1510 pet_expr_free(expr1);
1511 pet_expr_free(expr2);
1513 return is_subset;
1514 error:
1515 pet_expr_free(expr1);
1516 pet_expr_free(expr2);
1517 return -1;
1520 /* Given a set in the iteration space "domain", extend it to live in the space
1521 * of the domain of access relations.
1523 * That, is the number of arguments "n" is 0, then simply return domain.
1524 * Otherwise, return [domain -> [a_1,...,a_n]].
1526 static __isl_give isl_set *add_arguments(__isl_take isl_set *domain, int n)
1528 isl_map *map;
1530 if (n == 0)
1531 return domain;
1533 map = isl_map_from_domain(domain);
1534 map = isl_map_add_dims(map, isl_dim_out, n);
1535 return isl_map_wrap(map);
1538 /* Add extra conditions to the domains of all access relations in "expr",
1539 * introducing access relations if they are not already present.
1541 * The conditions are not added to the index expression. Instead, they
1542 * are used to try and simplify the index expression.
1544 __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr,
1545 __isl_take isl_set *cond)
1547 int i;
1548 isl_union_set *uset;
1549 enum pet_expr_access_type type;
1551 expr = pet_expr_cow(expr);
1552 if (!expr)
1553 goto error;
1555 for (i = 0; i < expr->n_arg; ++i) {
1556 expr->args[i] = pet_expr_restrict(expr->args[i],
1557 isl_set_copy(cond));
1558 if (!expr->args[i])
1559 goto error;
1562 if (expr->type != pet_expr_access) {
1563 isl_set_free(cond);
1564 return expr;
1567 expr = introduce_access_relations(expr);
1568 if (!expr)
1569 goto error;
1571 cond = add_arguments(cond, expr->n_arg);
1572 uset = isl_union_set_from_set(isl_set_copy(cond));
1573 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1574 if (!expr->acc.access[type])
1575 continue;
1576 expr->acc.access[type] =
1577 isl_union_map_intersect_domain(expr->acc.access[type],
1578 isl_union_set_copy(uset));
1579 if (!expr->acc.access[type])
1580 break;
1582 isl_union_set_free(uset);
1583 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, cond);
1584 if (type < pet_expr_access_end || !expr->acc.index)
1585 return pet_expr_free(expr);
1587 return expr;
1588 error:
1589 isl_set_free(cond);
1590 return pet_expr_free(expr);
1593 /* Modify the access relations (if any) and index expression
1594 * of the given access expression
1595 * based on the given iteration space transformation.
1596 * In particular, precompose the access relation and index expression
1597 * with the update function.
1599 * If the access has any arguments then the domain of the access relation
1600 * is a wrapped mapping from the iteration space to the space of
1601 * argument values. We only need to change the domain of this wrapped
1602 * mapping, so we extend the input transformation with an identity mapping
1603 * on the space of argument values.
1605 __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr,
1606 __isl_keep isl_multi_pw_aff *update)
1608 enum pet_expr_access_type type;
1610 expr = pet_expr_cow(expr);
1611 if (!expr)
1612 return NULL;
1613 if (expr->type != pet_expr_access)
1614 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1615 "not an access expression", return pet_expr_free(expr));
1617 update = isl_multi_pw_aff_copy(update);
1619 if (expr->n_arg > 0) {
1620 isl_space *space;
1621 isl_multi_pw_aff *id;
1623 space = isl_multi_pw_aff_get_space(expr->acc.index);
1624 space = isl_space_domain(space);
1625 space = isl_space_unwrap(space);
1626 space = isl_space_range(space);
1627 space = isl_space_map_from_set(space);
1628 id = isl_multi_pw_aff_identity(space);
1629 update = isl_multi_pw_aff_product(update, id);
1632 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1633 if (!expr->acc.access[type])
1634 continue;
1635 expr->acc.access[type] =
1636 isl_union_map_preimage_domain_multi_pw_aff(
1637 expr->acc.access[type],
1638 isl_multi_pw_aff_copy(update));
1639 if (!expr->acc.access[type])
1640 break;
1642 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1643 expr->acc.index, update);
1644 if (type < pet_expr_access_end || !expr->acc.index)
1645 return pet_expr_free(expr);
1647 return expr;
1650 static __isl_give pet_expr *update_domain(__isl_take pet_expr *expr, void *user)
1652 isl_multi_pw_aff *update = user;
1654 return pet_expr_access_update_domain(expr, update);
1657 /* Modify all access relations in "expr" by precomposing them with
1658 * the given iteration space transformation.
1660 __isl_give pet_expr *pet_expr_update_domain(__isl_take pet_expr *expr,
1661 __isl_take isl_multi_pw_aff *update)
1663 expr = pet_expr_map_access(expr, &update_domain, update);
1664 isl_multi_pw_aff_free(update);
1665 return expr;
1668 /* Given an expression with accesses that have a 0D anonymous domain,
1669 * replace those domains by "space".
1671 __isl_give pet_expr *pet_expr_insert_domain(__isl_take pet_expr *expr,
1672 __isl_take isl_space *space)
1674 isl_multi_pw_aff *mpa;
1676 space = isl_space_from_domain(space);
1677 mpa = isl_multi_pw_aff_zero(space);
1678 return pet_expr_update_domain(expr, mpa);
1681 /* Add all parameters in "space" to the access relations (if any)
1682 * and index expression of "expr".
1684 static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user)
1686 isl_space *space = user;
1687 enum pet_expr_access_type type;
1689 expr = pet_expr_cow(expr);
1690 if (!expr)
1691 return NULL;
1692 if (expr->type != pet_expr_access)
1693 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1694 "not an access expression", return pet_expr_free(expr));
1696 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1697 if (!expr->acc.access[type])
1698 continue;
1699 expr->acc.access[type] =
1700 isl_union_map_align_params(expr->acc.access[type],
1701 isl_space_copy(space));
1702 if (!expr->acc.access[type])
1703 break;
1705 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1706 isl_space_copy(space));
1707 if (type < pet_expr_access_end || !expr->acc.index)
1708 return pet_expr_free(expr);
1710 return expr;
1713 /* Add all parameters in "space" to all access relations and index expressions
1714 * in "expr".
1716 __isl_give pet_expr *pet_expr_align_params(__isl_take pet_expr *expr,
1717 __isl_take isl_space *space)
1719 expr = pet_expr_map_access(expr, &align_params, space);
1720 isl_space_free(space);
1721 return expr;
1724 /* Insert an argument expression corresponding to "test" in front
1725 * of the list of arguments described by *n_arg and *args.
1727 static __isl_give pet_expr *insert_access_arg(__isl_take pet_expr *expr,
1728 __isl_keep isl_multi_pw_aff *test)
1730 int i;
1731 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1733 if (!test)
1734 return pet_expr_free(expr);
1735 expr = pet_expr_cow(expr);
1736 if (!expr)
1737 return NULL;
1739 if (!expr->args) {
1740 expr->args = isl_calloc_array(ctx, pet_expr *, 1);
1741 if (!expr->args)
1742 return pet_expr_free(expr);
1743 } else {
1744 pet_expr **ext;
1745 ext = isl_calloc_array(ctx, pet_expr *, 1 + expr->n_arg);
1746 if (!ext)
1747 return pet_expr_free(expr);
1748 for (i = 0; i < expr->n_arg; ++i)
1749 ext[1 + i] = expr->args[i];
1750 free(expr->args);
1751 expr->args = ext;
1753 expr->n_arg++;
1754 expr->args[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1755 if (!expr->args[0])
1756 return pet_expr_free(expr);
1758 return expr;
1761 /* Make the expression "expr" depend on the value of "test"
1762 * being equal to "satisfied".
1764 * If "test" is an affine expression, we simply add the conditions
1765 * on the expression having the value "satisfied" to all access relations
1766 * (introducing access relations if they are missing) and index expressions.
1768 * Otherwise, we add a filter to "expr" (which is then assumed to be
1769 * an access expression) corresponding to "test" being equal to "satisfied".
1771 __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr,
1772 __isl_take isl_multi_pw_aff *test, int satisfied)
1774 isl_id *id;
1775 isl_ctx *ctx;
1776 isl_space *space;
1777 isl_pw_multi_aff *pma;
1778 enum pet_expr_access_type type;
1780 expr = pet_expr_cow(expr);
1781 if (!expr || !test)
1782 goto error;
1784 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
1785 isl_pw_aff *pa;
1786 isl_set *cond;
1788 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
1789 isl_multi_pw_aff_free(test);
1790 if (satisfied)
1791 cond = isl_pw_aff_non_zero_set(pa);
1792 else
1793 cond = isl_pw_aff_zero_set(pa);
1794 return pet_expr_restrict(expr, cond);
1797 ctx = isl_multi_pw_aff_get_ctx(test);
1798 if (expr->type != pet_expr_access)
1799 isl_die(ctx, isl_error_invalid,
1800 "can only filter access expressions", goto error);
1802 expr = introduce_access_relations(expr);
1803 if (!expr)
1804 goto error;
1806 space = isl_space_domain(isl_multi_pw_aff_get_space(expr->acc.index));
1807 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1808 pma = pet_filter_insert_pma(space, id, satisfied);
1810 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1811 if (!expr->acc.access[type])
1812 continue;
1813 expr->acc.access[type] =
1814 isl_union_map_preimage_domain_pw_multi_aff(
1815 expr->acc.access[type],
1816 isl_pw_multi_aff_copy(pma));
1817 if (!expr->acc.access[type])
1818 break;
1820 pma = isl_pw_multi_aff_gist(pma,
1821 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma)));
1822 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
1823 expr->acc.index, pma);
1824 if (type < pet_expr_access_end || !expr->acc.index)
1825 goto error;
1827 expr = insert_access_arg(expr, test);
1829 isl_multi_pw_aff_free(test);
1830 return expr;
1831 error:
1832 isl_multi_pw_aff_free(test);
1833 return pet_expr_free(expr);
1836 /* Add a reference identifier to access expression "expr".
1837 * "user" points to an integer that contains the sequence number
1838 * of the next reference.
1840 static __isl_give pet_expr *access_add_ref_id(__isl_take pet_expr *expr,
1841 void *user)
1843 isl_ctx *ctx;
1844 char name[50];
1845 int *n_ref = user;
1847 expr = pet_expr_cow(expr);
1848 if (!expr)
1849 return expr;
1850 if (expr->type != pet_expr_access)
1851 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1852 "not an access expression", return pet_expr_free(expr));
1854 ctx = pet_expr_get_ctx(expr);
1855 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
1856 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
1857 if (!expr->acc.ref_id)
1858 return pet_expr_free(expr);
1860 return expr;
1863 __isl_give pet_expr *pet_expr_add_ref_ids(__isl_take pet_expr *expr, int *n_ref)
1865 return pet_expr_map_access(expr, &access_add_ref_id, n_ref);
1868 /* Reset the user pointer on all parameter and tuple ids in
1869 * the access relations (if any) and the index expression
1870 * of the access expression "expr".
1872 static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr,
1873 void *user)
1875 enum pet_expr_access_type type;
1877 expr = pet_expr_cow(expr);
1878 if (!expr)
1879 return expr;
1880 if (expr->type != pet_expr_access)
1881 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1882 "not an access expression", return pet_expr_free(expr));
1884 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1885 if (!expr->acc.access[type])
1886 continue;
1887 expr->acc.access[type] =
1888 isl_union_map_reset_user(expr->acc.access[type]);
1889 if (!expr->acc.access[type])
1890 break;
1892 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
1893 if (type < pet_expr_access_end || !expr->acc.index)
1894 return pet_expr_free(expr);
1896 return expr;
1899 __isl_give pet_expr *pet_expr_anonymize(__isl_take pet_expr *expr)
1901 return pet_expr_map_access(expr, &access_anonymize, NULL);
1904 /* Data used in access_gist() callback.
1906 struct pet_access_gist_data {
1907 isl_set *domain;
1908 isl_union_map *value_bounds;
1911 /* Given an expression "expr" of type pet_expr_access, compute
1912 * the gist of the associated access relations (if any) and index expression
1913 * with respect to data->domain and the bounds on the values of the arguments
1914 * of the expression.
1916 * The arguments of "expr" have been gisted right before "expr" itself
1917 * is gisted. The gisted arguments may have become equal where before
1918 * they may not have been (obviously) equal. We therefore take
1919 * the opportunity to remove duplicate arguments here.
1921 static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user)
1923 struct pet_access_gist_data *data = user;
1924 isl_set *domain;
1925 isl_union_set *uset;
1926 enum pet_expr_access_type type;
1928 expr = pet_expr_remove_duplicate_args(expr);
1929 expr = pet_expr_cow(expr);
1930 if (!expr)
1931 return expr;
1932 if (expr->type != pet_expr_access)
1933 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1934 "not an access expression", return pet_expr_free(expr));
1936 domain = isl_set_copy(data->domain);
1937 if (expr->n_arg > 0)
1938 domain = pet_value_bounds_apply(domain, expr->n_arg, expr->args,
1939 data->value_bounds);
1941 uset = isl_union_set_from_set(isl_set_copy(domain));
1942 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1943 if (!expr->acc.access[type])
1944 continue;
1945 expr->acc.access[type] =
1946 isl_union_map_gist_domain(expr->acc.access[type],
1947 isl_union_set_copy(uset));
1948 if (!expr->acc.access[type])
1949 break;
1951 isl_union_set_free(uset);
1952 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
1953 if (type < pet_expr_access_end || !expr->acc.index)
1954 return pet_expr_free(expr);
1956 return expr;
1959 __isl_give pet_expr *pet_expr_gist(__isl_take pet_expr *expr,
1960 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
1962 struct pet_access_gist_data data = { context, value_bounds };
1964 return pet_expr_map_access(expr, &access_gist, &data);
1967 /* Mark "expr" as a read dependening on "read".
1969 __isl_give pet_expr *pet_expr_access_set_read(__isl_take pet_expr *expr,
1970 int read)
1972 if (!expr)
1973 return pet_expr_free(expr);
1974 if (expr->type != pet_expr_access)
1975 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1976 "not an access expression", return pet_expr_free(expr));
1977 if (expr->acc.read == read)
1978 return expr;
1979 expr = pet_expr_cow(expr);
1980 if (!expr)
1981 return NULL;
1982 expr->acc.read = read;
1984 return expr;
1987 /* Mark "expr" as a write dependening on "write".
1989 __isl_give pet_expr *pet_expr_access_set_write(__isl_take pet_expr *expr,
1990 int write)
1992 if (!expr)
1993 return pet_expr_free(expr);
1994 if (expr->type != pet_expr_access)
1995 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1996 "not an access expression", return pet_expr_free(expr));
1997 if (expr->acc.write == write)
1998 return expr;
1999 expr = pet_expr_cow(expr);
2000 if (!expr)
2001 return NULL;
2002 expr->acc.write = write;
2004 return expr;
2007 /* Mark "expr" as a kill dependening on "kill".
2009 __isl_give pet_expr *pet_expr_access_set_kill(__isl_take pet_expr *expr,
2010 int kill)
2012 if (!expr)
2013 return pet_expr_free(expr);
2014 if (expr->type != pet_expr_access)
2015 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2016 "not an access expression", return pet_expr_free(expr));
2017 if (expr->acc.kill == kill)
2018 return expr;
2019 expr = pet_expr_cow(expr);
2020 if (!expr)
2021 return NULL;
2022 expr->acc.kill = kill;
2024 return expr;
2027 /* Map the access type "type" to the corresponding location
2028 * in the access array.
2029 * In particular, the access relation of type pet_expr_access_killed is
2030 * stored in the element at position pet_expr_access_fake_killed.
2032 static enum pet_expr_access_type internalize_type(
2033 enum pet_expr_access_type type)
2035 if (type == pet_expr_access_killed)
2036 return pet_expr_access_fake_killed;
2037 return type;
2040 /* Replace the access relation of the given "type" of "expr" by "access".
2041 * If the access relation is non-empty and the type is a read or a write,
2042 * then also mark the access expression itself as a read or a write.
2044 __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr,
2045 enum pet_expr_access_type type, __isl_take isl_union_map *access)
2047 int empty;
2049 expr = pet_expr_cow(expr);
2050 if (!expr || !access)
2051 goto error;
2052 if (expr->type != pet_expr_access)
2053 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2054 "not an access expression", goto error);
2055 type = internalize_type(type);
2056 isl_union_map_free(expr->acc.access[type]);
2057 expr->acc.access[type] = access;
2059 if (expr->acc.kill)
2060 return expr;
2062 empty = isl_union_map_is_empty(access);
2063 if (empty < 0)
2064 return pet_expr_free(expr);
2065 if (empty)
2066 return expr;
2068 if (type == pet_expr_access_may_read)
2069 expr = pet_expr_access_set_read(expr, 1);
2070 else
2071 expr = pet_expr_access_set_write(expr, 1);
2073 return expr;
2074 error:
2075 isl_union_map_free(access);
2076 pet_expr_free(expr);
2077 return NULL;
2080 /* Replace the index expression of "expr" by "index" and
2081 * set the array depth accordingly.
2083 __isl_give pet_expr *pet_expr_access_set_index(__isl_take pet_expr *expr,
2084 __isl_take isl_multi_pw_aff *index)
2086 expr = pet_expr_cow(expr);
2087 if (!expr || !index)
2088 goto error;
2089 if (expr->type != pet_expr_access)
2090 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2091 "not an access expression", goto error);
2092 isl_multi_pw_aff_free(expr->acc.index);
2093 expr->acc.index = index;
2094 expr->acc.depth = isl_multi_pw_aff_dim(index, isl_dim_out);
2096 return expr;
2097 error:
2098 isl_multi_pw_aff_free(index);
2099 pet_expr_free(expr);
2100 return NULL;
2103 /* Return the reference identifier of access expression "expr".
2105 __isl_give isl_id *pet_expr_access_get_ref_id(__isl_keep pet_expr *expr)
2107 if (!expr)
2108 return NULL;
2109 if (expr->type != pet_expr_access)
2110 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2111 "not an access expression", return NULL);
2113 return isl_id_copy(expr->acc.ref_id);
2116 /* Replace the reference identifier of access expression "expr" by "ref_id".
2118 __isl_give pet_expr *pet_expr_access_set_ref_id(__isl_take pet_expr *expr,
2119 __isl_take isl_id *ref_id)
2121 expr = pet_expr_cow(expr);
2122 if (!expr || !ref_id)
2123 goto error;
2124 if (expr->type != pet_expr_access)
2125 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2126 "not an access expression", goto error);
2127 isl_id_free(expr->acc.ref_id);
2128 expr->acc.ref_id = ref_id;
2130 return expr;
2131 error:
2132 isl_id_free(ref_id);
2133 pet_expr_free(expr);
2134 return NULL;
2137 /* Tag the access relation "access" with "id".
2138 * That is, insert the id as the range of a wrapped relation
2139 * in the domain of "access".
2141 * If "access" is of the form
2143 * D[i] -> A[a]
2145 * then the result is of the form
2147 * [D[i] -> id[]] -> A[a]
2149 __isl_give isl_union_map *pet_expr_tag_access(__isl_keep pet_expr *expr,
2150 __isl_take isl_union_map *access)
2152 isl_space *space;
2153 isl_multi_aff *add_tag;
2154 isl_id *id;
2156 if (expr->type != pet_expr_access)
2157 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2158 "not an access expression",
2159 return isl_union_map_free(access));
2161 id = isl_id_copy(expr->acc.ref_id);
2162 space = pet_expr_access_get_domain_space(expr);
2163 space = isl_space_from_domain(space);
2164 space = isl_space_set_tuple_id(space, isl_dim_out, id);
2165 add_tag = isl_multi_aff_domain_map(space);
2166 access = isl_union_map_preimage_domain_multi_aff(access, add_tag);
2168 return access;
2171 /* Return the access relation of the given "type" associated to "expr"
2172 * that maps pairs of domain iterations and argument values
2173 * to the corresponding accessed data elements.
2175 * If the requested access relation is explicitly available,
2176 * then return a copy. Otherwise, check if it is irrelevant for
2177 * the access expression and return an empty relation if this is the case.
2178 * Otherwise, introduce the requested access relation in "expr" and
2179 * return a copy.
2181 __isl_give isl_union_map *pet_expr_access_get_dependent_access(
2182 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2184 isl_union_map *access;
2185 int empty;
2187 if (!expr)
2188 return NULL;
2189 if (expr->type != pet_expr_access)
2190 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2191 "not an access expression", return NULL);
2193 type = internalize_type(type);
2194 if (expr->acc.access[type])
2195 return isl_union_map_copy(expr->acc.access[type]);
2197 if (type == pet_expr_access_may_read)
2198 empty = !expr->acc.read;
2199 else
2200 empty = !expr->acc.write;
2202 if (!empty) {
2203 expr = pet_expr_copy(expr);
2204 expr = introduce_access_relations(expr);
2205 if (!expr)
2206 return NULL;
2207 access = isl_union_map_copy(expr->acc.access[type]);
2208 pet_expr_free(expr);
2210 return access;
2213 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr));
2216 /* Return the may read access relation associated to "expr"
2217 * that maps pairs of domain iterations and argument values
2218 * to the corresponding accessed data elements.
2220 __isl_give isl_union_map *pet_expr_access_get_dependent_may_read(
2221 __isl_keep pet_expr *expr)
2223 return pet_expr_access_get_dependent_access(expr,
2224 pet_expr_access_may_read);
2227 /* Return the may write access relation associated to "expr"
2228 * that maps pairs of domain iterations and argument values
2229 * to the corresponding accessed data elements.
2231 __isl_give isl_union_map *pet_expr_access_get_dependent_may_write(
2232 __isl_keep pet_expr *expr)
2234 return pet_expr_access_get_dependent_access(expr,
2235 pet_expr_access_may_write);
2238 /* Return the must write access relation associated to "expr"
2239 * that maps pairs of domain iterations and argument values
2240 * to the corresponding accessed data elements.
2242 __isl_give isl_union_map *pet_expr_access_get_dependent_must_write(
2243 __isl_keep pet_expr *expr)
2245 return pet_expr_access_get_dependent_access(expr,
2246 pet_expr_access_must_write);
2249 /* Return the relation of the given "type" mapping domain iterations
2250 * to the accessed data elements.
2251 * In particular, take the access relation and, in case of may_read
2252 * or may_write, project out the values of the arguments, if any.
2253 * In case of must_write, return the empty relation if there are
2254 * any arguments.
2256 __isl_give isl_union_map *pet_expr_access_get_access(__isl_keep pet_expr *expr,
2257 enum pet_expr_access_type type)
2259 isl_union_map *access;
2260 isl_space *space;
2261 isl_map *map;
2263 if (!expr)
2264 return NULL;
2265 if (expr->type != pet_expr_access)
2266 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2267 "not an access expression", return NULL);
2269 if (expr->n_arg != 0 && type == pet_expr_access_must_write) {
2270 space = pet_expr_access_get_parameter_space(expr);
2271 return isl_union_map_empty(space);
2274 access = pet_expr_access_get_dependent_access(expr, type);
2275 if (expr->n_arg == 0)
2276 return access;
2278 space = isl_multi_pw_aff_get_space(expr->acc.index);
2279 space = isl_space_domain(space);
2280 map = isl_map_universe(isl_space_unwrap(space));
2281 map = isl_map_domain_map(map);
2282 access = isl_union_map_apply_domain(access,
2283 isl_union_map_from_map(map));
2285 return access;
2288 /* Return the relation mapping domain iterations to all possibly
2289 * read data elements.
2291 __isl_give isl_union_map *pet_expr_access_get_may_read(
2292 __isl_keep pet_expr *expr)
2294 return pet_expr_access_get_access(expr, pet_expr_access_may_read);
2297 /* Return the relation mapping domain iterations to all possibly
2298 * written data elements.
2300 __isl_give isl_union_map *pet_expr_access_get_may_write(
2301 __isl_keep pet_expr *expr)
2303 return pet_expr_access_get_access(expr, pet_expr_access_may_write);
2306 /* Return a relation mapping domain iterations to definitely
2307 * written data elements, assuming the statement containing
2308 * the expression is executed.
2310 __isl_give isl_union_map *pet_expr_access_get_must_write(
2311 __isl_keep pet_expr *expr)
2313 return pet_expr_access_get_access(expr, pet_expr_access_must_write);
2316 /* Return the relation of the given "type" mapping domain iterations to
2317 * accessed data elements, with its domain tagged with the reference
2318 * identifier.
2320 static __isl_give isl_union_map *pet_expr_access_get_tagged_access(
2321 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2323 isl_union_map *access;
2325 if (!expr)
2326 return NULL;
2328 access = pet_expr_access_get_access(expr, type);
2329 access = pet_expr_tag_access(expr, access);
2331 return access;
2334 /* Return the relation mapping domain iterations to all possibly
2335 * read data elements, with its domain tagged with the reference
2336 * identifier.
2338 __isl_give isl_union_map *pet_expr_access_get_tagged_may_read(
2339 __isl_keep pet_expr *expr)
2341 return pet_expr_access_get_tagged_access(expr,
2342 pet_expr_access_may_read);
2345 /* Return the relation mapping domain iterations to all possibly
2346 * written data elements, with its domain tagged with the reference
2347 * identifier.
2349 __isl_give isl_union_map *pet_expr_access_get_tagged_may_write(
2350 __isl_keep pet_expr *expr)
2352 return pet_expr_access_get_tagged_access(expr,
2353 pet_expr_access_may_write);
2356 /* Return the operation type of operation expression "expr".
2358 enum pet_op_type pet_expr_op_get_type(__isl_keep pet_expr *expr)
2360 if (!expr)
2361 return pet_op_last;
2362 if (expr->type != pet_expr_op)
2363 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2364 "not an operation expression", return pet_op_last);
2366 return expr->op;
2369 /* Replace the operation type of operation expression "expr" by "type".
2371 __isl_give pet_expr *pet_expr_op_set_type(__isl_take pet_expr *expr,
2372 enum pet_op_type type)
2374 if (!expr)
2375 return pet_expr_free(expr);
2376 if (expr->type != pet_expr_op)
2377 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2378 "not an operation expression",
2379 return pet_expr_free(expr));
2380 if (expr->op == type)
2381 return expr;
2382 expr = pet_expr_cow(expr);
2383 if (!expr)
2384 return NULL;
2385 expr->op = type;
2387 return expr;
2390 /* Return the name of the function called by "expr".
2392 __isl_keep const char *pet_expr_call_get_name(__isl_keep pet_expr *expr)
2394 if (!expr)
2395 return NULL;
2396 if (expr->type != pet_expr_call)
2397 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2398 "not a call expression", return NULL);
2399 return expr->c.name;
2402 /* Replace the name of the function called by "expr" by "name".
2404 __isl_give pet_expr *pet_expr_call_set_name(__isl_take pet_expr *expr,
2405 __isl_keep const char *name)
2407 expr = pet_expr_cow(expr);
2408 if (!expr || !name)
2409 return pet_expr_free(expr);
2410 if (expr->type != pet_expr_call)
2411 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2412 "not a call expression", return pet_expr_free(expr));
2413 free(expr->c.name);
2414 expr->c.name = strdup(name);
2415 if (!expr->c.name)
2416 return pet_expr_free(expr);
2417 return expr;
2420 /* Does the call expression "expr" have an associated function summary?
2422 int pet_expr_call_has_summary(__isl_keep pet_expr *expr)
2424 if (!expr)
2425 return -1;
2426 if (expr->type != pet_expr_call)
2427 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2428 "not a call expression", return -1);
2430 return expr->c.summary != NULL;
2433 /* Return a copy of the function summary associated to
2434 * the call expression "expr".
2436 __isl_give pet_function_summary *pet_expr_call_get_summary(
2437 __isl_keep pet_expr *expr)
2439 if (!expr)
2440 return NULL;
2441 if (expr->type != pet_expr_call)
2442 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2443 "not a call expression", return NULL);
2445 return pet_function_summary_copy(expr->c.summary);
2448 /* Replace the function summary associated to the call expression "expr"
2449 * by "summary".
2451 __isl_give pet_expr *pet_expr_call_set_summary(__isl_take pet_expr *expr,
2452 __isl_take pet_function_summary *summary)
2454 expr = pet_expr_cow(expr);
2455 if (!expr || !summary)
2456 goto error;
2457 if (expr->type != pet_expr_call)
2458 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2459 "not a call expression", goto error);
2460 pet_function_summary_free(expr->c.summary);
2461 expr->c.summary = summary;
2462 return expr;
2463 error:
2464 pet_function_summary_free(summary);
2465 return pet_expr_free(expr);
2468 /* Replace the type of the cast performed by "expr" by "name".
2470 __isl_give pet_expr *pet_expr_cast_set_type_name(__isl_take pet_expr *expr,
2471 __isl_keep const char *name)
2473 expr = pet_expr_cow(expr);
2474 if (!expr || !name)
2475 return pet_expr_free(expr);
2476 if (expr->type != pet_expr_cast)
2477 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2478 "not a cast expression", return pet_expr_free(expr));
2479 free(expr->type_name);
2480 expr->type_name = strdup(name);
2481 if (!expr->type_name)
2482 return pet_expr_free(expr);
2483 return expr;
2486 /* Return the value of the integer represented by "expr".
2488 __isl_give isl_val *pet_expr_int_get_val(__isl_keep pet_expr *expr)
2490 if (!expr)
2491 return NULL;
2492 if (expr->type != pet_expr_int)
2493 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2494 "not an int expression", return NULL);
2496 return isl_val_copy(expr->i);
2499 /* Replace the value of the integer represented by "expr" by "v".
2501 __isl_give pet_expr *pet_expr_int_set_val(__isl_take pet_expr *expr,
2502 __isl_take isl_val *v)
2504 expr = pet_expr_cow(expr);
2505 if (!expr || !v)
2506 goto error;
2507 if (expr->type != pet_expr_int)
2508 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2509 "not an int expression", goto error);
2510 isl_val_free(expr->i);
2511 expr->i = v;
2513 return expr;
2514 error:
2515 isl_val_free(v);
2516 pet_expr_free(expr);
2517 return NULL;
2520 /* Replace the value and string representation of the double
2521 * represented by "expr" by "d" and "s".
2523 __isl_give pet_expr *pet_expr_double_set(__isl_take pet_expr *expr,
2524 double d, __isl_keep const char *s)
2526 expr = pet_expr_cow(expr);
2527 if (!expr || !s)
2528 return pet_expr_free(expr);
2529 if (expr->type != pet_expr_double)
2530 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2531 "not a double expression", return pet_expr_free(expr));
2532 expr->d.val = d;
2533 free(expr->d.s);
2534 expr->d.s = strdup(s);
2535 if (!expr->d.s)
2536 return pet_expr_free(expr);
2537 return expr;
2540 /* Return a string representation of the double expression "expr".
2542 __isl_give char *pet_expr_double_get_str(__isl_keep pet_expr *expr)
2544 if (!expr)
2545 return NULL;
2546 if (expr->type != pet_expr_double)
2547 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2548 "not a double expression", return NULL);
2549 return strdup(expr->d.s);
2552 /* Return a piecewise affine expression defined on the specified domain
2553 * that represents NaN.
2555 static __isl_give isl_pw_aff *non_affine(__isl_take isl_space *space)
2557 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space));
2560 /* This function is called when we come across an access that is
2561 * nested in what is supposed to be an affine expression.
2562 * "pc" is the context in which the affine expression is created.
2563 * If nesting is allowed in "pc", we return an affine expression that is
2564 * equal to a new parameter corresponding to this nested access.
2565 * Otherwise, we return NaN.
2567 * Note that we currently don't allow nested accesses themselves
2568 * to contain any nested accesses, so we check if "expr" itself
2569 * involves any nested accesses (either explicitly as arguments
2570 * or implicitly through parameters) and return NaN if it does.
2572 * The new parameter is resolved in resolve_nested.
2574 static __isl_give isl_pw_aff *nested_access(__isl_keep pet_expr *expr,
2575 __isl_keep pet_context *pc)
2577 isl_ctx *ctx;
2578 isl_id *id;
2579 isl_space *space;
2580 isl_local_space *ls;
2581 isl_aff *aff;
2582 int nested;
2584 if (!expr || !pc)
2585 return NULL;
2586 if (!pet_context_allow_nesting(pc))
2587 return non_affine(pet_context_get_space(pc));
2589 if (pet_expr_get_type(expr) != pet_expr_access)
2590 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2591 "not an access expression", return NULL);
2593 if (expr->n_arg > 0)
2594 return non_affine(pet_context_get_space(pc));
2596 space = pet_expr_access_get_parameter_space(expr);
2597 nested = pet_nested_any_in_space(space);
2598 isl_space_free(space);
2599 if (nested)
2600 return non_affine(pet_context_get_space(pc));
2602 ctx = pet_expr_get_ctx(expr);
2603 id = pet_nested_pet_expr(pet_expr_copy(expr));
2604 space = pet_context_get_space(pc);
2605 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2607 space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
2608 ls = isl_local_space_from_space(space);
2609 aff = isl_aff_var_on_domain(ls, isl_dim_param, 0);
2611 return isl_pw_aff_from_aff(aff);
2614 /* Extract an affine expression from the access pet_expr "expr".
2615 * "pc" is the context in which the affine expression is created.
2617 * If "expr" is actually an affine expression rather than
2618 * a real access, then we return that expression.
2619 * Otherwise, we require that "expr" is of an integral type.
2620 * If not, we return NaN.
2622 * If the variable has been assigned a known affine expression,
2623 * then we return that expression.
2625 * Otherwise, we return an expression that is equal to a parameter
2626 * representing "expr" (if "allow_nested" is set).
2628 static __isl_give isl_pw_aff *extract_affine_from_access(
2629 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2631 int pos;
2632 isl_id *id;
2634 if (pet_expr_is_affine(expr)) {
2635 isl_pw_aff *pa;
2636 isl_multi_pw_aff *mpa;
2638 mpa = pet_expr_access_get_index(expr);
2639 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
2640 isl_multi_pw_aff_free(mpa);
2641 return pa;
2644 if (pet_expr_get_type_size(expr) == 0)
2645 return non_affine(pet_context_get_space(pc));
2647 if (!pet_expr_is_scalar_access(expr))
2648 return nested_access(expr, pc);
2650 id = pet_expr_access_get_id(expr);
2651 if (pet_context_is_assigned(pc, id))
2652 return pet_context_get_value(pc, id);
2654 isl_id_free(id);
2655 return nested_access(expr, pc);
2658 /* Construct an affine expression from the integer constant "expr".
2659 * "pc" is the context in which the affine expression is created.
2661 static __isl_give isl_pw_aff *extract_affine_from_int(__isl_keep pet_expr *expr,
2662 __isl_keep pet_context *pc)
2664 isl_local_space *ls;
2665 isl_aff *aff;
2667 if (!expr)
2668 return NULL;
2670 ls = isl_local_space_from_space(pet_context_get_space(pc));
2671 aff = isl_aff_val_on_domain(ls, pet_expr_int_get_val(expr));
2673 return isl_pw_aff_from_aff(aff);
2676 /* Extract an affine expression from an addition or subtraction operation.
2677 * Return NaN if we are unable to extract an affine expression.
2679 * "pc" is the context in which the affine expression is created.
2681 static __isl_give isl_pw_aff *extract_affine_add_sub(__isl_keep pet_expr *expr,
2682 __isl_keep pet_context *pc)
2684 isl_pw_aff *lhs;
2685 isl_pw_aff *rhs;
2687 if (!expr)
2688 return NULL;
2689 if (expr->n_arg != 2)
2690 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2691 "expecting two arguments", return NULL);
2693 lhs = pet_expr_extract_affine(expr->args[0], pc);
2694 rhs = pet_expr_extract_affine(expr->args[1], pc);
2696 switch (pet_expr_op_get_type(expr)) {
2697 case pet_op_add:
2698 return isl_pw_aff_add(lhs, rhs);
2699 case pet_op_sub:
2700 return isl_pw_aff_sub(lhs, rhs);
2701 default:
2702 isl_pw_aff_free(lhs);
2703 isl_pw_aff_free(rhs);
2704 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2705 "not an addition or subtraction operation",
2706 return NULL);
2711 /* Extract an affine expression from an integer division or a modulo operation.
2712 * Return NaN if we are unable to extract an affine expression.
2714 * "pc" is the context in which the affine expression is created.
2716 * In particular, if "expr" is lhs/rhs, then return
2718 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2720 * If "expr" is lhs%rhs, then return
2722 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2724 * If the second argument (rhs) is not a (positive) integer constant,
2725 * then we fail to extract an affine expression.
2727 * We simplify the result in the context of the domain of "pc" in case
2728 * this domain implies that lhs >= 0 (or < 0).
2730 static __isl_give isl_pw_aff *extract_affine_div_mod(__isl_keep pet_expr *expr,
2731 __isl_keep pet_context *pc)
2733 int is_cst;
2734 isl_pw_aff *lhs;
2735 isl_pw_aff *rhs;
2736 isl_pw_aff *res;
2738 if (!expr)
2739 return NULL;
2740 if (expr->n_arg != 2)
2741 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2742 "expecting two arguments", return NULL);
2744 rhs = pet_expr_extract_affine(expr->args[1], pc);
2746 is_cst = isl_pw_aff_is_cst(rhs);
2747 if (is_cst < 0 || !is_cst) {
2748 isl_pw_aff_free(rhs);
2749 return non_affine(pet_context_get_space(pc));
2752 lhs = pet_expr_extract_affine(expr->args[0], pc);
2754 switch (pet_expr_op_get_type(expr)) {
2755 case pet_op_div:
2756 res = isl_pw_aff_tdiv_q(lhs, rhs);
2757 break;
2758 case pet_op_mod:
2759 res = isl_pw_aff_tdiv_r(lhs, rhs);
2760 break;
2761 default:
2762 isl_pw_aff_free(lhs);
2763 isl_pw_aff_free(rhs);
2764 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2765 "not a div or mod operator", return NULL);
2768 return isl_pw_aff_gist(res, pet_context_get_gist_domain(pc));
2771 /* Extract an affine expression from a multiplication operation.
2772 * Return NaN if we are unable to extract an affine expression.
2773 * In particular, if neither of the arguments is a (piecewise) constant
2774 * then we return NaN.
2776 * "pc" is the context in which the affine expression is created.
2778 static __isl_give isl_pw_aff *extract_affine_mul(__isl_keep pet_expr *expr,
2779 __isl_keep pet_context *pc)
2781 int lhs_cst, rhs_cst;
2782 isl_pw_aff *lhs;
2783 isl_pw_aff *rhs;
2785 if (!expr)
2786 return NULL;
2787 if (expr->n_arg != 2)
2788 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2789 "expecting two arguments", return NULL);
2791 lhs = pet_expr_extract_affine(expr->args[0], pc);
2792 rhs = pet_expr_extract_affine(expr->args[1], pc);
2794 lhs_cst = isl_pw_aff_is_cst(lhs);
2795 rhs_cst = isl_pw_aff_is_cst(rhs);
2796 if (lhs_cst >= 0 && rhs_cst >= 0 && (lhs_cst || rhs_cst))
2797 return isl_pw_aff_mul(lhs, rhs);
2799 isl_pw_aff_free(lhs);
2800 isl_pw_aff_free(rhs);
2802 if (lhs_cst < 0 || rhs_cst < 0)
2803 return NULL;
2805 return non_affine(pet_context_get_space(pc));
2808 /* Extract an affine expression from a negation operation.
2809 * Return NaN if we are unable to extract an affine expression.
2811 * "pc" is the context in which the affine expression is created.
2813 static __isl_give isl_pw_aff *extract_affine_neg(__isl_keep pet_expr *expr,
2814 __isl_keep pet_context *pc)
2816 isl_pw_aff *res;
2818 if (!expr)
2819 return NULL;
2820 if (expr->n_arg != 1)
2821 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2822 "expecting one argument", return NULL);
2824 res = pet_expr_extract_affine(expr->args[0], pc);
2825 return isl_pw_aff_neg(res);
2828 /* Extract an affine expression from a conditional operation.
2829 * Return NaN if we are unable to extract an affine expression.
2831 * "pc" is the context in which the affine expression is created.
2833 static __isl_give isl_pw_aff *extract_affine_cond(__isl_keep pet_expr *expr,
2834 __isl_keep pet_context *pc)
2836 isl_pw_aff *cond, *lhs, *rhs;
2838 if (!expr)
2839 return NULL;
2840 if (expr->n_arg != 3)
2841 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2842 "expecting three arguments", return NULL);
2844 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
2845 lhs = pet_expr_extract_affine(expr->args[1], pc);
2846 rhs = pet_expr_extract_affine(expr->args[2], pc);
2848 return isl_pw_aff_cond(cond, lhs, rhs);
2851 /* Compute
2853 * pwaff mod 2^width
2855 static __isl_give isl_pw_aff *wrap(__isl_take isl_pw_aff *pwaff, unsigned width)
2857 isl_ctx *ctx;
2858 isl_val *mod;
2860 ctx = isl_pw_aff_get_ctx(pwaff);
2861 mod = isl_val_int_from_ui(ctx, width);
2862 mod = isl_val_2exp(mod);
2864 pwaff = isl_pw_aff_mod_val(pwaff, mod);
2866 return pwaff;
2869 /* Limit the domain of "pwaff" to those elements where the function
2870 * value satisfies
2872 * 2^{width-1} <= pwaff < 2^{width-1}
2874 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
2875 unsigned width)
2877 isl_ctx *ctx;
2878 isl_val *v;
2879 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
2880 isl_local_space *ls = isl_local_space_from_space(space);
2881 isl_aff *bound;
2882 isl_set *dom;
2883 isl_pw_aff *b;
2885 ctx = isl_pw_aff_get_ctx(pwaff);
2886 v = isl_val_int_from_ui(ctx, width - 1);
2887 v = isl_val_2exp(v);
2889 bound = isl_aff_zero_on_domain(ls);
2890 bound = isl_aff_add_constant_val(bound, v);
2891 b = isl_pw_aff_from_aff(bound);
2893 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
2894 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2896 b = isl_pw_aff_neg(b);
2897 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
2898 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2900 return pwaff;
2903 /* Handle potential overflows on signed computations.
2905 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2906 * then we adjust the domain of "pa" to avoid overflows.
2908 static __isl_give isl_pw_aff *signed_overflow(__isl_take isl_pw_aff *pa,
2909 unsigned width)
2911 isl_ctx *ctx;
2912 struct pet_options *options;
2914 if (!pa)
2915 return NULL;
2917 ctx = isl_pw_aff_get_ctx(pa);
2918 options = isl_ctx_peek_pet_options(ctx);
2919 if (!options || options->signed_overflow == PET_OVERFLOW_AVOID)
2920 pa = avoid_overflow(pa, width);
2922 return pa;
2925 /* Extract an affine expression from some an operation.
2926 * Return NaN if we are unable to extract an affine expression.
2927 * If the result of a binary (non boolean) operation is unsigned,
2928 * then we wrap it based on the size of the type. If the result is signed,
2929 * then we ensure that no overflow occurs.
2931 * "pc" is the context in which the affine expression is created.
2933 static __isl_give isl_pw_aff *extract_affine_from_op(__isl_keep pet_expr *expr,
2934 __isl_keep pet_context *pc)
2936 isl_pw_aff *res;
2937 int type_size;
2939 switch (pet_expr_op_get_type(expr)) {
2940 case pet_op_add:
2941 case pet_op_sub:
2942 res = extract_affine_add_sub(expr, pc);
2943 break;
2944 case pet_op_div:
2945 case pet_op_mod:
2946 res = extract_affine_div_mod(expr, pc);
2947 break;
2948 case pet_op_mul:
2949 res = extract_affine_mul(expr, pc);
2950 break;
2951 case pet_op_minus:
2952 return extract_affine_neg(expr, pc);
2953 case pet_op_cond:
2954 return extract_affine_cond(expr, pc);
2955 case pet_op_eq:
2956 case pet_op_ne:
2957 case pet_op_le:
2958 case pet_op_ge:
2959 case pet_op_lt:
2960 case pet_op_gt:
2961 case pet_op_land:
2962 case pet_op_lor:
2963 case pet_op_lnot:
2964 return pet_expr_extract_affine_condition(expr, pc);
2965 default:
2966 return non_affine(pet_context_get_space(pc));
2969 if (!res)
2970 return NULL;
2971 if (isl_pw_aff_involves_nan(res)) {
2972 isl_space *space = isl_pw_aff_get_domain_space(res);
2973 isl_pw_aff_free(res);
2974 return non_affine(space);
2977 type_size = pet_expr_get_type_size(expr);
2978 if (type_size > 0)
2979 res = wrap(res, type_size);
2980 else
2981 res = signed_overflow(res, -type_size);
2983 return res;
2986 /* Extract an affine expression from some special function calls.
2987 * Return NaN if we are unable to extract an affine expression.
2988 * In particular, we handle "min", "max", "ceild", "floord",
2989 * "intMod", "intFloor" and "intCeil".
2990 * In case of the latter five, the second argument needs to be
2991 * a (positive) integer constant.
2993 * "pc" is the context in which the affine expression is created.
2995 static __isl_give isl_pw_aff *extract_affine_from_call(
2996 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2998 isl_pw_aff *aff1, *aff2;
2999 int n;
3000 const char *name;
3002 n = pet_expr_get_n_arg(expr);
3003 name = pet_expr_call_get_name(expr);
3004 if (!(n == 2 && !strcmp(name, "min")) &&
3005 !(n == 2 && !strcmp(name, "max")) &&
3006 !(n == 2 && !strcmp(name, "intMod")) &&
3007 !(n == 2 && !strcmp(name, "intFloor")) &&
3008 !(n == 2 && !strcmp(name, "intCeil")) &&
3009 !(n == 2 && !strcmp(name, "floord")) &&
3010 !(n == 2 && !strcmp(name, "ceild")))
3011 return non_affine(pet_context_get_space(pc));
3013 if (!strcmp(name, "min") || !strcmp(name, "max")) {
3014 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3015 aff2 = pet_expr_extract_affine(expr->args[1], pc);
3017 if (!strcmp(name, "min"))
3018 aff1 = isl_pw_aff_min(aff1, aff2);
3019 else
3020 aff1 = isl_pw_aff_max(aff1, aff2);
3021 } else if (!strcmp(name, "intMod")) {
3022 isl_val *v;
3024 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3025 return non_affine(pet_context_get_space(pc));
3026 v = pet_expr_int_get_val(expr->args[1]);
3027 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3028 aff1 = isl_pw_aff_mod_val(aff1, v);
3029 } else {
3030 isl_val *v;
3032 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3033 return non_affine(pet_context_get_space(pc));
3034 v = pet_expr_int_get_val(expr->args[1]);
3035 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3036 aff1 = isl_pw_aff_scale_down_val(aff1, v);
3037 if (!strcmp(name, "floord") || !strcmp(name, "intFloor"))
3038 aff1 = isl_pw_aff_floor(aff1);
3039 else
3040 aff1 = isl_pw_aff_ceil(aff1);
3043 return aff1;
3046 /* Extract an affine expression from "expr", if possible.
3047 * Otherwise return NaN.
3049 * "pc" is the context in which the affine expression is created.
3051 __isl_give isl_pw_aff *pet_expr_extract_affine(__isl_keep pet_expr *expr,
3052 __isl_keep pet_context *pc)
3054 if (!expr)
3055 return NULL;
3057 switch (pet_expr_get_type(expr)) {
3058 case pet_expr_access:
3059 return extract_affine_from_access(expr, pc);
3060 case pet_expr_int:
3061 return extract_affine_from_int(expr, pc);
3062 case pet_expr_op:
3063 return extract_affine_from_op(expr, pc);
3064 case pet_expr_call:
3065 return extract_affine_from_call(expr, pc);
3066 case pet_expr_cast:
3067 case pet_expr_double:
3068 case pet_expr_error:
3069 return non_affine(pet_context_get_space(pc));
3073 /* Extract an affine expressions representing the comparison "LHS op RHS"
3074 * Return NaN if we are unable to extract such an affine expression.
3076 * "pc" is the context in which the affine expression is created.
3078 * If the comparison is of the form
3080 * a <= min(b,c)
3082 * then the expression is constructed as the conjunction of
3083 * the comparisons
3085 * a <= b and a <= c
3087 * A similar optimization is performed for max(a,b) <= c.
3088 * We do this because that will lead to simpler representations
3089 * of the expression.
3090 * If isl is ever enhanced to explicitly deal with min and max expressions,
3091 * this optimization can be removed.
3093 __isl_give isl_pw_aff *pet_expr_extract_comparison(enum pet_op_type op,
3094 __isl_keep pet_expr *lhs, __isl_keep pet_expr *rhs,
3095 __isl_keep pet_context *pc)
3097 isl_pw_aff *lhs_pa, *rhs_pa;
3099 if (op == pet_op_gt)
3100 return pet_expr_extract_comparison(pet_op_lt, rhs, lhs, pc);
3101 if (op == pet_op_ge)
3102 return pet_expr_extract_comparison(pet_op_le, rhs, lhs, pc);
3104 if (op == pet_op_lt || op == pet_op_le) {
3105 if (pet_expr_is_min(rhs)) {
3106 lhs_pa = pet_expr_extract_comparison(op, lhs,
3107 rhs->args[0], pc);
3108 rhs_pa = pet_expr_extract_comparison(op, lhs,
3109 rhs->args[1], pc);
3110 return pet_and(lhs_pa, rhs_pa);
3112 if (pet_expr_is_max(lhs)) {
3113 lhs_pa = pet_expr_extract_comparison(op, lhs->args[0],
3114 rhs, pc);
3115 rhs_pa = pet_expr_extract_comparison(op, lhs->args[1],
3116 rhs, pc);
3117 return pet_and(lhs_pa, rhs_pa);
3121 lhs_pa = pet_expr_extract_affine(lhs, pc);
3122 rhs_pa = pet_expr_extract_affine(rhs, pc);
3124 return pet_comparison(op, lhs_pa, rhs_pa);
3127 /* Extract an affine expressions from the comparison "expr".
3128 * Return NaN if we are unable to extract such an affine expression.
3130 * "pc" is the context in which the affine expression is created.
3132 static __isl_give isl_pw_aff *extract_comparison(__isl_keep pet_expr *expr,
3133 __isl_keep pet_context *pc)
3135 enum pet_op_type type;
3137 if (!expr)
3138 return NULL;
3139 if (expr->n_arg != 2)
3140 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3141 "expecting two arguments", return NULL);
3143 type = pet_expr_op_get_type(expr);
3144 return pet_expr_extract_comparison(type, expr->args[0], expr->args[1],
3145 pc);
3148 /* Extract an affine expression representing the boolean operation
3149 * expressed by "expr".
3150 * Return NaN if we are unable to extract an affine expression.
3152 * "pc" is the context in which the affine expression is created.
3154 static __isl_give isl_pw_aff *extract_boolean(__isl_keep pet_expr *expr,
3155 __isl_keep pet_context *pc)
3157 isl_pw_aff *lhs, *rhs;
3158 int n;
3160 if (!expr)
3161 return NULL;
3163 n = pet_expr_get_n_arg(expr);
3164 lhs = pet_expr_extract_affine_condition(expr->args[0], pc);
3165 if (n == 1)
3166 return pet_not(lhs);
3168 rhs = pet_expr_extract_affine_condition(expr->args[1], pc);
3169 return pet_boolean(pet_expr_op_get_type(expr), lhs, rhs);
3172 /* Extract the affine expression "expr != 0 ? 1 : 0".
3173 * Return NaN if we are unable to extract an affine expression.
3175 * "pc" is the context in which the affine expression is created.
3177 static __isl_give isl_pw_aff *extract_implicit_condition(
3178 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3180 isl_pw_aff *res;
3182 res = pet_expr_extract_affine(expr, pc);
3183 return pet_to_bool(res);
3186 /* Extract a boolean affine expression from "expr".
3187 * Return NaN if we are unable to extract an affine expression.
3189 * "pc" is the context in which the affine expression is created.
3191 * If "expr" is neither a comparison nor a boolean operation,
3192 * then we assume it is an affine expression and return the
3193 * boolean expression "expr != 0 ? 1 : 0".
3195 __isl_give isl_pw_aff *pet_expr_extract_affine_condition(
3196 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3198 if (!expr)
3199 return NULL;
3201 if (pet_expr_is_comparison(expr))
3202 return extract_comparison(expr, pc);
3203 if (pet_expr_is_boolean(expr))
3204 return extract_boolean(expr, pc);
3206 return extract_implicit_condition(expr, pc);
3209 /* Check if "expr" is an assume expression and if its single argument
3210 * can be converted to an affine expression in the context of "pc".
3211 * If so, replace the argument by the affine expression.
3213 __isl_give pet_expr *pet_expr_resolve_assume(__isl_take pet_expr *expr,
3214 __isl_keep pet_context *pc)
3216 isl_pw_aff *cond;
3217 isl_multi_pw_aff *index;
3219 if (!expr)
3220 return NULL;
3221 if (!pet_expr_is_assume(expr))
3222 return expr;
3223 if (expr->n_arg != 1)
3224 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3225 "expecting one argument", return pet_expr_free(expr));
3227 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
3228 if (!cond)
3229 return pet_expr_free(expr);
3230 if (isl_pw_aff_involves_nan(cond)) {
3231 isl_pw_aff_free(cond);
3232 return expr;
3235 index = isl_multi_pw_aff_from_pw_aff(cond);
3236 expr = pet_expr_set_arg(expr, 0, pet_expr_from_index(index));
3238 return expr;
3241 /* Return the number of bits needed to represent the type of "expr".
3242 * See the description of the type_size field of pet_expr.
3244 int pet_expr_get_type_size(__isl_keep pet_expr *expr)
3246 return expr ? expr->type_size : 0;
3249 /* Replace the number of bits needed to represent the type of "expr"
3250 * by "type_size".
3251 * See the description of the type_size field of pet_expr.
3253 __isl_give pet_expr *pet_expr_set_type_size(__isl_take pet_expr *expr,
3254 int type_size)
3256 expr = pet_expr_cow(expr);
3257 if (!expr)
3258 return NULL;
3260 expr->type_size = type_size;
3262 return expr;
3265 /* Extend an access expression "expr" with an additional index "index".
3266 * In particular, add "index" as an extra argument to "expr" and
3267 * adjust the index expression of "expr" to refer to this extra argument.
3268 * The caller is responsible for calling pet_expr_access_set_depth
3269 * to update the corresponding access relation.
3271 * Note that we only collect the individual index expressions as
3272 * arguments of "expr" here.
3273 * An attempt to integrate them into the index expression of "expr"
3274 * is performed in pet_expr_access_plug_in_args.
3276 __isl_give pet_expr *pet_expr_access_subscript(__isl_take pet_expr *expr,
3277 __isl_take pet_expr *index)
3279 int n;
3280 isl_space *space;
3281 isl_local_space *ls;
3282 isl_pw_aff *pa;
3284 expr = pet_expr_cow(expr);
3285 if (!expr || !index)
3286 goto error;
3287 if (expr->type != pet_expr_access)
3288 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3289 "not an access pet_expr", goto error);
3291 n = pet_expr_get_n_arg(expr);
3292 expr = pet_expr_insert_arg(expr, n, index);
3293 if (!expr)
3294 return NULL;
3296 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3297 ls = isl_local_space_from_space(space);
3298 pa = isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, isl_dim_set, n));
3299 expr->acc.index = pet_array_subscript(expr->acc.index, pa);
3300 if (!expr->acc.index)
3301 return pet_expr_free(expr);
3303 return expr;
3304 error:
3305 pet_expr_free(expr);
3306 pet_expr_free(index);
3307 return NULL;
3310 /* Extend an access expression "expr" with an additional member acces to "id".
3311 * In particular, extend the index expression of "expr" to include
3312 * the additional member access.
3313 * The caller is responsible for calling pet_expr_access_set_depth
3314 * to update the corresponding access relation.
3316 __isl_give pet_expr *pet_expr_access_member(__isl_take pet_expr *expr,
3317 __isl_take isl_id *id)
3319 isl_space *space;
3320 isl_multi_pw_aff *field_access;
3322 expr = pet_expr_cow(expr);
3323 if (!expr || !id)
3324 goto error;
3325 if (expr->type != pet_expr_access)
3326 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3327 "not an access pet_expr", goto error);
3329 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3330 space = isl_space_from_domain(space);
3331 space = isl_space_set_tuple_id(space, isl_dim_out, id);
3332 field_access = isl_multi_pw_aff_zero(space);
3333 expr->acc.index = pet_array_member(expr->acc.index, field_access);
3334 if (!expr->acc.index)
3335 return pet_expr_free(expr);
3337 return expr;
3338 error:
3339 pet_expr_free(expr);
3340 isl_id_free(id);
3341 return NULL;
3344 void pet_expr_dump_with_indent(__isl_keep pet_expr *expr, int indent)
3346 int i;
3348 if (!expr)
3349 return;
3351 fprintf(stderr, "%*s", indent, "");
3353 switch (expr->type) {
3354 case pet_expr_double:
3355 fprintf(stderr, "%s\n", expr->d.s);
3356 break;
3357 case pet_expr_int:
3358 isl_val_dump(expr->i);
3359 break;
3360 case pet_expr_access:
3361 if (expr->acc.ref_id) {
3362 isl_id_dump(expr->acc.ref_id);
3363 fprintf(stderr, "%*s", indent, "");
3365 isl_multi_pw_aff_dump(expr->acc.index);
3366 fprintf(stderr, "%*sdepth: %d\n", indent + 2,
3367 "", expr->acc.depth);
3368 if (expr->acc.kill) {
3369 fprintf(stderr, "%*skill: 1\n", indent + 2, "");
3370 } else {
3371 fprintf(stderr, "%*sread: %d\n", indent + 2,
3372 "", expr->acc.read);
3373 fprintf(stderr, "%*swrite: %d\n", indent + 2,
3374 "", expr->acc.write);
3376 if (expr->acc.access[pet_expr_access_may_read]) {
3377 fprintf(stderr, "%*smay_read: ", indent + 2, "");
3378 isl_union_map_dump(
3379 expr->acc.access[pet_expr_access_may_read]);
3381 if (expr->acc.access[pet_expr_access_may_write]) {
3382 fprintf(stderr, "%*smay_write: ", indent + 2, "");
3383 isl_union_map_dump(
3384 expr->acc.access[pet_expr_access_may_write]);
3386 if (expr->acc.access[pet_expr_access_must_write]) {
3387 fprintf(stderr, "%*smust_write: ", indent + 2, "");
3388 isl_union_map_dump(
3389 expr->acc.access[pet_expr_access_must_write]);
3391 for (i = 0; i < expr->n_arg; ++i)
3392 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3393 break;
3394 case pet_expr_op:
3395 fprintf(stderr, "%s\n", op_str[expr->op]);
3396 for (i = 0; i < expr->n_arg; ++i)
3397 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3398 break;
3399 case pet_expr_call:
3400 fprintf(stderr, "%s/%d\n", expr->c.name, expr->n_arg);
3401 for (i = 0; i < expr->n_arg; ++i)
3402 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3403 if (expr->c.summary) {
3404 fprintf(stderr, "%*s", indent, "");
3405 fprintf(stderr, "summary:\n");
3406 pet_function_summary_dump_with_indent(expr->c.summary,
3407 indent + 2);
3409 break;
3410 case pet_expr_cast:
3411 fprintf(stderr, "(%s)\n", expr->type_name);
3412 for (i = 0; i < expr->n_arg; ++i)
3413 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3414 break;
3415 case pet_expr_error:
3416 fprintf(stderr, "ERROR\n");
3417 break;
3421 void pet_expr_dump(__isl_keep pet_expr *expr)
3423 pet_expr_dump_with_indent(expr, 0);