scop_plus.cc: fix typo in comment
[pet.git] / expr.c
blob5f88e0451990abbb5a523ce4a3457184d76b20a0
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 <isl/union_set.h>
39 #include "aff.h"
40 #include "array.h"
41 #include "expr.h"
42 #include "expr_arg.h"
43 #include "filter.h"
44 #include "nest.h"
45 #include "options.h"
46 #include "value_bounds.h"
48 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
50 static char *type_str[] = {
51 [pet_expr_access] = "access",
52 [pet_expr_call] = "call",
53 [pet_expr_cast] = "cast",
54 [pet_expr_double] = "double",
55 [pet_expr_int] = "int",
56 [pet_expr_op] = "op",
59 static char *op_str[] = {
60 [pet_op_add_assign] = "+=",
61 [pet_op_sub_assign] = "-=",
62 [pet_op_mul_assign] = "*=",
63 [pet_op_div_assign] = "/=",
64 [pet_op_assign] = "=",
65 [pet_op_add] = "+",
66 [pet_op_sub] = "-",
67 [pet_op_mul] = "*",
68 [pet_op_div] = "/",
69 [pet_op_mod] = "%",
70 [pet_op_shl] = "<<",
71 [pet_op_shr] = ">>",
72 [pet_op_eq] = "==",
73 [pet_op_ne] = "!=",
74 [pet_op_le] = "<=",
75 [pet_op_ge] = ">=",
76 [pet_op_lt] = "<",
77 [pet_op_gt] = ">",
78 [pet_op_minus] = "-",
79 [pet_op_post_inc] = "++",
80 [pet_op_post_dec] = "--",
81 [pet_op_pre_inc] = "++",
82 [pet_op_pre_dec] = "--",
83 [pet_op_address_of] = "&",
84 [pet_op_and] = "&",
85 [pet_op_xor] = "^",
86 [pet_op_or] = "|",
87 [pet_op_not] = "~",
88 [pet_op_land] = "&&",
89 [pet_op_lor] = "||",
90 [pet_op_lnot] = "!",
91 [pet_op_cond] = "?:",
92 [pet_op_assume] = "assume",
93 [pet_op_kill] = "kill"
96 const char *pet_op_str(enum pet_op_type op)
98 return op_str[op];
101 int pet_op_is_inc_dec(enum pet_op_type op)
103 return op == pet_op_post_inc || op == pet_op_post_dec ||
104 op == pet_op_pre_inc || op == pet_op_pre_dec;
107 const char *pet_type_str(enum pet_expr_type type)
109 return type_str[type];
112 enum pet_op_type pet_str_op(const char *str)
114 int i;
116 for (i = 0; i < ARRAY_SIZE(op_str); ++i)
117 if (!strcmp(op_str[i], str))
118 return i;
120 return -1;
123 enum pet_expr_type pet_str_type(const char *str)
125 int i;
127 for (i = 0; i < ARRAY_SIZE(type_str); ++i)
128 if (!strcmp(type_str[i], str))
129 return i;
131 return -1;
134 /* Construct a pet_expr of the given type.
136 __isl_give pet_expr *pet_expr_alloc(isl_ctx *ctx, enum pet_expr_type type)
138 pet_expr *expr;
140 expr = isl_calloc_type(ctx, struct pet_expr);
141 if (!expr)
142 return NULL;
144 expr->ctx = ctx;
145 isl_ctx_ref(ctx);
146 expr->type = type;
147 expr->ref = 1;
149 return expr;
152 /* Construct an access pet_expr from an index expression.
153 * By default, the access is considered to be a read access.
154 * The initial depth is set from the index expression and
155 * may still be updated by the caller before the access relation
156 * is created.
158 __isl_give pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
160 isl_ctx *ctx;
161 pet_expr *expr;
163 if (!index)
164 return NULL;
165 ctx = isl_multi_pw_aff_get_ctx(index);
166 expr = pet_expr_alloc(ctx, pet_expr_access);
167 if (!expr)
168 goto error;
170 expr->acc.read = 1;
171 expr->acc.write = 0;
173 expr = pet_expr_access_set_index(expr, index);
175 return expr;
176 error:
177 isl_multi_pw_aff_free(index);
178 return NULL;
181 /* Extend the range of "access" with "n" dimensions, retaining
182 * the tuple identifier on this range.
184 * If "access" represents a member access, then extend the range
185 * of the member.
187 static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
189 isl_id *id;
191 id = isl_map_get_tuple_id(access, isl_dim_out);
193 if (!isl_map_range_is_wrapping(access)) {
194 access = isl_map_add_dims(access, isl_dim_out, n);
195 } else {
196 isl_map *domain;
198 domain = isl_map_copy(access);
199 domain = isl_map_range_factor_domain(domain);
200 access = isl_map_range_factor_range(access);
201 access = extend_range(access, n);
202 access = isl_map_range_product(domain, access);
205 access = isl_map_set_tuple_id(access, isl_dim_out, id);
207 return access;
210 /* Does the access expression "expr" have any explicit access relation?
212 static int has_any_access_relation(__isl_keep pet_expr *expr)
214 enum pet_expr_access_type type;
216 if (!expr)
217 return -1;
219 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type)
220 if (expr->acc.access[type])
221 return 1;
223 return 0;
226 /* Are all relevant access relations explicitly available in "expr"?
228 static int has_relevant_access_relations(__isl_keep pet_expr *expr)
230 enum pet_expr_access_type type;
232 if (!expr)
233 return -1;
235 if (expr->acc.kill && !expr->acc.access[pet_expr_access_fake_killed])
236 return 0;
237 if (expr->acc.read && !expr->acc.access[pet_expr_access_may_read])
238 return 0;
239 if (expr->acc.write &&
240 (!expr->acc.access[pet_expr_access_may_write] ||
241 !expr->acc.access[pet_expr_access_must_write]))
242 return 0;
244 return 1;
247 /* Replace the depth of the access expr "expr" by "depth".
249 * To avoid inconsistencies between the depth and the access relation,
250 * we currently do not allow the depth to change once the access relation
251 * has been set or computed.
253 __isl_give pet_expr *pet_expr_access_set_depth(__isl_take pet_expr *expr,
254 int depth)
256 isl_map *access;
257 int dim;
259 if (!expr)
260 return NULL;
261 if (expr->acc.depth == depth)
262 return expr;
263 if (has_any_access_relation(expr))
264 isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
265 "depth cannot be changed after access relation "
266 "has been set or computed", return pet_expr_free(expr));
268 expr = pet_expr_cow(expr);
269 if (!expr)
270 return NULL;
271 expr->acc.depth = depth;
273 return expr;
276 /* Construct a pet_expr that kills the elements specified by
277 * the index expression "index" and the access relation "access".
279 __isl_give pet_expr *pet_expr_kill_from_access_and_index(
280 __isl_take isl_map *access, __isl_take isl_multi_pw_aff *index)
282 int depth;
283 pet_expr *expr;
285 if (!access || !index)
286 goto error;
288 expr = pet_expr_from_index(index);
289 expr = pet_expr_access_set_read(expr, 0);
290 expr = pet_expr_access_set_kill(expr, 1);
291 depth = isl_map_dim(access, isl_dim_out);
292 expr = pet_expr_access_set_depth(expr, depth);
293 expr = pet_expr_access_set_access(expr, pet_expr_access_killed,
294 isl_union_map_from_map(access));
295 return pet_expr_new_unary(0, pet_op_kill, expr);
296 error:
297 isl_map_free(access);
298 isl_multi_pw_aff_free(index);
299 return NULL;
302 /* Construct a unary pet_expr that performs "op" on "arg",
303 * where the result is represented using a type of "type_size" bits
304 * (may be zero if unknown or if the type is not an integer).
306 __isl_give pet_expr *pet_expr_new_unary(int type_size, enum pet_op_type op,
307 __isl_take pet_expr *arg)
309 isl_ctx *ctx;
310 pet_expr *expr;
312 if (!arg)
313 return NULL;
314 ctx = pet_expr_get_ctx(arg);
315 expr = pet_expr_alloc(ctx, pet_expr_op);
316 expr = pet_expr_set_n_arg(expr, 1);
317 if (!expr)
318 goto error;
320 expr->op = op;
321 expr->type_size = type_size;
322 expr->args[pet_un_arg] = arg;
324 return expr;
325 error:
326 pet_expr_free(arg);
327 return NULL;
330 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
331 * where the result is represented using a type of "type_size" bits
332 * (may be zero if unknown or if the type is not an integer).
334 __isl_give pet_expr *pet_expr_new_binary(int type_size, enum pet_op_type op,
335 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
337 isl_ctx *ctx;
338 pet_expr *expr;
340 if (!lhs || !rhs)
341 goto error;
342 ctx = pet_expr_get_ctx(lhs);
343 expr = pet_expr_alloc(ctx, pet_expr_op);
344 expr = pet_expr_set_n_arg(expr, 2);
345 if (!expr)
346 goto error;
348 expr->op = op;
349 expr->type_size = type_size;
350 expr->args[pet_bin_lhs] = lhs;
351 expr->args[pet_bin_rhs] = rhs;
353 return expr;
354 error:
355 pet_expr_free(lhs);
356 pet_expr_free(rhs);
357 return NULL;
360 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
362 __isl_give pet_expr *pet_expr_new_ternary(__isl_take pet_expr *cond,
363 __isl_take pet_expr *lhs, __isl_take pet_expr *rhs)
365 isl_ctx *ctx;
366 pet_expr *expr;
368 if (!cond || !lhs || !rhs)
369 goto error;
370 ctx = pet_expr_get_ctx(cond);
371 expr = pet_expr_alloc(ctx, pet_expr_op);
372 expr = pet_expr_set_n_arg(expr, 3);
373 if (!expr)
374 goto error;
376 expr->op = pet_op_cond;
377 expr->args[pet_ter_cond] = cond;
378 expr->args[pet_ter_true] = lhs;
379 expr->args[pet_ter_false] = rhs;
381 return expr;
382 error:
383 pet_expr_free(cond);
384 pet_expr_free(lhs);
385 pet_expr_free(rhs);
386 return NULL;
389 /* Construct a call pet_expr that calls function "name" with "n_arg"
390 * arguments. The caller is responsible for filling in the arguments.
392 __isl_give pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
393 unsigned n_arg)
395 pet_expr *expr;
397 expr = pet_expr_alloc(ctx, pet_expr_call);
398 expr = pet_expr_set_n_arg(expr, n_arg);
399 if (!expr)
400 return NULL;
402 expr->c.name = strdup(name);
403 if (!expr->c.name)
404 return pet_expr_free(expr);
406 return expr;
409 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
411 __isl_give pet_expr *pet_expr_new_cast(const char *type_name,
412 __isl_take pet_expr *arg)
414 isl_ctx *ctx;
415 pet_expr *expr;
417 if (!arg)
418 return NULL;
420 ctx = pet_expr_get_ctx(arg);
421 expr = pet_expr_alloc(ctx, pet_expr_cast);
422 expr = pet_expr_set_n_arg(expr, 1);
423 if (!expr)
424 goto error;
426 expr->type_name = strdup(type_name);
427 if (!expr->type_name)
428 goto error;
430 expr->args[0] = arg;
432 return expr;
433 error:
434 pet_expr_free(arg);
435 pet_expr_free(expr);
436 return NULL;
439 /* Construct a pet_expr that represents the double "d".
441 __isl_give pet_expr *pet_expr_new_double(isl_ctx *ctx,
442 double val, const char *s)
444 pet_expr *expr;
446 expr = pet_expr_alloc(ctx, pet_expr_double);
447 if (!expr)
448 return NULL;
450 expr->d.val = val;
451 expr->d.s = strdup(s);
452 if (!expr->d.s)
453 return pet_expr_free(expr);
455 return expr;
458 /* Construct a pet_expr that represents the integer value "v".
460 __isl_give pet_expr *pet_expr_new_int(__isl_take isl_val *v)
462 isl_ctx *ctx;
463 pet_expr *expr;
465 if (!v)
466 return NULL;
468 ctx = isl_val_get_ctx(v);
469 expr = pet_expr_alloc(ctx, pet_expr_int);
470 if (!expr)
471 goto error;
473 expr->i = v;
475 return expr;
476 error:
477 isl_val_free(v);
478 return NULL;
481 /* Return an independent duplicate of "expr".
483 * In case of an access expression, make sure the depth of the duplicate is set
484 * before the access relation (if any) is set and after the index expression
485 * is set.
487 static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr)
489 int i;
490 pet_expr *dup;
491 enum pet_expr_access_type type;
493 if (!expr)
494 return NULL;
496 dup = pet_expr_alloc(expr->ctx, expr->type);
497 dup = pet_expr_set_type_size(dup, expr->type_size);
498 dup = pet_expr_set_n_arg(dup, expr->n_arg);
499 for (i = 0; i < expr->n_arg; ++i)
500 dup = pet_expr_set_arg(dup, i, pet_expr_copy(expr->args[i]));
502 switch (expr->type) {
503 case pet_expr_access:
504 if (expr->acc.ref_id)
505 dup = pet_expr_access_set_ref_id(dup,
506 isl_id_copy(expr->acc.ref_id));
507 dup = pet_expr_access_set_index(dup,
508 isl_multi_pw_aff_copy(expr->acc.index));
509 dup = pet_expr_access_set_depth(dup, expr->acc.depth);
510 for (type = pet_expr_access_begin;
511 type < pet_expr_access_end; ++type) {
512 if (!expr->acc.access[type])
513 continue;
514 dup = pet_expr_access_set_access(dup, type,
515 isl_union_map_copy(expr->acc.access[type]));
517 dup = pet_expr_access_set_read(dup, expr->acc.read);
518 dup = pet_expr_access_set_write(dup, expr->acc.write);
519 dup = pet_expr_access_set_kill(dup, expr->acc.kill);
520 break;
521 case pet_expr_call:
522 dup = pet_expr_call_set_name(dup, expr->c.name);
523 if (expr->c.summary)
524 dup = pet_expr_call_set_summary(dup,
525 pet_function_summary_copy(expr->c.summary));
526 break;
527 case pet_expr_cast:
528 dup = pet_expr_cast_set_type_name(dup, expr->type_name);
529 break;
530 case pet_expr_double:
531 dup = pet_expr_double_set(dup, expr->d.val, expr->d.s);
532 break;
533 case pet_expr_int:
534 dup = pet_expr_int_set_val(dup, isl_val_copy(expr->i));
535 break;
536 case pet_expr_op:
537 dup = pet_expr_op_set_type(dup, expr->op);
538 break;
539 case pet_expr_error:
540 dup = pet_expr_free(dup);
541 break;
544 return dup;
547 __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr)
549 if (!expr)
550 return NULL;
552 if (expr->ref == 1)
553 return expr;
554 expr->ref--;
555 return pet_expr_dup(expr);
558 __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr)
560 enum pet_expr_access_type type;
561 int i;
563 if (!expr)
564 return NULL;
565 if (--expr->ref > 0)
566 return NULL;
568 for (i = 0; i < expr->n_arg; ++i)
569 pet_expr_free(expr->args[i]);
570 free(expr->args);
572 switch (expr->type) {
573 case pet_expr_access:
574 isl_id_free(expr->acc.ref_id);
575 for (type = pet_expr_access_begin;
576 type < pet_expr_access_end; ++type)
577 isl_union_map_free(expr->acc.access[type]);
578 isl_multi_pw_aff_free(expr->acc.index);
579 break;
580 case pet_expr_call:
581 free(expr->c.name);
582 pet_function_summary_free(expr->c.summary);
583 break;
584 case pet_expr_cast:
585 free(expr->type_name);
586 break;
587 case pet_expr_double:
588 free(expr->d.s);
589 break;
590 case pet_expr_int:
591 isl_val_free(expr->i);
592 break;
593 case pet_expr_op:
594 case pet_expr_error:
595 break;
598 isl_ctx_deref(expr->ctx);
599 free(expr);
600 return NULL;
603 /* Return an additional reference to "expr".
605 __isl_give pet_expr *pet_expr_copy(__isl_keep pet_expr *expr)
607 if (!expr)
608 return NULL;
610 expr->ref++;
611 return expr;
614 /* Return the isl_ctx in which "expr" was created.
616 isl_ctx *pet_expr_get_ctx(__isl_keep pet_expr *expr)
618 return expr ? expr->ctx : NULL;
621 /* Return the type of "expr".
623 enum pet_expr_type pet_expr_get_type(__isl_keep pet_expr *expr)
625 if (!expr)
626 return pet_expr_error;
627 return expr->type;
630 /* Return the number of arguments of "expr".
632 int pet_expr_get_n_arg(__isl_keep pet_expr *expr)
634 if (!expr)
635 return -1;
637 return expr->n_arg;
640 /* Set the number of arguments of "expr" to "n".
642 * If "expr" originally had more arguments, then remove the extra arguments.
643 * If "expr" originally had fewer arguments, then create space for
644 * the extra arguments ans initialize them to NULL.
646 __isl_give pet_expr *pet_expr_set_n_arg(__isl_take pet_expr *expr, int n)
648 int i;
649 pet_expr **args;
651 if (!expr)
652 return NULL;
653 if (expr->n_arg == n)
654 return expr;
655 expr = pet_expr_cow(expr);
656 if (!expr)
657 return NULL;
659 if (n < expr->n_arg) {
660 for (i = n; i < expr->n_arg; ++i)
661 pet_expr_free(expr->args[i]);
662 expr->n_arg = n;
663 return expr;
666 args = isl_realloc_array(expr->ctx, expr->args, pet_expr *, n);
667 if (!args)
668 return pet_expr_free(expr);
669 expr->args = args;
670 for (i = expr->n_arg; i < n; ++i)
671 expr->args[i] = NULL;
672 expr->n_arg = n;
674 return expr;
677 /* Return the argument of "expr" at position "pos".
679 __isl_give pet_expr *pet_expr_get_arg(__isl_keep pet_expr *expr, int pos)
681 if (!expr)
682 return NULL;
683 if (pos < 0 || pos >= expr->n_arg)
684 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
685 "position out of bounds", return NULL);
687 return pet_expr_copy(expr->args[pos]);
690 /* Replace the argument of "expr" at position "pos" by "arg".
692 __isl_give pet_expr *pet_expr_set_arg(__isl_take pet_expr *expr, int pos,
693 __isl_take pet_expr *arg)
695 if (!expr || !arg)
696 goto error;
697 if (pos < 0 || pos >= expr->n_arg)
698 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
699 "position out of bounds", goto error);
700 if (expr->args[pos] == arg) {
701 pet_expr_free(arg);
702 return expr;
705 expr = pet_expr_cow(expr);
706 if (!expr)
707 goto error;
709 pet_expr_free(expr->args[pos]);
710 expr->args[pos] = arg;
712 return expr;
713 error:
714 pet_expr_free(expr);
715 pet_expr_free(arg);
716 return NULL;
719 /* Does "expr" perform a comparison operation?
721 int pet_expr_is_comparison(__isl_keep pet_expr *expr)
723 if (!expr)
724 return -1;
725 if (expr->type != pet_expr_op)
726 return 0;
727 switch (expr->op) {
728 case pet_op_eq:
729 case pet_op_ne:
730 case pet_op_le:
731 case pet_op_ge:
732 case pet_op_lt:
733 case pet_op_gt:
734 return 1;
735 default:
736 return 0;
740 /* Does "expr" perform a boolean operation?
742 int pet_expr_is_boolean(__isl_keep pet_expr *expr)
744 if (!expr)
745 return -1;
746 if (expr->type != pet_expr_op)
747 return 0;
748 switch (expr->op) {
749 case pet_op_land:
750 case pet_op_lor:
751 case pet_op_lnot:
752 return 1;
753 default:
754 return 0;
758 /* Is "expr" an assume statement?
760 int pet_expr_is_assume(__isl_keep pet_expr *expr)
762 if (!expr)
763 return -1;
764 if (expr->type != pet_expr_op)
765 return 0;
766 return expr->op == pet_op_assume;
769 /* Does "expr" perform a min operation?
771 int pet_expr_is_min(__isl_keep pet_expr *expr)
773 if (!expr)
774 return -1;
775 if (expr->type != pet_expr_call)
776 return 0;
777 if (expr->n_arg != 2)
778 return 0;
779 if (strcmp(expr->c.name, "min") != 0)
780 return 0;
781 return 1;
784 /* Does "expr" perform a max operation?
786 int pet_expr_is_max(__isl_keep pet_expr *expr)
788 if (!expr)
789 return -1;
790 if (expr->type != pet_expr_call)
791 return 0;
792 if (expr->n_arg != 2)
793 return 0;
794 if (strcmp(expr->c.name, "max") != 0)
795 return 0;
796 return 1;
799 /* Does "expr" represent an access to an unnamed space, i.e.,
800 * does it represent an affine expression?
802 int pet_expr_is_affine(__isl_keep pet_expr *expr)
804 int has_id;
806 if (!expr)
807 return -1;
808 if (expr->type != pet_expr_access)
809 return 0;
811 has_id = isl_multi_pw_aff_has_tuple_id(expr->acc.index, isl_dim_out);
812 if (has_id < 0)
813 return -1;
815 return !has_id;
818 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
819 * not part of any struct?
821 int pet_expr_is_scalar_access(__isl_keep pet_expr *expr)
823 if (!expr)
824 return -1;
825 if (expr->type != pet_expr_access)
826 return 0;
827 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index))
828 return 0;
830 return expr->acc.depth == 0;
833 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
834 * of parameters.
836 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1,
837 __isl_keep isl_multi_pw_aff *mpa2)
839 int equal;
841 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
842 if (equal < 0 || equal)
843 return equal;
844 mpa2 = isl_multi_pw_aff_copy(mpa2);
845 mpa2 = isl_multi_pw_aff_align_params(mpa2,
846 isl_multi_pw_aff_get_space(mpa1));
847 equal = isl_multi_pw_aff_plain_is_equal(mpa1, mpa2);
848 isl_multi_pw_aff_free(mpa2);
850 return equal;
853 /* Construct an access relation from the index expression and
854 * the array depth of the access expression "expr".
856 * If the number of indices is smaller than the depth of the array,
857 * then we assume that all elements of the remaining dimensions
858 * are accessed.
860 static __isl_give isl_union_map *construct_access_relation(
861 __isl_keep pet_expr *expr)
863 isl_map *access;
864 int dim;
865 int read, write;
867 if (!expr)
868 return NULL;
870 access = isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr));
871 if (!access)
872 return NULL;
874 dim = isl_map_dim(access, isl_dim_out);
875 if (dim > expr->acc.depth)
876 isl_die(isl_map_get_ctx(access), isl_error_internal,
877 "number of indices greater than depth",
878 access = isl_map_free(access));
880 if (dim != expr->acc.depth)
881 access = extend_range(access, expr->acc.depth - dim);
883 return isl_union_map_from_map(access);
886 /* Ensure that all relevant access relations are explicitly
887 * available in "expr".
889 * If "expr" does not already have the relevant access relations, then create
890 * them based on the index expression and the array depth.
892 * We do not cow since adding an explicit access relation
893 * does not change the meaning of the expression.
895 static __isl_give pet_expr *introduce_access_relations(
896 __isl_take pet_expr *expr)
898 enum pet_expr_access_type type;
899 isl_union_map *access;
900 int dim;
901 int kill, read, write;
903 if (!expr)
904 return NULL;
905 if (has_relevant_access_relations(expr))
906 return expr;
908 access = construct_access_relation(expr);
909 if (!access)
910 return pet_expr_free(expr);
912 kill = expr->acc.kill;
913 read = expr->acc.read;
914 write = expr->acc.write;
915 if (kill && !expr->acc.access[pet_expr_access_fake_killed])
916 expr->acc.access[pet_expr_access_fake_killed] =
917 isl_union_map_copy(access);
918 if (read && !expr->acc.access[pet_expr_access_may_read])
919 expr->acc.access[pet_expr_access_may_read] =
920 isl_union_map_copy(access);
921 if (write && !expr->acc.access[pet_expr_access_may_write])
922 expr->acc.access[pet_expr_access_may_write] =
923 isl_union_map_copy(access);
924 if (write && !expr->acc.access[pet_expr_access_must_write])
925 expr->acc.access[pet_expr_access_must_write] =
926 isl_union_map_copy(access);
928 isl_union_map_free(access);
930 if (!has_relevant_access_relations(expr))
931 return pet_expr_free(expr);
933 return expr;
936 /* Return 1 if the two pet_exprs are equivalent.
938 int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2)
940 int i;
941 enum pet_expr_access_type type;
943 if (!expr1 || !expr2)
944 return 0;
946 if (expr1->type != expr2->type)
947 return 0;
948 if (expr1->n_arg != expr2->n_arg)
949 return 0;
950 for (i = 0; i < expr1->n_arg; ++i)
951 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
952 return 0;
953 switch (expr1->type) {
954 case pet_expr_error:
955 return -1;
956 case pet_expr_double:
957 if (strcmp(expr1->d.s, expr2->d.s))
958 return 0;
959 if (expr1->d.val != expr2->d.val)
960 return 0;
961 break;
962 case pet_expr_int:
963 if (!isl_val_eq(expr1->i, expr2->i))
964 return 0;
965 break;
966 case pet_expr_access:
967 if (expr1->acc.read != expr2->acc.read)
968 return 0;
969 if (expr1->acc.write != expr2->acc.write)
970 return 0;
971 if (expr1->acc.kill != expr2->acc.kill)
972 return 0;
973 if (expr1->acc.ref_id != expr2->acc.ref_id)
974 return 0;
975 if (!expr1->acc.index || !expr2->acc.index)
976 return 0;
977 if (!multi_pw_aff_is_equal(expr1->acc.index, expr2->acc.index))
978 return 0;
979 if (expr1->acc.depth != expr2->acc.depth)
980 return 0;
981 if (has_relevant_access_relations(expr1) !=
982 has_relevant_access_relations(expr2)) {
983 int equal;
984 expr1 = pet_expr_copy(expr1);
985 expr2 = pet_expr_copy(expr2);
986 expr1 = introduce_access_relations(expr1);
987 expr2 = introduce_access_relations(expr2);
988 equal = pet_expr_is_equal(expr1, expr2);
989 pet_expr_free(expr1);
990 pet_expr_free(expr2);
991 return equal;
993 for (type = pet_expr_access_begin;
994 type < pet_expr_access_end; ++type) {
995 if (!expr1->acc.access[type] !=
996 !expr2->acc.access[type])
997 return 0;
998 if (!expr1->acc.access[type])
999 continue;
1000 if (!isl_union_map_is_equal(expr1->acc.access[type],
1001 expr2->acc.access[type]))
1002 return 0;
1004 break;
1005 case pet_expr_op:
1006 if (expr1->op != expr2->op)
1007 return 0;
1008 break;
1009 case pet_expr_call:
1010 if (strcmp(expr1->c.name, expr2->c.name))
1011 return 0;
1012 break;
1013 case pet_expr_cast:
1014 if (strcmp(expr1->type_name, expr2->type_name))
1015 return 0;
1016 break;
1019 return 1;
1022 /* Does the access expression "expr" read the accessed elements?
1024 int pet_expr_access_is_read(__isl_keep pet_expr *expr)
1026 if (!expr)
1027 return -1;
1028 if (expr->type != pet_expr_access)
1029 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1030 "not an access expression", return -1);
1032 return expr->acc.read;
1035 /* Does the access expression "expr" write to the accessed elements?
1037 int pet_expr_access_is_write(__isl_keep pet_expr *expr)
1039 if (!expr)
1040 return -1;
1041 if (expr->type != pet_expr_access)
1042 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1043 "not an access expression", return -1);
1045 return expr->acc.write;
1048 /* Return the identifier of the array accessed by "expr".
1050 * If "expr" represents a member access, then return the identifier
1051 * of the outer structure array.
1053 __isl_give isl_id *pet_expr_access_get_id(__isl_keep pet_expr *expr)
1055 if (!expr)
1056 return NULL;
1057 if (expr->type != pet_expr_access)
1058 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1059 "not an access expression", return NULL);
1061 if (isl_multi_pw_aff_range_is_wrapping(expr->acc.index)) {
1062 isl_space *space;
1063 isl_id *id;
1065 space = isl_multi_pw_aff_get_space(expr->acc.index);
1066 space = isl_space_range(space);
1067 while (space && isl_space_is_wrapping(space))
1068 space = isl_space_domain(isl_space_unwrap(space));
1069 id = isl_space_get_tuple_id(space, isl_dim_set);
1070 isl_space_free(space);
1072 return id;
1075 return isl_multi_pw_aff_get_tuple_id(expr->acc.index, isl_dim_out);
1078 /* Return the parameter space of "expr".
1080 __isl_give isl_space *pet_expr_access_get_parameter_space(
1081 __isl_keep pet_expr *expr)
1083 isl_space *space;
1085 if (!expr)
1086 return NULL;
1087 if (expr->type != pet_expr_access)
1088 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1089 "not an access expression", return NULL);
1091 space = isl_multi_pw_aff_get_space(expr->acc.index);
1092 space = isl_space_params(space);
1094 return space;
1097 /* Return the domain space of "expr", including the arguments (if any).
1099 __isl_give isl_space *pet_expr_access_get_augmented_domain_space(
1100 __isl_keep pet_expr *expr)
1102 isl_space *space;
1104 if (!expr)
1105 return NULL;
1106 if (expr->type != pet_expr_access)
1107 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1108 "not an access expression", return NULL);
1110 space = isl_multi_pw_aff_get_space(expr->acc.index);
1111 space = isl_space_domain(space);
1113 return space;
1116 /* Return the domain space of "expr", without the arguments (if any).
1118 __isl_give isl_space *pet_expr_access_get_domain_space(
1119 __isl_keep pet_expr *expr)
1121 isl_space *space;
1123 space = pet_expr_access_get_augmented_domain_space(expr);
1124 if (isl_space_is_wrapping(space))
1125 space = isl_space_domain(isl_space_unwrap(space));
1127 return space;
1130 /* Return the space of the data accessed by "expr".
1132 __isl_give isl_space *pet_expr_access_get_data_space(__isl_keep pet_expr *expr)
1134 isl_space *space;
1136 if (!expr)
1137 return NULL;
1138 if (expr->type != pet_expr_access)
1139 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1140 "not an access expression", return NULL);
1142 space = isl_multi_pw_aff_get_space(expr->acc.index);
1143 space = isl_space_range(space);
1145 return space;
1148 /* Modify all expressions of type "type" in "expr" by calling "fn" on them.
1150 static __isl_give pet_expr *pet_expr_map_expr_of_type(__isl_take pet_expr *expr,
1151 enum pet_expr_type type,
1152 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1153 void *user)
1155 int i, n;
1157 n = pet_expr_get_n_arg(expr);
1158 for (i = 0; i < n; ++i) {
1159 pet_expr *arg = pet_expr_get_arg(expr, i);
1160 arg = pet_expr_map_expr_of_type(arg, type, fn, user);
1161 expr = pet_expr_set_arg(expr, i, arg);
1164 if (!expr)
1165 return NULL;
1167 if (expr->type == type)
1168 expr = fn(expr, user);
1170 return expr;
1173 /* Modify all expressions of type pet_expr_access in "expr"
1174 * by calling "fn" on them.
1176 __isl_give pet_expr *pet_expr_map_access(__isl_take pet_expr *expr,
1177 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1178 void *user)
1180 return pet_expr_map_expr_of_type(expr, pet_expr_access, fn, user);
1183 /* Modify all expressions of type pet_expr_call in "expr"
1184 * by calling "fn" on them.
1186 __isl_give pet_expr *pet_expr_map_call(__isl_take pet_expr *expr,
1187 __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user),
1188 void *user)
1190 return pet_expr_map_expr_of_type(expr, pet_expr_call, fn, user);
1193 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1195 * Return -1 on error (where fn returning a negative value is treated as
1196 * an error).
1197 * Otherwise return 0.
1199 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr *expr,
1200 enum pet_expr_type type,
1201 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1203 int i;
1205 if (!expr)
1206 return -1;
1208 for (i = 0; i < expr->n_arg; ++i)
1209 if (pet_expr_foreach_expr_of_type(expr->args[i],
1210 type, fn, user) < 0)
1211 return -1;
1213 if (expr->type == type)
1214 return fn(expr, user);
1216 return 0;
1219 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1221 * Return -1 on error (where fn returning a negative value is treated as
1222 * an error).
1223 * Otherwise return 0.
1225 int pet_expr_foreach_access_expr(__isl_keep pet_expr *expr,
1226 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1228 return pet_expr_foreach_expr_of_type(expr, pet_expr_access, fn, user);
1231 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1233 * Return -1 on error (where fn returning a negative value is treated as
1234 * an error).
1235 * Otherwise return 0.
1237 int pet_expr_foreach_call_expr(__isl_keep pet_expr *expr,
1238 int (*fn)(__isl_keep pet_expr *expr, void *user), void *user)
1240 return pet_expr_foreach_expr_of_type(expr, pet_expr_call, fn, user);
1243 /* Internal data structure for pet_expr_writes.
1244 * "id" is the identifier that we are looking for.
1245 * "found" is set if we have found the identifier being written to.
1247 struct pet_expr_writes_data {
1248 isl_id *id;
1249 int found;
1252 /* Given an access expression, check if it writes to data->id.
1253 * If so, set data->found and abort the search.
1255 static int writes(__isl_keep pet_expr *expr, void *user)
1257 struct pet_expr_writes_data *data = user;
1258 isl_id *write_id;
1260 if (!expr->acc.write)
1261 return 0;
1262 if (pet_expr_is_affine(expr))
1263 return 0;
1265 write_id = pet_expr_access_get_id(expr);
1266 isl_id_free(write_id);
1268 if (!write_id)
1269 return -1;
1271 if (write_id != data->id)
1272 return 0;
1274 data->found = 1;
1275 return -1;
1278 /* Does expression "expr" write to "id"?
1280 int pet_expr_writes(__isl_keep pet_expr *expr, __isl_keep isl_id *id)
1282 struct pet_expr_writes_data data;
1284 data.id = id;
1285 data.found = 0;
1286 if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
1287 !data.found)
1288 return -1;
1290 return data.found;
1293 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1294 * index expression and access relations of "expr" (if any)
1295 * to dimensions of "dst_type" at "dst_pos".
1297 __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr,
1298 enum isl_dim_type dst_type, unsigned dst_pos,
1299 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1301 enum pet_expr_access_type type;
1303 expr = pet_expr_cow(expr);
1304 if (!expr)
1305 return NULL;
1306 if (expr->type != pet_expr_access)
1307 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1308 "not an access pet_expr", return pet_expr_free(expr));
1310 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1311 if (!expr->acc.access[type])
1312 continue;
1313 expr->acc.access[type] =
1314 pet_union_map_move_dims(expr->acc.access[type],
1315 dst_type, dst_pos, src_type, src_pos, n);
1316 if (!expr->acc.access[type])
1317 break;
1319 expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index,
1320 dst_type, dst_pos, src_type, src_pos, n);
1321 if (!expr->acc.index || type < pet_expr_access_end)
1322 return pet_expr_free(expr);
1324 return expr;
1327 /* Replace the index expression and access relations (if any) of "expr"
1328 * by their preimages under the function represented by "ma".
1330 __isl_give pet_expr *pet_expr_access_pullback_multi_aff(
1331 __isl_take pet_expr *expr, __isl_take isl_multi_aff *ma)
1333 enum pet_expr_access_type type;
1335 expr = pet_expr_cow(expr);
1336 if (!expr || !ma)
1337 goto error;
1338 if (expr->type != pet_expr_access)
1339 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1340 "not an access pet_expr", goto error);
1342 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1343 if (!expr->acc.access[type])
1344 continue;
1345 expr->acc.access[type] =
1346 isl_union_map_preimage_domain_multi_aff(
1347 expr->acc.access[type], isl_multi_aff_copy(ma));
1348 if (!expr->acc.access[type])
1349 break;
1351 expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index,
1352 ma);
1353 if (!expr->acc.index || type < pet_expr_access_end)
1354 return pet_expr_free(expr);
1356 return expr;
1357 error:
1358 isl_multi_aff_free(ma);
1359 pet_expr_free(expr);
1360 return NULL;
1363 /* Replace the index expression and access relations (if any) of "expr"
1364 * by their preimages under the function represented by "mpa".
1366 __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff(
1367 __isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *mpa)
1369 enum pet_expr_access_type type;
1371 expr = pet_expr_cow(expr);
1372 if (!expr || !mpa)
1373 goto error;
1374 if (expr->type != pet_expr_access)
1375 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1376 "not an access pet_expr", goto error);
1378 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1379 if (!expr->acc.access[type])
1380 continue;
1381 expr->acc.access[type] =
1382 isl_union_map_preimage_domain_multi_pw_aff(
1383 expr->acc.access[type], isl_multi_pw_aff_copy(mpa));
1384 if (!expr->acc.access[type])
1385 break;
1387 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1388 expr->acc.index, mpa);
1389 if (!expr->acc.index || type < pet_expr_access_end)
1390 return pet_expr_free(expr);
1392 return expr;
1393 error:
1394 isl_multi_pw_aff_free(mpa);
1395 pet_expr_free(expr);
1396 return NULL;
1399 /* Return the index expression of access expression "expr".
1401 __isl_give isl_multi_pw_aff *pet_expr_access_get_index(
1402 __isl_keep pet_expr *expr)
1404 if (!expr)
1405 return NULL;
1406 if (expr->type != pet_expr_access)
1407 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1408 "not an access expression", return NULL);
1410 return isl_multi_pw_aff_copy(expr->acc.index);
1413 /* Align the parameters of expr->acc.index and expr->acc.access[*] (if set).
1415 __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr)
1417 isl_space *space;
1418 enum pet_expr_access_type type;
1420 expr = pet_expr_cow(expr);
1421 if (!expr)
1422 return NULL;
1423 if (expr->type != pet_expr_access)
1424 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1425 "not an access expression", return pet_expr_free(expr));
1427 if (!has_any_access_relation(expr))
1428 return expr;
1430 space = isl_multi_pw_aff_get_space(expr->acc.index);
1431 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1432 if (!expr->acc.access[type])
1433 continue;
1434 space = isl_space_align_params(space,
1435 isl_union_map_get_space(expr->acc.access[type]));
1437 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1438 isl_space_copy(space));
1439 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1440 if (!expr->acc.access[type])
1441 continue;
1442 expr->acc.access[type] =
1443 isl_union_map_align_params(expr->acc.access[type],
1444 isl_space_copy(space));
1445 if (!expr->acc.access[type])
1446 break;
1448 isl_space_free(space);
1449 if (!expr->acc.index || type < pet_expr_access_end)
1450 return pet_expr_free(expr);
1452 return expr;
1455 /* Are "expr1" and "expr2" both array accesses such that
1456 * the access relation of "expr1" is a subset of that of "expr2"?
1457 * Only take into account the first "n_arg" arguments.
1459 * This function is tailored for use by mark_self_dependences in nest.c.
1460 * In particular, the input expressions may have more than "n_arg"
1461 * elements in their arguments arrays, while only the first "n_arg"
1462 * elements are referenced from the access relations.
1464 int pet_expr_is_sub_access(__isl_keep pet_expr *expr1,
1465 __isl_keep pet_expr *expr2, int n_arg)
1467 isl_id *id1, *id2;
1468 int i, n1, n2;
1469 int is_subset;
1471 if (!expr1 || !expr2)
1472 return 0;
1473 if (pet_expr_get_type(expr1) != pet_expr_access)
1474 return 0;
1475 if (pet_expr_get_type(expr2) != pet_expr_access)
1476 return 0;
1477 if (pet_expr_is_affine(expr1))
1478 return 0;
1479 if (pet_expr_is_affine(expr2))
1480 return 0;
1481 n1 = pet_expr_get_n_arg(expr1);
1482 if (n1 > n_arg)
1483 n1 = n_arg;
1484 n2 = pet_expr_get_n_arg(expr2);
1485 if (n2 > n_arg)
1486 n2 = n_arg;
1487 if (n1 != n2)
1488 return 0;
1489 for (i = 0; i < n1; ++i) {
1490 int equal;
1491 equal = pet_expr_is_equal(expr1->args[i], expr2->args[i]);
1492 if (equal < 0 || !equal)
1493 return equal;
1495 id1 = pet_expr_access_get_id(expr1);
1496 id2 = pet_expr_access_get_id(expr2);
1497 isl_id_free(id1);
1498 isl_id_free(id2);
1499 if (!id1 || !id2)
1500 return 0;
1501 if (id1 != id2)
1502 return 0;
1504 expr1 = pet_expr_copy(expr1);
1505 expr2 = pet_expr_copy(expr2);
1506 expr1 = introduce_access_relations(expr1);
1507 expr2 = introduce_access_relations(expr2);
1508 if (!expr1 || !expr2)
1509 goto error;
1511 is_subset = isl_union_map_is_subset(
1512 expr1->acc.access[pet_expr_access_may_read],
1513 expr2->acc.access[pet_expr_access_may_read]);
1515 pet_expr_free(expr1);
1516 pet_expr_free(expr2);
1518 return is_subset;
1519 error:
1520 pet_expr_free(expr1);
1521 pet_expr_free(expr2);
1522 return -1;
1525 /* Given a set in the iteration space "domain", extend it to live in the space
1526 * of the domain of access relations.
1528 * That, is the number of arguments "n" is 0, then simply return domain.
1529 * Otherwise, return [domain -> [a_1,...,a_n]].
1531 static __isl_give isl_set *add_arguments(__isl_take isl_set *domain, int n)
1533 isl_map *map;
1535 if (n == 0)
1536 return domain;
1538 map = isl_map_from_domain(domain);
1539 map = isl_map_add_dims(map, isl_dim_out, n);
1540 return isl_map_wrap(map);
1543 /* Add extra conditions to the domains of all access relations in "expr",
1544 * introducing access relations if they are not already present.
1546 * The conditions are not added to the index expression. Instead, they
1547 * are used to try and simplify the index expression.
1549 __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr,
1550 __isl_take isl_set *cond)
1552 int i;
1553 isl_union_set *uset;
1554 enum pet_expr_access_type type;
1556 expr = pet_expr_cow(expr);
1557 if (!expr)
1558 goto error;
1560 for (i = 0; i < expr->n_arg; ++i) {
1561 expr->args[i] = pet_expr_restrict(expr->args[i],
1562 isl_set_copy(cond));
1563 if (!expr->args[i])
1564 goto error;
1567 if (expr->type != pet_expr_access) {
1568 isl_set_free(cond);
1569 return expr;
1572 expr = introduce_access_relations(expr);
1573 if (!expr)
1574 goto error;
1576 cond = add_arguments(cond, expr->n_arg);
1577 uset = isl_union_set_from_set(isl_set_copy(cond));
1578 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1579 if (!expr->acc.access[type])
1580 continue;
1581 expr->acc.access[type] =
1582 isl_union_map_intersect_domain(expr->acc.access[type],
1583 isl_union_set_copy(uset));
1584 if (!expr->acc.access[type])
1585 break;
1587 isl_union_set_free(uset);
1588 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, cond);
1589 if (type < pet_expr_access_end || !expr->acc.index)
1590 return pet_expr_free(expr);
1592 return expr;
1593 error:
1594 isl_set_free(cond);
1595 return pet_expr_free(expr);
1598 /* Modify the access relations (if any) and index expression
1599 * of the given access expression
1600 * based on the given iteration space transformation.
1601 * In particular, precompose the access relation and index expression
1602 * with the update function.
1604 * If the access has any arguments then the domain of the access relation
1605 * is a wrapped mapping from the iteration space to the space of
1606 * argument values. We only need to change the domain of this wrapped
1607 * mapping, so we extend the input transformation with an identity mapping
1608 * on the space of argument values.
1610 __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr,
1611 __isl_keep isl_multi_pw_aff *update)
1613 enum pet_expr_access_type type;
1615 expr = pet_expr_cow(expr);
1616 if (!expr)
1617 return NULL;
1618 if (expr->type != pet_expr_access)
1619 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1620 "not an access expression", return pet_expr_free(expr));
1622 update = isl_multi_pw_aff_copy(update);
1624 if (expr->n_arg > 0) {
1625 isl_space *space;
1626 isl_multi_pw_aff *id;
1628 space = isl_multi_pw_aff_get_space(expr->acc.index);
1629 space = isl_space_domain(space);
1630 space = isl_space_unwrap(space);
1631 space = isl_space_range(space);
1632 space = isl_space_map_from_set(space);
1633 id = isl_multi_pw_aff_identity(space);
1634 update = isl_multi_pw_aff_product(update, id);
1637 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1638 if (!expr->acc.access[type])
1639 continue;
1640 expr->acc.access[type] =
1641 isl_union_map_preimage_domain_multi_pw_aff(
1642 expr->acc.access[type],
1643 isl_multi_pw_aff_copy(update));
1644 if (!expr->acc.access[type])
1645 break;
1647 expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
1648 expr->acc.index, update);
1649 if (type < pet_expr_access_end || !expr->acc.index)
1650 return pet_expr_free(expr);
1652 return expr;
1655 static __isl_give pet_expr *update_domain(__isl_take pet_expr *expr, void *user)
1657 isl_multi_pw_aff *update = user;
1659 return pet_expr_access_update_domain(expr, update);
1662 /* Modify all access relations in "expr" by precomposing them with
1663 * the given iteration space transformation.
1665 __isl_give pet_expr *pet_expr_update_domain(__isl_take pet_expr *expr,
1666 __isl_take isl_multi_pw_aff *update)
1668 expr = pet_expr_map_access(expr, &update_domain, update);
1669 isl_multi_pw_aff_free(update);
1670 return expr;
1673 /* Given an expression with accesses that have a 0D anonymous domain,
1674 * replace those domains by "space".
1676 __isl_give pet_expr *pet_expr_insert_domain(__isl_take pet_expr *expr,
1677 __isl_take isl_space *space)
1679 isl_multi_pw_aff *mpa;
1681 space = isl_space_from_domain(space);
1682 mpa = isl_multi_pw_aff_zero(space);
1683 return pet_expr_update_domain(expr, mpa);
1686 /* Add all parameters in "space" to the access relations (if any)
1687 * and index expression of "expr".
1689 static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user)
1691 isl_space *space = user;
1692 enum pet_expr_access_type type;
1694 expr = pet_expr_cow(expr);
1695 if (!expr)
1696 return NULL;
1697 if (expr->type != pet_expr_access)
1698 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1699 "not an access expression", return pet_expr_free(expr));
1701 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1702 if (!expr->acc.access[type])
1703 continue;
1704 expr->acc.access[type] =
1705 isl_union_map_align_params(expr->acc.access[type],
1706 isl_space_copy(space));
1707 if (!expr->acc.access[type])
1708 break;
1710 expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
1711 isl_space_copy(space));
1712 if (type < pet_expr_access_end || !expr->acc.index)
1713 return pet_expr_free(expr);
1715 return expr;
1718 /* Add all parameters in "space" to all access relations and index expressions
1719 * in "expr".
1721 __isl_give pet_expr *pet_expr_align_params(__isl_take pet_expr *expr,
1722 __isl_take isl_space *space)
1724 expr = pet_expr_map_access(expr, &align_params, space);
1725 isl_space_free(space);
1726 return expr;
1729 /* Insert an argument expression corresponding to "test" in front
1730 * of the list of arguments described by *n_arg and *args.
1732 static __isl_give pet_expr *insert_access_arg(__isl_take pet_expr *expr,
1733 __isl_keep isl_multi_pw_aff *test)
1735 int i;
1736 isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
1738 if (!test)
1739 return pet_expr_free(expr);
1740 expr = pet_expr_cow(expr);
1741 if (!expr)
1742 return NULL;
1744 if (!expr->args) {
1745 expr->args = isl_calloc_array(ctx, pet_expr *, 1);
1746 if (!expr->args)
1747 return pet_expr_free(expr);
1748 } else {
1749 pet_expr **ext;
1750 ext = isl_calloc_array(ctx, pet_expr *, 1 + expr->n_arg);
1751 if (!ext)
1752 return pet_expr_free(expr);
1753 for (i = 0; i < expr->n_arg; ++i)
1754 ext[1 + i] = expr->args[i];
1755 free(expr->args);
1756 expr->args = ext;
1758 expr->n_arg++;
1759 expr->args[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
1760 if (!expr->args[0])
1761 return pet_expr_free(expr);
1763 return expr;
1766 /* Make the expression "expr" depend on the value of "test"
1767 * being equal to "satisfied".
1769 * If "test" is an affine expression, we simply add the conditions
1770 * on the expression having the value "satisfied" to all access relations
1771 * (introducing access relations if they are missing) and index expressions.
1773 * Otherwise, we add a filter to "expr" (which is then assumed to be
1774 * an access expression) corresponding to "test" being equal to "satisfied".
1776 __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr,
1777 __isl_take isl_multi_pw_aff *test, int satisfied)
1779 isl_id *id;
1780 isl_ctx *ctx;
1781 isl_space *space;
1782 isl_pw_multi_aff *pma;
1783 enum pet_expr_access_type type;
1785 expr = pet_expr_cow(expr);
1786 if (!expr || !test)
1787 goto error;
1789 if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
1790 isl_pw_aff *pa;
1791 isl_set *cond;
1793 pa = isl_multi_pw_aff_get_pw_aff(test, 0);
1794 isl_multi_pw_aff_free(test);
1795 if (satisfied)
1796 cond = isl_pw_aff_non_zero_set(pa);
1797 else
1798 cond = isl_pw_aff_zero_set(pa);
1799 return pet_expr_restrict(expr, cond);
1802 ctx = isl_multi_pw_aff_get_ctx(test);
1803 if (expr->type != pet_expr_access)
1804 isl_die(ctx, isl_error_invalid,
1805 "can only filter access expressions", goto error);
1807 expr = introduce_access_relations(expr);
1808 if (!expr)
1809 goto error;
1811 space = isl_space_domain(isl_multi_pw_aff_get_space(expr->acc.index));
1812 id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
1813 pma = pet_filter_insert_pma(space, id, satisfied);
1815 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1816 if (!expr->acc.access[type])
1817 continue;
1818 expr->acc.access[type] =
1819 isl_union_map_preimage_domain_pw_multi_aff(
1820 expr->acc.access[type],
1821 isl_pw_multi_aff_copy(pma));
1822 if (!expr->acc.access[type])
1823 break;
1825 pma = isl_pw_multi_aff_gist(pma,
1826 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma)));
1827 expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
1828 expr->acc.index, pma);
1829 if (type < pet_expr_access_end || !expr->acc.index)
1830 goto error;
1832 expr = insert_access_arg(expr, test);
1834 isl_multi_pw_aff_free(test);
1835 return expr;
1836 error:
1837 isl_multi_pw_aff_free(test);
1838 return pet_expr_free(expr);
1841 /* Add a reference identifier to access expression "expr".
1842 * "user" points to an integer that contains the sequence number
1843 * of the next reference.
1845 static __isl_give pet_expr *access_add_ref_id(__isl_take pet_expr *expr,
1846 void *user)
1848 isl_ctx *ctx;
1849 char name[50];
1850 int *n_ref = user;
1852 expr = pet_expr_cow(expr);
1853 if (!expr)
1854 return expr;
1855 if (expr->type != pet_expr_access)
1856 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1857 "not an access expression", return pet_expr_free(expr));
1859 ctx = pet_expr_get_ctx(expr);
1860 snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
1861 expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
1862 if (!expr->acc.ref_id)
1863 return pet_expr_free(expr);
1865 return expr;
1868 __isl_give pet_expr *pet_expr_add_ref_ids(__isl_take pet_expr *expr, int *n_ref)
1870 return pet_expr_map_access(expr, &access_add_ref_id, n_ref);
1873 /* Reset the user pointer on all parameter and tuple ids in
1874 * the access relations (if any) and the index expression
1875 * of the access expression "expr".
1877 static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr,
1878 void *user)
1880 enum pet_expr_access_type type;
1882 expr = pet_expr_cow(expr);
1883 if (!expr)
1884 return expr;
1885 if (expr->type != pet_expr_access)
1886 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1887 "not an access expression", return pet_expr_free(expr));
1889 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1890 if (!expr->acc.access[type])
1891 continue;
1892 expr->acc.access[type] =
1893 isl_union_map_reset_user(expr->acc.access[type]);
1894 if (!expr->acc.access[type])
1895 break;
1897 expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
1898 if (type < pet_expr_access_end || !expr->acc.index)
1899 return pet_expr_free(expr);
1901 return expr;
1904 __isl_give pet_expr *pet_expr_anonymize(__isl_take pet_expr *expr)
1906 return pet_expr_map_access(expr, &access_anonymize, NULL);
1909 /* Data used in access_gist() callback.
1911 struct pet_access_gist_data {
1912 isl_set *domain;
1913 isl_union_map *value_bounds;
1916 /* Given an expression "expr" of type pet_expr_access, compute
1917 * the gist of the associated access relations (if any) and index expression
1918 * with respect to data->domain and the bounds on the values of the arguments
1919 * of the expression.
1921 * The arguments of "expr" have been gisted right before "expr" itself
1922 * is gisted. The gisted arguments may have become equal where before
1923 * they may not have been (obviously) equal. We therefore take
1924 * the opportunity to remove duplicate arguments here.
1926 static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user)
1928 struct pet_access_gist_data *data = user;
1929 isl_set *domain;
1930 isl_union_set *uset;
1931 enum pet_expr_access_type type;
1933 expr = pet_expr_remove_duplicate_args(expr);
1934 expr = pet_expr_cow(expr);
1935 if (!expr)
1936 return expr;
1937 if (expr->type != pet_expr_access)
1938 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1939 "not an access expression", return pet_expr_free(expr));
1941 domain = isl_set_copy(data->domain);
1942 if (expr->n_arg > 0)
1943 domain = pet_value_bounds_apply(domain, expr->n_arg, expr->args,
1944 data->value_bounds);
1946 uset = isl_union_set_from_set(isl_set_copy(domain));
1947 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
1948 if (!expr->acc.access[type])
1949 continue;
1950 expr->acc.access[type] =
1951 isl_union_map_gist_domain(expr->acc.access[type],
1952 isl_union_set_copy(uset));
1953 if (!expr->acc.access[type])
1954 break;
1956 isl_union_set_free(uset);
1957 expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain);
1958 if (type < pet_expr_access_end || !expr->acc.index)
1959 return pet_expr_free(expr);
1961 return expr;
1964 __isl_give pet_expr *pet_expr_gist(__isl_take pet_expr *expr,
1965 __isl_keep isl_set *context, __isl_keep isl_union_map *value_bounds)
1967 struct pet_access_gist_data data = { context, value_bounds };
1969 return pet_expr_map_access(expr, &access_gist, &data);
1972 /* Mark "expr" as a read dependening on "read".
1974 __isl_give pet_expr *pet_expr_access_set_read(__isl_take pet_expr *expr,
1975 int read)
1977 if (!expr)
1978 return pet_expr_free(expr);
1979 if (expr->type != pet_expr_access)
1980 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
1981 "not an access expression", return pet_expr_free(expr));
1982 if (expr->acc.read == read)
1983 return expr;
1984 expr = pet_expr_cow(expr);
1985 if (!expr)
1986 return NULL;
1987 expr->acc.read = read;
1989 return expr;
1992 /* Mark "expr" as a write dependening on "write".
1994 __isl_give pet_expr *pet_expr_access_set_write(__isl_take pet_expr *expr,
1995 int write)
1997 if (!expr)
1998 return pet_expr_free(expr);
1999 if (expr->type != pet_expr_access)
2000 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2001 "not an access expression", return pet_expr_free(expr));
2002 if (expr->acc.write == write)
2003 return expr;
2004 expr = pet_expr_cow(expr);
2005 if (!expr)
2006 return NULL;
2007 expr->acc.write = write;
2009 return expr;
2012 /* Mark "expr" as a kill dependening on "kill".
2014 __isl_give pet_expr *pet_expr_access_set_kill(__isl_take pet_expr *expr,
2015 int kill)
2017 if (!expr)
2018 return pet_expr_free(expr);
2019 if (expr->type != pet_expr_access)
2020 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2021 "not an access expression", return pet_expr_free(expr));
2022 if (expr->acc.kill == kill)
2023 return expr;
2024 expr = pet_expr_cow(expr);
2025 if (!expr)
2026 return NULL;
2027 expr->acc.kill = kill;
2029 return expr;
2032 /* Map the access type "type" to the corresponding location
2033 * in the access array.
2034 * In particular, the access relation of type pet_expr_access_killed is
2035 * stored in the element at position pet_expr_access_fake_killed.
2037 static enum pet_expr_access_type internalize_type(
2038 enum pet_expr_access_type type)
2040 if (type == pet_expr_access_killed)
2041 return pet_expr_access_fake_killed;
2042 return type;
2045 /* Replace the access relation of the given "type" of "expr" by "access".
2046 * If the access relation is non-empty and the type is a read or a write,
2047 * then also mark the access expression itself as a read or a write.
2049 __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr,
2050 enum pet_expr_access_type type, __isl_take isl_union_map *access)
2052 int empty;
2054 expr = pet_expr_cow(expr);
2055 if (!expr || !access)
2056 goto error;
2057 if (expr->type != pet_expr_access)
2058 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2059 "not an access expression", goto error);
2060 type = internalize_type(type);
2061 isl_union_map_free(expr->acc.access[type]);
2062 expr->acc.access[type] = access;
2064 if (expr->acc.kill)
2065 return expr;
2067 empty = isl_union_map_is_empty(access);
2068 if (empty < 0)
2069 return pet_expr_free(expr);
2070 if (empty)
2071 return expr;
2073 if (type == pet_expr_access_may_read)
2074 expr = pet_expr_access_set_read(expr, 1);
2075 else
2076 expr = pet_expr_access_set_write(expr, 1);
2078 return expr;
2079 error:
2080 isl_union_map_free(access);
2081 pet_expr_free(expr);
2082 return NULL;
2085 /* Replace the index expression of "expr" by "index" and
2086 * set the array depth accordingly.
2088 __isl_give pet_expr *pet_expr_access_set_index(__isl_take pet_expr *expr,
2089 __isl_take isl_multi_pw_aff *index)
2091 expr = pet_expr_cow(expr);
2092 if (!expr || !index)
2093 goto error;
2094 if (expr->type != pet_expr_access)
2095 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2096 "not an access expression", goto error);
2097 isl_multi_pw_aff_free(expr->acc.index);
2098 expr->acc.index = index;
2099 expr->acc.depth = isl_multi_pw_aff_dim(index, isl_dim_out);
2101 return expr;
2102 error:
2103 isl_multi_pw_aff_free(index);
2104 pet_expr_free(expr);
2105 return NULL;
2108 /* Return the reference identifier of access expression "expr".
2110 __isl_give isl_id *pet_expr_access_get_ref_id(__isl_keep pet_expr *expr)
2112 if (!expr)
2113 return NULL;
2114 if (expr->type != pet_expr_access)
2115 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2116 "not an access expression", return NULL);
2118 return isl_id_copy(expr->acc.ref_id);
2121 /* Replace the reference identifier of access expression "expr" by "ref_id".
2123 __isl_give pet_expr *pet_expr_access_set_ref_id(__isl_take pet_expr *expr,
2124 __isl_take isl_id *ref_id)
2126 expr = pet_expr_cow(expr);
2127 if (!expr || !ref_id)
2128 goto error;
2129 if (expr->type != pet_expr_access)
2130 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2131 "not an access expression", goto error);
2132 isl_id_free(expr->acc.ref_id);
2133 expr->acc.ref_id = ref_id;
2135 return expr;
2136 error:
2137 isl_id_free(ref_id);
2138 pet_expr_free(expr);
2139 return NULL;
2142 /* Tag the access relation "access" with "id".
2143 * That is, insert the id as the range of a wrapped relation
2144 * in the domain of "access".
2146 * If "access" is of the form
2148 * D[i] -> A[a]
2150 * then the result is of the form
2152 * [D[i] -> id[]] -> A[a]
2154 __isl_give isl_union_map *pet_expr_tag_access(__isl_keep pet_expr *expr,
2155 __isl_take isl_union_map *access)
2157 isl_space *space;
2158 isl_multi_aff *add_tag;
2159 isl_id *id;
2161 if (expr->type != pet_expr_access)
2162 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2163 "not an access expression",
2164 return isl_union_map_free(access));
2166 id = isl_id_copy(expr->acc.ref_id);
2167 space = pet_expr_access_get_domain_space(expr);
2168 space = isl_space_from_domain(space);
2169 space = isl_space_set_tuple_id(space, isl_dim_out, id);
2170 add_tag = isl_multi_aff_domain_map(space);
2171 access = isl_union_map_preimage_domain_multi_aff(access, add_tag);
2173 return access;
2176 /* Return the access relation of the given "type" associated to "expr"
2177 * that maps pairs of domain iterations and argument values
2178 * to the corresponding accessed data elements.
2180 * If the requested access relation is explicitly available,
2181 * then return a copy. Otherwise, check if it is irrelevant for
2182 * the access expression and return an empty relation if this is the case.
2183 * Otherwise, introduce the requested access relation in "expr" and
2184 * return a copy.
2186 __isl_give isl_union_map *pet_expr_access_get_dependent_access(
2187 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2189 isl_union_map *access;
2190 int empty;
2192 if (!expr)
2193 return NULL;
2194 if (expr->type != pet_expr_access)
2195 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2196 "not an access expression", return NULL);
2198 type = internalize_type(type);
2199 if (expr->acc.access[type])
2200 return isl_union_map_copy(expr->acc.access[type]);
2202 if (type == pet_expr_access_may_read)
2203 empty = !expr->acc.read;
2204 else
2205 empty = !expr->acc.write;
2207 if (!empty) {
2208 expr = pet_expr_copy(expr);
2209 expr = introduce_access_relations(expr);
2210 if (!expr)
2211 return NULL;
2212 access = isl_union_map_copy(expr->acc.access[type]);
2213 pet_expr_free(expr);
2215 return access;
2218 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr));
2221 /* Return the may read access relation associated to "expr"
2222 * that maps pairs of domain iterations and argument values
2223 * to the corresponding accessed data elements.
2225 __isl_give isl_union_map *pet_expr_access_get_dependent_may_read(
2226 __isl_keep pet_expr *expr)
2228 return pet_expr_access_get_dependent_access(expr,
2229 pet_expr_access_may_read);
2232 /* Return the may write access relation associated to "expr"
2233 * that maps pairs of domain iterations and argument values
2234 * to the corresponding accessed data elements.
2236 __isl_give isl_union_map *pet_expr_access_get_dependent_may_write(
2237 __isl_keep pet_expr *expr)
2239 return pet_expr_access_get_dependent_access(expr,
2240 pet_expr_access_may_write);
2243 /* Return the must write access relation associated to "expr"
2244 * that maps pairs of domain iterations and argument values
2245 * to the corresponding accessed data elements.
2247 __isl_give isl_union_map *pet_expr_access_get_dependent_must_write(
2248 __isl_keep pet_expr *expr)
2250 return pet_expr_access_get_dependent_access(expr,
2251 pet_expr_access_must_write);
2254 /* Return the relation of the given "type" mapping domain iterations
2255 * to the accessed data elements.
2256 * In particular, take the access relation and, in case of may_read
2257 * or may_write, project out the values of the arguments, if any.
2258 * In case of must_write, return the empty relation if there are
2259 * any arguments.
2261 __isl_give isl_union_map *pet_expr_access_get_access(__isl_keep pet_expr *expr,
2262 enum pet_expr_access_type type)
2264 isl_union_map *access;
2265 isl_space *space;
2266 isl_map *map;
2268 if (!expr)
2269 return NULL;
2270 if (expr->type != pet_expr_access)
2271 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2272 "not an access expression", return NULL);
2274 if (expr->n_arg != 0 && type == pet_expr_access_must_write) {
2275 space = pet_expr_access_get_parameter_space(expr);
2276 return isl_union_map_empty(space);
2279 access = pet_expr_access_get_dependent_access(expr, type);
2280 if (expr->n_arg == 0)
2281 return access;
2283 space = isl_multi_pw_aff_get_space(expr->acc.index);
2284 space = isl_space_domain(space);
2285 map = isl_map_universe(isl_space_unwrap(space));
2286 map = isl_map_domain_map(map);
2287 access = isl_union_map_apply_domain(access,
2288 isl_union_map_from_map(map));
2290 return access;
2293 /* Return the relation mapping domain iterations to all possibly
2294 * read data elements.
2296 __isl_give isl_union_map *pet_expr_access_get_may_read(
2297 __isl_keep pet_expr *expr)
2299 return pet_expr_access_get_access(expr, pet_expr_access_may_read);
2302 /* Return the relation mapping domain iterations to all possibly
2303 * written data elements.
2305 __isl_give isl_union_map *pet_expr_access_get_may_write(
2306 __isl_keep pet_expr *expr)
2308 return pet_expr_access_get_access(expr, pet_expr_access_may_write);
2311 /* Return a relation mapping domain iterations to definitely
2312 * written data elements, assuming the statement containing
2313 * the expression is executed.
2315 __isl_give isl_union_map *pet_expr_access_get_must_write(
2316 __isl_keep pet_expr *expr)
2318 return pet_expr_access_get_access(expr, pet_expr_access_must_write);
2321 /* Return the relation of the given "type" mapping domain iterations to
2322 * accessed data elements, with its domain tagged with the reference
2323 * identifier.
2325 static __isl_give isl_union_map *pet_expr_access_get_tagged_access(
2326 __isl_keep pet_expr *expr, enum pet_expr_access_type type)
2328 isl_union_map *access;
2330 if (!expr)
2331 return NULL;
2333 access = pet_expr_access_get_access(expr, type);
2334 access = pet_expr_tag_access(expr, access);
2336 return access;
2339 /* Return the relation mapping domain iterations to all possibly
2340 * read data elements, with its domain tagged with the reference
2341 * identifier.
2343 __isl_give isl_union_map *pet_expr_access_get_tagged_may_read(
2344 __isl_keep pet_expr *expr)
2346 return pet_expr_access_get_tagged_access(expr,
2347 pet_expr_access_may_read);
2350 /* Return the relation mapping domain iterations to all possibly
2351 * written data elements, with its domain tagged with the reference
2352 * identifier.
2354 __isl_give isl_union_map *pet_expr_access_get_tagged_may_write(
2355 __isl_keep pet_expr *expr)
2357 return pet_expr_access_get_tagged_access(expr,
2358 pet_expr_access_may_write);
2361 /* Return the operation type of operation expression "expr".
2363 enum pet_op_type pet_expr_op_get_type(__isl_keep pet_expr *expr)
2365 if (!expr)
2366 return pet_op_last;
2367 if (expr->type != pet_expr_op)
2368 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2369 "not an operation expression", return pet_op_last);
2371 return expr->op;
2374 /* Replace the operation type of operation expression "expr" by "type".
2376 __isl_give pet_expr *pet_expr_op_set_type(__isl_take pet_expr *expr,
2377 enum pet_op_type type)
2379 if (!expr)
2380 return pet_expr_free(expr);
2381 if (expr->type != pet_expr_op)
2382 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2383 "not an operation expression",
2384 return pet_expr_free(expr));
2385 if (expr->op == type)
2386 return expr;
2387 expr = pet_expr_cow(expr);
2388 if (!expr)
2389 return NULL;
2390 expr->op = type;
2392 return expr;
2395 /* Return the name of the function called by "expr".
2397 __isl_keep const char *pet_expr_call_get_name(__isl_keep pet_expr *expr)
2399 if (!expr)
2400 return NULL;
2401 if (expr->type != pet_expr_call)
2402 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2403 "not a call expression", return NULL);
2404 return expr->c.name;
2407 /* Replace the name of the function called by "expr" by "name".
2409 __isl_give pet_expr *pet_expr_call_set_name(__isl_take pet_expr *expr,
2410 __isl_keep const char *name)
2412 expr = pet_expr_cow(expr);
2413 if (!expr || !name)
2414 return pet_expr_free(expr);
2415 if (expr->type != pet_expr_call)
2416 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2417 "not a call expression", return pet_expr_free(expr));
2418 free(expr->c.name);
2419 expr->c.name = strdup(name);
2420 if (!expr->c.name)
2421 return pet_expr_free(expr);
2422 return expr;
2425 /* Does the call expression "expr" have an associated function summary?
2427 int pet_expr_call_has_summary(__isl_keep pet_expr *expr)
2429 if (!expr)
2430 return -1;
2431 if (expr->type != pet_expr_call)
2432 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2433 "not a call expression", return -1);
2435 return expr->c.summary != NULL;
2438 /* Return a copy of the function summary associated to
2439 * the call expression "expr".
2441 __isl_give pet_function_summary *pet_expr_call_get_summary(
2442 __isl_keep pet_expr *expr)
2444 if (!expr)
2445 return NULL;
2446 if (expr->type != pet_expr_call)
2447 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2448 "not a call expression", return NULL);
2450 return pet_function_summary_copy(expr->c.summary);
2453 /* Replace the function summary associated to the call expression "expr"
2454 * by "summary".
2456 __isl_give pet_expr *pet_expr_call_set_summary(__isl_take pet_expr *expr,
2457 __isl_take pet_function_summary *summary)
2459 expr = pet_expr_cow(expr);
2460 if (!expr || !summary)
2461 goto error;
2462 if (expr->type != pet_expr_call)
2463 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2464 "not a call expression", goto error);
2465 pet_function_summary_free(expr->c.summary);
2466 expr->c.summary = summary;
2467 return expr;
2468 error:
2469 pet_function_summary_free(summary);
2470 return pet_expr_free(expr);
2473 /* Replace the type of the cast performed by "expr" by "name".
2475 __isl_give pet_expr *pet_expr_cast_set_type_name(__isl_take pet_expr *expr,
2476 __isl_keep const char *name)
2478 expr = pet_expr_cow(expr);
2479 if (!expr || !name)
2480 return pet_expr_free(expr);
2481 if (expr->type != pet_expr_cast)
2482 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2483 "not a cast expression", return pet_expr_free(expr));
2484 free(expr->type_name);
2485 expr->type_name = strdup(name);
2486 if (!expr->type_name)
2487 return pet_expr_free(expr);
2488 return expr;
2491 /* Return the value of the integer represented by "expr".
2493 __isl_give isl_val *pet_expr_int_get_val(__isl_keep pet_expr *expr)
2495 if (!expr)
2496 return NULL;
2497 if (expr->type != pet_expr_int)
2498 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2499 "not an int expression", return NULL);
2501 return isl_val_copy(expr->i);
2504 /* Replace the value of the integer represented by "expr" by "v".
2506 __isl_give pet_expr *pet_expr_int_set_val(__isl_take pet_expr *expr,
2507 __isl_take isl_val *v)
2509 expr = pet_expr_cow(expr);
2510 if (!expr || !v)
2511 goto error;
2512 if (expr->type != pet_expr_int)
2513 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2514 "not an int expression", goto error);
2515 isl_val_free(expr->i);
2516 expr->i = v;
2518 return expr;
2519 error:
2520 isl_val_free(v);
2521 pet_expr_free(expr);
2522 return NULL;
2525 /* Replace the value and string representation of the double
2526 * represented by "expr" by "d" and "s".
2528 __isl_give pet_expr *pet_expr_double_set(__isl_take pet_expr *expr,
2529 double d, __isl_keep const char *s)
2531 expr = pet_expr_cow(expr);
2532 if (!expr || !s)
2533 return pet_expr_free(expr);
2534 if (expr->type != pet_expr_double)
2535 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2536 "not a double expression", return pet_expr_free(expr));
2537 expr->d.val = d;
2538 free(expr->d.s);
2539 expr->d.s = strdup(s);
2540 if (!expr->d.s)
2541 return pet_expr_free(expr);
2542 return expr;
2545 /* Return a string representation of the double expression "expr".
2547 __isl_give char *pet_expr_double_get_str(__isl_keep pet_expr *expr)
2549 if (!expr)
2550 return NULL;
2551 if (expr->type != pet_expr_double)
2552 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2553 "not a double expression", return NULL);
2554 return strdup(expr->d.s);
2557 /* Return a piecewise affine expression defined on the specified domain
2558 * that represents NaN.
2560 static __isl_give isl_pw_aff *non_affine(__isl_take isl_space *space)
2562 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space));
2565 /* This function is called when we come across an access that is
2566 * nested in what is supposed to be an affine expression.
2567 * "pc" is the context in which the affine expression is created.
2568 * If nesting is allowed in "pc", we return an affine expression that is
2569 * equal to a new parameter corresponding to this nested access.
2570 * Otherwise, we return NaN.
2572 * Note that we currently don't allow nested accesses themselves
2573 * to contain any nested accesses, so we check if "expr" itself
2574 * involves any nested accesses (either explicitly as arguments
2575 * or implicitly through parameters) and return NaN if it does.
2577 * The new parameter is resolved in resolve_nested.
2579 static __isl_give isl_pw_aff *nested_access(__isl_keep pet_expr *expr,
2580 __isl_keep pet_context *pc)
2582 isl_ctx *ctx;
2583 isl_id *id;
2584 isl_space *space;
2585 isl_local_space *ls;
2586 isl_aff *aff;
2587 int nested;
2589 if (!expr || !pc)
2590 return NULL;
2591 if (!pet_context_allow_nesting(pc))
2592 return non_affine(pet_context_get_space(pc));
2594 if (pet_expr_get_type(expr) != pet_expr_access)
2595 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2596 "not an access expression", return NULL);
2598 if (expr->n_arg > 0)
2599 return non_affine(pet_context_get_space(pc));
2601 space = pet_expr_access_get_parameter_space(expr);
2602 nested = pet_nested_any_in_space(space);
2603 isl_space_free(space);
2604 if (nested)
2605 return non_affine(pet_context_get_space(pc));
2607 ctx = pet_expr_get_ctx(expr);
2608 id = pet_nested_pet_expr(pet_expr_copy(expr));
2609 space = pet_context_get_space(pc);
2610 space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
2612 space = isl_space_set_dim_id(space, isl_dim_param, 0, id);
2613 ls = isl_local_space_from_space(space);
2614 aff = isl_aff_var_on_domain(ls, isl_dim_param, 0);
2616 return isl_pw_aff_from_aff(aff);
2619 /* Extract an affine expression from the access pet_expr "expr".
2620 * "pc" is the context in which the affine expression is created.
2622 * If "expr" is actually an affine expression rather than
2623 * a real access, then we return that expression.
2624 * Otherwise, we require that "expr" is of an integral type.
2625 * If not, we return NaN.
2627 * If the variable has been assigned a known affine expression,
2628 * then we return that expression.
2630 * Otherwise, we return an expression that is equal to a parameter
2631 * representing "expr" (if "allow_nested" is set).
2633 static __isl_give isl_pw_aff *extract_affine_from_access(
2634 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
2636 int pos;
2637 isl_id *id;
2639 if (pet_expr_is_affine(expr)) {
2640 isl_pw_aff *pa;
2641 isl_multi_pw_aff *mpa;
2643 mpa = pet_expr_access_get_index(expr);
2644 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
2645 isl_multi_pw_aff_free(mpa);
2646 return pa;
2649 if (pet_expr_get_type_size(expr) == 0)
2650 return non_affine(pet_context_get_space(pc));
2652 if (!pet_expr_is_scalar_access(expr))
2653 return nested_access(expr, pc);
2655 id = pet_expr_access_get_id(expr);
2656 if (pet_context_is_assigned(pc, id))
2657 return pet_context_get_value(pc, id);
2659 isl_id_free(id);
2660 return nested_access(expr, pc);
2663 /* Construct an affine expression from the integer constant "expr".
2664 * "pc" is the context in which the affine expression is created.
2666 static __isl_give isl_pw_aff *extract_affine_from_int(__isl_keep pet_expr *expr,
2667 __isl_keep pet_context *pc)
2669 isl_local_space *ls;
2670 isl_aff *aff;
2672 if (!expr)
2673 return NULL;
2675 ls = isl_local_space_from_space(pet_context_get_space(pc));
2676 aff = isl_aff_val_on_domain(ls, pet_expr_int_get_val(expr));
2678 return isl_pw_aff_from_aff(aff);
2681 /* Extract an affine expression from an addition or subtraction operation.
2682 * Return NaN if we are unable to extract an affine expression.
2684 * "pc" is the context in which the affine expression is created.
2686 static __isl_give isl_pw_aff *extract_affine_add_sub(__isl_keep pet_expr *expr,
2687 __isl_keep pet_context *pc)
2689 isl_pw_aff *lhs;
2690 isl_pw_aff *rhs;
2692 if (!expr)
2693 return NULL;
2694 if (expr->n_arg != 2)
2695 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2696 "expecting two arguments", return NULL);
2698 lhs = pet_expr_extract_affine(expr->args[0], pc);
2699 rhs = pet_expr_extract_affine(expr->args[1], pc);
2701 switch (pet_expr_op_get_type(expr)) {
2702 case pet_op_add:
2703 return isl_pw_aff_add(lhs, rhs);
2704 case pet_op_sub:
2705 return isl_pw_aff_sub(lhs, rhs);
2706 default:
2707 isl_pw_aff_free(lhs);
2708 isl_pw_aff_free(rhs);
2709 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2710 "not an addition or subtraction operation",
2711 return NULL);
2716 /* Extract an affine expression from an integer division or a modulo operation.
2717 * Return NaN if we are unable to extract an affine expression.
2719 * "pc" is the context in which the affine expression is created.
2721 * In particular, if "expr" is lhs/rhs, then return
2723 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2725 * If "expr" is lhs%rhs, then return
2727 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2729 * If the second argument (rhs) is not a (positive) integer constant,
2730 * then we fail to extract an affine expression.
2732 * We simplify the result in the context of the domain of "pc" in case
2733 * this domain implies that lhs >= 0 (or < 0).
2735 static __isl_give isl_pw_aff *extract_affine_div_mod(__isl_keep pet_expr *expr,
2736 __isl_keep pet_context *pc)
2738 int is_cst;
2739 isl_pw_aff *lhs;
2740 isl_pw_aff *rhs;
2741 isl_pw_aff *res;
2743 if (!expr)
2744 return NULL;
2745 if (expr->n_arg != 2)
2746 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2747 "expecting two arguments", return NULL);
2749 rhs = pet_expr_extract_affine(expr->args[1], pc);
2751 is_cst = isl_pw_aff_is_cst(rhs);
2752 if (is_cst < 0 || !is_cst) {
2753 isl_pw_aff_free(rhs);
2754 return non_affine(pet_context_get_space(pc));
2757 lhs = pet_expr_extract_affine(expr->args[0], pc);
2759 switch (pet_expr_op_get_type(expr)) {
2760 case pet_op_div:
2761 res = isl_pw_aff_tdiv_q(lhs, rhs);
2762 break;
2763 case pet_op_mod:
2764 res = isl_pw_aff_tdiv_r(lhs, rhs);
2765 break;
2766 default:
2767 isl_pw_aff_free(lhs);
2768 isl_pw_aff_free(rhs);
2769 isl_die(pet_expr_get_ctx(expr), isl_error_internal,
2770 "not a div or mod operator", return NULL);
2773 return isl_pw_aff_gist(res, pet_context_get_gist_domain(pc));
2776 /* Extract an affine expression from a multiplication operation.
2777 * Return NaN if we are unable to extract an affine expression.
2778 * In particular, if neither of the arguments is a (piecewise) constant
2779 * then we return NaN.
2781 * "pc" is the context in which the affine expression is created.
2783 static __isl_give isl_pw_aff *extract_affine_mul(__isl_keep pet_expr *expr,
2784 __isl_keep pet_context *pc)
2786 int lhs_cst, rhs_cst;
2787 isl_pw_aff *lhs;
2788 isl_pw_aff *rhs;
2790 if (!expr)
2791 return NULL;
2792 if (expr->n_arg != 2)
2793 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2794 "expecting two arguments", return NULL);
2796 lhs = pet_expr_extract_affine(expr->args[0], pc);
2797 rhs = pet_expr_extract_affine(expr->args[1], pc);
2799 lhs_cst = isl_pw_aff_is_cst(lhs);
2800 rhs_cst = isl_pw_aff_is_cst(rhs);
2801 if (lhs_cst >= 0 && rhs_cst >= 0 && (lhs_cst || rhs_cst))
2802 return isl_pw_aff_mul(lhs, rhs);
2804 isl_pw_aff_free(lhs);
2805 isl_pw_aff_free(rhs);
2807 if (lhs_cst < 0 || rhs_cst < 0)
2808 return NULL;
2810 return non_affine(pet_context_get_space(pc));
2813 /* Extract an affine expression from a negation operation.
2814 * Return NaN if we are unable to extract an affine expression.
2816 * "pc" is the context in which the affine expression is created.
2818 static __isl_give isl_pw_aff *extract_affine_neg(__isl_keep pet_expr *expr,
2819 __isl_keep pet_context *pc)
2821 isl_pw_aff *res;
2823 if (!expr)
2824 return NULL;
2825 if (expr->n_arg != 1)
2826 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2827 "expecting one argument", return NULL);
2829 res = pet_expr_extract_affine(expr->args[0], pc);
2830 return isl_pw_aff_neg(res);
2833 /* Extract an affine expression from a conditional operation.
2834 * Return NaN if we are unable to extract an affine expression.
2836 * "pc" is the context in which the affine expression is created.
2838 static __isl_give isl_pw_aff *extract_affine_cond(__isl_keep pet_expr *expr,
2839 __isl_keep pet_context *pc)
2841 isl_pw_aff *cond, *lhs, *rhs;
2843 if (!expr)
2844 return NULL;
2845 if (expr->n_arg != 3)
2846 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
2847 "expecting three arguments", return NULL);
2849 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
2850 lhs = pet_expr_extract_affine(expr->args[1], pc);
2851 rhs = pet_expr_extract_affine(expr->args[2], pc);
2853 return isl_pw_aff_cond(cond, lhs, rhs);
2856 /* Compute
2858 * pwaff mod 2^width
2860 static __isl_give isl_pw_aff *wrap(__isl_take isl_pw_aff *pwaff, unsigned width)
2862 isl_ctx *ctx;
2863 isl_val *mod;
2865 ctx = isl_pw_aff_get_ctx(pwaff);
2866 mod = isl_val_int_from_ui(ctx, width);
2867 mod = isl_val_2exp(mod);
2869 pwaff = isl_pw_aff_mod_val(pwaff, mod);
2871 return pwaff;
2874 /* Limit the domain of "pwaff" to those elements where the function
2875 * value satisfies
2877 * 2^{width-1} <= pwaff < 2^{width-1}
2879 static __isl_give isl_pw_aff *avoid_overflow(__isl_take isl_pw_aff *pwaff,
2880 unsigned width)
2882 isl_ctx *ctx;
2883 isl_val *v;
2884 isl_space *space = isl_pw_aff_get_domain_space(pwaff);
2885 isl_local_space *ls = isl_local_space_from_space(space);
2886 isl_aff *bound;
2887 isl_set *dom;
2888 isl_pw_aff *b;
2890 ctx = isl_pw_aff_get_ctx(pwaff);
2891 v = isl_val_int_from_ui(ctx, width - 1);
2892 v = isl_val_2exp(v);
2894 bound = isl_aff_zero_on_domain(ls);
2895 bound = isl_aff_add_constant_val(bound, v);
2896 b = isl_pw_aff_from_aff(bound);
2898 dom = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff), isl_pw_aff_copy(b));
2899 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2901 b = isl_pw_aff_neg(b);
2902 dom = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff), b);
2903 pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
2905 return pwaff;
2908 /* Handle potential overflows on signed computations.
2910 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2911 * then we adjust the domain of "pa" to avoid overflows.
2913 static __isl_give isl_pw_aff *signed_overflow(__isl_take isl_pw_aff *pa,
2914 unsigned width)
2916 isl_ctx *ctx;
2917 struct pet_options *options;
2919 if (!pa)
2920 return NULL;
2922 ctx = isl_pw_aff_get_ctx(pa);
2923 options = isl_ctx_peek_pet_options(ctx);
2924 if (!options || options->signed_overflow == PET_OVERFLOW_AVOID)
2925 pa = avoid_overflow(pa, width);
2927 return pa;
2930 /* Extract an affine expression from some an operation.
2931 * Return NaN if we are unable to extract an affine expression.
2932 * If the result of a binary (non boolean) operation is unsigned,
2933 * then we wrap it based on the size of the type. If the result is signed,
2934 * then we ensure that no overflow occurs.
2936 * "pc" is the context in which the affine expression is created.
2938 static __isl_give isl_pw_aff *extract_affine_from_op(__isl_keep pet_expr *expr,
2939 __isl_keep pet_context *pc)
2941 isl_pw_aff *res;
2942 int type_size;
2944 switch (pet_expr_op_get_type(expr)) {
2945 case pet_op_add:
2946 case pet_op_sub:
2947 res = extract_affine_add_sub(expr, pc);
2948 break;
2949 case pet_op_div:
2950 case pet_op_mod:
2951 res = extract_affine_div_mod(expr, pc);
2952 break;
2953 case pet_op_mul:
2954 res = extract_affine_mul(expr, pc);
2955 break;
2956 case pet_op_minus:
2957 return extract_affine_neg(expr, pc);
2958 case pet_op_cond:
2959 return extract_affine_cond(expr, pc);
2960 case pet_op_eq:
2961 case pet_op_ne:
2962 case pet_op_le:
2963 case pet_op_ge:
2964 case pet_op_lt:
2965 case pet_op_gt:
2966 case pet_op_land:
2967 case pet_op_lor:
2968 case pet_op_lnot:
2969 return pet_expr_extract_affine_condition(expr, pc);
2970 default:
2971 return non_affine(pet_context_get_space(pc));
2974 if (!res)
2975 return NULL;
2976 if (isl_pw_aff_involves_nan(res)) {
2977 isl_space *space = isl_pw_aff_get_domain_space(res);
2978 isl_pw_aff_free(res);
2979 return non_affine(space);
2982 type_size = pet_expr_get_type_size(expr);
2983 if (type_size > 0)
2984 res = wrap(res, type_size);
2985 else
2986 res = signed_overflow(res, -type_size);
2988 return res;
2991 /* Internal data structure for affine builtin function declarations.
2993 * "pencil" is set if the builtin is pencil specific.
2994 * "n_args" is the number of arguments the function takes.
2995 * "name" is the function name.
2997 struct affine_builtin_decl {
2998 int pencil;
2999 int n_args;
3000 const char *name;
3003 static struct affine_builtin_decl affine_builtins[] = {
3004 { 0, 2, "min" },
3005 { 1, 2, "imin" },
3006 { 1, 2, "umin" },
3007 { 0, 2, "max" },
3008 { 1, 2, "imax" },
3009 { 1, 2, "umax" },
3010 { 0, 2, "intMod" },
3011 { 0, 2, "intFloor" },
3012 { 0, 2, "intCeil" },
3013 { 0, 2, "floord" },
3014 { 0, 2, "ceild" }
3017 /* List of min and max builtin functions.
3019 static const char *min_max_builtins[] = {
3020 "min", "imin", "umin",
3021 "max", "imax", "umax"
3024 /* Is a function call to "name" with "n_args" arguments a call to a
3025 * builtin function for which we can construct an affine expression?
3026 * pencil specific builtins are only recognized if "pencil" is set.
3028 static int is_affine_builtin(int pencil, int n_args, const char *name)
3030 int i;
3032 for (i = 0; i < ARRAY_SIZE(affine_builtins); ++i) {
3033 struct affine_builtin_decl *decl = &affine_builtins[i];
3035 if (decl->pencil && !pencil)
3036 continue;
3037 if (decl->n_args == n_args && !strcmp(decl->name, name))
3038 return 1;
3041 return 0;
3044 /* Is function "name" a known min or max builtin function?
3046 static int is_min_or_max_builtin(const char *name)
3048 int i;
3050 for (i = 0; i < ARRAY_SIZE(min_max_builtins); ++i)
3051 if (!strcmp(min_max_builtins[i], name))
3052 return 1;
3054 return 0;
3057 /* Extract an affine expression from some special function calls.
3058 * Return NaN if we are unable to extract an affine expression.
3059 * In particular, we handle "min", "max", "ceild", "floord",
3060 * "intMod", "intFloor" and "intCeil".
3061 * In case of the latter five, the second argument needs to be
3062 * a (positive) integer constant.
3063 * If the pencil option is set, then we also handle "{i,u}min" and
3064 * "{i,u}max".
3066 * "pc" is the context in which the affine expression is created.
3068 static __isl_give isl_pw_aff *extract_affine_from_call(
3069 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3071 isl_ctx *ctx;
3072 isl_pw_aff *aff1, *aff2;
3073 int n;
3074 const char *name;
3075 struct pet_options *options;
3077 if (!expr)
3078 return NULL;
3079 ctx = pet_expr_get_ctx(expr);
3080 options = isl_ctx_peek_pet_options(ctx);
3082 n = pet_expr_get_n_arg(expr);
3083 name = pet_expr_call_get_name(expr);
3084 if (!is_affine_builtin(options->pencil, n, name))
3085 return non_affine(pet_context_get_space(pc));
3087 if (is_min_or_max_builtin(name)) {
3088 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3089 aff2 = pet_expr_extract_affine(expr->args[1], pc);
3091 if (strstr(name, "min"))
3092 aff1 = isl_pw_aff_min(aff1, aff2);
3093 else
3094 aff1 = isl_pw_aff_max(aff1, aff2);
3095 } else if (!strcmp(name, "intMod")) {
3096 isl_val *v;
3098 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3099 return non_affine(pet_context_get_space(pc));
3100 v = pet_expr_int_get_val(expr->args[1]);
3101 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3102 aff1 = isl_pw_aff_mod_val(aff1, v);
3103 } else {
3104 isl_val *v;
3106 if (pet_expr_get_type(expr->args[1]) != pet_expr_int)
3107 return non_affine(pet_context_get_space(pc));
3108 v = pet_expr_int_get_val(expr->args[1]);
3109 aff1 = pet_expr_extract_affine(expr->args[0], pc);
3110 aff1 = isl_pw_aff_scale_down_val(aff1, v);
3111 if (!strcmp(name, "floord") || !strcmp(name, "intFloor"))
3112 aff1 = isl_pw_aff_floor(aff1);
3113 else
3114 aff1 = isl_pw_aff_ceil(aff1);
3117 return aff1;
3120 /* Extract an affine expression from "expr", if possible.
3121 * Otherwise return NaN.
3123 * "pc" is the context in which the affine expression is created.
3125 __isl_give isl_pw_aff *pet_expr_extract_affine(__isl_keep pet_expr *expr,
3126 __isl_keep pet_context *pc)
3128 if (!expr)
3129 return NULL;
3131 switch (pet_expr_get_type(expr)) {
3132 case pet_expr_access:
3133 return extract_affine_from_access(expr, pc);
3134 case pet_expr_int:
3135 return extract_affine_from_int(expr, pc);
3136 case pet_expr_op:
3137 return extract_affine_from_op(expr, pc);
3138 case pet_expr_call:
3139 return extract_affine_from_call(expr, pc);
3140 case pet_expr_cast:
3141 case pet_expr_double:
3142 case pet_expr_error:
3143 return non_affine(pet_context_get_space(pc));
3147 /* Extract an affine expressions representing the comparison "LHS op RHS"
3148 * Return NaN if we are unable to extract such an affine expression.
3150 * "pc" is the context in which the affine expression is created.
3152 * If the comparison is of the form
3154 * a <= min(b,c)
3156 * then the expression is constructed as the conjunction of
3157 * the comparisons
3159 * a <= b and a <= c
3161 * A similar optimization is performed for max(a,b) <= c.
3162 * We do this because that will lead to simpler representations
3163 * of the expression.
3164 * If isl is ever enhanced to explicitly deal with min and max expressions,
3165 * this optimization can be removed.
3167 __isl_give isl_pw_aff *pet_expr_extract_comparison(enum pet_op_type op,
3168 __isl_keep pet_expr *lhs, __isl_keep pet_expr *rhs,
3169 __isl_keep pet_context *pc)
3171 isl_pw_aff *lhs_pa, *rhs_pa;
3173 if (op == pet_op_gt)
3174 return pet_expr_extract_comparison(pet_op_lt, rhs, lhs, pc);
3175 if (op == pet_op_ge)
3176 return pet_expr_extract_comparison(pet_op_le, rhs, lhs, pc);
3178 if (op == pet_op_lt || op == pet_op_le) {
3179 if (pet_expr_is_min(rhs)) {
3180 lhs_pa = pet_expr_extract_comparison(op, lhs,
3181 rhs->args[0], pc);
3182 rhs_pa = pet_expr_extract_comparison(op, lhs,
3183 rhs->args[1], pc);
3184 return pet_and(lhs_pa, rhs_pa);
3186 if (pet_expr_is_max(lhs)) {
3187 lhs_pa = pet_expr_extract_comparison(op, lhs->args[0],
3188 rhs, pc);
3189 rhs_pa = pet_expr_extract_comparison(op, lhs->args[1],
3190 rhs, pc);
3191 return pet_and(lhs_pa, rhs_pa);
3195 lhs_pa = pet_expr_extract_affine(lhs, pc);
3196 rhs_pa = pet_expr_extract_affine(rhs, pc);
3198 return pet_comparison(op, lhs_pa, rhs_pa);
3201 /* Extract an affine expressions from the comparison "expr".
3202 * Return NaN if we are unable to extract such an affine expression.
3204 * "pc" is the context in which the affine expression is created.
3206 static __isl_give isl_pw_aff *extract_comparison(__isl_keep pet_expr *expr,
3207 __isl_keep pet_context *pc)
3209 enum pet_op_type type;
3211 if (!expr)
3212 return NULL;
3213 if (expr->n_arg != 2)
3214 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3215 "expecting two arguments", return NULL);
3217 type = pet_expr_op_get_type(expr);
3218 return pet_expr_extract_comparison(type, expr->args[0], expr->args[1],
3219 pc);
3222 /* Extract an affine expression representing the boolean operation
3223 * expressed by "expr".
3224 * Return NaN if we are unable to extract an affine expression.
3226 * "pc" is the context in which the affine expression is created.
3228 static __isl_give isl_pw_aff *extract_boolean(__isl_keep pet_expr *expr,
3229 __isl_keep pet_context *pc)
3231 isl_pw_aff *lhs, *rhs;
3232 int n;
3234 if (!expr)
3235 return NULL;
3237 n = pet_expr_get_n_arg(expr);
3238 lhs = pet_expr_extract_affine_condition(expr->args[0], pc);
3239 if (n == 1)
3240 return pet_not(lhs);
3242 rhs = pet_expr_extract_affine_condition(expr->args[1], pc);
3243 return pet_boolean(pet_expr_op_get_type(expr), lhs, rhs);
3246 /* Extract the affine expression "expr != 0 ? 1 : 0".
3247 * Return NaN if we are unable to extract an affine expression.
3249 * "pc" is the context in which the affine expression is created.
3251 static __isl_give isl_pw_aff *extract_implicit_condition(
3252 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3254 isl_pw_aff *res;
3256 res = pet_expr_extract_affine(expr, pc);
3257 return pet_to_bool(res);
3260 /* Extract a boolean affine expression from "expr".
3261 * Return NaN if we are unable to extract an affine expression.
3263 * "pc" is the context in which the affine expression is created.
3265 * If "expr" is neither a comparison nor a boolean operation,
3266 * then we assume it is an affine expression and return the
3267 * boolean expression "expr != 0 ? 1 : 0".
3269 __isl_give isl_pw_aff *pet_expr_extract_affine_condition(
3270 __isl_keep pet_expr *expr, __isl_keep pet_context *pc)
3272 if (!expr)
3273 return NULL;
3275 if (pet_expr_is_comparison(expr))
3276 return extract_comparison(expr, pc);
3277 if (pet_expr_is_boolean(expr))
3278 return extract_boolean(expr, pc);
3280 return extract_implicit_condition(expr, pc);
3283 /* Check if "expr" is an assume expression and if its single argument
3284 * can be converted to an affine expression in the context of "pc".
3285 * If so, replace the argument by the affine expression.
3287 __isl_give pet_expr *pet_expr_resolve_assume(__isl_take pet_expr *expr,
3288 __isl_keep pet_context *pc)
3290 isl_pw_aff *cond;
3291 isl_multi_pw_aff *index;
3293 if (!expr)
3294 return NULL;
3295 if (!pet_expr_is_assume(expr))
3296 return expr;
3297 if (expr->n_arg != 1)
3298 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3299 "expecting one argument", return pet_expr_free(expr));
3301 cond = pet_expr_extract_affine_condition(expr->args[0], pc);
3302 if (!cond)
3303 return pet_expr_free(expr);
3304 if (isl_pw_aff_involves_nan(cond)) {
3305 isl_pw_aff_free(cond);
3306 return expr;
3309 index = isl_multi_pw_aff_from_pw_aff(cond);
3310 expr = pet_expr_set_arg(expr, 0, pet_expr_from_index(index));
3312 return expr;
3315 /* Return the number of bits needed to represent the type of "expr".
3316 * See the description of the type_size field of pet_expr.
3318 int pet_expr_get_type_size(__isl_keep pet_expr *expr)
3320 return expr ? expr->type_size : 0;
3323 /* Replace the number of bits needed to represent the type of "expr"
3324 * by "type_size".
3325 * See the description of the type_size field of pet_expr.
3327 __isl_give pet_expr *pet_expr_set_type_size(__isl_take pet_expr *expr,
3328 int type_size)
3330 expr = pet_expr_cow(expr);
3331 if (!expr)
3332 return NULL;
3334 expr->type_size = type_size;
3336 return expr;
3339 /* Extend an access expression "expr" with an additional index "index".
3340 * In particular, add "index" as an extra argument to "expr" and
3341 * adjust the index expression of "expr" to refer to this extra argument.
3342 * The caller is responsible for calling pet_expr_access_set_depth
3343 * to update the corresponding access relation.
3345 * Note that we only collect the individual index expressions as
3346 * arguments of "expr" here.
3347 * An attempt to integrate them into the index expression of "expr"
3348 * is performed in pet_expr_access_plug_in_args.
3350 __isl_give pet_expr *pet_expr_access_subscript(__isl_take pet_expr *expr,
3351 __isl_take pet_expr *index)
3353 int n;
3354 isl_space *space;
3355 isl_local_space *ls;
3356 isl_pw_aff *pa;
3358 expr = pet_expr_cow(expr);
3359 if (!expr || !index)
3360 goto error;
3361 if (expr->type != pet_expr_access)
3362 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3363 "not an access pet_expr", goto error);
3365 n = pet_expr_get_n_arg(expr);
3366 expr = pet_expr_insert_arg(expr, n, index);
3367 if (!expr)
3368 return NULL;
3370 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3371 ls = isl_local_space_from_space(space);
3372 pa = isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, isl_dim_set, n));
3373 expr->acc.index = pet_array_subscript(expr->acc.index, pa);
3374 if (!expr->acc.index)
3375 return pet_expr_free(expr);
3377 return expr;
3378 error:
3379 pet_expr_free(expr);
3380 pet_expr_free(index);
3381 return NULL;
3384 /* Extend an access expression "expr" with an additional member acces to "id".
3385 * In particular, extend the index expression of "expr" to include
3386 * the additional member access.
3387 * The caller is responsible for calling pet_expr_access_set_depth
3388 * to update the corresponding access relation.
3390 __isl_give pet_expr *pet_expr_access_member(__isl_take pet_expr *expr,
3391 __isl_take isl_id *id)
3393 isl_space *space;
3394 isl_multi_pw_aff *field_access;
3396 expr = pet_expr_cow(expr);
3397 if (!expr || !id)
3398 goto error;
3399 if (expr->type != pet_expr_access)
3400 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
3401 "not an access pet_expr", goto error);
3403 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
3404 space = isl_space_from_domain(space);
3405 space = isl_space_set_tuple_id(space, isl_dim_out, id);
3406 field_access = isl_multi_pw_aff_zero(space);
3407 expr->acc.index = pet_array_member(expr->acc.index, field_access);
3408 if (!expr->acc.index)
3409 return pet_expr_free(expr);
3411 return expr;
3412 error:
3413 pet_expr_free(expr);
3414 isl_id_free(id);
3415 return NULL;
3418 void pet_expr_dump_with_indent(__isl_keep pet_expr *expr, int indent)
3420 int i;
3422 if (!expr)
3423 return;
3425 fprintf(stderr, "%*s", indent, "");
3427 switch (expr->type) {
3428 case pet_expr_double:
3429 fprintf(stderr, "%s\n", expr->d.s);
3430 break;
3431 case pet_expr_int:
3432 isl_val_dump(expr->i);
3433 break;
3434 case pet_expr_access:
3435 if (expr->acc.ref_id) {
3436 isl_id_dump(expr->acc.ref_id);
3437 fprintf(stderr, "%*s", indent, "");
3439 isl_multi_pw_aff_dump(expr->acc.index);
3440 fprintf(stderr, "%*sdepth: %d\n", indent + 2,
3441 "", expr->acc.depth);
3442 if (expr->acc.kill) {
3443 fprintf(stderr, "%*skill: 1\n", indent + 2, "");
3444 } else {
3445 fprintf(stderr, "%*sread: %d\n", indent + 2,
3446 "", expr->acc.read);
3447 fprintf(stderr, "%*swrite: %d\n", indent + 2,
3448 "", expr->acc.write);
3450 if (expr->acc.access[pet_expr_access_may_read]) {
3451 fprintf(stderr, "%*smay_read: ", indent + 2, "");
3452 isl_union_map_dump(
3453 expr->acc.access[pet_expr_access_may_read]);
3455 if (expr->acc.access[pet_expr_access_may_write]) {
3456 fprintf(stderr, "%*smay_write: ", indent + 2, "");
3457 isl_union_map_dump(
3458 expr->acc.access[pet_expr_access_may_write]);
3460 if (expr->acc.access[pet_expr_access_must_write]) {
3461 fprintf(stderr, "%*smust_write: ", indent + 2, "");
3462 isl_union_map_dump(
3463 expr->acc.access[pet_expr_access_must_write]);
3465 for (i = 0; i < expr->n_arg; ++i)
3466 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3467 break;
3468 case pet_expr_op:
3469 fprintf(stderr, "%s\n", op_str[expr->op]);
3470 for (i = 0; i < expr->n_arg; ++i)
3471 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3472 break;
3473 case pet_expr_call:
3474 fprintf(stderr, "%s/%d\n", expr->c.name, expr->n_arg);
3475 for (i = 0; i < expr->n_arg; ++i)
3476 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3477 if (expr->c.summary) {
3478 fprintf(stderr, "%*s", indent, "");
3479 fprintf(stderr, "summary:\n");
3480 pet_function_summary_dump_with_indent(expr->c.summary,
3481 indent + 2);
3483 break;
3484 case pet_expr_cast:
3485 fprintf(stderr, "(%s)\n", expr->type_name);
3486 for (i = 0; i < expr->n_arg; ++i)
3487 pet_expr_dump_with_indent(expr->args[i], indent + 2);
3488 break;
3489 case pet_expr_error:
3490 fprintf(stderr, "ERROR\n");
3491 break;
3495 void pet_expr_dump(__isl_keep pet_expr *expr)
3497 pet_expr_dump_with_indent(expr, 0);