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
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
44 #include "value_bounds.h"
46 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
48 static char *type_str
[] = {
49 [pet_expr_access
] = "access",
50 [pet_expr_call
] = "call",
51 [pet_expr_cast
] = "cast",
52 [pet_expr_double
] = "double",
53 [pet_expr_int
] = "int",
57 static char *op_str
[] = {
58 [pet_op_add_assign
] = "+=",
59 [pet_op_sub_assign
] = "-=",
60 [pet_op_mul_assign
] = "*=",
61 [pet_op_div_assign
] = "/=",
62 [pet_op_assign
] = "=",
77 [pet_op_post_inc
] = "++",
78 [pet_op_post_dec
] = "--",
79 [pet_op_pre_inc
] = "++",
80 [pet_op_pre_dec
] = "--",
81 [pet_op_address_of
] = "&",
90 [pet_op_assume
] = "assume",
91 [pet_op_kill
] = "kill"
94 const char *pet_op_str(enum pet_op_type op
)
99 int pet_op_is_inc_dec(enum pet_op_type op
)
101 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
102 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
105 const char *pet_type_str(enum pet_expr_type type
)
107 return type_str
[type
];
110 enum pet_op_type
pet_str_op(const char *str
)
114 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
115 if (!strcmp(op_str
[i
], str
))
121 enum pet_expr_type
pet_str_type(const char *str
)
125 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
126 if (!strcmp(type_str
[i
], str
))
132 /* Construct a pet_expr of the given type.
134 __isl_give pet_expr
*pet_expr_alloc(isl_ctx
*ctx
, enum pet_expr_type type
)
138 expr
= isl_calloc_type(ctx
, struct pet_expr
);
150 /* Construct an access pet_expr from an index expression.
151 * By default, the access is considered to be a read access.
152 * The initial depth is set from the index expression and
153 * may still be updated by the caller before the access relation
156 __isl_give pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
163 ctx
= isl_multi_pw_aff_get_ctx(index
);
164 expr
= pet_expr_alloc(ctx
, pet_expr_access
);
171 expr
= pet_expr_access_set_index(expr
, index
);
175 isl_multi_pw_aff_free(index
);
179 /* Construct an access pet_expr from an access relation and an index expression.
180 * By default, it is considered to be a read access.
182 __isl_give pet_expr
*pet_expr_from_access_and_index(__isl_take isl_map
*access
,
183 __isl_take isl_multi_pw_aff
*index
)
188 expr
= pet_expr_from_index(index
);
189 depth
= isl_map_dim(access
, isl_dim_out
);
190 expr
= pet_expr_access_set_depth(expr
, depth
);
191 return pet_expr_access_set_access(expr
, access
);
194 /* Extend the range of "access" with "n" dimensions, retaining
195 * the tuple identifier on this range.
197 * If "access" represents a member access, then extend the range
200 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
204 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
206 if (!isl_map_range_is_wrapping(access
)) {
207 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
211 domain
= isl_map_copy(access
);
212 domain
= isl_map_range_factor_domain(domain
);
213 access
= isl_map_range_factor_range(access
);
214 access
= extend_range(access
, n
);
215 access
= isl_map_range_product(domain
, access
);
218 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
223 /* Does the access expression "expr" have an explicit access relation?
225 static int has_access_relation(__isl_keep pet_expr
*expr
)
230 if (expr
->acc
.access
)
236 /* Replace the depth of the access expr "expr" by "depth".
238 * To avoid inconsistencies between the depth and the access relation,
239 * we currently do not allow the depth to change once the access relation
240 * has been set or computed.
242 __isl_give pet_expr
*pet_expr_access_set_depth(__isl_take pet_expr
*expr
,
250 if (expr
->acc
.depth
== depth
)
252 if (has_access_relation(expr
))
253 isl_die(pet_expr_get_ctx(expr
), isl_error_unsupported
,
254 "depth cannot be changed after access relation "
255 "has been set or computed", return pet_expr_free(expr
));
257 expr
= pet_expr_cow(expr
);
260 expr
->acc
.depth
= depth
;
265 /* Construct a pet_expr that kills the elements specified by
266 * the index expression "index" and the access relation "access".
268 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
269 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
273 if (!access
|| !index
)
276 expr
= pet_expr_from_access_and_index(access
, index
);
277 expr
= pet_expr_access_set_read(expr
, 0);
278 expr
= pet_expr_access_set_kill(expr
, 1);
279 return pet_expr_new_unary(pet_op_kill
, expr
);
281 isl_map_free(access
);
282 isl_multi_pw_aff_free(index
);
286 /* Construct a unary pet_expr that performs "op" on "arg".
288 __isl_give pet_expr
*pet_expr_new_unary(enum pet_op_type op
,
289 __isl_take pet_expr
*arg
)
296 ctx
= pet_expr_get_ctx(arg
);
297 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
298 expr
= pet_expr_set_n_arg(expr
, 1);
303 expr
->args
[pet_un_arg
] = arg
;
311 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
312 * where the result is represented using a type of "type_size" bits
313 * (may be zero if unknown or if the type is not an integer).
315 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
316 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
323 ctx
= pet_expr_get_ctx(lhs
);
324 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
325 expr
= pet_expr_set_n_arg(expr
, 2);
330 expr
->type_size
= type_size
;
331 expr
->args
[pet_bin_lhs
] = lhs
;
332 expr
->args
[pet_bin_rhs
] = rhs
;
341 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
343 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
344 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
349 if (!cond
|| !lhs
|| !rhs
)
351 ctx
= pet_expr_get_ctx(cond
);
352 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
353 expr
= pet_expr_set_n_arg(expr
, 3);
357 expr
->op
= pet_op_cond
;
358 expr
->args
[pet_ter_cond
] = cond
;
359 expr
->args
[pet_ter_true
] = lhs
;
360 expr
->args
[pet_ter_false
] = rhs
;
370 /* Construct a call pet_expr that calls function "name" with "n_arg"
371 * arguments. The caller is responsible for filling in the arguments.
373 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
378 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
379 expr
= pet_expr_set_n_arg(expr
, n_arg
);
383 expr
->name
= strdup(name
);
385 return pet_expr_free(expr
);
390 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
392 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
393 __isl_take pet_expr
*arg
)
401 ctx
= pet_expr_get_ctx(arg
);
402 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
403 expr
= pet_expr_set_n_arg(expr
, 1);
407 expr
->type_name
= strdup(type_name
);
408 if (!expr
->type_name
)
420 /* Construct a pet_expr that represents the double "d".
422 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
423 double val
, const char *s
)
427 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
432 expr
->d
.s
= strdup(s
);
434 return pet_expr_free(expr
);
439 /* Construct a pet_expr that represents the integer value "v".
441 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
449 ctx
= isl_val_get_ctx(v
);
450 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
462 /* Return an independent duplicate of "expr".
464 * In case of an access expression, make sure the depth of the duplicate is set
465 * before the access relation (if any) is set and after the index expression
468 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
476 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
477 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
478 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
479 for (i
= 0; i
< expr
->n_arg
; ++i
)
480 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
482 switch (expr
->type
) {
483 case pet_expr_access
:
484 if (expr
->acc
.ref_id
)
485 dup
= pet_expr_access_set_ref_id(dup
,
486 isl_id_copy(expr
->acc
.ref_id
));
487 dup
= pet_expr_access_set_index(dup
,
488 isl_multi_pw_aff_copy(expr
->acc
.index
));
489 dup
= pet_expr_access_set_depth(dup
, expr
->acc
.depth
);
490 if (expr
->acc
.access
)
491 dup
= pet_expr_access_set_access(dup
,
492 isl_map_copy(expr
->acc
.access
));
493 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
494 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
495 dup
= pet_expr_access_set_kill(dup
, expr
->acc
.kill
);
498 dup
= pet_expr_call_set_name(dup
, expr
->name
);
501 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
503 case pet_expr_double
:
504 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
507 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
510 dup
= pet_expr_op_set_type(dup
, expr
->op
);
513 dup
= pet_expr_free(dup
);
520 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
528 return pet_expr_dup(expr
);
531 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
540 for (i
= 0; i
< expr
->n_arg
; ++i
)
541 pet_expr_free(expr
->args
[i
]);
544 switch (expr
->type
) {
545 case pet_expr_access
:
546 isl_id_free(expr
->acc
.ref_id
);
547 isl_map_free(expr
->acc
.access
);
548 isl_multi_pw_aff_free(expr
->acc
.index
);
554 free(expr
->type_name
);
556 case pet_expr_double
:
560 isl_val_free(expr
->i
);
567 isl_ctx_deref(expr
->ctx
);
572 /* Return an additional reference to "expr".
574 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
583 /* Return the isl_ctx in which "expr" was created.
585 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
587 return expr
? expr
->ctx
: NULL
;
590 /* Return the type of "expr".
592 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
595 return pet_expr_error
;
599 /* Return the number of arguments of "expr".
601 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
609 /* Set the number of arguments of "expr" to "n".
611 * If "expr" originally had more arguments, then remove the extra arguments.
612 * If "expr" originally had fewer arguments, then create space for
613 * the extra arguments ans initialize them to NULL.
615 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
622 if (expr
->n_arg
== n
)
624 expr
= pet_expr_cow(expr
);
628 if (n
< expr
->n_arg
) {
629 for (i
= n
; i
< expr
->n_arg
; ++i
)
630 pet_expr_free(expr
->args
[i
]);
635 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
637 return pet_expr_free(expr
);
639 for (i
= expr
->n_arg
; i
< n
; ++i
)
640 expr
->args
[i
] = NULL
;
646 /* Return the argument of "expr" at position "pos".
648 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
652 if (pos
< 0 || pos
>= expr
->n_arg
)
653 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
654 "position out of bounds", return NULL
);
656 return pet_expr_copy(expr
->args
[pos
]);
659 /* Replace the argument of "expr" at position "pos" by "arg".
661 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
662 __isl_take pet_expr
*arg
)
666 if (pos
< 0 || pos
>= expr
->n_arg
)
667 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
668 "position out of bounds", goto error
);
669 if (expr
->args
[pos
] == arg
) {
674 expr
= pet_expr_cow(expr
);
678 pet_expr_free(expr
->args
[pos
]);
679 expr
->args
[pos
] = arg
;
688 /* Does "expr" perform a comparison operation?
690 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
694 if (expr
->type
!= pet_expr_op
)
709 /* Does "expr" perform a boolean operation?
711 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
715 if (expr
->type
!= pet_expr_op
)
727 /* Is "expr" an assume statement?
729 int pet_expr_is_assume(__isl_keep pet_expr
*expr
)
733 if (expr
->type
!= pet_expr_op
)
735 return expr
->op
== pet_op_assume
;
738 /* Does "expr" perform a min operation?
740 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
744 if (expr
->type
!= pet_expr_call
)
746 if (expr
->n_arg
!= 2)
748 if (strcmp(expr
->name
, "min") != 0)
753 /* Does "expr" perform a max operation?
755 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
759 if (expr
->type
!= pet_expr_call
)
761 if (expr
->n_arg
!= 2)
763 if (strcmp(expr
->name
, "max") != 0)
768 /* Does "expr" represent an access to an unnamed space, i.e.,
769 * does it represent an affine expression?
771 int pet_expr_is_affine(__isl_keep pet_expr
*expr
)
777 if (expr
->type
!= pet_expr_access
)
780 has_id
= isl_multi_pw_aff_has_tuple_id(expr
->acc
.index
, isl_dim_out
);
787 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
788 * not part of any struct?
790 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
794 if (expr
->type
!= pet_expr_access
)
796 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
))
799 return expr
->acc
.depth
== 0;
802 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
805 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
806 __isl_keep isl_multi_pw_aff
*mpa2
)
810 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
811 if (equal
< 0 || equal
)
813 mpa2
= isl_multi_pw_aff_copy(mpa2
);
814 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
815 isl_multi_pw_aff_get_space(mpa1
));
816 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
817 isl_multi_pw_aff_free(mpa2
);
822 /* Construct an access relation from the index expression and
823 * the array depth of the access expression "expr".
825 * If the number of indices is smaller than the depth of the array,
826 * then we assume that all elements of the remaining dimensions
829 static __isl_give isl_map
*construct_access_relation(__isl_keep pet_expr
*expr
)
838 access
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
842 dim
= isl_map_dim(access
, isl_dim_out
);
843 if (dim
> expr
->acc
.depth
)
844 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
845 "number of indices greater than depth",
846 access
= isl_map_free(access
));
848 if (dim
!= expr
->acc
.depth
)
849 access
= extend_range(access
, expr
->acc
.depth
- dim
);
854 /* Ensure that "expr" has an explicit access relation.
856 * If "expr" does not already have an access relation, then create
857 * one based on the index expression and the array depth.
859 * We do not cow since adding an explicit access relation
860 * does not change the meaning of the expression.
862 static __isl_give pet_expr
*introduce_access_relation(
863 __isl_take pet_expr
*expr
)
870 if (has_access_relation(expr
))
873 access
= construct_access_relation(expr
);
875 return pet_expr_free(expr
);
877 expr
->acc
.access
= access
;
882 /* Return 1 if the two pet_exprs are equivalent.
884 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
888 if (!expr1
|| !expr2
)
891 if (expr1
->type
!= expr2
->type
)
893 if (expr1
->n_arg
!= expr2
->n_arg
)
895 for (i
= 0; i
< expr1
->n_arg
; ++i
)
896 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
898 switch (expr1
->type
) {
901 case pet_expr_double
:
902 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
904 if (expr1
->d
.val
!= expr2
->d
.val
)
908 if (!isl_val_eq(expr1
->i
, expr2
->i
))
911 case pet_expr_access
:
912 if (expr1
->acc
.read
!= expr2
->acc
.read
)
914 if (expr1
->acc
.write
!= expr2
->acc
.write
)
916 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
918 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
920 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
922 if (!multi_pw_aff_is_equal(expr1
->acc
.index
, expr2
->acc
.index
))
924 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
926 if (has_access_relation(expr1
) != has_access_relation(expr2
)) {
928 expr1
= pet_expr_copy(expr1
);
929 expr2
= pet_expr_copy(expr2
);
930 expr1
= introduce_access_relation(expr1
);
931 expr2
= introduce_access_relation(expr2
);
932 equal
= pet_expr_is_equal(expr1
, expr2
);
933 pet_expr_free(expr1
);
934 pet_expr_free(expr2
);
937 if (expr1
->acc
.access
&&
938 !isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
942 if (expr1
->op
!= expr2
->op
)
946 if (strcmp(expr1
->name
, expr2
->name
))
950 if (strcmp(expr1
->type_name
, expr2
->type_name
))
958 /* Does the access expression "expr" read the accessed elements?
960 int pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
964 if (expr
->type
!= pet_expr_access
)
965 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
966 "not an access expression", return -1);
968 return expr
->acc
.read
;
971 /* Does the access expression "expr" write to the accessed elements?
973 int pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
977 if (expr
->type
!= pet_expr_access
)
978 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
979 "not an access expression", return -1);
981 return expr
->acc
.write
;
984 /* Return the identifier of the array accessed by "expr".
986 * If "expr" represents a member access, then return the identifier
987 * of the outer structure array.
989 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
993 if (expr
->type
!= pet_expr_access
)
994 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
995 "not an access expression", return NULL
);
997 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
)) {
1001 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1002 space
= isl_space_range(space
);
1003 while (space
&& isl_space_is_wrapping(space
))
1004 space
= isl_space_domain(isl_space_unwrap(space
));
1005 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
1006 isl_space_free(space
);
1011 return isl_multi_pw_aff_get_tuple_id(expr
->acc
.index
, isl_dim_out
);
1014 /* Return the parameter space of "expr".
1016 __isl_give isl_space
*pet_expr_access_get_parameter_space(
1017 __isl_keep pet_expr
*expr
)
1023 if (expr
->type
!= pet_expr_access
)
1024 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1025 "not an access expression", return NULL
);
1027 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1028 space
= isl_space_params(space
);
1033 /* Return the domain space of "expr", without the arguments (if any).
1035 __isl_give isl_space
*pet_expr_access_get_domain_space(
1036 __isl_keep pet_expr
*expr
)
1042 if (expr
->type
!= pet_expr_access
)
1043 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1044 "not an access expression", return NULL
);
1046 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1047 space
= isl_space_domain(space
);
1048 if (isl_space_is_wrapping(space
))
1049 space
= isl_space_domain(isl_space_unwrap(space
));
1054 /* Return the space of the data accessed by "expr".
1056 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
1062 if (expr
->type
!= pet_expr_access
)
1063 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1064 "not an access expression", return NULL
);
1066 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1067 space
= isl_space_range(space
);
1072 /* Modify all expressions of type pet_expr_access in "expr"
1073 * by calling "fn" on them.
1075 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
1076 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1081 n
= pet_expr_get_n_arg(expr
);
1082 for (i
= 0; i
< n
; ++i
) {
1083 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1084 arg
= pet_expr_map_access(arg
, fn
, user
);
1085 expr
= pet_expr_set_arg(expr
, i
, arg
);
1091 if (expr
->type
== pet_expr_access
)
1092 expr
= fn(expr
, user
);
1097 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1099 * Return -1 on error (where fn returning a negative value is treated as
1101 * Otherwise return 0.
1103 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
1104 enum pet_expr_type type
,
1105 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1112 for (i
= 0; i
< expr
->n_arg
; ++i
)
1113 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
1114 type
, fn
, user
) < 0)
1117 if (expr
->type
== type
)
1118 return fn(expr
, user
);
1123 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1125 * Return -1 on error (where fn returning a negative value is treated as
1127 * Otherwise return 0.
1129 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
1130 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1132 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1135 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1137 * Return -1 on error (where fn returning a negative value is treated as
1139 * Otherwise return 0.
1141 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
1142 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1144 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1147 /* Internal data structure for pet_expr_writes.
1148 * "id" is the identifier that we are looking for.
1149 * "found" is set if we have found the identifier being written to.
1151 struct pet_expr_writes_data
{
1156 /* Given an access expression, check if it writes to data->id.
1157 * If so, set data->found and abort the search.
1159 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1161 struct pet_expr_writes_data
*data
= user
;
1164 if (!expr
->acc
.write
)
1166 if (pet_expr_is_affine(expr
))
1169 write_id
= pet_expr_access_get_id(expr
);
1170 isl_id_free(write_id
);
1175 if (write_id
!= data
->id
)
1182 /* Does expression "expr" write to "id"?
1184 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1186 struct pet_expr_writes_data data
;
1190 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1197 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1198 * index expression and access relation of "expr" (if any)
1199 * to dimensions of "dst_type" at "dst_pos".
1201 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1202 enum isl_dim_type dst_type
, unsigned dst_pos
,
1203 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1205 expr
= pet_expr_cow(expr
);
1208 if (expr
->type
!= pet_expr_access
)
1209 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1210 "not an access pet_expr", return pet_expr_free(expr
));
1212 if (expr
->acc
.access
) {
1213 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
1214 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1215 if (!expr
->acc
.access
)
1217 isl_multi_pw_aff_free(expr
->acc
.index
);
1219 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1220 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1221 if (!expr
->acc
.index
)
1222 return pet_expr_free(expr
);
1227 /* Replace the index expression and access relation (if any) of "expr"
1228 * by their preimages under the function represented by "ma".
1230 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1231 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1233 expr
= pet_expr_cow(expr
);
1236 if (expr
->type
!= pet_expr_access
)
1237 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1238 "not an access pet_expr", goto error
);
1240 if (expr
->acc
.access
) {
1241 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(
1242 expr
->acc
.access
, isl_multi_aff_copy(ma
));
1243 if (!expr
->acc
.access
)
1245 isl_multi_pw_aff_free(expr
->acc
.index
);
1247 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1249 if (!expr
->acc
.index
)
1250 return pet_expr_free(expr
);
1254 isl_multi_aff_free(ma
);
1255 pet_expr_free(expr
);
1259 /* Replace the index expression and access relation (if any) of "expr"
1260 * by their preimages under the function represented by "mpa".
1262 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1263 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1265 expr
= pet_expr_cow(expr
);
1268 if (expr
->type
!= pet_expr_access
)
1269 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1270 "not an access pet_expr", goto error
);
1272 if (expr
->acc
.access
) {
1273 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1274 expr
->acc
.access
, isl_multi_pw_aff_copy(mpa
));
1275 if (!expr
->acc
.access
)
1277 isl_multi_pw_aff_free(expr
->acc
.index
);
1279 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1280 expr
->acc
.index
, mpa
);
1281 if (!expr
->acc
.index
)
1282 return pet_expr_free(expr
);
1286 isl_multi_pw_aff_free(mpa
);
1287 pet_expr_free(expr
);
1291 /* Return the index expression of access expression "expr".
1293 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1294 __isl_keep pet_expr
*expr
)
1298 if (expr
->type
!= pet_expr_access
)
1299 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1300 "not an access expression", return NULL
);
1302 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1305 /* Align the parameters of expr->acc.index and expr->acc.access (if set).
1307 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1309 expr
= pet_expr_cow(expr
);
1312 if (expr
->type
!= pet_expr_access
)
1313 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1314 "not an access expression", return pet_expr_free(expr
));
1316 if (!has_access_relation(expr
))
1319 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1320 isl_multi_pw_aff_get_space(expr
->acc
.index
));
1321 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1322 isl_map_get_space(expr
->acc
.access
));
1323 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1324 return pet_expr_free(expr
);
1329 /* Are "expr1" and "expr2" both array accesses such that
1330 * the access relation of "expr1" is a subset of that of "expr2"?
1331 * Only take into account the first "n_arg" arguments.
1333 * This function is tailored for use by mark_self_dependences in nest.c.
1334 * In particular, the input expressions may have more than "n_arg"
1335 * elements in their arguments arrays, while only the first "n_arg"
1336 * elements are referenced from the access relations.
1338 int pet_expr_is_sub_access(__isl_keep pet_expr
*expr1
,
1339 __isl_keep pet_expr
*expr2
, int n_arg
)
1345 if (!expr1
|| !expr2
)
1347 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1349 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1351 if (pet_expr_is_affine(expr1
))
1353 if (pet_expr_is_affine(expr2
))
1355 n1
= pet_expr_get_n_arg(expr1
);
1358 n2
= pet_expr_get_n_arg(expr2
);
1363 for (i
= 0; i
< n1
; ++i
) {
1365 equal
= pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]);
1366 if (equal
< 0 || !equal
)
1369 id1
= pet_expr_access_get_id(expr1
);
1370 id2
= pet_expr_access_get_id(expr2
);
1378 expr1
= pet_expr_copy(expr1
);
1379 expr2
= pet_expr_copy(expr2
);
1380 expr1
= introduce_access_relation(expr1
);
1381 expr2
= introduce_access_relation(expr2
);
1382 if (!expr1
|| !expr2
)
1385 is_subset
= isl_map_is_subset(expr1
->acc
.access
, expr2
->acc
.access
);
1387 pet_expr_free(expr1
);
1388 pet_expr_free(expr2
);
1392 pet_expr_free(expr1
);
1393 pet_expr_free(expr2
);
1397 /* Given a set in the iteration space "domain", extend it to live in the space
1398 * of the domain of access relations.
1400 * That, is the number of arguments "n" is 0, then simply return domain.
1401 * Otherwise, return [domain -> [a_1,...,a_n]].
1403 static __isl_give isl_set
*add_arguments(__isl_take isl_set
*domain
, int n
)
1410 map
= isl_map_from_domain(domain
);
1411 map
= isl_map_add_dims(map
, isl_dim_out
, n
);
1412 return isl_map_wrap(map
);
1415 /* Add extra conditions to the domains of all access relations in "expr",
1416 * introducing access relations if they are not already present.
1418 * The conditions are not added to the index expression. Instead, they
1419 * are used to try and simplify the index expression.
1421 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1422 __isl_take isl_set
*cond
)
1426 expr
= pet_expr_cow(expr
);
1430 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1431 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1432 isl_set_copy(cond
));
1437 if (expr
->type
!= pet_expr_access
) {
1442 expr
= introduce_access_relation(expr
);
1446 cond
= add_arguments(cond
, expr
->n_arg
);
1447 expr
->acc
.access
= isl_map_intersect_domain(expr
->acc
.access
,
1448 isl_set_copy(cond
));
1449 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, cond
);
1450 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1451 return pet_expr_free(expr
);
1456 return pet_expr_free(expr
);
1459 /* Modify the access relation (if any) and index expression
1460 * of the given access expression
1461 * based on the given iteration space transformation.
1462 * In particular, precompose the access relation and index expression
1463 * with the update function.
1465 * If the access has any arguments then the domain of the access relation
1466 * is a wrapped mapping from the iteration space to the space of
1467 * argument values. We only need to change the domain of this wrapped
1468 * mapping, so we extend the input transformation with an identity mapping
1469 * on the space of argument values.
1471 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1472 __isl_keep isl_multi_pw_aff
*update
)
1474 expr
= pet_expr_cow(expr
);
1477 if (expr
->type
!= pet_expr_access
)
1478 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1479 "not an access expression", return pet_expr_free(expr
));
1481 update
= isl_multi_pw_aff_copy(update
);
1483 if (expr
->n_arg
> 0) {
1485 isl_multi_pw_aff
*id
;
1487 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1488 space
= isl_space_domain(space
);
1489 space
= isl_space_unwrap(space
);
1490 space
= isl_space_range(space
);
1491 space
= isl_space_map_from_set(space
);
1492 id
= isl_multi_pw_aff_identity(space
);
1493 update
= isl_multi_pw_aff_product(update
, id
);
1496 if (expr
->acc
.access
) {
1497 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1499 isl_multi_pw_aff_copy(update
));
1500 if (!expr
->acc
.access
)
1502 isl_multi_pw_aff_free(expr
->acc
.index
);
1504 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1505 expr
->acc
.index
, update
);
1506 if (!expr
->acc
.index
)
1507 return pet_expr_free(expr
);
1512 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1514 isl_multi_pw_aff
*update
= user
;
1516 return pet_expr_access_update_domain(expr
, update
);
1519 /* Modify all access relations in "expr" by precomposing them with
1520 * the given iteration space transformation.
1522 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1523 __isl_take isl_multi_pw_aff
*update
)
1525 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1526 isl_multi_pw_aff_free(update
);
1530 /* Given an expression with accesses that have a 0D anonymous domain,
1531 * replace those domains by "space".
1533 __isl_give pet_expr
*pet_expr_insert_domain(__isl_take pet_expr
*expr
,
1534 __isl_take isl_space
*space
)
1536 isl_multi_pw_aff
*mpa
;
1538 space
= isl_space_from_domain(space
);
1539 mpa
= isl_multi_pw_aff_zero(space
);
1540 return pet_expr_update_domain(expr
, mpa
);
1543 /* Add all parameters in "space" to the access relation (if any)
1544 * and index expression of "expr".
1546 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1548 isl_space
*space
= user
;
1550 expr
= pet_expr_cow(expr
);
1553 if (expr
->type
!= pet_expr_access
)
1554 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1555 "not an access expression", return pet_expr_free(expr
));
1557 if (expr
->acc
.access
) {
1558 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1559 isl_space_copy(space
));
1560 if (!expr
->acc
.access
)
1562 isl_multi_pw_aff_free(expr
->acc
.index
);
1564 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1565 isl_space_copy(space
));
1566 if (!expr
->acc
.index
)
1567 return pet_expr_free(expr
);
1572 /* Add all parameters in "space" to all access relations and index expressions
1575 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1576 __isl_take isl_space
*space
)
1578 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1579 isl_space_free(space
);
1583 /* Insert an argument expression corresponding to "test" in front
1584 * of the list of arguments described by *n_arg and *args.
1586 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1587 __isl_keep isl_multi_pw_aff
*test
)
1590 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1593 return pet_expr_free(expr
);
1594 expr
= pet_expr_cow(expr
);
1599 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1601 return pet_expr_free(expr
);
1604 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1606 return pet_expr_free(expr
);
1607 for (i
= 0; i
< expr
->n_arg
; ++i
)
1608 ext
[1 + i
] = expr
->args
[i
];
1613 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1615 return pet_expr_free(expr
);
1620 /* Make the expression "expr" depend on the value of "test"
1621 * being equal to "satisfied".
1623 * If "test" is an affine expression, we simply add the conditions
1624 * on the expression having the value "satisfied" to all access relations
1625 * (introducing access relations if they are missing) and index expressions.
1627 * Otherwise, we add a filter to "expr" (which is then assumed to be
1628 * an access expression) corresponding to "test" being equal to "satisfied".
1630 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1631 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1636 isl_pw_multi_aff
*pma
;
1638 expr
= pet_expr_cow(expr
);
1642 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1646 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
1647 isl_multi_pw_aff_free(test
);
1649 cond
= isl_pw_aff_non_zero_set(pa
);
1651 cond
= isl_pw_aff_zero_set(pa
);
1652 return pet_expr_restrict(expr
, cond
);
1655 ctx
= isl_multi_pw_aff_get_ctx(test
);
1656 if (expr
->type
!= pet_expr_access
)
1657 isl_die(ctx
, isl_error_invalid
,
1658 "can only filter access expressions", goto error
);
1660 expr
= introduce_access_relation(expr
);
1664 space
= isl_space_domain(isl_multi_pw_aff_get_space(expr
->acc
.index
));
1665 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1666 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
1668 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
1670 isl_pw_multi_aff_copy(pma
));
1671 pma
= isl_pw_multi_aff_gist(pma
,
1672 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
)));
1673 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
1674 expr
->acc
.index
, pma
);
1675 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1678 expr
= insert_access_arg(expr
, test
);
1680 isl_multi_pw_aff_free(test
);
1683 isl_multi_pw_aff_free(test
);
1684 return pet_expr_free(expr
);
1687 /* Add a reference identifier to access expression "expr".
1688 * "user" points to an integer that contains the sequence number
1689 * of the next reference.
1691 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
1698 expr
= pet_expr_cow(expr
);
1701 if (expr
->type
!= pet_expr_access
)
1702 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1703 "not an access expression", return pet_expr_free(expr
));
1705 ctx
= pet_expr_get_ctx(expr
);
1706 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1707 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1708 if (!expr
->acc
.ref_id
)
1709 return pet_expr_free(expr
);
1714 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
1716 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1719 /* Reset the user pointer on all parameter and tuple ids in
1720 * the access relation (if any) and the index expression
1721 * of the access expression "expr".
1723 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
1726 expr
= pet_expr_cow(expr
);
1729 if (expr
->type
!= pet_expr_access
)
1730 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1731 "not an access expression", return pet_expr_free(expr
));
1733 if (expr
->acc
.access
) {
1734 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1735 if (!expr
->acc
.access
)
1737 isl_multi_pw_aff_free(expr
->acc
.index
);
1739 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1740 if (!expr
->acc
.index
)
1741 return pet_expr_free(expr
);
1746 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
1748 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1751 /* Data used in access_gist() callback.
1753 struct pet_access_gist_data
{
1755 isl_union_map
*value_bounds
;
1758 /* Given an expression "expr" of type pet_expr_access, compute
1759 * the gist of the associated access relation (if any) and index expression
1760 * with respect to data->domain and the bounds on the values of the arguments
1761 * of the expression.
1763 * The arguments of "expr" have been gisted right before "expr" itself
1764 * is gisted. The gisted arguments may have become equal where before
1765 * they may not have been (obviously) equal. We therefore take
1766 * the opportunity to remove duplicate arguments here.
1768 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
1770 struct pet_access_gist_data
*data
= user
;
1773 expr
= pet_expr_remove_duplicate_args(expr
);
1774 expr
= pet_expr_cow(expr
);
1777 if (expr
->type
!= pet_expr_access
)
1778 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1779 "not an access expression", return pet_expr_free(expr
));
1781 domain
= isl_set_copy(data
->domain
);
1782 if (expr
->n_arg
> 0)
1783 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1784 data
->value_bounds
);
1786 if (expr
->acc
.access
) {
1787 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1788 isl_set_copy(domain
));
1789 if (!expr
->acc
.access
)
1791 isl_multi_pw_aff_free(expr
->acc
.index
);
1793 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1794 if (!expr
->acc
.index
)
1795 return pet_expr_free(expr
);
1800 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
1801 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1803 struct pet_access_gist_data data
= { context
, value_bounds
};
1805 return pet_expr_map_access(expr
, &access_gist
, &data
);
1808 /* Mark "expr" as a read dependening on "read".
1810 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
1814 return pet_expr_free(expr
);
1815 if (expr
->type
!= pet_expr_access
)
1816 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1817 "not an access expression", return pet_expr_free(expr
));
1818 if (expr
->acc
.read
== read
)
1820 expr
= pet_expr_cow(expr
);
1823 expr
->acc
.read
= read
;
1828 /* Mark "expr" as a write dependening on "write".
1830 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
1834 return pet_expr_free(expr
);
1835 if (expr
->type
!= pet_expr_access
)
1836 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1837 "not an access expression", return pet_expr_free(expr
));
1838 if (expr
->acc
.write
== write
)
1840 expr
= pet_expr_cow(expr
);
1843 expr
->acc
.write
= write
;
1848 /* Mark "expr" as a kill dependening on "kill".
1850 __isl_give pet_expr
*pet_expr_access_set_kill(__isl_take pet_expr
*expr
,
1854 return pet_expr_free(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
));
1858 if (expr
->acc
.kill
== kill
)
1860 expr
= pet_expr_cow(expr
);
1863 expr
->acc
.kill
= kill
;
1868 /* Replace the access relation of "expr" by "access".
1870 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
1871 __isl_take isl_map
*access
)
1873 expr
= pet_expr_cow(expr
);
1874 if (!expr
|| !access
)
1876 if (expr
->type
!= pet_expr_access
)
1877 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1878 "not an access expression", goto error
);
1879 isl_map_free(expr
->acc
.access
);
1880 expr
->acc
.access
= access
;
1884 isl_map_free(access
);
1885 pet_expr_free(expr
);
1889 /* Replace the index expression of "expr" by "index" and
1890 * set the array depth accordingly.
1892 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
1893 __isl_take isl_multi_pw_aff
*index
)
1895 expr
= pet_expr_cow(expr
);
1896 if (!expr
|| !index
)
1898 if (expr
->type
!= pet_expr_access
)
1899 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1900 "not an access expression", goto error
);
1901 isl_multi_pw_aff_free(expr
->acc
.index
);
1902 expr
->acc
.index
= index
;
1903 expr
->acc
.depth
= isl_multi_pw_aff_dim(index
, isl_dim_out
);
1907 isl_multi_pw_aff_free(index
);
1908 pet_expr_free(expr
);
1912 /* Return the reference identifier of access expression "expr".
1914 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
1918 if (expr
->type
!= pet_expr_access
)
1919 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1920 "not an access expression", return NULL
);
1922 return isl_id_copy(expr
->acc
.ref_id
);
1925 /* Replace the reference identifier of access expression "expr" by "ref_id".
1927 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
1928 __isl_take isl_id
*ref_id
)
1930 expr
= pet_expr_cow(expr
);
1931 if (!expr
|| !ref_id
)
1933 if (expr
->type
!= pet_expr_access
)
1934 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1935 "not an access expression", goto error
);
1936 isl_id_free(expr
->acc
.ref_id
);
1937 expr
->acc
.ref_id
= ref_id
;
1941 isl_id_free(ref_id
);
1942 pet_expr_free(expr
);
1946 /* Tag the access relation "access" with "id".
1947 * That is, insert the id as the range of a wrapped relation
1948 * in the domain of "access".
1950 * If "access" is of the form
1954 * then the result is of the form
1956 * [D[i] -> id[]] -> A[a]
1958 __isl_give isl_union_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
1959 __isl_take isl_union_map
*access
)
1962 isl_multi_aff
*add_tag
;
1965 if (expr
->type
!= pet_expr_access
)
1966 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1967 "not an access expression",
1968 return isl_union_map_free(access
));
1970 id
= isl_id_copy(expr
->acc
.ref_id
);
1971 space
= pet_expr_access_get_domain_space(expr
);
1972 space
= isl_space_from_domain(space
);
1973 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
1974 add_tag
= isl_multi_aff_domain_map(space
);
1975 access
= isl_union_map_preimage_domain_multi_aff(access
, add_tag
);
1980 /* Return the relation mapping pairs of domain iterations and argument
1981 * values to the corresponding accessed data elements.
1983 static __isl_give isl_map
*pet_expr_access_get_dependent_access(
1984 __isl_keep pet_expr
*expr
)
1990 if (expr
->type
!= pet_expr_access
)
1991 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1992 "not an access expression", return NULL
);
1994 if (expr
->acc
.access
)
1995 return isl_map_copy(expr
->acc
.access
);
1997 expr
= pet_expr_copy(expr
);
1998 expr
= introduce_access_relation(expr
);
2001 access
= isl_map_copy(expr
->acc
.access
);
2002 pet_expr_free(expr
);
2007 /* Return an empty access relation for access expression "expr".
2009 static __isl_give isl_union_map
*empty_access_relation(
2010 __isl_keep pet_expr
*expr
)
2012 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr
));
2015 /* Return the may read access relation associated to "expr"
2016 * that maps pairs of domain iterations and argument values
2017 * to the corresponding accessed data elements.
2019 * Since the accesses are currently represented by a single access relation,
2020 * we return the entire access relation if "expr" is a read and
2021 * an empty relation if it is not.
2023 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_read(
2024 __isl_keep pet_expr
*expr
)
2030 if (!pet_expr_access_is_read(expr
))
2031 return empty_access_relation(expr
);
2032 access
= pet_expr_access_get_dependent_access(expr
);
2033 return isl_union_map_from_map(access
);
2036 /* Return the may write access relation associated to "expr"
2037 * that maps pairs of domain iterations and argument values
2038 * to the corresponding accessed data elements.
2040 * Since the accesses are currently represented by a single access relation,
2041 * we return the entire access relation if "expr" is a write and
2042 * an empty relation if it is not.
2044 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_write(
2045 __isl_keep pet_expr
*expr
)
2051 if (!pet_expr_access_is_write(expr
))
2052 return empty_access_relation(expr
);
2053 access
= pet_expr_access_get_dependent_access(expr
);
2054 return isl_union_map_from_map(access
);
2057 /* Return the must write access relation associated to "expr"
2058 * that maps pairs of domain iterations and argument values
2059 * to the corresponding accessed data elements.
2061 * Since the accesses are currently represented by a single access relation,
2062 * we return the entire access relation when "expr" is a write.
2064 __isl_give isl_union_map
*pet_expr_access_get_dependent_must_write(
2065 __isl_keep pet_expr
*expr
)
2071 if (!pet_expr_access_is_write(expr
))
2072 return empty_access_relation(expr
);
2073 access
= pet_expr_access_get_dependent_access(expr
);
2074 return isl_union_map_from_map(access
);
2077 /* Return the relation mapping domain iterations to all possibly
2078 * accessed data elements.
2079 * In particular, take the access relation and project out the values
2080 * of the arguments, if any.
2082 __isl_give isl_map
*pet_expr_access_get_may_access(__isl_keep pet_expr
*expr
)
2090 if (expr
->type
!= pet_expr_access
)
2091 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2092 "not an access expression", return NULL
);
2094 access
= pet_expr_access_get_dependent_access(expr
);
2095 if (expr
->n_arg
== 0)
2098 space
= isl_space_domain(isl_map_get_space(access
));
2099 map
= isl_map_universe(isl_space_unwrap(space
));
2100 map
= isl_map_domain_map(map
);
2101 access
= isl_map_apply_domain(access
, map
);
2106 /* Return the relation mapping domain iterations to all possibly
2107 * read data elements.
2109 * Since the accesses are currently represented by a single access relation,
2110 * we return the may access relation if "expr" is a read and
2111 * an empty relation if it is not.
2113 __isl_give isl_union_map
*pet_expr_access_get_may_read(
2114 __isl_keep pet_expr
*expr
)
2118 if (!pet_expr_access_is_read(expr
))
2119 return empty_access_relation(expr
);
2120 return isl_union_map_from_map(pet_expr_access_get_may_access(expr
));
2123 /* Return the relation mapping domain iterations to all possibly
2124 * written data elements.
2126 * Since the accesses are currently represented by a single access relation,
2127 * we return the may access relation if "expr" is a write and
2128 * an empty relation if it is not.
2130 __isl_give isl_union_map
*pet_expr_access_get_may_write(
2131 __isl_keep pet_expr
*expr
)
2135 if (!pet_expr_access_is_write(expr
))
2136 return empty_access_relation(expr
);
2137 return isl_union_map_from_map(pet_expr_access_get_may_access(expr
));
2140 /* Return a relation mapping domain iterations to definitely
2141 * accessed data elements, assuming the statement containing
2142 * the expression is executed.
2144 * If there are no arguments, then all elements are accessed.
2145 * Otherwise, we conservatively return an empty relation.
2147 static __isl_give isl_map
*pet_expr_access_get_must_access(
2148 __isl_keep pet_expr
*expr
)
2154 if (expr
->type
!= pet_expr_access
)
2155 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2156 "not an access expression", return NULL
);
2158 if (expr
->n_arg
== 0)
2159 return pet_expr_access_get_dependent_access(expr
);
2161 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
2162 space
= isl_space_domain_factor_domain(space
);
2164 return isl_map_empty(space
);
2167 /* Return a relation mapping domain iterations to definitely
2168 * written data elements, assuming the statement containing
2169 * the expression is executed.
2171 * Since the accesses are currently represented by a single access relation,
2172 * we return the must access relation if "expr" is a write and
2173 * an empty relation if it is not.
2175 __isl_give isl_union_map
*pet_expr_access_get_must_write(
2176 __isl_keep pet_expr
*expr
)
2180 if (!pet_expr_access_is_write(expr
))
2181 return empty_access_relation(expr
);
2182 return isl_union_map_from_map(pet_expr_access_get_must_access(expr
));
2185 /* Return the relation mapping domain iterations to all possibly
2186 * read data elements, with its domain tagged with the reference
2189 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_read(
2190 __isl_keep pet_expr
*expr
)
2192 isl_union_map
*access
;
2197 access
= pet_expr_access_get_may_read(expr
);
2198 access
= pet_expr_tag_access(expr
, access
);
2203 /* Return the relation mapping domain iterations to all possibly
2204 * written data elements, with its domain tagged with the reference
2207 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_write(
2208 __isl_keep pet_expr
*expr
)
2210 isl_union_map
*access
;
2215 access
= pet_expr_access_get_may_write(expr
);
2216 access
= pet_expr_tag_access(expr
, access
);
2221 /* Return the operation type of operation expression "expr".
2223 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
2227 if (expr
->type
!= pet_expr_op
)
2228 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2229 "not an operation expression", return pet_op_last
);
2234 /* Replace the operation type of operation expression "expr" by "type".
2236 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
2237 enum pet_op_type type
)
2240 return pet_expr_free(expr
);
2241 if (expr
->type
!= pet_expr_op
)
2242 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2243 "not an operation expression",
2244 return pet_expr_free(expr
));
2245 if (expr
->op
== type
)
2247 expr
= pet_expr_cow(expr
);
2255 /* Return the name of the function called by "expr".
2257 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
2261 if (expr
->type
!= pet_expr_call
)
2262 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2263 "not a call expression", return NULL
);
2267 /* Replace the name of the function called by "expr" by "name".
2269 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
2270 __isl_keep
const char *name
)
2272 expr
= pet_expr_cow(expr
);
2274 return pet_expr_free(expr
);
2275 if (expr
->type
!= pet_expr_call
)
2276 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2277 "not a call expression", return pet_expr_free(expr
));
2279 expr
->name
= strdup(name
);
2281 return pet_expr_free(expr
);
2285 /* Replace the type of the cast performed by "expr" by "name".
2287 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
2288 __isl_keep
const char *name
)
2290 expr
= pet_expr_cow(expr
);
2292 return pet_expr_free(expr
);
2293 if (expr
->type
!= pet_expr_cast
)
2294 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2295 "not a cast expression", return pet_expr_free(expr
));
2296 free(expr
->type_name
);
2297 expr
->type_name
= strdup(name
);
2298 if (!expr
->type_name
)
2299 return pet_expr_free(expr
);
2303 /* Return the value of the integer represented by "expr".
2305 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
2309 if (expr
->type
!= pet_expr_int
)
2310 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2311 "not an int expression", return NULL
);
2313 return isl_val_copy(expr
->i
);
2316 /* Replace the value of the integer represented by "expr" by "v".
2318 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
2319 __isl_take isl_val
*v
)
2321 expr
= pet_expr_cow(expr
);
2324 if (expr
->type
!= pet_expr_int
)
2325 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2326 "not an int expression", goto error
);
2327 isl_val_free(expr
->i
);
2333 pet_expr_free(expr
);
2337 /* Replace the value and string representation of the double
2338 * represented by "expr" by "d" and "s".
2340 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
2341 double d
, __isl_keep
const char *s
)
2343 expr
= pet_expr_cow(expr
);
2345 return pet_expr_free(expr
);
2346 if (expr
->type
!= pet_expr_double
)
2347 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2348 "not a double expression", return pet_expr_free(expr
));
2351 expr
->d
.s
= strdup(s
);
2353 return pet_expr_free(expr
);
2357 /* Return a string representation of the double expression "expr".
2359 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2363 if (expr
->type
!= pet_expr_double
)
2364 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2365 "not a double expression", return NULL
);
2366 return strdup(expr
->d
.s
);
2369 /* Return a piecewise affine expression defined on the specified domain
2370 * that represents NaN.
2372 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2374 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2377 /* This function is called when we come across an access that is
2378 * nested in what is supposed to be an affine expression.
2379 * "pc" is the context in which the affine expression is created.
2380 * If nesting is allowed in "pc", we return an affine expression that is
2381 * equal to a new parameter corresponding to this nested access.
2382 * Otherwise, we return NaN.
2384 * Note that we currently don't allow nested accesses themselves
2385 * to contain any nested accesses, so we check if "expr" itself
2386 * involves any nested accesses (either explicitly as arguments
2387 * or implicitly through parameters) and return NaN if it does.
2389 * The new parameter is resolved in resolve_nested.
2391 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2392 __isl_keep pet_context
*pc
)
2397 isl_local_space
*ls
;
2403 if (!pet_context_allow_nesting(pc
))
2404 return non_affine(pet_context_get_space(pc
));
2406 if (pet_expr_get_type(expr
) != pet_expr_access
)
2407 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2408 "not an access expression", return NULL
);
2410 if (expr
->n_arg
> 0)
2411 return non_affine(pet_context_get_space(pc
));
2413 space
= pet_expr_access_get_parameter_space(expr
);
2414 nested
= pet_nested_any_in_space(space
);
2415 isl_space_free(space
);
2417 return non_affine(pet_context_get_space(pc
));
2419 ctx
= pet_expr_get_ctx(expr
);
2420 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2421 space
= pet_context_get_space(pc
);
2422 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2424 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2425 ls
= isl_local_space_from_space(space
);
2426 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2428 return isl_pw_aff_from_aff(aff
);
2431 /* Extract an affine expression from the access pet_expr "expr".
2432 * "pc" is the context in which the affine expression is created.
2434 * If "expr" is actually an affine expression rather than
2435 * a real access, then we return that expression.
2436 * Otherwise, we require that "expr" is of an integral type.
2437 * If not, we return NaN.
2439 * If the variable has been assigned a known affine expression,
2440 * then we return that expression.
2442 * Otherwise, we return an expression that is equal to a parameter
2443 * representing "expr" (if "allow_nested" is set).
2445 static __isl_give isl_pw_aff
*extract_affine_from_access(
2446 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2451 if (pet_expr_is_affine(expr
)) {
2453 isl_multi_pw_aff
*mpa
;
2455 mpa
= pet_expr_access_get_index(expr
);
2456 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
2457 isl_multi_pw_aff_free(mpa
);
2461 if (pet_expr_get_type_size(expr
) == 0)
2462 return non_affine(pet_context_get_space(pc
));
2464 if (!pet_expr_is_scalar_access(expr
))
2465 return nested_access(expr
, pc
);
2467 id
= pet_expr_access_get_id(expr
);
2468 if (pet_context_is_assigned(pc
, id
))
2469 return pet_context_get_value(pc
, id
);
2472 return nested_access(expr
, pc
);
2475 /* Construct an affine expression from the integer constant "expr".
2476 * "pc" is the context in which the affine expression is created.
2478 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2479 __isl_keep pet_context
*pc
)
2481 isl_local_space
*ls
;
2487 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2488 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2490 return isl_pw_aff_from_aff(aff
);
2493 /* Extract an affine expression from an addition or subtraction operation.
2494 * Return NaN if we are unable to extract an affine expression.
2496 * "pc" is the context in which the affine expression is created.
2498 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2499 __isl_keep pet_context
*pc
)
2506 if (expr
->n_arg
!= 2)
2507 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2508 "expecting two arguments", return NULL
);
2510 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2511 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2513 switch (pet_expr_op_get_type(expr
)) {
2515 return isl_pw_aff_add(lhs
, rhs
);
2517 return isl_pw_aff_sub(lhs
, rhs
);
2519 isl_pw_aff_free(lhs
);
2520 isl_pw_aff_free(rhs
);
2521 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2522 "not an addition or subtraction operation",
2528 /* Extract an affine expression from an integer division or a modulo operation.
2529 * Return NaN if we are unable to extract an affine expression.
2531 * "pc" is the context in which the affine expression is created.
2533 * In particular, if "expr" is lhs/rhs, then return
2535 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2537 * If "expr" is lhs%rhs, then return
2539 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2541 * If the second argument (rhs) is not a (positive) integer constant,
2542 * then we fail to extract an affine expression.
2544 * We simplify the result in the context of the domain of "pc" in case
2545 * this domain implies that lhs >= 0 (or < 0).
2547 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2548 __isl_keep pet_context
*pc
)
2557 if (expr
->n_arg
!= 2)
2558 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2559 "expecting two arguments", return NULL
);
2561 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2563 is_cst
= isl_pw_aff_is_cst(rhs
);
2564 if (is_cst
< 0 || !is_cst
) {
2565 isl_pw_aff_free(rhs
);
2566 return non_affine(pet_context_get_space(pc
));
2569 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2571 switch (pet_expr_op_get_type(expr
)) {
2573 res
= isl_pw_aff_tdiv_q(lhs
, rhs
);
2576 res
= isl_pw_aff_tdiv_r(lhs
, rhs
);
2579 isl_pw_aff_free(lhs
);
2580 isl_pw_aff_free(rhs
);
2581 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2582 "not a div or mod operator", return NULL
);
2585 return isl_pw_aff_gist(res
, pet_context_get_gist_domain(pc
));
2588 /* Extract an affine expression from a multiplication operation.
2589 * Return NaN if we are unable to extract an affine expression.
2590 * In particular, if neither of the arguments is a (piecewise) constant
2591 * then we return NaN.
2593 * "pc" is the context in which the affine expression is created.
2595 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2596 __isl_keep pet_context
*pc
)
2598 int lhs_cst
, rhs_cst
;
2604 if (expr
->n_arg
!= 2)
2605 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2606 "expecting two arguments", return NULL
);
2608 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2609 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2611 lhs_cst
= isl_pw_aff_is_cst(lhs
);
2612 rhs_cst
= isl_pw_aff_is_cst(rhs
);
2613 if (lhs_cst
< 0 || rhs_cst
< 0 || (!lhs_cst
&& !rhs_cst
)) {
2614 isl_pw_aff_free(lhs
);
2615 isl_pw_aff_free(rhs
);
2616 return non_affine(pet_context_get_space(pc
));
2619 return isl_pw_aff_mul(lhs
, rhs
);
2622 /* Extract an affine expression from a negation operation.
2623 * Return NaN if we are unable to extract an affine expression.
2625 * "pc" is the context in which the affine expression is created.
2627 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
2628 __isl_keep pet_context
*pc
)
2634 if (expr
->n_arg
!= 1)
2635 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2636 "expecting one argument", return NULL
);
2638 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
2639 return isl_pw_aff_neg(res
);
2642 /* Extract an affine expression from a conditional operation.
2643 * Return NaN if we are unable to extract an affine expression.
2645 * "pc" is the context in which the affine expression is created.
2647 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
2648 __isl_keep pet_context
*pc
)
2650 isl_pw_aff
*cond
, *lhs
, *rhs
;
2654 if (expr
->n_arg
!= 3)
2655 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2656 "expecting three arguments", return NULL
);
2658 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2659 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2660 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
2662 return isl_pw_aff_cond(cond
, lhs
, rhs
);
2669 static __isl_give isl_pw_aff
*wrap(__isl_take isl_pw_aff
*pwaff
, unsigned width
)
2674 ctx
= isl_pw_aff_get_ctx(pwaff
);
2675 mod
= isl_val_int_from_ui(ctx
, width
);
2676 mod
= isl_val_2exp(mod
);
2678 pwaff
= isl_pw_aff_mod_val(pwaff
, mod
);
2683 /* Limit the domain of "pwaff" to those elements where the function
2686 * 2^{width-1} <= pwaff < 2^{width-1}
2688 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
2693 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
2694 isl_local_space
*ls
= isl_local_space_from_space(space
);
2699 ctx
= isl_pw_aff_get_ctx(pwaff
);
2700 v
= isl_val_int_from_ui(ctx
, width
- 1);
2701 v
= isl_val_2exp(v
);
2703 bound
= isl_aff_zero_on_domain(ls
);
2704 bound
= isl_aff_add_constant_val(bound
, v
);
2705 b
= isl_pw_aff_from_aff(bound
);
2707 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
2708 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2710 b
= isl_pw_aff_neg(b
);
2711 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
2712 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2717 /* Handle potential overflows on signed computations.
2719 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2720 * then we adjust the domain of "pa" to avoid overflows.
2722 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
2726 struct pet_options
*options
;
2731 ctx
= isl_pw_aff_get_ctx(pa
);
2732 options
= isl_ctx_peek_pet_options(ctx
);
2733 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
2734 pa
= avoid_overflow(pa
, width
);
2739 /* Extract an affine expression from some an operation.
2740 * Return NaN if we are unable to extract an affine expression.
2741 * If the result of a binary (non boolean) operation is unsigned,
2742 * then we wrap it based on the size of the type. If the result is signed,
2743 * then we ensure that no overflow occurs.
2745 * "pc" is the context in which the affine expression is created.
2747 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
2748 __isl_keep pet_context
*pc
)
2753 switch (pet_expr_op_get_type(expr
)) {
2756 res
= extract_affine_add_sub(expr
, pc
);
2760 res
= extract_affine_div_mod(expr
, pc
);
2763 res
= extract_affine_mul(expr
, pc
);
2766 return extract_affine_neg(expr
, pc
);
2768 return extract_affine_cond(expr
, pc
);
2778 return pet_expr_extract_affine_condition(expr
, pc
);
2780 return non_affine(pet_context_get_space(pc
));
2785 if (isl_pw_aff_involves_nan(res
)) {
2786 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
2787 isl_pw_aff_free(res
);
2788 return non_affine(space
);
2791 type_size
= pet_expr_get_type_size(expr
);
2793 res
= wrap(res
, type_size
);
2795 res
= signed_overflow(res
, -type_size
);
2800 /* Extract an affine expression from some special function calls.
2801 * Return NaN if we are unable to extract an affine expression.
2802 * In particular, we handle "min", "max", "ceild", "floord",
2803 * "intMod", "intFloor" and "intCeil".
2804 * In case of the latter five, the second argument needs to be
2805 * a (positive) integer constant.
2807 * "pc" is the context in which the affine expression is created.
2809 static __isl_give isl_pw_aff
*extract_affine_from_call(
2810 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2812 isl_pw_aff
*aff1
, *aff2
;
2816 n
= pet_expr_get_n_arg(expr
);
2817 name
= pet_expr_call_get_name(expr
);
2818 if (!(n
== 2 && !strcmp(name
, "min")) &&
2819 !(n
== 2 && !strcmp(name
, "max")) &&
2820 !(n
== 2 && !strcmp(name
, "intMod")) &&
2821 !(n
== 2 && !strcmp(name
, "intFloor")) &&
2822 !(n
== 2 && !strcmp(name
, "intCeil")) &&
2823 !(n
== 2 && !strcmp(name
, "floord")) &&
2824 !(n
== 2 && !strcmp(name
, "ceild")))
2825 return non_affine(pet_context_get_space(pc
));
2827 if (!strcmp(name
, "min") || !strcmp(name
, "max")) {
2828 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2829 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
2831 if (!strcmp(name
, "min"))
2832 aff1
= isl_pw_aff_min(aff1
, aff2
);
2834 aff1
= isl_pw_aff_max(aff1
, aff2
);
2835 } else if (!strcmp(name
, "intMod")) {
2838 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2839 return non_affine(pet_context_get_space(pc
));
2840 v
= pet_expr_int_get_val(expr
->args
[1]);
2841 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2842 aff1
= isl_pw_aff_mod_val(aff1
, v
);
2846 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2847 return non_affine(pet_context_get_space(pc
));
2848 v
= pet_expr_int_get_val(expr
->args
[1]);
2849 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2850 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
2851 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
2852 aff1
= isl_pw_aff_floor(aff1
);
2854 aff1
= isl_pw_aff_ceil(aff1
);
2860 /* Extract an affine expression from "expr", if possible.
2861 * Otherwise return NaN.
2863 * "pc" is the context in which the affine expression is created.
2865 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
2866 __isl_keep pet_context
*pc
)
2871 switch (pet_expr_get_type(expr
)) {
2872 case pet_expr_access
:
2873 return extract_affine_from_access(expr
, pc
);
2875 return extract_affine_from_int(expr
, pc
);
2877 return extract_affine_from_op(expr
, pc
);
2879 return extract_affine_from_call(expr
, pc
);
2881 case pet_expr_double
:
2882 case pet_expr_error
:
2883 return non_affine(pet_context_get_space(pc
));
2887 /* Extract an affine expressions representing the comparison "LHS op RHS"
2888 * Return NaN if we are unable to extract such an affine expression.
2890 * "pc" is the context in which the affine expression is created.
2892 * If the comparison is of the form
2896 * then the expression is constructed as the conjunction of
2901 * A similar optimization is performed for max(a,b) <= c.
2902 * We do this because that will lead to simpler representations
2903 * of the expression.
2904 * If isl is ever enhanced to explicitly deal with min and max expressions,
2905 * this optimization can be removed.
2907 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
2908 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
2909 __isl_keep pet_context
*pc
)
2911 isl_pw_aff
*lhs_pa
, *rhs_pa
;
2913 if (op
== pet_op_gt
)
2914 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
2915 if (op
== pet_op_ge
)
2916 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
2918 if (op
== pet_op_lt
|| op
== pet_op_le
) {
2919 if (pet_expr_is_min(rhs
)) {
2920 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2922 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2924 return pet_and(lhs_pa
, rhs_pa
);
2926 if (pet_expr_is_max(lhs
)) {
2927 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
2929 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
2931 return pet_and(lhs_pa
, rhs_pa
);
2935 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
2936 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
2938 return pet_comparison(op
, lhs_pa
, rhs_pa
);
2941 /* Extract an affine expressions from the comparison "expr".
2942 * Return NaN if we are unable to extract such an affine expression.
2944 * "pc" is the context in which the affine expression is created.
2946 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
2947 __isl_keep pet_context
*pc
)
2949 enum pet_op_type type
;
2953 if (expr
->n_arg
!= 2)
2954 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2955 "expecting two arguments", return NULL
);
2957 type
= pet_expr_op_get_type(expr
);
2958 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
2962 /* Extract an affine expression representing the boolean operation
2963 * expressed by "expr".
2964 * Return NaN if we are unable to extract an affine expression.
2966 * "pc" is the context in which the affine expression is created.
2968 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
2969 __isl_keep pet_context
*pc
)
2971 isl_pw_aff
*lhs
, *rhs
;
2977 n
= pet_expr_get_n_arg(expr
);
2978 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2980 return pet_not(lhs
);
2982 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
2983 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
2986 /* Extract the affine expression "expr != 0 ? 1 : 0".
2987 * Return NaN if we are unable to extract an affine expression.
2989 * "pc" is the context in which the affine expression is created.
2991 static __isl_give isl_pw_aff
*extract_implicit_condition(
2992 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2996 res
= pet_expr_extract_affine(expr
, pc
);
2997 return pet_to_bool(res
);
3000 /* Extract a boolean affine expression from "expr".
3001 * Return NaN if we are unable to extract an affine expression.
3003 * "pc" is the context in which the affine expression is created.
3005 * If "expr" is neither a comparison nor a boolean operation,
3006 * then we assume it is an affine expression and return the
3007 * boolean expression "expr != 0 ? 1 : 0".
3009 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
3010 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3015 if (pet_expr_is_comparison(expr
))
3016 return extract_comparison(expr
, pc
);
3017 if (pet_expr_is_boolean(expr
))
3018 return extract_boolean(expr
, pc
);
3020 return extract_implicit_condition(expr
, pc
);
3023 /* Check if "expr" is an assume expression and if its single argument
3024 * can be converted to an affine expression in the context of "pc".
3025 * If so, replace the argument by the affine expression.
3027 __isl_give pet_expr
*pet_expr_resolve_assume(__isl_take pet_expr
*expr
,
3028 __isl_keep pet_context
*pc
)
3031 isl_multi_pw_aff
*index
;
3035 if (!pet_expr_is_assume(expr
))
3037 if (expr
->n_arg
!= 1)
3038 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3039 "expecting one argument", return pet_expr_free(expr
));
3041 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3043 return pet_expr_free(expr
);
3044 if (isl_pw_aff_involves_nan(cond
)) {
3045 isl_pw_aff_free(cond
);
3049 index
= isl_multi_pw_aff_from_pw_aff(cond
);
3050 expr
= pet_expr_set_arg(expr
, 0, pet_expr_from_index(index
));
3055 /* Return the number of bits needed to represent the type of "expr".
3056 * See the description of the type_size field of pet_expr.
3058 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
3060 return expr
? expr
->type_size
: 0;
3063 /* Replace the number of bits needed to represent the type of "expr"
3065 * See the description of the type_size field of pet_expr.
3067 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
3070 expr
= pet_expr_cow(expr
);
3074 expr
->type_size
= type_size
;
3079 /* Extend an access expression "expr" with an additional index "index".
3080 * In particular, add "index" as an extra argument to "expr" and
3081 * adjust the index expression of "expr" to refer to this extra argument.
3082 * The caller is responsible for calling pet_expr_access_set_depth
3083 * to update the corresponding access relation.
3085 * Note that we only collect the individual index expressions as
3086 * arguments of "expr" here.
3087 * An attempt to integrate them into the index expression of "expr"
3088 * is performed in pet_expr_access_plug_in_args.
3090 __isl_give pet_expr
*pet_expr_access_subscript(__isl_take pet_expr
*expr
,
3091 __isl_take pet_expr
*index
)
3095 isl_local_space
*ls
;
3098 expr
= pet_expr_cow(expr
);
3099 if (!expr
|| !index
)
3101 if (expr
->type
!= pet_expr_access
)
3102 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3103 "not an access pet_expr", goto error
);
3105 n
= pet_expr_get_n_arg(expr
);
3106 expr
= pet_expr_insert_arg(expr
, n
, index
);
3110 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3111 ls
= isl_local_space_from_space(space
);
3112 pa
= isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, isl_dim_set
, n
));
3113 expr
->acc
.index
= pet_array_subscript(expr
->acc
.index
, pa
);
3114 if (!expr
->acc
.index
)
3115 return pet_expr_free(expr
);
3119 pet_expr_free(expr
);
3120 pet_expr_free(index
);
3124 /* Extend an access expression "expr" with an additional member acces to "id".
3125 * In particular, extend the index expression of "expr" to include
3126 * the additional member access.
3127 * The caller is responsible for calling pet_expr_access_set_depth
3128 * to update the corresponding access relation.
3130 __isl_give pet_expr
*pet_expr_access_member(__isl_take pet_expr
*expr
,
3131 __isl_take isl_id
*id
)
3134 isl_multi_pw_aff
*field_access
;
3136 expr
= pet_expr_cow(expr
);
3139 if (expr
->type
!= pet_expr_access
)
3140 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3141 "not an access pet_expr", goto error
);
3143 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3144 space
= isl_space_from_domain(space
);
3145 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3146 field_access
= isl_multi_pw_aff_zero(space
);
3147 expr
->acc
.index
= pet_array_member(expr
->acc
.index
, field_access
);
3148 if (!expr
->acc
.index
)
3149 return pet_expr_free(expr
);
3153 pet_expr_free(expr
);
3158 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
3165 fprintf(stderr
, "%*s", indent
, "");
3167 switch (expr
->type
) {
3168 case pet_expr_double
:
3169 fprintf(stderr
, "%s\n", expr
->d
.s
);
3172 isl_val_dump(expr
->i
);
3174 case pet_expr_access
:
3175 if (expr
->acc
.ref_id
) {
3176 isl_id_dump(expr
->acc
.ref_id
);
3177 fprintf(stderr
, "%*s", indent
, "");
3179 isl_multi_pw_aff_dump(expr
->acc
.index
);
3180 fprintf(stderr
, "%*sdepth: %d\n", indent
+ 2,
3181 "", expr
->acc
.depth
);
3182 if (expr
->acc
.kill
) {
3183 fprintf(stderr
, "%*skill: 1\n", indent
+ 2, "");
3185 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
3186 "", expr
->acc
.read
);
3187 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
3188 "", expr
->acc
.write
);
3190 if (expr
->acc
.access
) {
3191 fprintf(stderr
, "%*saccess: ", indent
+ 2, "");
3192 isl_map_dump(expr
->acc
.access
);
3194 for (i
= 0; i
< expr
->n_arg
; ++i
)
3195 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3198 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
3199 for (i
= 0; i
< expr
->n_arg
; ++i
)
3200 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3203 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
3204 for (i
= 0; i
< expr
->n_arg
; ++i
)
3205 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3208 fprintf(stderr
, "(%s)\n", expr
->type_name
);
3209 for (i
= 0; i
< expr
->n_arg
; ++i
)
3210 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3212 case pet_expr_error
:
3213 fprintf(stderr
, "ERROR\n");
3218 void pet_expr_dump(__isl_keep pet_expr
*expr
)
3220 pet_expr_dump_with_indent(expr
, 0);