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 access relation and an index expression.
151 * By default, it is considered to be a read access.
153 __isl_give pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
154 __isl_take isl_multi_pw_aff
*index
)
156 isl_ctx
*ctx
= isl_map_get_ctx(access
);
159 if (!index
|| !access
)
161 expr
= pet_expr_alloc(ctx
, pet_expr_access
);
165 expr
->acc
.access
= access
;
166 expr
->acc
.index
= index
;
172 isl_map_free(access
);
173 isl_multi_pw_aff_free(index
);
177 /* Construct an access pet_expr from an index expression.
178 * By default, the access is considered to be a read access.
180 __isl_give pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
184 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
185 return pet_expr_from_access_and_index(access
, index
);
188 /* Extend the range of "access" with "n" dimensions, retaining
189 * the tuple identifier on this range.
191 * If "access" represents a member access, then extend the range
194 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
198 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
200 if (!isl_map_range_is_wrapping(access
)) {
201 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
205 domain
= isl_map_copy(access
);
206 domain
= isl_map_range_factor_domain(domain
);
207 access
= isl_map_range_factor_range(access
);
208 access
= extend_range(access
, n
);
209 access
= isl_map_range_product(domain
, access
);
212 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
217 /* Finalize the construction of an access expression by setting
218 * the depth of the accessed array.
220 * The index expression may have been updated by
221 * pet_expr_access_subscript and/or pet_expr_access_member
222 * without the access relation having been updated accordingly.
223 * We perform this update here, taking into account the depth
224 * of the accessed array.
226 * If the number of indices is smaller than the depth of the array,
227 * then we assume that all elements of the remaining dimensions
230 __isl_give pet_expr
*pet_expr_access_set_depth(__isl_take pet_expr
*expr
,
236 expr
= pet_expr_cow(expr
);
240 access
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
242 return pet_expr_free(expr
);
244 dim
= isl_map_dim(access
, isl_dim_out
);
246 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
247 "number of indices greater than depth",
248 access
= isl_map_free(access
));
251 access
= extend_range(access
, depth
- dim
);
253 return pet_expr_access_set_access(expr
, access
);
256 /* Construct a pet_expr that kills the elements specified by
257 * the index expression "index" and the access relation "access".
259 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
260 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
264 if (!access
|| !index
)
267 expr
= pet_expr_from_access_and_index(access
, index
);
268 expr
= pet_expr_access_set_read(expr
, 0);
269 return pet_expr_new_unary(pet_op_kill
, expr
);
271 isl_map_free(access
);
272 isl_multi_pw_aff_free(index
);
276 /* Construct a unary pet_expr that performs "op" on "arg".
278 __isl_give pet_expr
*pet_expr_new_unary(enum pet_op_type op
,
279 __isl_take pet_expr
*arg
)
286 ctx
= pet_expr_get_ctx(arg
);
287 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
288 expr
= pet_expr_set_n_arg(expr
, 1);
293 expr
->args
[pet_un_arg
] = arg
;
301 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
302 * where the result is represented using a type of "type_size" bits
303 * (may be zero if unknown or if the type is not an integer).
305 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
306 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
313 ctx
= pet_expr_get_ctx(lhs
);
314 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
315 expr
= pet_expr_set_n_arg(expr
, 2);
320 expr
->type_size
= type_size
;
321 expr
->args
[pet_bin_lhs
] = lhs
;
322 expr
->args
[pet_bin_rhs
] = rhs
;
331 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
333 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
334 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
339 if (!cond
|| !lhs
|| !rhs
)
341 ctx
= pet_expr_get_ctx(cond
);
342 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
343 expr
= pet_expr_set_n_arg(expr
, 3);
347 expr
->op
= pet_op_cond
;
348 expr
->args
[pet_ter_cond
] = cond
;
349 expr
->args
[pet_ter_true
] = lhs
;
350 expr
->args
[pet_ter_false
] = rhs
;
360 /* Construct a call pet_expr that calls function "name" with "n_arg"
361 * arguments. The caller is responsible for filling in the arguments.
363 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
368 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
369 expr
= pet_expr_set_n_arg(expr
, n_arg
);
373 expr
->name
= strdup(name
);
375 return pet_expr_free(expr
);
380 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
382 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
383 __isl_take pet_expr
*arg
)
391 ctx
= pet_expr_get_ctx(arg
);
392 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
393 expr
= pet_expr_set_n_arg(expr
, 1);
397 expr
->type_name
= strdup(type_name
);
398 if (!expr
->type_name
)
410 /* Construct a pet_expr that represents the double "d".
412 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
413 double val
, const char *s
)
417 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
422 expr
->d
.s
= strdup(s
);
424 return pet_expr_free(expr
);
429 /* Construct a pet_expr that represents the integer value "v".
431 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
439 ctx
= isl_val_get_ctx(v
);
440 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
452 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
460 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
461 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
462 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
463 for (i
= 0; i
< expr
->n_arg
; ++i
)
464 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
466 switch (expr
->type
) {
467 case pet_expr_access
:
468 if (expr
->acc
.ref_id
)
469 dup
= pet_expr_access_set_ref_id(dup
,
470 isl_id_copy(expr
->acc
.ref_id
));
471 dup
= pet_expr_access_set_access(dup
,
472 isl_map_copy(expr
->acc
.access
));
473 dup
= pet_expr_access_set_index(dup
,
474 isl_multi_pw_aff_copy(expr
->acc
.index
));
475 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
476 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
479 dup
= pet_expr_call_set_name(dup
, expr
->name
);
482 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
484 case pet_expr_double
:
485 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
488 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
491 dup
= pet_expr_op_set_type(dup
, expr
->op
);
494 dup
= pet_expr_free(dup
);
501 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
509 return pet_expr_dup(expr
);
512 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
521 for (i
= 0; i
< expr
->n_arg
; ++i
)
522 pet_expr_free(expr
->args
[i
]);
525 switch (expr
->type
) {
526 case pet_expr_access
:
527 isl_id_free(expr
->acc
.ref_id
);
528 isl_map_free(expr
->acc
.access
);
529 isl_multi_pw_aff_free(expr
->acc
.index
);
535 free(expr
->type_name
);
537 case pet_expr_double
:
541 isl_val_free(expr
->i
);
548 isl_ctx_deref(expr
->ctx
);
553 /* Return an additional reference to "expr".
555 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
564 /* Return the isl_ctx in which "expr" was created.
566 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
568 return expr
? expr
->ctx
: NULL
;
571 /* Return the type of "expr".
573 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
576 return pet_expr_error
;
580 /* Return the number of arguments of "expr".
582 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
590 /* Set the number of arguments of "expr" to "n".
592 * If "expr" originally had more arguments, then remove the extra arguments.
593 * If "expr" originally had fewer arguments, then create space for
594 * the extra arguments ans initialize them to NULL.
596 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
603 if (expr
->n_arg
== n
)
605 expr
= pet_expr_cow(expr
);
609 if (n
< expr
->n_arg
) {
610 for (i
= n
; i
< expr
->n_arg
; ++i
)
611 pet_expr_free(expr
->args
[i
]);
616 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
618 return pet_expr_free(expr
);
620 for (i
= expr
->n_arg
; i
< n
; ++i
)
621 expr
->args
[i
] = NULL
;
627 /* Return the argument of "expr" at position "pos".
629 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
633 if (pos
< 0 || pos
>= expr
->n_arg
)
634 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
635 "position out of bounds", return NULL
);
637 return pet_expr_copy(expr
->args
[pos
]);
640 /* Replace the argument of "expr" at position "pos" by "arg".
642 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
643 __isl_take pet_expr
*arg
)
647 if (pos
< 0 || pos
>= expr
->n_arg
)
648 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
649 "position out of bounds", goto error
);
650 if (expr
->args
[pos
] == arg
) {
655 expr
= pet_expr_cow(expr
);
659 pet_expr_free(expr
->args
[pos
]);
660 expr
->args
[pos
] = arg
;
669 /* Does "expr" perform a comparison operation?
671 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
675 if (expr
->type
!= pet_expr_op
)
690 /* Does "expr" perform a boolean operation?
692 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
696 if (expr
->type
!= pet_expr_op
)
708 /* Is "expr" an assume statement?
710 int pet_expr_is_assume(__isl_keep pet_expr
*expr
)
714 if (expr
->type
!= pet_expr_op
)
716 return expr
->op
== pet_op_assume
;
719 /* Does "expr" perform a min operation?
721 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
725 if (expr
->type
!= pet_expr_call
)
727 if (expr
->n_arg
!= 2)
729 if (strcmp(expr
->name
, "min") != 0)
734 /* Does "expr" perform a max operation?
736 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
740 if (expr
->type
!= pet_expr_call
)
742 if (expr
->n_arg
!= 2)
744 if (strcmp(expr
->name
, "max") != 0)
749 /* Does "expr" represent an access to an unnamed space, i.e.,
750 * does it represent an affine expression?
752 int pet_expr_is_affine(__isl_keep pet_expr
*expr
)
758 if (expr
->type
!= pet_expr_access
)
761 has_id
= isl_multi_pw_aff_has_tuple_id(expr
->acc
.index
, isl_dim_out
);
768 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
769 * not part of any struct?
771 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
775 if (expr
->type
!= pet_expr_access
)
777 if (isl_map_range_is_wrapping(expr
->acc
.access
))
780 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
783 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
786 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
787 __isl_keep isl_multi_pw_aff
*mpa2
)
791 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
792 if (equal
< 0 || equal
)
794 mpa2
= isl_multi_pw_aff_copy(mpa2
);
795 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
796 isl_multi_pw_aff_get_space(mpa1
));
797 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
798 isl_multi_pw_aff_free(mpa2
);
803 /* Return 1 if the two pet_exprs are equivalent.
805 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
809 if (!expr1
|| !expr2
)
812 if (expr1
->type
!= expr2
->type
)
814 if (expr1
->n_arg
!= expr2
->n_arg
)
816 for (i
= 0; i
< expr1
->n_arg
; ++i
)
817 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
819 switch (expr1
->type
) {
822 case pet_expr_double
:
823 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
825 if (expr1
->d
.val
!= expr2
->d
.val
)
829 if (!isl_val_eq(expr1
->i
, expr2
->i
))
832 case pet_expr_access
:
833 if (expr1
->acc
.read
!= expr2
->acc
.read
)
835 if (expr1
->acc
.write
!= expr2
->acc
.write
)
837 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
839 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
841 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
843 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
845 if (!multi_pw_aff_is_equal(expr1
->acc
.index
, expr2
->acc
.index
))
849 if (expr1
->op
!= expr2
->op
)
853 if (strcmp(expr1
->name
, expr2
->name
))
857 if (strcmp(expr1
->type_name
, expr2
->type_name
))
865 /* Does the access expression "expr" read the accessed elements?
867 int pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
871 if (expr
->type
!= pet_expr_access
)
872 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
873 "not an access expression", return -1);
875 return expr
->acc
.read
;
878 /* Does the access expression "expr" write to the accessed elements?
880 int pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
884 if (expr
->type
!= pet_expr_access
)
885 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
886 "not an access expression", return -1);
888 return expr
->acc
.write
;
891 /* Return the identifier of the array accessed by "expr".
893 * If "expr" represents a member access, then return the identifier
894 * of the outer structure array.
896 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
900 if (expr
->type
!= pet_expr_access
)
901 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
902 "not an access expression", return NULL
);
904 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
)) {
908 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
909 space
= isl_space_range(space
);
910 while (space
&& isl_space_is_wrapping(space
))
911 space
= isl_space_domain(isl_space_unwrap(space
));
912 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
913 isl_space_free(space
);
918 return isl_multi_pw_aff_get_tuple_id(expr
->acc
.index
, isl_dim_out
);
921 /* Return the parameter space of "expr".
923 __isl_give isl_space
*pet_expr_access_get_parameter_space(
924 __isl_keep pet_expr
*expr
)
930 if (expr
->type
!= pet_expr_access
)
931 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
932 "not an access expression", return NULL
);
934 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
935 space
= isl_space_params(space
);
940 /* Return the domain space of "expr", without the arguments (if any).
942 __isl_give isl_space
*pet_expr_access_get_domain_space(
943 __isl_keep pet_expr
*expr
)
949 if (expr
->type
!= pet_expr_access
)
950 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
951 "not an access expression", return NULL
);
953 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
954 space
= isl_space_domain(space
);
955 if (isl_space_is_wrapping(space
))
956 space
= isl_space_domain(isl_space_unwrap(space
));
961 /* Return the space of the data accessed by "expr".
963 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
969 if (expr
->type
!= pet_expr_access
)
970 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
971 "not an access expression", return NULL
);
973 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
974 space
= isl_space_range(space
);
979 /* Modify all expressions of type pet_expr_access in "expr"
980 * by calling "fn" on them.
982 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
983 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
988 n
= pet_expr_get_n_arg(expr
);
989 for (i
= 0; i
< n
; ++i
) {
990 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
991 arg
= pet_expr_map_access(arg
, fn
, user
);
992 expr
= pet_expr_set_arg(expr
, i
, arg
);
998 if (expr
->type
== pet_expr_access
)
999 expr
= fn(expr
, user
);
1004 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1006 * Return -1 on error (where fn returning a negative value is treated as
1008 * Otherwise return 0.
1010 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
1011 enum pet_expr_type type
,
1012 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1019 for (i
= 0; i
< expr
->n_arg
; ++i
)
1020 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
1021 type
, fn
, user
) < 0)
1024 if (expr
->type
== type
)
1025 return fn(expr
, user
);
1030 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1032 * Return -1 on error (where fn returning a negative value is treated as
1034 * Otherwise return 0.
1036 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
1037 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1039 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1042 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1044 * Return -1 on error (where fn returning a negative value is treated as
1046 * Otherwise return 0.
1048 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
1049 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1051 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1054 /* Internal data structure for pet_expr_writes.
1055 * "id" is the identifier that we are looking for.
1056 * "found" is set if we have found the identifier being written to.
1058 struct pet_expr_writes_data
{
1063 /* Given an access expression, check if it writes to data->id.
1064 * If so, set data->found and abort the search.
1066 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1068 struct pet_expr_writes_data
*data
= user
;
1071 if (!expr
->acc
.write
)
1073 if (pet_expr_is_affine(expr
))
1076 write_id
= pet_expr_access_get_id(expr
);
1077 isl_id_free(write_id
);
1082 if (write_id
!= data
->id
)
1089 /* Does expression "expr" write to "id"?
1091 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1093 struct pet_expr_writes_data data
;
1097 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1104 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1105 * index expression and access relation of "expr"
1106 * to dimensions of "dst_type" at "dst_pos".
1108 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1109 enum isl_dim_type dst_type
, unsigned dst_pos
,
1110 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1112 expr
= pet_expr_cow(expr
);
1115 if (expr
->type
!= pet_expr_access
)
1116 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1117 "not an access pet_expr", return pet_expr_free(expr
));
1119 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
1120 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1121 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1122 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1123 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1124 return pet_expr_free(expr
);
1129 /* Replace the index expression and access relation of "expr"
1130 * by their preimages under the function represented by "ma".
1132 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1133 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1135 expr
= pet_expr_cow(expr
);
1138 if (expr
->type
!= pet_expr_access
)
1139 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1140 "not an access pet_expr", goto error
);
1142 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(expr
->acc
.access
,
1143 isl_multi_aff_copy(ma
));
1144 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1146 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1147 return pet_expr_free(expr
);
1151 isl_multi_aff_free(ma
);
1152 pet_expr_free(expr
);
1156 /* Replace the index expression and access relation of "expr"
1157 * by their preimages under the function represented by "mpa".
1159 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1160 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1162 expr
= pet_expr_cow(expr
);
1165 if (expr
->type
!= pet_expr_access
)
1166 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1167 "not an access pet_expr", goto error
);
1169 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1170 expr
->acc
.access
, isl_multi_pw_aff_copy(mpa
));
1171 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1172 expr
->acc
.index
, mpa
);
1173 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1174 return pet_expr_free(expr
);
1178 isl_multi_pw_aff_free(mpa
);
1179 pet_expr_free(expr
);
1183 /* Return the index expression of access expression "expr".
1185 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1186 __isl_keep pet_expr
*expr
)
1190 if (expr
->type
!= pet_expr_access
)
1191 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1192 "not an access expression", return NULL
);
1194 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1197 /* Align the parameters of expr->acc.index and expr->acc.access.
1199 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1201 expr
= pet_expr_cow(expr
);
1204 if (expr
->type
!= pet_expr_access
)
1205 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1206 "not an access expression", return pet_expr_free(expr
));
1208 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1209 isl_multi_pw_aff_get_space(expr
->acc
.index
));
1210 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1211 isl_map_get_space(expr
->acc
.access
));
1212 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1213 return pet_expr_free(expr
);
1218 /* Are "expr1" and "expr2" both array accesses such that
1219 * the access relation of "expr1" is a subset of that of "expr2"?
1220 * Only take into account the first "n_arg" arguments.
1222 * This function is tailored for use by mark_self_dependences in nest.c.
1223 * In particular, the input expressions may have more than "n_arg"
1224 * elements in their arguments arrays, while only the first "n_arg"
1225 * elements are referenced from the access relations.
1227 int pet_expr_is_sub_access(__isl_keep pet_expr
*expr1
,
1228 __isl_keep pet_expr
*expr2
, int n_arg
)
1233 if (!expr1
|| !expr2
)
1235 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1237 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1239 if (pet_expr_is_affine(expr1
))
1241 if (pet_expr_is_affine(expr2
))
1243 n1
= pet_expr_get_n_arg(expr1
);
1246 n2
= pet_expr_get_n_arg(expr2
);
1251 for (i
= 0; i
< n1
; ++i
) {
1253 equal
= pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]);
1254 if (equal
< 0 || !equal
)
1257 id1
= pet_expr_access_get_id(expr1
);
1258 id2
= pet_expr_access_get_id(expr2
);
1266 return isl_map_is_subset(expr1
->acc
.access
, expr2
->acc
.access
);
1269 /* Given a set in the iteration space "domain", extend it to live in the space
1270 * of the domain of access relations.
1272 * That, is the number of arguments "n" is 0, then simply return domain.
1273 * Otherwise, return [domain -> [a_1,...,a_n]].
1275 static __isl_give isl_set
*add_arguments(__isl_take isl_set
*domain
, int n
)
1282 map
= isl_map_from_domain(domain
);
1283 map
= isl_map_add_dims(map
, isl_dim_out
, n
);
1284 return isl_map_wrap(map
);
1287 /* Add extra conditions to the domains of all access relations in "expr".
1289 * The conditions are not added to the index expression. Instead, they
1290 * are used to try and simplify the index expression.
1292 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1293 __isl_take isl_set
*cond
)
1297 expr
= pet_expr_cow(expr
);
1301 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1302 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1303 isl_set_copy(cond
));
1308 if (expr
->type
== pet_expr_access
) {
1309 cond
= add_arguments(cond
, expr
->n_arg
);
1310 expr
->acc
.access
= isl_map_intersect_domain(expr
->acc
.access
,
1311 isl_set_copy(cond
));
1312 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
,
1313 isl_set_copy(cond
));
1314 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1322 return pet_expr_free(expr
);
1325 /* Modify the access relation and index expression
1326 * of the given access expression
1327 * based on the given iteration space transformation.
1328 * In particular, precompose the access relation and index expression
1329 * with the update function.
1331 * If the access has any arguments then the domain of the access relation
1332 * is a wrapped mapping from the iteration space to the space of
1333 * argument values. We only need to change the domain of this wrapped
1334 * mapping, so we extend the input transformation with an identity mapping
1335 * on the space of argument values.
1337 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1338 __isl_keep isl_multi_pw_aff
*update
)
1340 expr
= pet_expr_cow(expr
);
1343 if (expr
->type
!= pet_expr_access
)
1344 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1345 "not an access expression", return pet_expr_free(expr
));
1347 update
= isl_multi_pw_aff_copy(update
);
1349 if (expr
->n_arg
> 0) {
1351 isl_multi_pw_aff
*id
;
1353 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1354 space
= isl_space_domain(space
);
1355 space
= isl_space_unwrap(space
);
1356 space
= isl_space_range(space
);
1357 space
= isl_space_map_from_set(space
);
1358 id
= isl_multi_pw_aff_identity(space
);
1359 update
= isl_multi_pw_aff_product(update
, id
);
1362 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1364 isl_multi_pw_aff_copy(update
));
1365 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1366 expr
->acc
.index
, update
);
1367 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1368 return pet_expr_free(expr
);
1373 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1375 isl_multi_pw_aff
*update
= user
;
1377 return pet_expr_access_update_domain(expr
, update
);
1380 /* Modify all access relations in "expr" by precomposing them with
1381 * the given iteration space transformation.
1383 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1384 __isl_take isl_multi_pw_aff
*update
)
1386 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1387 isl_multi_pw_aff_free(update
);
1391 /* Given an expression with accesses that have a 0D anonymous domain,
1392 * replace those domains by "space".
1394 __isl_give pet_expr
*pet_expr_insert_domain(__isl_take pet_expr
*expr
,
1395 __isl_take isl_space
*space
)
1397 isl_multi_pw_aff
*mpa
;
1399 space
= isl_space_from_domain(space
);
1400 mpa
= isl_multi_pw_aff_zero(space
);
1401 return pet_expr_update_domain(expr
, mpa
);
1404 /* Add all parameters in "space" to the access relation and index expression
1407 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1409 isl_space
*space
= user
;
1411 expr
= pet_expr_cow(expr
);
1414 if (expr
->type
!= pet_expr_access
)
1415 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1416 "not an access expression", return pet_expr_free(expr
));
1418 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1419 isl_space_copy(space
));
1420 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1421 isl_space_copy(space
));
1422 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1423 return pet_expr_free(expr
);
1428 /* Add all parameters in "space" to all access relations and index expressions
1431 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1432 __isl_take isl_space
*space
)
1434 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1435 isl_space_free(space
);
1439 /* Insert an argument expression corresponding to "test" in front
1440 * of the list of arguments described by *n_arg and *args.
1442 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1443 __isl_keep isl_multi_pw_aff
*test
)
1446 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1449 return pet_expr_free(expr
);
1450 expr
= pet_expr_cow(expr
);
1455 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1457 return pet_expr_free(expr
);
1460 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1462 return pet_expr_free(expr
);
1463 for (i
= 0; i
< expr
->n_arg
; ++i
)
1464 ext
[1 + i
] = expr
->args
[i
];
1469 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1471 return pet_expr_free(expr
);
1476 /* Make the expression "expr" depend on the value of "test"
1477 * being equal to "satisfied".
1479 * If "test" is an affine expression, we simply add the conditions
1480 * on the expression having the value "satisfied" to all access relations
1481 * and index expressions.
1483 * Otherwise, we add a filter to "expr" (which is then assumed to be
1484 * an access expression) corresponding to "test" being equal to "satisfied".
1486 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1487 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1492 isl_pw_multi_aff
*pma
;
1494 expr
= pet_expr_cow(expr
);
1498 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1502 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
1503 isl_multi_pw_aff_free(test
);
1505 cond
= isl_pw_aff_non_zero_set(pa
);
1507 cond
= isl_pw_aff_zero_set(pa
);
1508 return pet_expr_restrict(expr
, cond
);
1511 ctx
= isl_multi_pw_aff_get_ctx(test
);
1512 if (expr
->type
!= pet_expr_access
)
1513 isl_die(ctx
, isl_error_invalid
,
1514 "can only filter access expressions", goto error
);
1516 space
= isl_space_domain(isl_multi_pw_aff_get_space(expr
->acc
.index
));
1517 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1518 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
1520 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
1522 isl_pw_multi_aff_copy(pma
));
1523 pma
= isl_pw_multi_aff_gist(pma
,
1524 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
)));
1525 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
1526 expr
->acc
.index
, pma
);
1527 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1530 expr
= insert_access_arg(expr
, test
);
1532 isl_multi_pw_aff_free(test
);
1535 isl_multi_pw_aff_free(test
);
1536 return pet_expr_free(expr
);
1539 /* Add a reference identifier to access expression "expr".
1540 * "user" points to an integer that contains the sequence number
1541 * of the next reference.
1543 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
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 ctx
= pet_expr_get_ctx(expr
);
1558 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1559 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1560 if (!expr
->acc
.ref_id
)
1561 return pet_expr_free(expr
);
1566 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
1568 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1571 /* Reset the user pointer on all parameter and tuple ids in
1572 * the access relation and the index expressions
1573 * of the access expression "expr".
1575 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
1578 expr
= pet_expr_cow(expr
);
1581 if (expr
->type
!= pet_expr_access
)
1582 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1583 "not an access expression", return pet_expr_free(expr
));
1585 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1586 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1587 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1588 return pet_expr_free(expr
);
1593 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
1595 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1598 /* Data used in access_gist() callback.
1600 struct pet_access_gist_data
{
1602 isl_union_map
*value_bounds
;
1605 /* Given an expression "expr" of type pet_expr_access, compute
1606 * the gist of the associated access relation and index expression
1607 * with respect to data->domain and the bounds on the values of the arguments
1608 * of the expression.
1610 * The arguments of "expr" have been gisted right before "expr" itself
1611 * is gisted. The gisted arguments may have become equal where before
1612 * they may not have been (obviously) equal. We therefore take
1613 * the opportunity to remove duplicate arguments here.
1615 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
1617 struct pet_access_gist_data
*data
= user
;
1620 expr
= pet_expr_remove_duplicate_args(expr
);
1621 expr
= pet_expr_cow(expr
);
1624 if (expr
->type
!= pet_expr_access
)
1625 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1626 "not an access expression", return pet_expr_free(expr
));
1628 domain
= isl_set_copy(data
->domain
);
1629 if (expr
->n_arg
> 0)
1630 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1631 data
->value_bounds
);
1633 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1634 isl_set_copy(domain
));
1635 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1636 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1637 return pet_expr_free(expr
);
1642 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
1643 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1645 struct pet_access_gist_data data
= { context
, value_bounds
};
1647 return pet_expr_map_access(expr
, &access_gist
, &data
);
1650 /* Mark "expr" as a read dependening on "read".
1652 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
1656 return pet_expr_free(expr
);
1657 if (expr
->type
!= pet_expr_access
)
1658 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1659 "not an access expression", return pet_expr_free(expr
));
1660 if (expr
->acc
.read
== read
)
1662 expr
= pet_expr_cow(expr
);
1665 expr
->acc
.read
= read
;
1670 /* Mark "expr" as a write dependening on "write".
1672 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
1676 return pet_expr_free(expr
);
1677 if (expr
->type
!= pet_expr_access
)
1678 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1679 "not an access expression", return pet_expr_free(expr
));
1680 if (expr
->acc
.write
== write
)
1682 expr
= pet_expr_cow(expr
);
1685 expr
->acc
.write
= write
;
1690 /* Replace the access relation of "expr" by "access".
1692 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
1693 __isl_take isl_map
*access
)
1695 expr
= pet_expr_cow(expr
);
1696 if (!expr
|| !access
)
1698 if (expr
->type
!= pet_expr_access
)
1699 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1700 "not an access expression", goto error
);
1701 isl_map_free(expr
->acc
.access
);
1702 expr
->acc
.access
= access
;
1706 isl_map_free(access
);
1707 pet_expr_free(expr
);
1711 /* Replace the index expression of "expr" by "index".
1713 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
1714 __isl_take isl_multi_pw_aff
*index
)
1716 expr
= pet_expr_cow(expr
);
1717 if (!expr
|| !index
)
1719 if (expr
->type
!= pet_expr_access
)
1720 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1721 "not an access expression", goto error
);
1722 isl_multi_pw_aff_free(expr
->acc
.index
);
1723 expr
->acc
.index
= index
;
1727 isl_multi_pw_aff_free(index
);
1728 pet_expr_free(expr
);
1732 /* Return the reference identifier of access expression "expr".
1734 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
1738 if (expr
->type
!= pet_expr_access
)
1739 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1740 "not an access expression", return NULL
);
1742 return isl_id_copy(expr
->acc
.ref_id
);
1745 /* Replace the reference identifier of access expression "expr" by "ref_id".
1747 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
1748 __isl_take isl_id
*ref_id
)
1750 expr
= pet_expr_cow(expr
);
1751 if (!expr
|| !ref_id
)
1753 if (expr
->type
!= pet_expr_access
)
1754 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1755 "not an access expression", goto error
);
1756 isl_id_free(expr
->acc
.ref_id
);
1757 expr
->acc
.ref_id
= ref_id
;
1761 isl_id_free(ref_id
);
1762 pet_expr_free(expr
);
1766 /* Tag the access relation "access" with "id".
1767 * That is, insert the id as the range of a wrapped relation
1768 * in the domain of "access".
1770 * If "access" is of the form
1774 * then the result is of the form
1776 * [D[i] -> id[]] -> A[a]
1778 __isl_give isl_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
1779 __isl_take isl_map
*access
)
1785 if (expr
->type
!= pet_expr_access
)
1786 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1787 "not an access expression",
1788 return isl_map_free(access
));
1790 id
= isl_id_copy(expr
->acc
.ref_id
);
1791 space
= isl_space_range(isl_map_get_space(access
));
1792 space
= isl_space_from_range(space
);
1793 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
1794 add_tag
= isl_map_universe(space
);
1795 access
= isl_map_domain_product(access
, add_tag
);
1800 /* Return the relation mapping pairs of domain iterations and argument
1801 * values to the corresponding accessed data elements.
1803 __isl_give isl_map
*pet_expr_access_get_dependent_access(
1804 __isl_keep pet_expr
*expr
)
1808 if (expr
->type
!= pet_expr_access
)
1809 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1810 "not an access expression", return NULL
);
1812 return isl_map_copy(expr
->acc
.access
);
1815 /* Return the relation mapping domain iterations to all possibly
1816 * accessed data elements.
1817 * In particular, take the access relation and project out the values
1818 * of the arguments, if any.
1820 __isl_give isl_map
*pet_expr_access_get_may_access(__isl_keep pet_expr
*expr
)
1828 if (expr
->type
!= pet_expr_access
)
1829 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1830 "not an access expression", return NULL
);
1832 access
= pet_expr_access_get_dependent_access(expr
);
1833 if (expr
->n_arg
== 0)
1836 space
= isl_space_domain(isl_map_get_space(access
));
1837 map
= isl_map_universe(isl_space_unwrap(space
));
1838 map
= isl_map_domain_map(map
);
1839 access
= isl_map_apply_domain(access
, map
);
1844 /* Return a relation mapping domain iterations to definitely
1845 * accessed data elements, assuming the statement containing
1846 * the expression is executed.
1848 * If there are no arguments, then all elements are accessed.
1849 * Otherwise, we conservatively return an empty relation.
1851 __isl_give isl_map
*pet_expr_access_get_must_access(__isl_keep pet_expr
*expr
)
1857 if (expr
->type
!= pet_expr_access
)
1858 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1859 "not an access expression", return NULL
);
1861 if (expr
->n_arg
== 0)
1862 return pet_expr_access_get_dependent_access(expr
);
1864 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1865 space
= isl_space_domain_factor_domain(space
);
1867 return isl_map_empty(space
);
1870 /* Return the relation mapping domain iterations to all possibly
1871 * accessed data elements, with its domain tagged with the reference
1874 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
1875 __isl_keep pet_expr
*expr
)
1882 access
= pet_expr_access_get_may_access(expr
);
1883 access
= pet_expr_tag_access(expr
, access
);
1888 /* Return the operation type of operation expression "expr".
1890 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
1894 if (expr
->type
!= pet_expr_op
)
1895 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1896 "not an operation expression", return pet_op_last
);
1901 /* Replace the operation type of operation expression "expr" by "type".
1903 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
1904 enum pet_op_type type
)
1907 return pet_expr_free(expr
);
1908 if (expr
->type
!= pet_expr_op
)
1909 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1910 "not an operation expression",
1911 return pet_expr_free(expr
));
1912 if (expr
->op
== type
)
1914 expr
= pet_expr_cow(expr
);
1922 /* Return the name of the function called by "expr".
1924 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
1928 if (expr
->type
!= pet_expr_call
)
1929 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1930 "not a call expression", return NULL
);
1934 /* Replace the name of the function called by "expr" by "name".
1936 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
1937 __isl_keep
const char *name
)
1939 expr
= pet_expr_cow(expr
);
1941 return pet_expr_free(expr
);
1942 if (expr
->type
!= pet_expr_call
)
1943 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1944 "not a call expression", return pet_expr_free(expr
));
1946 expr
->name
= strdup(name
);
1948 return pet_expr_free(expr
);
1952 /* Replace the type of the cast performed by "expr" by "name".
1954 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
1955 __isl_keep
const char *name
)
1957 expr
= pet_expr_cow(expr
);
1959 return pet_expr_free(expr
);
1960 if (expr
->type
!= pet_expr_cast
)
1961 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1962 "not a cast expression", return pet_expr_free(expr
));
1963 free(expr
->type_name
);
1964 expr
->type_name
= strdup(name
);
1965 if (!expr
->type_name
)
1966 return pet_expr_free(expr
);
1970 /* Return the value of the integer represented by "expr".
1972 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
1976 if (expr
->type
!= pet_expr_int
)
1977 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1978 "not an int expression", return NULL
);
1980 return isl_val_copy(expr
->i
);
1983 /* Replace the value of the integer represented by "expr" by "v".
1985 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
1986 __isl_take isl_val
*v
)
1988 expr
= pet_expr_cow(expr
);
1991 if (expr
->type
!= pet_expr_int
)
1992 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1993 "not an int expression", goto error
);
1994 isl_val_free(expr
->i
);
2000 pet_expr_free(expr
);
2004 /* Replace the value and string representation of the double
2005 * represented by "expr" by "d" and "s".
2007 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
2008 double d
, __isl_keep
const char *s
)
2010 expr
= pet_expr_cow(expr
);
2012 return pet_expr_free(expr
);
2013 if (expr
->type
!= pet_expr_double
)
2014 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2015 "not a double expression", return pet_expr_free(expr
));
2018 expr
->d
.s
= strdup(s
);
2020 return pet_expr_free(expr
);
2024 /* Return a string representation of the double expression "expr".
2026 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2030 if (expr
->type
!= pet_expr_double
)
2031 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2032 "not a double expression", return NULL
);
2033 return strdup(expr
->d
.s
);
2036 /* Return a piecewise affine expression defined on the specified domain
2037 * that represents NaN.
2039 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2041 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2044 /* This function is called when we come across an access that is
2045 * nested in what is supposed to be an affine expression.
2046 * "pc" is the context in which the affine expression is created.
2047 * If nesting is allowed in "pc", we return an affine expression that is
2048 * equal to a new parameter corresponding to this nested access.
2049 * Otherwise, we return NaN.
2051 * Note that we currently don't allow nested accesses themselves
2052 * to contain any nested accesses, so we check if "expr" itself
2053 * involves any nested accesses (either explicitly as arguments
2054 * or implicitly through parameters) and return NaN if it does.
2056 * The new parameter is resolved in resolve_nested.
2058 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2059 __isl_keep pet_context
*pc
)
2064 isl_local_space
*ls
;
2070 if (!pet_context_allow_nesting(pc
))
2071 return non_affine(pet_context_get_space(pc
));
2073 if (pet_expr_get_type(expr
) != pet_expr_access
)
2074 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2075 "not an access expression", return NULL
);
2077 if (expr
->n_arg
> 0)
2078 return non_affine(pet_context_get_space(pc
));
2080 space
= pet_expr_access_get_parameter_space(expr
);
2081 nested
= pet_nested_any_in_space(space
);
2082 isl_space_free(space
);
2084 return non_affine(pet_context_get_space(pc
));
2086 ctx
= pet_expr_get_ctx(expr
);
2087 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2088 space
= pet_context_get_space(pc
);
2089 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2091 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2092 ls
= isl_local_space_from_space(space
);
2093 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2095 return isl_pw_aff_from_aff(aff
);
2098 /* Extract an affine expression from the access pet_expr "expr".
2099 * "pc" is the context in which the affine expression is created.
2101 * If "expr" is actually an affine expression rather than
2102 * a real access, then we return that expression.
2103 * Otherwise, we require that "expr" is of an integral type.
2104 * If not, we return NaN.
2106 * If the variable has been assigned a known affine expression,
2107 * then we return that expression.
2109 * Otherwise, we return an expression that is equal to a parameter
2110 * representing "expr" (if "allow_nested" is set).
2112 static __isl_give isl_pw_aff
*extract_affine_from_access(
2113 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2118 if (pet_expr_is_affine(expr
)) {
2120 isl_multi_pw_aff
*mpa
;
2122 mpa
= pet_expr_access_get_index(expr
);
2123 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
2124 isl_multi_pw_aff_free(mpa
);
2128 if (pet_expr_get_type_size(expr
) == 0)
2129 return non_affine(pet_context_get_space(pc
));
2131 if (!pet_expr_is_scalar_access(expr
))
2132 return nested_access(expr
, pc
);
2134 id
= pet_expr_access_get_id(expr
);
2135 if (pet_context_is_assigned(pc
, id
))
2136 return pet_context_get_value(pc
, id
);
2139 return nested_access(expr
, pc
);
2142 /* Construct an affine expression from the integer constant "expr".
2143 * "pc" is the context in which the affine expression is created.
2145 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2146 __isl_keep pet_context
*pc
)
2148 isl_local_space
*ls
;
2154 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2155 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2157 return isl_pw_aff_from_aff(aff
);
2160 /* Extract an affine expression from an addition or subtraction operation.
2161 * Return NaN if we are unable to extract an affine expression.
2163 * "pc" is the context in which the affine expression is created.
2165 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2166 __isl_keep pet_context
*pc
)
2173 if (expr
->n_arg
!= 2)
2174 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2175 "expecting two arguments", return NULL
);
2177 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2178 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2180 switch (pet_expr_op_get_type(expr
)) {
2182 return isl_pw_aff_add(lhs
, rhs
);
2184 return isl_pw_aff_sub(lhs
, rhs
);
2186 isl_pw_aff_free(lhs
);
2187 isl_pw_aff_free(rhs
);
2188 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2189 "not an addition or subtraction operation",
2195 /* Extract an affine expression from an integer division or a modulo operation.
2196 * Return NaN if we are unable to extract an affine expression.
2198 * "pc" is the context in which the affine expression is created.
2200 * In particular, if "expr" is lhs/rhs, then return
2202 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2204 * If "expr" is lhs%rhs, then return
2206 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2208 * If the second argument (rhs) is not a (positive) integer constant,
2209 * then we fail to extract an affine expression.
2211 * We simplify the result in the context of the domain of "pc" in case
2212 * this domain implies that lhs >= 0 (or < 0).
2214 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2215 __isl_keep pet_context
*pc
)
2224 if (expr
->n_arg
!= 2)
2225 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2226 "expecting two arguments", return NULL
);
2228 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2230 is_cst
= isl_pw_aff_is_cst(rhs
);
2231 if (is_cst
< 0 || !is_cst
) {
2232 isl_pw_aff_free(rhs
);
2233 return non_affine(pet_context_get_space(pc
));
2236 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2238 switch (pet_expr_op_get_type(expr
)) {
2240 res
= isl_pw_aff_tdiv_q(lhs
, rhs
);
2243 res
= isl_pw_aff_tdiv_r(lhs
, rhs
);
2246 isl_pw_aff_free(lhs
);
2247 isl_pw_aff_free(rhs
);
2248 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2249 "not a div or mod operator", return NULL
);
2252 return isl_pw_aff_gist(res
, pet_context_get_gist_domain(pc
));
2255 /* Extract an affine expression from a multiplication operation.
2256 * Return NaN if we are unable to extract an affine expression.
2257 * In particular, if neither of the arguments is a (piecewise) constant
2258 * then we return NaN.
2260 * "pc" is the context in which the affine expression is created.
2262 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2263 __isl_keep pet_context
*pc
)
2265 int lhs_cst
, rhs_cst
;
2271 if (expr
->n_arg
!= 2)
2272 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2273 "expecting two arguments", return NULL
);
2275 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2276 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2278 lhs_cst
= isl_pw_aff_is_cst(lhs
);
2279 rhs_cst
= isl_pw_aff_is_cst(rhs
);
2280 if (lhs_cst
< 0 || rhs_cst
< 0 || (!lhs_cst
&& !rhs_cst
)) {
2281 isl_pw_aff_free(lhs
);
2282 isl_pw_aff_free(rhs
);
2283 return non_affine(pet_context_get_space(pc
));
2286 return isl_pw_aff_mul(lhs
, rhs
);
2289 /* Extract an affine expression from a negation operation.
2290 * Return NaN if we are unable to extract an affine expression.
2292 * "pc" is the context in which the affine expression is created.
2294 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
2295 __isl_keep pet_context
*pc
)
2301 if (expr
->n_arg
!= 1)
2302 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2303 "expecting one argument", return NULL
);
2305 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
2306 return isl_pw_aff_neg(res
);
2309 /* Extract an affine expression from a conditional operation.
2310 * Return NaN if we are unable to extract an affine expression.
2312 * "pc" is the context in which the affine expression is created.
2314 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
2315 __isl_keep pet_context
*pc
)
2317 isl_pw_aff
*cond
, *lhs
, *rhs
;
2321 if (expr
->n_arg
!= 3)
2322 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2323 "expecting three arguments", return NULL
);
2325 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2326 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2327 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
2329 return isl_pw_aff_cond(cond
, lhs
, rhs
);
2336 static __isl_give isl_pw_aff
*wrap(__isl_take isl_pw_aff
*pwaff
, unsigned width
)
2341 ctx
= isl_pw_aff_get_ctx(pwaff
);
2342 mod
= isl_val_int_from_ui(ctx
, width
);
2343 mod
= isl_val_2exp(mod
);
2345 pwaff
= isl_pw_aff_mod_val(pwaff
, mod
);
2350 /* Limit the domain of "pwaff" to those elements where the function
2353 * 2^{width-1} <= pwaff < 2^{width-1}
2355 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
2360 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
2361 isl_local_space
*ls
= isl_local_space_from_space(space
);
2366 ctx
= isl_pw_aff_get_ctx(pwaff
);
2367 v
= isl_val_int_from_ui(ctx
, width
- 1);
2368 v
= isl_val_2exp(v
);
2370 bound
= isl_aff_zero_on_domain(ls
);
2371 bound
= isl_aff_add_constant_val(bound
, v
);
2372 b
= isl_pw_aff_from_aff(bound
);
2374 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
2375 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2377 b
= isl_pw_aff_neg(b
);
2378 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
2379 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2384 /* Handle potential overflows on signed computations.
2386 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2387 * then we adjust the domain of "pa" to avoid overflows.
2389 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
2393 struct pet_options
*options
;
2398 ctx
= isl_pw_aff_get_ctx(pa
);
2399 options
= isl_ctx_peek_pet_options(ctx
);
2400 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
2401 pa
= avoid_overflow(pa
, width
);
2406 /* Extract an affine expression from some an operation.
2407 * Return NaN if we are unable to extract an affine expression.
2408 * If the result of a binary (non boolean) operation is unsigned,
2409 * then we wrap it based on the size of the type. If the result is signed,
2410 * then we ensure that no overflow occurs.
2412 * "pc" is the context in which the affine expression is created.
2414 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
2415 __isl_keep pet_context
*pc
)
2420 switch (pet_expr_op_get_type(expr
)) {
2423 res
= extract_affine_add_sub(expr
, pc
);
2427 res
= extract_affine_div_mod(expr
, pc
);
2430 res
= extract_affine_mul(expr
, pc
);
2433 return extract_affine_neg(expr
, pc
);
2435 return extract_affine_cond(expr
, pc
);
2445 return pet_expr_extract_affine_condition(expr
, pc
);
2447 return non_affine(pet_context_get_space(pc
));
2452 if (isl_pw_aff_involves_nan(res
)) {
2453 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
2454 isl_pw_aff_free(res
);
2455 return non_affine(space
);
2458 type_size
= pet_expr_get_type_size(expr
);
2460 res
= wrap(res
, type_size
);
2462 res
= signed_overflow(res
, -type_size
);
2467 /* Extract an affine expression from some special function calls.
2468 * Return NaN if we are unable to extract an affine expression.
2469 * In particular, we handle "min", "max", "ceild", "floord",
2470 * "intMod", "intFloor" and "intCeil".
2471 * In case of the latter five, the second argument needs to be
2472 * a (positive) integer constant.
2474 * "pc" is the context in which the affine expression is created.
2476 static __isl_give isl_pw_aff
*extract_affine_from_call(
2477 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2479 isl_pw_aff
*aff1
, *aff2
;
2483 n
= pet_expr_get_n_arg(expr
);
2484 name
= pet_expr_call_get_name(expr
);
2485 if (!(n
== 2 && !strcmp(name
, "min")) &&
2486 !(n
== 2 && !strcmp(name
, "max")) &&
2487 !(n
== 2 && !strcmp(name
, "intMod")) &&
2488 !(n
== 2 && !strcmp(name
, "intFloor")) &&
2489 !(n
== 2 && !strcmp(name
, "intCeil")) &&
2490 !(n
== 2 && !strcmp(name
, "floord")) &&
2491 !(n
== 2 && !strcmp(name
, "ceild")))
2492 return non_affine(pet_context_get_space(pc
));
2494 if (!strcmp(name
, "min") || !strcmp(name
, "max")) {
2495 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2496 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
2498 if (!strcmp(name
, "min"))
2499 aff1
= isl_pw_aff_min(aff1
, aff2
);
2501 aff1
= isl_pw_aff_max(aff1
, aff2
);
2502 } else if (!strcmp(name
, "intMod")) {
2505 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2506 return non_affine(pet_context_get_space(pc
));
2507 v
= pet_expr_int_get_val(expr
->args
[1]);
2508 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2509 aff1
= isl_pw_aff_mod_val(aff1
, v
);
2513 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2514 return non_affine(pet_context_get_space(pc
));
2515 v
= pet_expr_int_get_val(expr
->args
[1]);
2516 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2517 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
2518 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
2519 aff1
= isl_pw_aff_floor(aff1
);
2521 aff1
= isl_pw_aff_ceil(aff1
);
2527 /* Extract an affine expression from "expr", if possible.
2528 * Otherwise return NaN.
2530 * "pc" is the context in which the affine expression is created.
2532 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
2533 __isl_keep pet_context
*pc
)
2538 switch (pet_expr_get_type(expr
)) {
2539 case pet_expr_access
:
2540 return extract_affine_from_access(expr
, pc
);
2542 return extract_affine_from_int(expr
, pc
);
2544 return extract_affine_from_op(expr
, pc
);
2546 return extract_affine_from_call(expr
, pc
);
2548 case pet_expr_double
:
2549 case pet_expr_error
:
2550 return non_affine(pet_context_get_space(pc
));
2554 /* Extract an affine expressions representing the comparison "LHS op RHS"
2555 * Return NaN if we are unable to extract such an affine expression.
2557 * "pc" is the context in which the affine expression is created.
2559 * If the comparison is of the form
2563 * then the expression is constructed as the conjunction of
2568 * A similar optimization is performed for max(a,b) <= c.
2569 * We do this because that will lead to simpler representations
2570 * of the expression.
2571 * If isl is ever enhanced to explicitly deal with min and max expressions,
2572 * this optimization can be removed.
2574 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
2575 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
2576 __isl_keep pet_context
*pc
)
2578 isl_pw_aff
*lhs_pa
, *rhs_pa
;
2580 if (op
== pet_op_gt
)
2581 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
2582 if (op
== pet_op_ge
)
2583 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
2585 if (op
== pet_op_lt
|| op
== pet_op_le
) {
2586 if (pet_expr_is_min(rhs
)) {
2587 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2589 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2591 return pet_and(lhs_pa
, rhs_pa
);
2593 if (pet_expr_is_max(lhs
)) {
2594 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
2596 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
2598 return pet_and(lhs_pa
, rhs_pa
);
2602 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
2603 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
2605 return pet_comparison(op
, lhs_pa
, rhs_pa
);
2608 /* Extract an affine expressions from the comparison "expr".
2609 * Return NaN if we are unable to extract such an affine expression.
2611 * "pc" is the context in which the affine expression is created.
2613 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
2614 __isl_keep pet_context
*pc
)
2616 enum pet_op_type type
;
2620 if (expr
->n_arg
!= 2)
2621 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2622 "expecting two arguments", return NULL
);
2624 type
= pet_expr_op_get_type(expr
);
2625 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
2629 /* Extract an affine expression representing the boolean operation
2630 * expressed by "expr".
2631 * Return NaN if we are unable to extract an affine expression.
2633 * "pc" is the context in which the affine expression is created.
2635 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
2636 __isl_keep pet_context
*pc
)
2638 isl_pw_aff
*lhs
, *rhs
;
2644 n
= pet_expr_get_n_arg(expr
);
2645 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2647 return pet_not(lhs
);
2649 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
2650 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
2653 /* Extract the affine expression "expr != 0 ? 1 : 0".
2654 * Return NaN if we are unable to extract an affine expression.
2656 * "pc" is the context in which the affine expression is created.
2658 static __isl_give isl_pw_aff
*extract_implicit_condition(
2659 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2663 res
= pet_expr_extract_affine(expr
, pc
);
2664 return pet_to_bool(res
);
2667 /* Extract a boolean affine expression from "expr".
2668 * Return NaN if we are unable to extract an affine expression.
2670 * "pc" is the context in which the affine expression is created.
2672 * If "expr" is neither a comparison nor a boolean operation,
2673 * then we assume it is an affine expression and return the
2674 * boolean expression "expr != 0 ? 1 : 0".
2676 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
2677 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2682 if (pet_expr_is_comparison(expr
))
2683 return extract_comparison(expr
, pc
);
2684 if (pet_expr_is_boolean(expr
))
2685 return extract_boolean(expr
, pc
);
2687 return extract_implicit_condition(expr
, pc
);
2690 /* Check if "expr" is an assume expression and if its single argument
2691 * can be converted to an affine expression in the context of "pc".
2692 * If so, replace the argument by the affine expression.
2694 __isl_give pet_expr
*pet_expr_resolve_assume(__isl_take pet_expr
*expr
,
2695 __isl_keep pet_context
*pc
)
2698 isl_multi_pw_aff
*index
;
2702 if (!pet_expr_is_assume(expr
))
2704 if (expr
->n_arg
!= 1)
2705 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2706 "expecting one argument", return pet_expr_free(expr
));
2708 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2710 return pet_expr_free(expr
);
2711 if (isl_pw_aff_involves_nan(cond
)) {
2712 isl_pw_aff_free(cond
);
2716 index
= isl_multi_pw_aff_from_pw_aff(cond
);
2717 expr
= pet_expr_set_arg(expr
, 0, pet_expr_from_index(index
));
2722 /* Return the number of bits needed to represent the type of "expr".
2723 * See the description of the type_size field of pet_expr.
2725 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
2727 return expr
? expr
->type_size
: 0;
2730 /* Replace the number of bits needed to represent the type of "expr"
2732 * See the description of the type_size field of pet_expr.
2734 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
2737 expr
= pet_expr_cow(expr
);
2741 expr
->type_size
= type_size
;
2746 /* Extend an access expression "expr" with an additional index "index".
2747 * In particular, add "index" as an extra argument to "expr" and
2748 * adjust the index expression of "expr" to refer to this extra argument.
2749 * The caller is responsible for calling pet_expr_access_set_depth
2750 * to update the corresponding access relation.
2752 * Note that we only collect the individual index expressions as
2753 * arguments of "expr" here.
2754 * An attempt to integrate them into the index expression of "expr"
2755 * is performed in pet_expr_access_plug_in_args.
2757 __isl_give pet_expr
*pet_expr_access_subscript(__isl_take pet_expr
*expr
,
2758 __isl_take pet_expr
*index
)
2762 isl_local_space
*ls
;
2765 expr
= pet_expr_cow(expr
);
2766 if (!expr
|| !index
)
2768 if (expr
->type
!= pet_expr_access
)
2769 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2770 "not an access pet_expr", goto error
);
2772 n
= pet_expr_get_n_arg(expr
);
2773 expr
= pet_expr_insert_arg(expr
, n
, index
);
2777 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
2778 ls
= isl_local_space_from_space(space
);
2779 pa
= isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, isl_dim_set
, n
));
2780 expr
->acc
.index
= pet_array_subscript(expr
->acc
.index
, pa
);
2781 if (!expr
->acc
.index
)
2782 return pet_expr_free(expr
);
2786 pet_expr_free(expr
);
2787 pet_expr_free(index
);
2791 /* Extend an access expression "expr" with an additional member acces to "id".
2792 * In particular, extend the index expression of "expr" to include
2793 * the additional member access.
2794 * The caller is responsible for calling pet_expr_access_set_depth
2795 * to update the corresponding access relation.
2797 __isl_give pet_expr
*pet_expr_access_member(__isl_take pet_expr
*expr
,
2798 __isl_take isl_id
*id
)
2801 isl_multi_pw_aff
*field_access
;
2803 expr
= pet_expr_cow(expr
);
2806 if (expr
->type
!= pet_expr_access
)
2807 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2808 "not an access pet_expr", goto error
);
2810 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
2811 space
= isl_space_from_domain(space
);
2812 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
2813 field_access
= isl_multi_pw_aff_zero(space
);
2814 expr
->acc
.index
= pet_array_member(expr
->acc
.index
, field_access
);
2815 if (!expr
->acc
.index
)
2816 return pet_expr_free(expr
);
2820 pet_expr_free(expr
);
2825 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
2832 fprintf(stderr
, "%*s", indent
, "");
2834 switch (expr
->type
) {
2835 case pet_expr_double
:
2836 fprintf(stderr
, "%s\n", expr
->d
.s
);
2839 isl_val_dump(expr
->i
);
2841 case pet_expr_access
:
2842 if (expr
->acc
.ref_id
) {
2843 isl_id_dump(expr
->acc
.ref_id
);
2844 fprintf(stderr
, "%*s", indent
, "");
2846 isl_map_dump(expr
->acc
.access
);
2847 fprintf(stderr
, "%*s", indent
, "");
2848 isl_multi_pw_aff_dump(expr
->acc
.index
);
2849 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
2850 "", expr
->acc
.read
);
2851 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
2852 "", expr
->acc
.write
);
2853 for (i
= 0; i
< expr
->n_arg
; ++i
)
2854 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2857 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
2858 for (i
= 0; i
< expr
->n_arg
; ++i
)
2859 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2862 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
2863 for (i
= 0; i
< expr
->n_arg
; ++i
)
2864 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2867 fprintf(stderr
, "(%s)\n", expr
->type_name
);
2868 for (i
= 0; i
< expr
->n_arg
; ++i
)
2869 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2871 case pet_expr_error
:
2872 fprintf(stderr
, "ERROR\n");
2877 void pet_expr_dump(__isl_keep pet_expr
*expr
)
2879 pet_expr_dump_with_indent(expr
, 0);