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 /* Extend the range of "access" with "n" dimensions, retaining
180 * the tuple identifier on this range.
182 * If "access" represents a member access, then extend the range
185 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
189 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
191 if (!isl_map_range_is_wrapping(access
)) {
192 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
196 domain
= isl_map_copy(access
);
197 domain
= isl_map_range_factor_domain(domain
);
198 access
= isl_map_range_factor_range(access
);
199 access
= extend_range(access
, n
);
200 access
= isl_map_range_product(domain
, access
);
203 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
208 /* Does the access expression "expr" have an explicit access relation?
210 static int has_access_relation(__isl_keep pet_expr
*expr
)
215 if (expr
->acc
.access
)
221 /* Replace the depth of the access expr "expr" by "depth".
223 * To avoid inconsistencies between the depth and the access relation,
224 * we currently do not allow the depth to change once the access relation
225 * has been set or computed.
227 __isl_give pet_expr
*pet_expr_access_set_depth(__isl_take pet_expr
*expr
,
235 if (expr
->acc
.depth
== depth
)
237 if (has_access_relation(expr
))
238 isl_die(pet_expr_get_ctx(expr
), isl_error_unsupported
,
239 "depth cannot be changed after access relation "
240 "has been set or computed", return pet_expr_free(expr
));
242 expr
= pet_expr_cow(expr
);
245 expr
->acc
.depth
= depth
;
250 /* Construct a pet_expr that kills the elements specified by
251 * the index expression "index" and the access relation "access".
253 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
254 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
259 if (!access
|| !index
)
262 expr
= pet_expr_from_index(index
);
263 expr
= pet_expr_access_set_read(expr
, 0);
264 expr
= pet_expr_access_set_kill(expr
, 1);
265 depth
= isl_map_dim(access
, isl_dim_out
);
266 expr
= pet_expr_access_set_depth(expr
, depth
);
267 expr
= pet_expr_access_set_access(expr
, access
);
268 return pet_expr_new_unary(pet_op_kill
, expr
);
270 isl_map_free(access
);
271 isl_multi_pw_aff_free(index
);
275 /* Construct a unary pet_expr that performs "op" on "arg".
277 __isl_give pet_expr
*pet_expr_new_unary(enum pet_op_type op
,
278 __isl_take pet_expr
*arg
)
285 ctx
= pet_expr_get_ctx(arg
);
286 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
287 expr
= pet_expr_set_n_arg(expr
, 1);
292 expr
->args
[pet_un_arg
] = arg
;
300 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
301 * where the result is represented using a type of "type_size" bits
302 * (may be zero if unknown or if the type is not an integer).
304 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
305 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
312 ctx
= pet_expr_get_ctx(lhs
);
313 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
314 expr
= pet_expr_set_n_arg(expr
, 2);
319 expr
->type_size
= type_size
;
320 expr
->args
[pet_bin_lhs
] = lhs
;
321 expr
->args
[pet_bin_rhs
] = rhs
;
330 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
332 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
333 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
338 if (!cond
|| !lhs
|| !rhs
)
340 ctx
= pet_expr_get_ctx(cond
);
341 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
342 expr
= pet_expr_set_n_arg(expr
, 3);
346 expr
->op
= pet_op_cond
;
347 expr
->args
[pet_ter_cond
] = cond
;
348 expr
->args
[pet_ter_true
] = lhs
;
349 expr
->args
[pet_ter_false
] = rhs
;
359 /* Construct a call pet_expr that calls function "name" with "n_arg"
360 * arguments. The caller is responsible for filling in the arguments.
362 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
367 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
368 expr
= pet_expr_set_n_arg(expr
, n_arg
);
372 expr
->name
= strdup(name
);
374 return pet_expr_free(expr
);
379 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
381 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
382 __isl_take pet_expr
*arg
)
390 ctx
= pet_expr_get_ctx(arg
);
391 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
392 expr
= pet_expr_set_n_arg(expr
, 1);
396 expr
->type_name
= strdup(type_name
);
397 if (!expr
->type_name
)
409 /* Construct a pet_expr that represents the double "d".
411 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
412 double val
, const char *s
)
416 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
421 expr
->d
.s
= strdup(s
);
423 return pet_expr_free(expr
);
428 /* Construct a pet_expr that represents the integer value "v".
430 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
438 ctx
= isl_val_get_ctx(v
);
439 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
451 /* Return an independent duplicate of "expr".
453 * In case of an access expression, make sure the depth of the duplicate is set
454 * before the access relation (if any) is set and after the index expression
457 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
465 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
466 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
467 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
468 for (i
= 0; i
< expr
->n_arg
; ++i
)
469 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
471 switch (expr
->type
) {
472 case pet_expr_access
:
473 if (expr
->acc
.ref_id
)
474 dup
= pet_expr_access_set_ref_id(dup
,
475 isl_id_copy(expr
->acc
.ref_id
));
476 dup
= pet_expr_access_set_index(dup
,
477 isl_multi_pw_aff_copy(expr
->acc
.index
));
478 dup
= pet_expr_access_set_depth(dup
, expr
->acc
.depth
);
479 if (expr
->acc
.access
)
480 dup
= pet_expr_access_set_access(dup
,
481 isl_map_copy(expr
->acc
.access
));
482 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
483 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
484 dup
= pet_expr_access_set_kill(dup
, expr
->acc
.kill
);
487 dup
= pet_expr_call_set_name(dup
, expr
->name
);
490 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
492 case pet_expr_double
:
493 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
496 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
499 dup
= pet_expr_op_set_type(dup
, expr
->op
);
502 dup
= pet_expr_free(dup
);
509 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
517 return pet_expr_dup(expr
);
520 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
529 for (i
= 0; i
< expr
->n_arg
; ++i
)
530 pet_expr_free(expr
->args
[i
]);
533 switch (expr
->type
) {
534 case pet_expr_access
:
535 isl_id_free(expr
->acc
.ref_id
);
536 isl_map_free(expr
->acc
.access
);
537 isl_multi_pw_aff_free(expr
->acc
.index
);
543 free(expr
->type_name
);
545 case pet_expr_double
:
549 isl_val_free(expr
->i
);
556 isl_ctx_deref(expr
->ctx
);
561 /* Return an additional reference to "expr".
563 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
572 /* Return the isl_ctx in which "expr" was created.
574 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
576 return expr
? expr
->ctx
: NULL
;
579 /* Return the type of "expr".
581 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
584 return pet_expr_error
;
588 /* Return the number of arguments of "expr".
590 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
598 /* Set the number of arguments of "expr" to "n".
600 * If "expr" originally had more arguments, then remove the extra arguments.
601 * If "expr" originally had fewer arguments, then create space for
602 * the extra arguments ans initialize them to NULL.
604 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
611 if (expr
->n_arg
== n
)
613 expr
= pet_expr_cow(expr
);
617 if (n
< expr
->n_arg
) {
618 for (i
= n
; i
< expr
->n_arg
; ++i
)
619 pet_expr_free(expr
->args
[i
]);
624 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
626 return pet_expr_free(expr
);
628 for (i
= expr
->n_arg
; i
< n
; ++i
)
629 expr
->args
[i
] = NULL
;
635 /* Return the argument of "expr" at position "pos".
637 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
641 if (pos
< 0 || pos
>= expr
->n_arg
)
642 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
643 "position out of bounds", return NULL
);
645 return pet_expr_copy(expr
->args
[pos
]);
648 /* Replace the argument of "expr" at position "pos" by "arg".
650 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
651 __isl_take pet_expr
*arg
)
655 if (pos
< 0 || pos
>= expr
->n_arg
)
656 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
657 "position out of bounds", goto error
);
658 if (expr
->args
[pos
] == arg
) {
663 expr
= pet_expr_cow(expr
);
667 pet_expr_free(expr
->args
[pos
]);
668 expr
->args
[pos
] = arg
;
677 /* Does "expr" perform a comparison operation?
679 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
683 if (expr
->type
!= pet_expr_op
)
698 /* Does "expr" perform a boolean operation?
700 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
704 if (expr
->type
!= pet_expr_op
)
716 /* Is "expr" an assume statement?
718 int pet_expr_is_assume(__isl_keep pet_expr
*expr
)
722 if (expr
->type
!= pet_expr_op
)
724 return expr
->op
== pet_op_assume
;
727 /* Does "expr" perform a min operation?
729 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
733 if (expr
->type
!= pet_expr_call
)
735 if (expr
->n_arg
!= 2)
737 if (strcmp(expr
->name
, "min") != 0)
742 /* Does "expr" perform a max operation?
744 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
748 if (expr
->type
!= pet_expr_call
)
750 if (expr
->n_arg
!= 2)
752 if (strcmp(expr
->name
, "max") != 0)
757 /* Does "expr" represent an access to an unnamed space, i.e.,
758 * does it represent an affine expression?
760 int pet_expr_is_affine(__isl_keep pet_expr
*expr
)
766 if (expr
->type
!= pet_expr_access
)
769 has_id
= isl_multi_pw_aff_has_tuple_id(expr
->acc
.index
, isl_dim_out
);
776 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
777 * not part of any struct?
779 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
783 if (expr
->type
!= pet_expr_access
)
785 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
))
788 return expr
->acc
.depth
== 0;
791 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
794 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
795 __isl_keep isl_multi_pw_aff
*mpa2
)
799 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
800 if (equal
< 0 || equal
)
802 mpa2
= isl_multi_pw_aff_copy(mpa2
);
803 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
804 isl_multi_pw_aff_get_space(mpa1
));
805 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
806 isl_multi_pw_aff_free(mpa2
);
811 /* Construct an access relation from the index expression and
812 * the array depth of the access expression "expr".
814 * If the number of indices is smaller than the depth of the array,
815 * then we assume that all elements of the remaining dimensions
818 static __isl_give isl_map
*construct_access_relation(__isl_keep pet_expr
*expr
)
827 access
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
831 dim
= isl_map_dim(access
, isl_dim_out
);
832 if (dim
> expr
->acc
.depth
)
833 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
834 "number of indices greater than depth",
835 access
= isl_map_free(access
));
837 if (dim
!= expr
->acc
.depth
)
838 access
= extend_range(access
, expr
->acc
.depth
- dim
);
843 /* Ensure that "expr" has an explicit access relation.
845 * If "expr" does not already have an access relation, then create
846 * one based on the index expression and the array depth.
848 * We do not cow since adding an explicit access relation
849 * does not change the meaning of the expression.
851 static __isl_give pet_expr
*introduce_access_relation(
852 __isl_take pet_expr
*expr
)
859 if (has_access_relation(expr
))
862 access
= construct_access_relation(expr
);
864 return pet_expr_free(expr
);
866 expr
->acc
.access
= access
;
871 /* Return 1 if the two pet_exprs are equivalent.
873 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
877 if (!expr1
|| !expr2
)
880 if (expr1
->type
!= expr2
->type
)
882 if (expr1
->n_arg
!= expr2
->n_arg
)
884 for (i
= 0; i
< expr1
->n_arg
; ++i
)
885 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
887 switch (expr1
->type
) {
890 case pet_expr_double
:
891 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
893 if (expr1
->d
.val
!= expr2
->d
.val
)
897 if (!isl_val_eq(expr1
->i
, expr2
->i
))
900 case pet_expr_access
:
901 if (expr1
->acc
.read
!= expr2
->acc
.read
)
903 if (expr1
->acc
.write
!= expr2
->acc
.write
)
905 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
907 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
909 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
911 if (!multi_pw_aff_is_equal(expr1
->acc
.index
, expr2
->acc
.index
))
913 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
915 if (has_access_relation(expr1
) != has_access_relation(expr2
)) {
917 expr1
= pet_expr_copy(expr1
);
918 expr2
= pet_expr_copy(expr2
);
919 expr1
= introduce_access_relation(expr1
);
920 expr2
= introduce_access_relation(expr2
);
921 equal
= pet_expr_is_equal(expr1
, expr2
);
922 pet_expr_free(expr1
);
923 pet_expr_free(expr2
);
926 if (expr1
->acc
.access
&&
927 !isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
931 if (expr1
->op
!= expr2
->op
)
935 if (strcmp(expr1
->name
, expr2
->name
))
939 if (strcmp(expr1
->type_name
, expr2
->type_name
))
947 /* Does the access expression "expr" read the accessed elements?
949 int pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
953 if (expr
->type
!= pet_expr_access
)
954 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
955 "not an access expression", return -1);
957 return expr
->acc
.read
;
960 /* Does the access expression "expr" write to the accessed elements?
962 int pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
966 if (expr
->type
!= pet_expr_access
)
967 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
968 "not an access expression", return -1);
970 return expr
->acc
.write
;
973 /* Return the identifier of the array accessed by "expr".
975 * If "expr" represents a member access, then return the identifier
976 * of the outer structure array.
978 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
982 if (expr
->type
!= pet_expr_access
)
983 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
984 "not an access expression", return NULL
);
986 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
)) {
990 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
991 space
= isl_space_range(space
);
992 while (space
&& isl_space_is_wrapping(space
))
993 space
= isl_space_domain(isl_space_unwrap(space
));
994 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
995 isl_space_free(space
);
1000 return isl_multi_pw_aff_get_tuple_id(expr
->acc
.index
, isl_dim_out
);
1003 /* Return the parameter space of "expr".
1005 __isl_give isl_space
*pet_expr_access_get_parameter_space(
1006 __isl_keep pet_expr
*expr
)
1012 if (expr
->type
!= pet_expr_access
)
1013 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1014 "not an access expression", return NULL
);
1016 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1017 space
= isl_space_params(space
);
1022 /* Return the domain space of "expr", without the arguments (if any).
1024 __isl_give isl_space
*pet_expr_access_get_domain_space(
1025 __isl_keep pet_expr
*expr
)
1031 if (expr
->type
!= pet_expr_access
)
1032 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1033 "not an access expression", return NULL
);
1035 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1036 space
= isl_space_domain(space
);
1037 if (isl_space_is_wrapping(space
))
1038 space
= isl_space_domain(isl_space_unwrap(space
));
1043 /* Return the space of the data accessed by "expr".
1045 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
1051 if (expr
->type
!= pet_expr_access
)
1052 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1053 "not an access expression", return NULL
);
1055 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1056 space
= isl_space_range(space
);
1061 /* Modify all expressions of type pet_expr_access in "expr"
1062 * by calling "fn" on them.
1064 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
1065 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1070 n
= pet_expr_get_n_arg(expr
);
1071 for (i
= 0; i
< n
; ++i
) {
1072 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1073 arg
= pet_expr_map_access(arg
, fn
, user
);
1074 expr
= pet_expr_set_arg(expr
, i
, arg
);
1080 if (expr
->type
== pet_expr_access
)
1081 expr
= fn(expr
, user
);
1086 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1088 * Return -1 on error (where fn returning a negative value is treated as
1090 * Otherwise return 0.
1092 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
1093 enum pet_expr_type type
,
1094 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1101 for (i
= 0; i
< expr
->n_arg
; ++i
)
1102 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
1103 type
, fn
, user
) < 0)
1106 if (expr
->type
== type
)
1107 return fn(expr
, user
);
1112 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1114 * Return -1 on error (where fn returning a negative value is treated as
1116 * Otherwise return 0.
1118 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
1119 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1121 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1124 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1126 * Return -1 on error (where fn returning a negative value is treated as
1128 * Otherwise return 0.
1130 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
1131 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1133 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1136 /* Internal data structure for pet_expr_writes.
1137 * "id" is the identifier that we are looking for.
1138 * "found" is set if we have found the identifier being written to.
1140 struct pet_expr_writes_data
{
1145 /* Given an access expression, check if it writes to data->id.
1146 * If so, set data->found and abort the search.
1148 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1150 struct pet_expr_writes_data
*data
= user
;
1153 if (!expr
->acc
.write
)
1155 if (pet_expr_is_affine(expr
))
1158 write_id
= pet_expr_access_get_id(expr
);
1159 isl_id_free(write_id
);
1164 if (write_id
!= data
->id
)
1171 /* Does expression "expr" write to "id"?
1173 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1175 struct pet_expr_writes_data data
;
1179 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1186 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1187 * index expression and access relation of "expr" (if any)
1188 * to dimensions of "dst_type" at "dst_pos".
1190 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1191 enum isl_dim_type dst_type
, unsigned dst_pos
,
1192 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1194 expr
= pet_expr_cow(expr
);
1197 if (expr
->type
!= pet_expr_access
)
1198 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1199 "not an access pet_expr", return pet_expr_free(expr
));
1201 if (expr
->acc
.access
) {
1202 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
1203 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1204 if (!expr
->acc
.access
)
1206 isl_multi_pw_aff_free(expr
->acc
.index
);
1208 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1209 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1210 if (!expr
->acc
.index
)
1211 return pet_expr_free(expr
);
1216 /* Replace the index expression and access relation (if any) of "expr"
1217 * by their preimages under the function represented by "ma".
1219 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1220 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1222 expr
= pet_expr_cow(expr
);
1225 if (expr
->type
!= pet_expr_access
)
1226 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1227 "not an access pet_expr", goto error
);
1229 if (expr
->acc
.access
) {
1230 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(
1231 expr
->acc
.access
, isl_multi_aff_copy(ma
));
1232 if (!expr
->acc
.access
)
1234 isl_multi_pw_aff_free(expr
->acc
.index
);
1236 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1238 if (!expr
->acc
.index
)
1239 return pet_expr_free(expr
);
1243 isl_multi_aff_free(ma
);
1244 pet_expr_free(expr
);
1248 /* Replace the index expression and access relation (if any) of "expr"
1249 * by their preimages under the function represented by "mpa".
1251 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1252 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1254 expr
= pet_expr_cow(expr
);
1257 if (expr
->type
!= pet_expr_access
)
1258 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1259 "not an access pet_expr", goto error
);
1261 if (expr
->acc
.access
) {
1262 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1263 expr
->acc
.access
, isl_multi_pw_aff_copy(mpa
));
1264 if (!expr
->acc
.access
)
1266 isl_multi_pw_aff_free(expr
->acc
.index
);
1268 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1269 expr
->acc
.index
, mpa
);
1270 if (!expr
->acc
.index
)
1271 return pet_expr_free(expr
);
1275 isl_multi_pw_aff_free(mpa
);
1276 pet_expr_free(expr
);
1280 /* Return the index expression of access expression "expr".
1282 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1283 __isl_keep pet_expr
*expr
)
1287 if (expr
->type
!= pet_expr_access
)
1288 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1289 "not an access expression", return NULL
);
1291 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1294 /* Align the parameters of expr->acc.index and expr->acc.access (if set).
1296 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1298 expr
= pet_expr_cow(expr
);
1301 if (expr
->type
!= pet_expr_access
)
1302 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1303 "not an access expression", return pet_expr_free(expr
));
1305 if (!has_access_relation(expr
))
1308 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1309 isl_multi_pw_aff_get_space(expr
->acc
.index
));
1310 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1311 isl_map_get_space(expr
->acc
.access
));
1312 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1313 return pet_expr_free(expr
);
1318 /* Are "expr1" and "expr2" both array accesses such that
1319 * the access relation of "expr1" is a subset of that of "expr2"?
1320 * Only take into account the first "n_arg" arguments.
1322 * This function is tailored for use by mark_self_dependences in nest.c.
1323 * In particular, the input expressions may have more than "n_arg"
1324 * elements in their arguments arrays, while only the first "n_arg"
1325 * elements are referenced from the access relations.
1327 int pet_expr_is_sub_access(__isl_keep pet_expr
*expr1
,
1328 __isl_keep pet_expr
*expr2
, int n_arg
)
1334 if (!expr1
|| !expr2
)
1336 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1338 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1340 if (pet_expr_is_affine(expr1
))
1342 if (pet_expr_is_affine(expr2
))
1344 n1
= pet_expr_get_n_arg(expr1
);
1347 n2
= pet_expr_get_n_arg(expr2
);
1352 for (i
= 0; i
< n1
; ++i
) {
1354 equal
= pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]);
1355 if (equal
< 0 || !equal
)
1358 id1
= pet_expr_access_get_id(expr1
);
1359 id2
= pet_expr_access_get_id(expr2
);
1367 expr1
= pet_expr_copy(expr1
);
1368 expr2
= pet_expr_copy(expr2
);
1369 expr1
= introduce_access_relation(expr1
);
1370 expr2
= introduce_access_relation(expr2
);
1371 if (!expr1
|| !expr2
)
1374 is_subset
= isl_map_is_subset(expr1
->acc
.access
, expr2
->acc
.access
);
1376 pet_expr_free(expr1
);
1377 pet_expr_free(expr2
);
1381 pet_expr_free(expr1
);
1382 pet_expr_free(expr2
);
1386 /* Given a set in the iteration space "domain", extend it to live in the space
1387 * of the domain of access relations.
1389 * That, is the number of arguments "n" is 0, then simply return domain.
1390 * Otherwise, return [domain -> [a_1,...,a_n]].
1392 static __isl_give isl_set
*add_arguments(__isl_take isl_set
*domain
, int n
)
1399 map
= isl_map_from_domain(domain
);
1400 map
= isl_map_add_dims(map
, isl_dim_out
, n
);
1401 return isl_map_wrap(map
);
1404 /* Add extra conditions to the domains of all access relations in "expr",
1405 * introducing access relations if they are not already present.
1407 * The conditions are not added to the index expression. Instead, they
1408 * are used to try and simplify the index expression.
1410 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1411 __isl_take isl_set
*cond
)
1415 expr
= pet_expr_cow(expr
);
1419 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1420 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1421 isl_set_copy(cond
));
1426 if (expr
->type
!= pet_expr_access
) {
1431 expr
= introduce_access_relation(expr
);
1435 cond
= add_arguments(cond
, expr
->n_arg
);
1436 expr
->acc
.access
= isl_map_intersect_domain(expr
->acc
.access
,
1437 isl_set_copy(cond
));
1438 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, cond
);
1439 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1440 return pet_expr_free(expr
);
1445 return pet_expr_free(expr
);
1448 /* Modify the access relation (if any) and index expression
1449 * of the given access expression
1450 * based on the given iteration space transformation.
1451 * In particular, precompose the access relation and index expression
1452 * with the update function.
1454 * If the access has any arguments then the domain of the access relation
1455 * is a wrapped mapping from the iteration space to the space of
1456 * argument values. We only need to change the domain of this wrapped
1457 * mapping, so we extend the input transformation with an identity mapping
1458 * on the space of argument values.
1460 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1461 __isl_keep isl_multi_pw_aff
*update
)
1463 expr
= pet_expr_cow(expr
);
1466 if (expr
->type
!= pet_expr_access
)
1467 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1468 "not an access expression", return pet_expr_free(expr
));
1470 update
= isl_multi_pw_aff_copy(update
);
1472 if (expr
->n_arg
> 0) {
1474 isl_multi_pw_aff
*id
;
1476 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1477 space
= isl_space_domain(space
);
1478 space
= isl_space_unwrap(space
);
1479 space
= isl_space_range(space
);
1480 space
= isl_space_map_from_set(space
);
1481 id
= isl_multi_pw_aff_identity(space
);
1482 update
= isl_multi_pw_aff_product(update
, id
);
1485 if (expr
->acc
.access
) {
1486 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1488 isl_multi_pw_aff_copy(update
));
1489 if (!expr
->acc
.access
)
1491 isl_multi_pw_aff_free(expr
->acc
.index
);
1493 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1494 expr
->acc
.index
, update
);
1495 if (!expr
->acc
.index
)
1496 return pet_expr_free(expr
);
1501 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1503 isl_multi_pw_aff
*update
= user
;
1505 return pet_expr_access_update_domain(expr
, update
);
1508 /* Modify all access relations in "expr" by precomposing them with
1509 * the given iteration space transformation.
1511 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1512 __isl_take isl_multi_pw_aff
*update
)
1514 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1515 isl_multi_pw_aff_free(update
);
1519 /* Given an expression with accesses that have a 0D anonymous domain,
1520 * replace those domains by "space".
1522 __isl_give pet_expr
*pet_expr_insert_domain(__isl_take pet_expr
*expr
,
1523 __isl_take isl_space
*space
)
1525 isl_multi_pw_aff
*mpa
;
1527 space
= isl_space_from_domain(space
);
1528 mpa
= isl_multi_pw_aff_zero(space
);
1529 return pet_expr_update_domain(expr
, mpa
);
1532 /* Add all parameters in "space" to the access relation (if any)
1533 * and index expression of "expr".
1535 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1537 isl_space
*space
= user
;
1539 expr
= pet_expr_cow(expr
);
1542 if (expr
->type
!= pet_expr_access
)
1543 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1544 "not an access expression", return pet_expr_free(expr
));
1546 if (expr
->acc
.access
) {
1547 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1548 isl_space_copy(space
));
1549 if (!expr
->acc
.access
)
1551 isl_multi_pw_aff_free(expr
->acc
.index
);
1553 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1554 isl_space_copy(space
));
1555 if (!expr
->acc
.index
)
1556 return pet_expr_free(expr
);
1561 /* Add all parameters in "space" to all access relations and index expressions
1564 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1565 __isl_take isl_space
*space
)
1567 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1568 isl_space_free(space
);
1572 /* Insert an argument expression corresponding to "test" in front
1573 * of the list of arguments described by *n_arg and *args.
1575 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1576 __isl_keep isl_multi_pw_aff
*test
)
1579 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1582 return pet_expr_free(expr
);
1583 expr
= pet_expr_cow(expr
);
1588 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1590 return pet_expr_free(expr
);
1593 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1595 return pet_expr_free(expr
);
1596 for (i
= 0; i
< expr
->n_arg
; ++i
)
1597 ext
[1 + i
] = expr
->args
[i
];
1602 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1604 return pet_expr_free(expr
);
1609 /* Make the expression "expr" depend on the value of "test"
1610 * being equal to "satisfied".
1612 * If "test" is an affine expression, we simply add the conditions
1613 * on the expression having the value "satisfied" to all access relations
1614 * (introducing access relations if they are missing) and index expressions.
1616 * Otherwise, we add a filter to "expr" (which is then assumed to be
1617 * an access expression) corresponding to "test" being equal to "satisfied".
1619 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1620 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1625 isl_pw_multi_aff
*pma
;
1627 expr
= pet_expr_cow(expr
);
1631 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1635 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
1636 isl_multi_pw_aff_free(test
);
1638 cond
= isl_pw_aff_non_zero_set(pa
);
1640 cond
= isl_pw_aff_zero_set(pa
);
1641 return pet_expr_restrict(expr
, cond
);
1644 ctx
= isl_multi_pw_aff_get_ctx(test
);
1645 if (expr
->type
!= pet_expr_access
)
1646 isl_die(ctx
, isl_error_invalid
,
1647 "can only filter access expressions", goto error
);
1649 expr
= introduce_access_relation(expr
);
1653 space
= isl_space_domain(isl_multi_pw_aff_get_space(expr
->acc
.index
));
1654 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1655 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
1657 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
1659 isl_pw_multi_aff_copy(pma
));
1660 pma
= isl_pw_multi_aff_gist(pma
,
1661 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
)));
1662 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
1663 expr
->acc
.index
, pma
);
1664 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1667 expr
= insert_access_arg(expr
, test
);
1669 isl_multi_pw_aff_free(test
);
1672 isl_multi_pw_aff_free(test
);
1673 return pet_expr_free(expr
);
1676 /* Add a reference identifier to access expression "expr".
1677 * "user" points to an integer that contains the sequence number
1678 * of the next reference.
1680 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
1687 expr
= pet_expr_cow(expr
);
1690 if (expr
->type
!= pet_expr_access
)
1691 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1692 "not an access expression", return pet_expr_free(expr
));
1694 ctx
= pet_expr_get_ctx(expr
);
1695 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1696 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1697 if (!expr
->acc
.ref_id
)
1698 return pet_expr_free(expr
);
1703 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
1705 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1708 /* Reset the user pointer on all parameter and tuple ids in
1709 * the access relation (if any) and the index expression
1710 * of the access expression "expr".
1712 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
1715 expr
= pet_expr_cow(expr
);
1718 if (expr
->type
!= pet_expr_access
)
1719 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1720 "not an access expression", return pet_expr_free(expr
));
1722 if (expr
->acc
.access
) {
1723 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1724 if (!expr
->acc
.access
)
1726 isl_multi_pw_aff_free(expr
->acc
.index
);
1728 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1729 if (!expr
->acc
.index
)
1730 return pet_expr_free(expr
);
1735 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
1737 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1740 /* Data used in access_gist() callback.
1742 struct pet_access_gist_data
{
1744 isl_union_map
*value_bounds
;
1747 /* Given an expression "expr" of type pet_expr_access, compute
1748 * the gist of the associated access relation (if any) and index expression
1749 * with respect to data->domain and the bounds on the values of the arguments
1750 * of the expression.
1752 * The arguments of "expr" have been gisted right before "expr" itself
1753 * is gisted. The gisted arguments may have become equal where before
1754 * they may not have been (obviously) equal. We therefore take
1755 * the opportunity to remove duplicate arguments here.
1757 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
1759 struct pet_access_gist_data
*data
= user
;
1762 expr
= pet_expr_remove_duplicate_args(expr
);
1763 expr
= pet_expr_cow(expr
);
1766 if (expr
->type
!= pet_expr_access
)
1767 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1768 "not an access expression", return pet_expr_free(expr
));
1770 domain
= isl_set_copy(data
->domain
);
1771 if (expr
->n_arg
> 0)
1772 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1773 data
->value_bounds
);
1775 if (expr
->acc
.access
) {
1776 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1777 isl_set_copy(domain
));
1778 if (!expr
->acc
.access
)
1780 isl_multi_pw_aff_free(expr
->acc
.index
);
1782 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1783 if (!expr
->acc
.index
)
1784 return pet_expr_free(expr
);
1789 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
1790 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1792 struct pet_access_gist_data data
= { context
, value_bounds
};
1794 return pet_expr_map_access(expr
, &access_gist
, &data
);
1797 /* Mark "expr" as a read dependening on "read".
1799 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
1803 return pet_expr_free(expr
);
1804 if (expr
->type
!= pet_expr_access
)
1805 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1806 "not an access expression", return pet_expr_free(expr
));
1807 if (expr
->acc
.read
== read
)
1809 expr
= pet_expr_cow(expr
);
1812 expr
->acc
.read
= read
;
1817 /* Mark "expr" as a write dependening on "write".
1819 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
1823 return pet_expr_free(expr
);
1824 if (expr
->type
!= pet_expr_access
)
1825 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1826 "not an access expression", return pet_expr_free(expr
));
1827 if (expr
->acc
.write
== write
)
1829 expr
= pet_expr_cow(expr
);
1832 expr
->acc
.write
= write
;
1837 /* Mark "expr" as a kill dependening on "kill".
1839 __isl_give pet_expr
*pet_expr_access_set_kill(__isl_take pet_expr
*expr
,
1843 return pet_expr_free(expr
);
1844 if (expr
->type
!= pet_expr_access
)
1845 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1846 "not an access expression", return pet_expr_free(expr
));
1847 if (expr
->acc
.kill
== kill
)
1849 expr
= pet_expr_cow(expr
);
1852 expr
->acc
.kill
= kill
;
1857 /* Replace the access relation of "expr" by "access".
1859 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
1860 __isl_take isl_map
*access
)
1862 expr
= pet_expr_cow(expr
);
1863 if (!expr
|| !access
)
1865 if (expr
->type
!= pet_expr_access
)
1866 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1867 "not an access expression", goto error
);
1868 isl_map_free(expr
->acc
.access
);
1869 expr
->acc
.access
= access
;
1873 isl_map_free(access
);
1874 pet_expr_free(expr
);
1878 /* Replace the index expression of "expr" by "index" and
1879 * set the array depth accordingly.
1881 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
1882 __isl_take isl_multi_pw_aff
*index
)
1884 expr
= pet_expr_cow(expr
);
1885 if (!expr
|| !index
)
1887 if (expr
->type
!= pet_expr_access
)
1888 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1889 "not an access expression", goto error
);
1890 isl_multi_pw_aff_free(expr
->acc
.index
);
1891 expr
->acc
.index
= index
;
1892 expr
->acc
.depth
= isl_multi_pw_aff_dim(index
, isl_dim_out
);
1896 isl_multi_pw_aff_free(index
);
1897 pet_expr_free(expr
);
1901 /* Return the reference identifier of access expression "expr".
1903 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
1907 if (expr
->type
!= pet_expr_access
)
1908 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1909 "not an access expression", return NULL
);
1911 return isl_id_copy(expr
->acc
.ref_id
);
1914 /* Replace the reference identifier of access expression "expr" by "ref_id".
1916 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
1917 __isl_take isl_id
*ref_id
)
1919 expr
= pet_expr_cow(expr
);
1920 if (!expr
|| !ref_id
)
1922 if (expr
->type
!= pet_expr_access
)
1923 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1924 "not an access expression", goto error
);
1925 isl_id_free(expr
->acc
.ref_id
);
1926 expr
->acc
.ref_id
= ref_id
;
1930 isl_id_free(ref_id
);
1931 pet_expr_free(expr
);
1935 /* Tag the access relation "access" with "id".
1936 * That is, insert the id as the range of a wrapped relation
1937 * in the domain of "access".
1939 * If "access" is of the form
1943 * then the result is of the form
1945 * [D[i] -> id[]] -> A[a]
1947 __isl_give isl_union_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
1948 __isl_take isl_union_map
*access
)
1951 isl_multi_aff
*add_tag
;
1954 if (expr
->type
!= pet_expr_access
)
1955 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1956 "not an access expression",
1957 return isl_union_map_free(access
));
1959 id
= isl_id_copy(expr
->acc
.ref_id
);
1960 space
= pet_expr_access_get_domain_space(expr
);
1961 space
= isl_space_from_domain(space
);
1962 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
1963 add_tag
= isl_multi_aff_domain_map(space
);
1964 access
= isl_union_map_preimage_domain_multi_aff(access
, add_tag
);
1969 /* Return the relation mapping pairs of domain iterations and argument
1970 * values to the corresponding accessed data elements.
1972 static __isl_give isl_map
*pet_expr_access_get_dependent_access(
1973 __isl_keep pet_expr
*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 NULL
);
1983 if (expr
->acc
.access
)
1984 return isl_map_copy(expr
->acc
.access
);
1986 expr
= pet_expr_copy(expr
);
1987 expr
= introduce_access_relation(expr
);
1990 access
= isl_map_copy(expr
->acc
.access
);
1991 pet_expr_free(expr
);
1996 /* Return an empty access relation for access expression "expr".
1998 static __isl_give isl_union_map
*empty_access_relation(
1999 __isl_keep pet_expr
*expr
)
2001 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr
));
2004 /* Return the may read access relation associated to "expr"
2005 * that maps pairs of domain iterations and argument values
2006 * to the corresponding accessed data elements.
2008 * Since the accesses are currently represented by a single access relation,
2009 * we return the entire access relation if "expr" is a read and
2010 * an empty relation if it is not.
2012 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_read(
2013 __isl_keep pet_expr
*expr
)
2019 if (!pet_expr_access_is_read(expr
))
2020 return empty_access_relation(expr
);
2021 access
= pet_expr_access_get_dependent_access(expr
);
2022 return isl_union_map_from_map(access
);
2025 /* Return the may write access relation associated to "expr"
2026 * that maps pairs of domain iterations and argument values
2027 * to the corresponding accessed data elements.
2029 * Since the accesses are currently represented by a single access relation,
2030 * we return the entire access relation if "expr" is a write and
2031 * an empty relation if it is not.
2033 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_write(
2034 __isl_keep pet_expr
*expr
)
2040 if (!pet_expr_access_is_write(expr
))
2041 return empty_access_relation(expr
);
2042 access
= pet_expr_access_get_dependent_access(expr
);
2043 return isl_union_map_from_map(access
);
2046 /* Return the must write access relation associated to "expr"
2047 * that maps pairs of domain iterations and argument values
2048 * to the corresponding accessed data elements.
2050 * Since the accesses are currently represented by a single access relation,
2051 * we return the entire access relation when "expr" is a write.
2053 __isl_give isl_union_map
*pet_expr_access_get_dependent_must_write(
2054 __isl_keep pet_expr
*expr
)
2060 if (!pet_expr_access_is_write(expr
))
2061 return empty_access_relation(expr
);
2062 access
= pet_expr_access_get_dependent_access(expr
);
2063 return isl_union_map_from_map(access
);
2066 /* Return the relation mapping domain iterations to all possibly
2067 * accessed data elements.
2068 * In particular, take the access relation and project out the values
2069 * of the arguments, if any.
2071 __isl_give isl_map
*pet_expr_access_get_may_access(__isl_keep pet_expr
*expr
)
2079 if (expr
->type
!= pet_expr_access
)
2080 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2081 "not an access expression", return NULL
);
2083 access
= pet_expr_access_get_dependent_access(expr
);
2084 if (expr
->n_arg
== 0)
2087 space
= isl_space_domain(isl_map_get_space(access
));
2088 map
= isl_map_universe(isl_space_unwrap(space
));
2089 map
= isl_map_domain_map(map
);
2090 access
= isl_map_apply_domain(access
, map
);
2095 /* Return the relation mapping domain iterations to all possibly
2096 * read data elements.
2098 * Since the accesses are currently represented by a single access relation,
2099 * we return the may access relation if "expr" is a read and
2100 * an empty relation if it is not.
2102 __isl_give isl_union_map
*pet_expr_access_get_may_read(
2103 __isl_keep pet_expr
*expr
)
2107 if (!pet_expr_access_is_read(expr
))
2108 return empty_access_relation(expr
);
2109 return isl_union_map_from_map(pet_expr_access_get_may_access(expr
));
2112 /* Return the relation mapping domain iterations to all possibly
2113 * written data elements.
2115 * Since the accesses are currently represented by a single access relation,
2116 * we return the may access relation if "expr" is a write and
2117 * an empty relation if it is not.
2119 __isl_give isl_union_map
*pet_expr_access_get_may_write(
2120 __isl_keep pet_expr
*expr
)
2124 if (!pet_expr_access_is_write(expr
))
2125 return empty_access_relation(expr
);
2126 return isl_union_map_from_map(pet_expr_access_get_may_access(expr
));
2129 /* Return a relation mapping domain iterations to definitely
2130 * accessed data elements, assuming the statement containing
2131 * the expression is executed.
2133 * If there are no arguments, then all elements are accessed.
2134 * Otherwise, we conservatively return an empty relation.
2136 static __isl_give isl_map
*pet_expr_access_get_must_access(
2137 __isl_keep pet_expr
*expr
)
2143 if (expr
->type
!= pet_expr_access
)
2144 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2145 "not an access expression", return NULL
);
2147 if (expr
->n_arg
== 0)
2148 return pet_expr_access_get_dependent_access(expr
);
2150 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
2151 space
= isl_space_domain_factor_domain(space
);
2153 return isl_map_empty(space
);
2156 /* Return a relation mapping domain iterations to definitely
2157 * written data elements, assuming the statement containing
2158 * the expression is executed.
2160 * Since the accesses are currently represented by a single access relation,
2161 * we return the must access relation if "expr" is a write and
2162 * an empty relation if it is not.
2164 __isl_give isl_union_map
*pet_expr_access_get_must_write(
2165 __isl_keep pet_expr
*expr
)
2169 if (!pet_expr_access_is_write(expr
))
2170 return empty_access_relation(expr
);
2171 return isl_union_map_from_map(pet_expr_access_get_must_access(expr
));
2174 /* Return the relation mapping domain iterations to all possibly
2175 * read data elements, with its domain tagged with the reference
2178 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_read(
2179 __isl_keep pet_expr
*expr
)
2181 isl_union_map
*access
;
2186 access
= pet_expr_access_get_may_read(expr
);
2187 access
= pet_expr_tag_access(expr
, access
);
2192 /* Return the relation mapping domain iterations to all possibly
2193 * written data elements, with its domain tagged with the reference
2196 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_write(
2197 __isl_keep pet_expr
*expr
)
2199 isl_union_map
*access
;
2204 access
= pet_expr_access_get_may_write(expr
);
2205 access
= pet_expr_tag_access(expr
, access
);
2210 /* Return the operation type of operation expression "expr".
2212 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
2216 if (expr
->type
!= pet_expr_op
)
2217 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2218 "not an operation expression", return pet_op_last
);
2223 /* Replace the operation type of operation expression "expr" by "type".
2225 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
2226 enum pet_op_type type
)
2229 return pet_expr_free(expr
);
2230 if (expr
->type
!= pet_expr_op
)
2231 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2232 "not an operation expression",
2233 return pet_expr_free(expr
));
2234 if (expr
->op
== type
)
2236 expr
= pet_expr_cow(expr
);
2244 /* Return the name of the function called by "expr".
2246 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
2250 if (expr
->type
!= pet_expr_call
)
2251 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2252 "not a call expression", return NULL
);
2256 /* Replace the name of the function called by "expr" by "name".
2258 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
2259 __isl_keep
const char *name
)
2261 expr
= pet_expr_cow(expr
);
2263 return pet_expr_free(expr
);
2264 if (expr
->type
!= pet_expr_call
)
2265 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2266 "not a call expression", return pet_expr_free(expr
));
2268 expr
->name
= strdup(name
);
2270 return pet_expr_free(expr
);
2274 /* Replace the type of the cast performed by "expr" by "name".
2276 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
2277 __isl_keep
const char *name
)
2279 expr
= pet_expr_cow(expr
);
2281 return pet_expr_free(expr
);
2282 if (expr
->type
!= pet_expr_cast
)
2283 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2284 "not a cast expression", return pet_expr_free(expr
));
2285 free(expr
->type_name
);
2286 expr
->type_name
= strdup(name
);
2287 if (!expr
->type_name
)
2288 return pet_expr_free(expr
);
2292 /* Return the value of the integer represented by "expr".
2294 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
2298 if (expr
->type
!= pet_expr_int
)
2299 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2300 "not an int expression", return NULL
);
2302 return isl_val_copy(expr
->i
);
2305 /* Replace the value of the integer represented by "expr" by "v".
2307 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
2308 __isl_take isl_val
*v
)
2310 expr
= pet_expr_cow(expr
);
2313 if (expr
->type
!= pet_expr_int
)
2314 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2315 "not an int expression", goto error
);
2316 isl_val_free(expr
->i
);
2322 pet_expr_free(expr
);
2326 /* Replace the value and string representation of the double
2327 * represented by "expr" by "d" and "s".
2329 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
2330 double d
, __isl_keep
const char *s
)
2332 expr
= pet_expr_cow(expr
);
2334 return pet_expr_free(expr
);
2335 if (expr
->type
!= pet_expr_double
)
2336 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2337 "not a double expression", return pet_expr_free(expr
));
2340 expr
->d
.s
= strdup(s
);
2342 return pet_expr_free(expr
);
2346 /* Return a string representation of the double expression "expr".
2348 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2352 if (expr
->type
!= pet_expr_double
)
2353 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2354 "not a double expression", return NULL
);
2355 return strdup(expr
->d
.s
);
2358 /* Return a piecewise affine expression defined on the specified domain
2359 * that represents NaN.
2361 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2363 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2366 /* This function is called when we come across an access that is
2367 * nested in what is supposed to be an affine expression.
2368 * "pc" is the context in which the affine expression is created.
2369 * If nesting is allowed in "pc", we return an affine expression that is
2370 * equal to a new parameter corresponding to this nested access.
2371 * Otherwise, we return NaN.
2373 * Note that we currently don't allow nested accesses themselves
2374 * to contain any nested accesses, so we check if "expr" itself
2375 * involves any nested accesses (either explicitly as arguments
2376 * or implicitly through parameters) and return NaN if it does.
2378 * The new parameter is resolved in resolve_nested.
2380 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2381 __isl_keep pet_context
*pc
)
2386 isl_local_space
*ls
;
2392 if (!pet_context_allow_nesting(pc
))
2393 return non_affine(pet_context_get_space(pc
));
2395 if (pet_expr_get_type(expr
) != pet_expr_access
)
2396 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2397 "not an access expression", return NULL
);
2399 if (expr
->n_arg
> 0)
2400 return non_affine(pet_context_get_space(pc
));
2402 space
= pet_expr_access_get_parameter_space(expr
);
2403 nested
= pet_nested_any_in_space(space
);
2404 isl_space_free(space
);
2406 return non_affine(pet_context_get_space(pc
));
2408 ctx
= pet_expr_get_ctx(expr
);
2409 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2410 space
= pet_context_get_space(pc
);
2411 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2413 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2414 ls
= isl_local_space_from_space(space
);
2415 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2417 return isl_pw_aff_from_aff(aff
);
2420 /* Extract an affine expression from the access pet_expr "expr".
2421 * "pc" is the context in which the affine expression is created.
2423 * If "expr" is actually an affine expression rather than
2424 * a real access, then we return that expression.
2425 * Otherwise, we require that "expr" is of an integral type.
2426 * If not, we return NaN.
2428 * If the variable has been assigned a known affine expression,
2429 * then we return that expression.
2431 * Otherwise, we return an expression that is equal to a parameter
2432 * representing "expr" (if "allow_nested" is set).
2434 static __isl_give isl_pw_aff
*extract_affine_from_access(
2435 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2440 if (pet_expr_is_affine(expr
)) {
2442 isl_multi_pw_aff
*mpa
;
2444 mpa
= pet_expr_access_get_index(expr
);
2445 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
2446 isl_multi_pw_aff_free(mpa
);
2450 if (pet_expr_get_type_size(expr
) == 0)
2451 return non_affine(pet_context_get_space(pc
));
2453 if (!pet_expr_is_scalar_access(expr
))
2454 return nested_access(expr
, pc
);
2456 id
= pet_expr_access_get_id(expr
);
2457 if (pet_context_is_assigned(pc
, id
))
2458 return pet_context_get_value(pc
, id
);
2461 return nested_access(expr
, pc
);
2464 /* Construct an affine expression from the integer constant "expr".
2465 * "pc" is the context in which the affine expression is created.
2467 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2468 __isl_keep pet_context
*pc
)
2470 isl_local_space
*ls
;
2476 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2477 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2479 return isl_pw_aff_from_aff(aff
);
2482 /* Extract an affine expression from an addition or subtraction operation.
2483 * Return NaN if we are unable to extract an affine expression.
2485 * "pc" is the context in which the affine expression is created.
2487 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2488 __isl_keep pet_context
*pc
)
2495 if (expr
->n_arg
!= 2)
2496 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2497 "expecting two arguments", return NULL
);
2499 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2500 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2502 switch (pet_expr_op_get_type(expr
)) {
2504 return isl_pw_aff_add(lhs
, rhs
);
2506 return isl_pw_aff_sub(lhs
, rhs
);
2508 isl_pw_aff_free(lhs
);
2509 isl_pw_aff_free(rhs
);
2510 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2511 "not an addition or subtraction operation",
2517 /* Extract an affine expression from an integer division or a modulo operation.
2518 * Return NaN if we are unable to extract an affine expression.
2520 * "pc" is the context in which the affine expression is created.
2522 * In particular, if "expr" is lhs/rhs, then return
2524 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2526 * If "expr" is lhs%rhs, then return
2528 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2530 * If the second argument (rhs) is not a (positive) integer constant,
2531 * then we fail to extract an affine expression.
2533 * We simplify the result in the context of the domain of "pc" in case
2534 * this domain implies that lhs >= 0 (or < 0).
2536 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2537 __isl_keep pet_context
*pc
)
2546 if (expr
->n_arg
!= 2)
2547 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2548 "expecting two arguments", return NULL
);
2550 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2552 is_cst
= isl_pw_aff_is_cst(rhs
);
2553 if (is_cst
< 0 || !is_cst
) {
2554 isl_pw_aff_free(rhs
);
2555 return non_affine(pet_context_get_space(pc
));
2558 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2560 switch (pet_expr_op_get_type(expr
)) {
2562 res
= isl_pw_aff_tdiv_q(lhs
, rhs
);
2565 res
= isl_pw_aff_tdiv_r(lhs
, rhs
);
2568 isl_pw_aff_free(lhs
);
2569 isl_pw_aff_free(rhs
);
2570 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2571 "not a div or mod operator", return NULL
);
2574 return isl_pw_aff_gist(res
, pet_context_get_gist_domain(pc
));
2577 /* Extract an affine expression from a multiplication operation.
2578 * Return NaN if we are unable to extract an affine expression.
2579 * In particular, if neither of the arguments is a (piecewise) constant
2580 * then we return NaN.
2582 * "pc" is the context in which the affine expression is created.
2584 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2585 __isl_keep pet_context
*pc
)
2587 int lhs_cst
, rhs_cst
;
2593 if (expr
->n_arg
!= 2)
2594 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2595 "expecting two arguments", return NULL
);
2597 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2598 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2600 lhs_cst
= isl_pw_aff_is_cst(lhs
);
2601 rhs_cst
= isl_pw_aff_is_cst(rhs
);
2602 if (lhs_cst
< 0 || rhs_cst
< 0 || (!lhs_cst
&& !rhs_cst
)) {
2603 isl_pw_aff_free(lhs
);
2604 isl_pw_aff_free(rhs
);
2605 return non_affine(pet_context_get_space(pc
));
2608 return isl_pw_aff_mul(lhs
, rhs
);
2611 /* Extract an affine expression from a negation operation.
2612 * Return NaN if we are unable to extract an affine expression.
2614 * "pc" is the context in which the affine expression is created.
2616 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
2617 __isl_keep pet_context
*pc
)
2623 if (expr
->n_arg
!= 1)
2624 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2625 "expecting one argument", return NULL
);
2627 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
2628 return isl_pw_aff_neg(res
);
2631 /* Extract an affine expression from a conditional operation.
2632 * Return NaN if we are unable to extract an affine expression.
2634 * "pc" is the context in which the affine expression is created.
2636 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
2637 __isl_keep pet_context
*pc
)
2639 isl_pw_aff
*cond
, *lhs
, *rhs
;
2643 if (expr
->n_arg
!= 3)
2644 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2645 "expecting three arguments", return NULL
);
2647 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2648 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2649 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
2651 return isl_pw_aff_cond(cond
, lhs
, rhs
);
2658 static __isl_give isl_pw_aff
*wrap(__isl_take isl_pw_aff
*pwaff
, unsigned width
)
2663 ctx
= isl_pw_aff_get_ctx(pwaff
);
2664 mod
= isl_val_int_from_ui(ctx
, width
);
2665 mod
= isl_val_2exp(mod
);
2667 pwaff
= isl_pw_aff_mod_val(pwaff
, mod
);
2672 /* Limit the domain of "pwaff" to those elements where the function
2675 * 2^{width-1} <= pwaff < 2^{width-1}
2677 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
2682 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
2683 isl_local_space
*ls
= isl_local_space_from_space(space
);
2688 ctx
= isl_pw_aff_get_ctx(pwaff
);
2689 v
= isl_val_int_from_ui(ctx
, width
- 1);
2690 v
= isl_val_2exp(v
);
2692 bound
= isl_aff_zero_on_domain(ls
);
2693 bound
= isl_aff_add_constant_val(bound
, v
);
2694 b
= isl_pw_aff_from_aff(bound
);
2696 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
2697 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2699 b
= isl_pw_aff_neg(b
);
2700 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
2701 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2706 /* Handle potential overflows on signed computations.
2708 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2709 * then we adjust the domain of "pa" to avoid overflows.
2711 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
2715 struct pet_options
*options
;
2720 ctx
= isl_pw_aff_get_ctx(pa
);
2721 options
= isl_ctx_peek_pet_options(ctx
);
2722 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
2723 pa
= avoid_overflow(pa
, width
);
2728 /* Extract an affine expression from some an operation.
2729 * Return NaN if we are unable to extract an affine expression.
2730 * If the result of a binary (non boolean) operation is unsigned,
2731 * then we wrap it based on the size of the type. If the result is signed,
2732 * then we ensure that no overflow occurs.
2734 * "pc" is the context in which the affine expression is created.
2736 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
2737 __isl_keep pet_context
*pc
)
2742 switch (pet_expr_op_get_type(expr
)) {
2745 res
= extract_affine_add_sub(expr
, pc
);
2749 res
= extract_affine_div_mod(expr
, pc
);
2752 res
= extract_affine_mul(expr
, pc
);
2755 return extract_affine_neg(expr
, pc
);
2757 return extract_affine_cond(expr
, pc
);
2767 return pet_expr_extract_affine_condition(expr
, pc
);
2769 return non_affine(pet_context_get_space(pc
));
2774 if (isl_pw_aff_involves_nan(res
)) {
2775 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
2776 isl_pw_aff_free(res
);
2777 return non_affine(space
);
2780 type_size
= pet_expr_get_type_size(expr
);
2782 res
= wrap(res
, type_size
);
2784 res
= signed_overflow(res
, -type_size
);
2789 /* Extract an affine expression from some special function calls.
2790 * Return NaN if we are unable to extract an affine expression.
2791 * In particular, we handle "min", "max", "ceild", "floord",
2792 * "intMod", "intFloor" and "intCeil".
2793 * In case of the latter five, the second argument needs to be
2794 * a (positive) integer constant.
2796 * "pc" is the context in which the affine expression is created.
2798 static __isl_give isl_pw_aff
*extract_affine_from_call(
2799 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2801 isl_pw_aff
*aff1
, *aff2
;
2805 n
= pet_expr_get_n_arg(expr
);
2806 name
= pet_expr_call_get_name(expr
);
2807 if (!(n
== 2 && !strcmp(name
, "min")) &&
2808 !(n
== 2 && !strcmp(name
, "max")) &&
2809 !(n
== 2 && !strcmp(name
, "intMod")) &&
2810 !(n
== 2 && !strcmp(name
, "intFloor")) &&
2811 !(n
== 2 && !strcmp(name
, "intCeil")) &&
2812 !(n
== 2 && !strcmp(name
, "floord")) &&
2813 !(n
== 2 && !strcmp(name
, "ceild")))
2814 return non_affine(pet_context_get_space(pc
));
2816 if (!strcmp(name
, "min") || !strcmp(name
, "max")) {
2817 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2818 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
2820 if (!strcmp(name
, "min"))
2821 aff1
= isl_pw_aff_min(aff1
, aff2
);
2823 aff1
= isl_pw_aff_max(aff1
, aff2
);
2824 } else if (!strcmp(name
, "intMod")) {
2827 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2828 return non_affine(pet_context_get_space(pc
));
2829 v
= pet_expr_int_get_val(expr
->args
[1]);
2830 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2831 aff1
= isl_pw_aff_mod_val(aff1
, v
);
2835 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2836 return non_affine(pet_context_get_space(pc
));
2837 v
= pet_expr_int_get_val(expr
->args
[1]);
2838 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2839 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
2840 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
2841 aff1
= isl_pw_aff_floor(aff1
);
2843 aff1
= isl_pw_aff_ceil(aff1
);
2849 /* Extract an affine expression from "expr", if possible.
2850 * Otherwise return NaN.
2852 * "pc" is the context in which the affine expression is created.
2854 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
2855 __isl_keep pet_context
*pc
)
2860 switch (pet_expr_get_type(expr
)) {
2861 case pet_expr_access
:
2862 return extract_affine_from_access(expr
, pc
);
2864 return extract_affine_from_int(expr
, pc
);
2866 return extract_affine_from_op(expr
, pc
);
2868 return extract_affine_from_call(expr
, pc
);
2870 case pet_expr_double
:
2871 case pet_expr_error
:
2872 return non_affine(pet_context_get_space(pc
));
2876 /* Extract an affine expressions representing the comparison "LHS op RHS"
2877 * Return NaN if we are unable to extract such an affine expression.
2879 * "pc" is the context in which the affine expression is created.
2881 * If the comparison is of the form
2885 * then the expression is constructed as the conjunction of
2890 * A similar optimization is performed for max(a,b) <= c.
2891 * We do this because that will lead to simpler representations
2892 * of the expression.
2893 * If isl is ever enhanced to explicitly deal with min and max expressions,
2894 * this optimization can be removed.
2896 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
2897 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
2898 __isl_keep pet_context
*pc
)
2900 isl_pw_aff
*lhs_pa
, *rhs_pa
;
2902 if (op
== pet_op_gt
)
2903 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
2904 if (op
== pet_op_ge
)
2905 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
2907 if (op
== pet_op_lt
|| op
== pet_op_le
) {
2908 if (pet_expr_is_min(rhs
)) {
2909 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2911 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2913 return pet_and(lhs_pa
, rhs_pa
);
2915 if (pet_expr_is_max(lhs
)) {
2916 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
2918 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
2920 return pet_and(lhs_pa
, rhs_pa
);
2924 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
2925 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
2927 return pet_comparison(op
, lhs_pa
, rhs_pa
);
2930 /* Extract an affine expressions from the comparison "expr".
2931 * Return NaN if we are unable to extract such an affine expression.
2933 * "pc" is the context in which the affine expression is created.
2935 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
2936 __isl_keep pet_context
*pc
)
2938 enum pet_op_type type
;
2942 if (expr
->n_arg
!= 2)
2943 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2944 "expecting two arguments", return NULL
);
2946 type
= pet_expr_op_get_type(expr
);
2947 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
2951 /* Extract an affine expression representing the boolean operation
2952 * expressed by "expr".
2953 * Return NaN if we are unable to extract an affine expression.
2955 * "pc" is the context in which the affine expression is created.
2957 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
2958 __isl_keep pet_context
*pc
)
2960 isl_pw_aff
*lhs
, *rhs
;
2966 n
= pet_expr_get_n_arg(expr
);
2967 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2969 return pet_not(lhs
);
2971 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
2972 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
2975 /* Extract the affine expression "expr != 0 ? 1 : 0".
2976 * Return NaN if we are unable to extract an affine expression.
2978 * "pc" is the context in which the affine expression is created.
2980 static __isl_give isl_pw_aff
*extract_implicit_condition(
2981 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2985 res
= pet_expr_extract_affine(expr
, pc
);
2986 return pet_to_bool(res
);
2989 /* Extract a boolean affine expression from "expr".
2990 * Return NaN if we are unable to extract an affine expression.
2992 * "pc" is the context in which the affine expression is created.
2994 * If "expr" is neither a comparison nor a boolean operation,
2995 * then we assume it is an affine expression and return the
2996 * boolean expression "expr != 0 ? 1 : 0".
2998 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
2999 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3004 if (pet_expr_is_comparison(expr
))
3005 return extract_comparison(expr
, pc
);
3006 if (pet_expr_is_boolean(expr
))
3007 return extract_boolean(expr
, pc
);
3009 return extract_implicit_condition(expr
, pc
);
3012 /* Check if "expr" is an assume expression and if its single argument
3013 * can be converted to an affine expression in the context of "pc".
3014 * If so, replace the argument by the affine expression.
3016 __isl_give pet_expr
*pet_expr_resolve_assume(__isl_take pet_expr
*expr
,
3017 __isl_keep pet_context
*pc
)
3020 isl_multi_pw_aff
*index
;
3024 if (!pet_expr_is_assume(expr
))
3026 if (expr
->n_arg
!= 1)
3027 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3028 "expecting one argument", return pet_expr_free(expr
));
3030 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3032 return pet_expr_free(expr
);
3033 if (isl_pw_aff_involves_nan(cond
)) {
3034 isl_pw_aff_free(cond
);
3038 index
= isl_multi_pw_aff_from_pw_aff(cond
);
3039 expr
= pet_expr_set_arg(expr
, 0, pet_expr_from_index(index
));
3044 /* Return the number of bits needed to represent the type of "expr".
3045 * See the description of the type_size field of pet_expr.
3047 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
3049 return expr
? expr
->type_size
: 0;
3052 /* Replace the number of bits needed to represent the type of "expr"
3054 * See the description of the type_size field of pet_expr.
3056 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
3059 expr
= pet_expr_cow(expr
);
3063 expr
->type_size
= type_size
;
3068 /* Extend an access expression "expr" with an additional index "index".
3069 * In particular, add "index" as an extra argument to "expr" and
3070 * adjust the index expression of "expr" to refer to this extra argument.
3071 * The caller is responsible for calling pet_expr_access_set_depth
3072 * to update the corresponding access relation.
3074 * Note that we only collect the individual index expressions as
3075 * arguments of "expr" here.
3076 * An attempt to integrate them into the index expression of "expr"
3077 * is performed in pet_expr_access_plug_in_args.
3079 __isl_give pet_expr
*pet_expr_access_subscript(__isl_take pet_expr
*expr
,
3080 __isl_take pet_expr
*index
)
3084 isl_local_space
*ls
;
3087 expr
= pet_expr_cow(expr
);
3088 if (!expr
|| !index
)
3090 if (expr
->type
!= pet_expr_access
)
3091 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3092 "not an access pet_expr", goto error
);
3094 n
= pet_expr_get_n_arg(expr
);
3095 expr
= pet_expr_insert_arg(expr
, n
, index
);
3099 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3100 ls
= isl_local_space_from_space(space
);
3101 pa
= isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, isl_dim_set
, n
));
3102 expr
->acc
.index
= pet_array_subscript(expr
->acc
.index
, pa
);
3103 if (!expr
->acc
.index
)
3104 return pet_expr_free(expr
);
3108 pet_expr_free(expr
);
3109 pet_expr_free(index
);
3113 /* Extend an access expression "expr" with an additional member acces to "id".
3114 * In particular, extend the index expression of "expr" to include
3115 * the additional member access.
3116 * The caller is responsible for calling pet_expr_access_set_depth
3117 * to update the corresponding access relation.
3119 __isl_give pet_expr
*pet_expr_access_member(__isl_take pet_expr
*expr
,
3120 __isl_take isl_id
*id
)
3123 isl_multi_pw_aff
*field_access
;
3125 expr
= pet_expr_cow(expr
);
3128 if (expr
->type
!= pet_expr_access
)
3129 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3130 "not an access pet_expr", goto error
);
3132 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3133 space
= isl_space_from_domain(space
);
3134 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3135 field_access
= isl_multi_pw_aff_zero(space
);
3136 expr
->acc
.index
= pet_array_member(expr
->acc
.index
, field_access
);
3137 if (!expr
->acc
.index
)
3138 return pet_expr_free(expr
);
3142 pet_expr_free(expr
);
3147 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
3154 fprintf(stderr
, "%*s", indent
, "");
3156 switch (expr
->type
) {
3157 case pet_expr_double
:
3158 fprintf(stderr
, "%s\n", expr
->d
.s
);
3161 isl_val_dump(expr
->i
);
3163 case pet_expr_access
:
3164 if (expr
->acc
.ref_id
) {
3165 isl_id_dump(expr
->acc
.ref_id
);
3166 fprintf(stderr
, "%*s", indent
, "");
3168 isl_multi_pw_aff_dump(expr
->acc
.index
);
3169 fprintf(stderr
, "%*sdepth: %d\n", indent
+ 2,
3170 "", expr
->acc
.depth
);
3171 if (expr
->acc
.kill
) {
3172 fprintf(stderr
, "%*skill: 1\n", indent
+ 2, "");
3174 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
3175 "", expr
->acc
.read
);
3176 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
3177 "", expr
->acc
.write
);
3179 if (expr
->acc
.access
) {
3180 fprintf(stderr
, "%*saccess: ", indent
+ 2, "");
3181 isl_map_dump(expr
->acc
.access
);
3183 for (i
= 0; i
< expr
->n_arg
; ++i
)
3184 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3187 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
3188 for (i
= 0; i
< expr
->n_arg
; ++i
)
3189 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3192 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
3193 for (i
= 0; i
< expr
->n_arg
; ++i
)
3194 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3197 fprintf(stderr
, "(%s)\n", expr
->type_name
);
3198 for (i
= 0; i
< expr
->n_arg
; ++i
)
3199 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
3201 case pet_expr_error
:
3202 fprintf(stderr
, "ERROR\n");
3207 void pet_expr_dump(__isl_keep pet_expr
*expr
)
3209 pet_expr_dump_with_indent(expr
, 0);