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
41 #include <isl/space.h>
42 #include <isl/local_space.h>
45 #include <isl/union_set.h>
46 #include <isl/union_map.h>
47 #include <isl/printer.h>
56 #include "value_bounds.h"
59 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
61 static char *type_str
[] = {
62 [pet_expr_access
] = "access",
63 [pet_expr_call
] = "call",
64 [pet_expr_cast
] = "cast",
65 [pet_expr_double
] = "double",
66 [pet_expr_int
] = "int",
70 static char *op_str
[] = {
71 [pet_op_add_assign
] = "+=",
72 [pet_op_sub_assign
] = "-=",
73 [pet_op_mul_assign
] = "*=",
74 [pet_op_div_assign
] = "/=",
75 [pet_op_assign
] = "=",
90 [pet_op_post_inc
] = "++",
91 [pet_op_post_dec
] = "--",
92 [pet_op_pre_inc
] = "++",
93 [pet_op_pre_dec
] = "--",
94 [pet_op_address_of
] = "&",
102 [pet_op_cond
] = "?:",
103 [pet_op_assume
] = "assume",
104 [pet_op_kill
] = "kill"
107 const char *pet_op_str(enum pet_op_type op
)
112 int pet_op_is_inc_dec(enum pet_op_type op
)
114 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
115 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
118 const char *pet_type_str(enum pet_expr_type type
)
120 return type_str
[type
];
123 enum pet_op_type
pet_str_op(const char *str
)
127 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
128 if (!strcmp(op_str
[i
], str
))
134 enum pet_expr_type
pet_str_type(const char *str
)
138 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
139 if (!strcmp(type_str
[i
], str
))
145 /* Construct a pet_expr of the given type.
147 __isl_give pet_expr
*pet_expr_alloc(isl_ctx
*ctx
, enum pet_expr_type type
)
151 expr
= isl_calloc_type(ctx
, struct pet_expr
);
163 /* Construct an access pet_expr from an index expression.
164 * By default, the access is considered to be a read access.
165 * The initial depth is set from the index expression and
166 * may still be updated by the caller before the access relation
169 __isl_give pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
176 ctx
= isl_multi_pw_aff_get_ctx(index
);
177 expr
= pet_expr_alloc(ctx
, pet_expr_access
);
184 expr
= pet_expr_access_set_index(expr
, index
);
188 isl_multi_pw_aff_free(index
);
192 /* Extend the range of "access" with "n" dimensions, retaining
193 * the tuple identifier on this range.
195 * If "access" represents a member access, then extend the range
198 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
202 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
204 if (!isl_map_range_is_wrapping(access
)) {
205 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
209 domain
= isl_map_copy(access
);
210 domain
= isl_map_range_factor_domain(domain
);
211 access
= isl_map_range_factor_range(access
);
212 access
= extend_range(access
, n
);
213 access
= isl_map_range_product(domain
, access
);
216 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
221 /* Does the access expression "expr" have any explicit access relation?
223 isl_bool
pet_expr_access_has_any_access_relation(__isl_keep pet_expr
*expr
)
225 enum pet_expr_access_type type
;
228 return isl_bool_error
;
230 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
)
231 if (expr
->acc
.access
[type
])
232 return isl_bool_true
;
234 return isl_bool_false
;
237 /* Are all relevant access relations explicitly available in "expr"?
239 static int has_relevant_access_relations(__isl_keep pet_expr
*expr
)
244 if (expr
->acc
.kill
&& !expr
->acc
.access
[pet_expr_access_fake_killed
])
246 if (expr
->acc
.read
&& !expr
->acc
.access
[pet_expr_access_may_read
])
248 if (expr
->acc
.write
&&
249 (!expr
->acc
.access
[pet_expr_access_may_write
] ||
250 !expr
->acc
.access
[pet_expr_access_must_write
]))
256 /* Replace the depth of the access expr "expr" by "depth".
258 * To avoid inconsistencies between the depth and the access relation,
259 * we currently do not allow the depth to change once the access relation
260 * has been set or computed.
262 __isl_give pet_expr
*pet_expr_access_set_depth(__isl_take pet_expr
*expr
,
267 if (expr
->acc
.depth
== depth
)
269 if (pet_expr_access_has_any_access_relation(expr
))
270 isl_die(pet_expr_get_ctx(expr
), isl_error_unsupported
,
271 "depth cannot be changed after access relation "
272 "has been set or computed", return pet_expr_free(expr
));
274 expr
= pet_expr_cow(expr
);
277 expr
->acc
.depth
= depth
;
282 /* Construct a pet_expr that kills the elements specified by
283 * the index expression "index" and the access relation "access".
285 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
286 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
291 if (!access
|| !index
)
294 expr
= pet_expr_from_index(index
);
295 expr
= pet_expr_access_set_read(expr
, 0);
296 expr
= pet_expr_access_set_kill(expr
, 1);
297 depth
= isl_map_dim(access
, isl_dim_out
);
298 expr
= pet_expr_access_set_depth(expr
, depth
);
299 expr
= pet_expr_access_set_access(expr
, pet_expr_access_killed
,
300 isl_union_map_from_map(access
));
301 return pet_expr_new_unary(0, pet_op_kill
, expr
);
303 isl_map_free(access
);
304 isl_multi_pw_aff_free(index
);
308 /* Construct a unary pet_expr that performs "op" on "arg",
309 * where the result is represented using a type of "type_size" bits
310 * (may be zero if unknown or if the type is not an integer).
312 __isl_give pet_expr
*pet_expr_new_unary(int type_size
, enum pet_op_type op
,
313 __isl_take pet_expr
*arg
)
320 ctx
= pet_expr_get_ctx(arg
);
321 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
322 expr
= pet_expr_set_n_arg(expr
, 1);
327 expr
->type_size
= type_size
;
328 expr
->args
[pet_un_arg
] = arg
;
336 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
337 * where the result is represented using a type of "type_size" bits
338 * (may be zero if unknown or if the type is not an integer).
340 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
341 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
348 ctx
= pet_expr_get_ctx(lhs
);
349 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
350 expr
= pet_expr_set_n_arg(expr
, 2);
355 expr
->type_size
= type_size
;
356 expr
->args
[pet_bin_lhs
] = lhs
;
357 expr
->args
[pet_bin_rhs
] = rhs
;
366 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
368 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
369 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
374 if (!cond
|| !lhs
|| !rhs
)
376 ctx
= pet_expr_get_ctx(cond
);
377 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
378 expr
= pet_expr_set_n_arg(expr
, 3);
382 expr
->op
= pet_op_cond
;
383 expr
->args
[pet_ter_cond
] = cond
;
384 expr
->args
[pet_ter_true
] = lhs
;
385 expr
->args
[pet_ter_false
] = rhs
;
395 /* Construct a call pet_expr that calls function "name" with "n_arg"
396 * arguments. The caller is responsible for filling in the arguments.
398 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
403 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
404 expr
= pet_expr_set_n_arg(expr
, n_arg
);
408 expr
->c
.name
= strdup(name
);
410 return pet_expr_free(expr
);
415 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
417 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
418 __isl_take pet_expr
*arg
)
426 ctx
= pet_expr_get_ctx(arg
);
427 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
428 expr
= pet_expr_set_n_arg(expr
, 1);
432 expr
->type_name
= strdup(type_name
);
433 if (!expr
->type_name
)
445 /* Construct a pet_expr that represents the double "d".
447 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
448 double val
, const char *s
)
452 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
457 expr
->d
.s
= strdup(s
);
459 return pet_expr_free(expr
);
464 /* Construct a pet_expr that represents the integer value "v".
466 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
474 ctx
= isl_val_get_ctx(v
);
475 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
487 /* Return an independent duplicate of "expr".
489 * In case of an access expression, make sure the depth of the duplicate is set
490 * before the access relation (if any) is set and after the index expression
493 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
497 enum pet_expr_access_type type
;
502 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
503 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
504 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
505 for (i
= 0; i
< expr
->n_arg
; ++i
)
506 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
508 switch (expr
->type
) {
509 case pet_expr_access
:
510 if (expr
->acc
.ref_id
)
511 dup
= pet_expr_access_set_ref_id(dup
,
512 isl_id_copy(expr
->acc
.ref_id
));
513 dup
= pet_expr_access_set_index(dup
,
514 isl_multi_pw_aff_copy(expr
->acc
.index
));
515 dup
= pet_expr_access_set_depth(dup
, expr
->acc
.depth
);
516 for (type
= pet_expr_access_begin
;
517 type
< pet_expr_access_end
; ++type
) {
518 if (!expr
->acc
.access
[type
])
520 dup
= pet_expr_access_set_access(dup
, type
,
521 isl_union_map_copy(expr
->acc
.access
[type
]));
523 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
524 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
525 dup
= pet_expr_access_set_kill(dup
, expr
->acc
.kill
);
528 dup
= pet_expr_call_set_name(dup
, expr
->c
.name
);
530 dup
= pet_expr_call_set_summary(dup
,
531 pet_function_summary_copy(expr
->c
.summary
));
534 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
536 case pet_expr_double
:
537 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
540 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
543 dup
= pet_expr_op_set_type(dup
, expr
->op
);
546 dup
= pet_expr_free(dup
);
553 /* Return a pet_expr that is equal to "expr" and that has only
554 * a single reference.
556 * If "expr" itself only has one reference, then clear its hash value
557 * since the returned pet_expr will be modified.
559 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
564 if (expr
->ref
== 1) {
569 return pet_expr_dup(expr
);
572 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
574 enum pet_expr_access_type type
;
582 for (i
= 0; i
< expr
->n_arg
; ++i
)
583 pet_expr_free(expr
->args
[i
]);
586 switch (expr
->type
) {
587 case pet_expr_access
:
588 isl_id_free(expr
->acc
.ref_id
);
589 for (type
= pet_expr_access_begin
;
590 type
< pet_expr_access_end
; ++type
)
591 isl_union_map_free(expr
->acc
.access
[type
]);
592 isl_multi_pw_aff_free(expr
->acc
.index
);
596 pet_function_summary_free(expr
->c
.summary
);
599 free(expr
->type_name
);
601 case pet_expr_double
:
605 isl_val_free(expr
->i
);
612 isl_ctx_deref(expr
->ctx
);
617 /* Return an additional reference to "expr".
619 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
628 /* Return the isl_ctx in which "expr" was created.
630 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
632 return expr
? expr
->ctx
: NULL
;
635 /* Return the type of "expr".
637 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
640 return pet_expr_error
;
644 /* Return the number of arguments of "expr".
646 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
654 /* Set the number of arguments of "expr" to "n".
656 * If "expr" originally had more arguments, then remove the extra arguments.
657 * If "expr" originally had fewer arguments, then create space for
658 * the extra arguments ans initialize them to NULL.
660 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
667 if (expr
->n_arg
== n
)
669 expr
= pet_expr_cow(expr
);
673 if (n
< expr
->n_arg
) {
674 for (i
= n
; i
< expr
->n_arg
; ++i
)
675 pet_expr_free(expr
->args
[i
]);
680 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
682 return pet_expr_free(expr
);
684 for (i
= expr
->n_arg
; i
< n
; ++i
)
685 expr
->args
[i
] = NULL
;
691 /* Return the argument of "expr" at position "pos".
693 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
697 if (pos
< 0 || pos
>= expr
->n_arg
)
698 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
699 "position out of bounds", return NULL
);
701 return pet_expr_copy(expr
->args
[pos
]);
704 /* Replace "expr" by its argument at position "pos".
706 __isl_give pet_expr
*pet_expr_arg(__isl_take pet_expr
*expr
, int pos
)
710 arg
= pet_expr_get_arg(expr
, pos
);
716 /* Replace the argument of "expr" at position "pos" by "arg".
718 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
719 __isl_take pet_expr
*arg
)
723 if (pos
< 0 || pos
>= expr
->n_arg
)
724 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
725 "position out of bounds", goto error
);
726 if (expr
->args
[pos
] == arg
) {
731 expr
= pet_expr_cow(expr
);
735 pet_expr_free(expr
->args
[pos
]);
736 expr
->args
[pos
] = arg
;
745 /* Does "expr" perform a comparison operation?
747 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
751 if (expr
->type
!= pet_expr_op
)
766 /* Does "expr" perform a boolean operation?
768 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
772 if (expr
->type
!= pet_expr_op
)
784 /* Is "expr" an address-of operation?
786 int pet_expr_is_address_of(__isl_keep pet_expr
*expr
)
790 if (expr
->type
!= pet_expr_op
)
792 return expr
->op
== pet_op_address_of
;
795 /* Is "expr" an assume statement?
797 int pet_expr_is_assume(__isl_keep pet_expr
*expr
)
801 if (expr
->type
!= pet_expr_op
)
803 return expr
->op
== pet_op_assume
;
806 /* Does "expr" perform a min operation?
808 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
812 if (expr
->type
!= pet_expr_call
)
814 if (expr
->n_arg
!= 2)
816 if (strcmp(expr
->c
.name
, "min") != 0)
821 /* Does "expr" perform a max operation?
823 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
827 if (expr
->type
!= pet_expr_call
)
829 if (expr
->n_arg
!= 2)
831 if (strcmp(expr
->c
.name
, "max") != 0)
836 /* Does "expr" represent an access to an unnamed space, i.e.,
837 * does it represent an affine expression?
839 isl_bool
pet_expr_is_affine(__isl_keep pet_expr
*expr
)
844 return isl_bool_error
;
845 if (expr
->type
!= pet_expr_access
)
846 return isl_bool_false
;
848 has_id
= isl_multi_pw_aff_has_tuple_id(expr
->acc
.index
, isl_dim_out
);
850 return isl_bool_error
;
855 /* Given that "expr" represents an affine expression, i.e., that
856 * it is an access to an unnamed (1D) space, return this affine expression.
858 __isl_give isl_pw_aff
*pet_expr_get_affine(__isl_keep pet_expr
*expr
)
862 isl_multi_pw_aff
*mpa
;
864 is_affine
= pet_expr_is_affine(expr
);
868 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
869 "not an affine expression", return NULL
);
871 mpa
= pet_expr_access_get_index(expr
);
872 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
873 isl_multi_pw_aff_free(mpa
);
877 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
878 * not part of any struct?
880 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
884 if (expr
->type
!= pet_expr_access
)
886 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
))
889 return expr
->acc
.depth
== 0;
892 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
895 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
896 __isl_keep isl_multi_pw_aff
*mpa2
)
900 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
901 if (equal
< 0 || equal
)
903 mpa2
= isl_multi_pw_aff_copy(mpa2
);
904 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
905 isl_multi_pw_aff_get_space(mpa1
));
906 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
907 isl_multi_pw_aff_free(mpa2
);
912 /* Construct an access relation from the index expression and
913 * the array depth of the access expression "expr".
915 * If the number of indices is smaller than the depth of the array,
916 * then we assume that all elements of the remaining dimensions
919 static __isl_give isl_union_map
*construct_access_relation(
920 __isl_keep pet_expr
*expr
)
928 access
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
932 dim
= isl_map_dim(access
, isl_dim_out
);
933 if (dim
> expr
->acc
.depth
)
934 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
935 "number of indices greater than depth",
936 access
= isl_map_free(access
));
938 if (dim
!= expr
->acc
.depth
)
939 access
= extend_range(access
, expr
->acc
.depth
- dim
);
941 return isl_union_map_from_map(access
);
944 /* Ensure that all relevant access relations are explicitly
945 * available in "expr".
947 * If "expr" does not already have the relevant access relations, then create
948 * them based on the index expression and the array depth.
950 * We do not cow since adding an explicit access relation
951 * does not change the meaning of the expression.
952 * However, the explicit access relations may modify the hash value,
953 * so the cached value is reset.
955 static __isl_give pet_expr
*introduce_access_relations(
956 __isl_take pet_expr
*expr
)
958 isl_union_map
*access
;
959 int kill
, read
, write
;
963 if (has_relevant_access_relations(expr
))
966 access
= construct_access_relation(expr
);
968 return pet_expr_free(expr
);
971 kill
= expr
->acc
.kill
;
972 read
= expr
->acc
.read
;
973 write
= expr
->acc
.write
;
974 if (kill
&& !expr
->acc
.access
[pet_expr_access_fake_killed
])
975 expr
->acc
.access
[pet_expr_access_fake_killed
] =
976 isl_union_map_copy(access
);
977 if (read
&& !expr
->acc
.access
[pet_expr_access_may_read
])
978 expr
->acc
.access
[pet_expr_access_may_read
] =
979 isl_union_map_copy(access
);
980 if (write
&& !expr
->acc
.access
[pet_expr_access_may_write
])
981 expr
->acc
.access
[pet_expr_access_may_write
] =
982 isl_union_map_copy(access
);
983 if (write
&& !expr
->acc
.access
[pet_expr_access_must_write
])
984 expr
->acc
.access
[pet_expr_access_must_write
] =
985 isl_union_map_copy(access
);
987 isl_union_map_free(access
);
989 if (!has_relevant_access_relations(expr
))
990 return pet_expr_free(expr
);
995 /* Return a hash value that digests "expr".
996 * If a hash value was computed already, then return that value.
997 * Otherwise, compute the hash value and store a copy in expr->hash.
999 uint32_t pet_expr_get_hash(__isl_keep pet_expr
*expr
)
1002 enum pet_expr_access_type type
;
1003 uint32_t hash
, hash_f
;
1010 hash
= isl_hash_init();
1011 isl_hash_byte(hash
, expr
->type
& 0xFF);
1012 isl_hash_byte(hash
, expr
->n_arg
& 0xFF);
1013 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1015 hash_i
= pet_expr_get_hash(expr
->args
[i
]);
1016 isl_hash_hash(hash
, hash_i
);
1018 switch (expr
->type
) {
1019 case pet_expr_error
:
1021 case pet_expr_double
:
1022 hash
= isl_hash_string(hash
, expr
->d
.s
);
1025 hash_f
= isl_val_get_hash(expr
->i
);
1026 isl_hash_hash(hash
, hash_f
);
1028 case pet_expr_access
:
1029 isl_hash_byte(hash
, expr
->acc
.read
& 0xFF);
1030 isl_hash_byte(hash
, expr
->acc
.write
& 0xFF);
1031 isl_hash_byte(hash
, expr
->acc
.kill
& 0xFF);
1032 hash_f
= isl_id_get_hash(expr
->acc
.ref_id
);
1033 isl_hash_hash(hash
, hash_f
);
1034 hash_f
= isl_multi_pw_aff_get_hash(expr
->acc
.index
);
1035 isl_hash_hash(hash
, hash_f
);
1036 isl_hash_byte(hash
, expr
->acc
.depth
& 0xFF);
1037 for (type
= pet_expr_access_begin
;
1038 type
< pet_expr_access_end
; ++type
) {
1039 hash_f
= isl_union_map_get_hash(expr
->acc
.access
[type
]);
1040 isl_hash_hash(hash
, hash_f
);
1044 isl_hash_byte(hash
, expr
->op
& 0xFF);
1047 hash
= isl_hash_string(hash
, expr
->c
.name
);
1050 hash
= isl_hash_string(hash
, expr
->type_name
);
1057 /* Return 1 if the two pet_exprs are equivalent.
1059 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
1062 enum pet_expr_access_type type
;
1064 if (!expr1
|| !expr2
)
1067 if (expr1
->type
!= expr2
->type
)
1069 if (expr1
->n_arg
!= expr2
->n_arg
)
1071 for (i
= 0; i
< expr1
->n_arg
; ++i
)
1072 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
1074 switch (expr1
->type
) {
1075 case pet_expr_error
:
1077 case pet_expr_double
:
1078 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
1080 if (expr1
->d
.val
!= expr2
->d
.val
)
1084 if (!isl_val_eq(expr1
->i
, expr2
->i
))
1087 case pet_expr_access
:
1088 if (expr1
->acc
.read
!= expr2
->acc
.read
)
1090 if (expr1
->acc
.write
!= expr2
->acc
.write
)
1092 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
1094 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
1096 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
1098 if (!multi_pw_aff_is_equal(expr1
->acc
.index
, expr2
->acc
.index
))
1100 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
1102 if (has_relevant_access_relations(expr1
) !=
1103 has_relevant_access_relations(expr2
)) {
1105 expr1
= pet_expr_copy(expr1
);
1106 expr2
= pet_expr_copy(expr2
);
1107 expr1
= introduce_access_relations(expr1
);
1108 expr2
= introduce_access_relations(expr2
);
1109 equal
= pet_expr_is_equal(expr1
, expr2
);
1110 pet_expr_free(expr1
);
1111 pet_expr_free(expr2
);
1114 for (type
= pet_expr_access_begin
;
1115 type
< pet_expr_access_end
; ++type
) {
1116 if (!expr1
->acc
.access
[type
] !=
1117 !expr2
->acc
.access
[type
])
1119 if (!expr1
->acc
.access
[type
])
1121 if (!isl_union_map_is_equal(expr1
->acc
.access
[type
],
1122 expr2
->acc
.access
[type
]))
1127 if (expr1
->op
!= expr2
->op
)
1131 if (strcmp(expr1
->c
.name
, expr2
->c
.name
))
1135 if (strcmp(expr1
->type_name
, expr2
->type_name
))
1143 /* Do "expr1" and "expr2" represent two accesses to the same array
1144 * that are also of the same type? That is, can these two accesses
1145 * be replaced by a single access?
1147 isl_bool
pet_expr_is_same_access(__isl_keep pet_expr
*expr1
,
1148 __isl_keep pet_expr
*expr2
)
1150 isl_space
*space1
, *space2
;
1153 if (!expr1
|| !expr2
)
1154 return isl_bool_error
;
1155 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1156 return isl_bool_false
;
1157 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1158 return isl_bool_false
;
1159 if (expr1
->acc
.read
!= expr2
->acc
.read
)
1160 return isl_bool_false
;
1161 if (expr1
->acc
.write
!= expr2
->acc
.write
)
1162 return isl_bool_false
;
1163 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
1164 return isl_bool_false
;
1165 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
1166 return isl_bool_false
;
1168 space1
= isl_multi_pw_aff_get_space(expr1
->acc
.index
);
1169 space2
= isl_multi_pw_aff_get_space(expr2
->acc
.index
);
1170 same
= isl_space_tuple_is_equal(space1
, isl_dim_out
,
1171 space2
, isl_dim_out
);
1172 if (same
>= 0 && same
)
1173 same
= isl_space_tuple_is_equal(space1
, isl_dim_in
,
1174 space2
, isl_dim_in
);
1175 isl_space_free(space1
);
1176 isl_space_free(space2
);
1181 /* Does the access expression "expr" read the accessed elements?
1183 isl_bool
pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
1186 return isl_bool_error
;
1187 if (expr
->type
!= pet_expr_access
)
1188 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1189 "not an access expression", return isl_bool_error
);
1191 return expr
->acc
.read
;
1194 /* Does the access expression "expr" write to the accessed elements?
1196 isl_bool
pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
1199 return isl_bool_error
;
1200 if (expr
->type
!= pet_expr_access
)
1201 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1202 "not an access expression", return isl_bool_error
);
1204 return expr
->acc
.write
;
1207 /* Does the access expression "expr" kill the accessed elements?
1209 isl_bool
pet_expr_access_is_kill(__isl_keep pet_expr
*expr
)
1212 return isl_bool_error
;
1213 if (expr
->type
!= pet_expr_access
)
1214 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1215 "not an access expression", return isl_bool_error
);
1217 return expr
->acc
.kill
;
1220 /* Return the identifier of the array accessed by "expr".
1222 * If "expr" represents a member access, then return the identifier
1223 * of the outer structure array.
1225 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
1229 if (expr
->type
!= pet_expr_access
)
1230 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1231 "not an access expression", return NULL
);
1233 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
)) {
1237 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1238 space
= isl_space_range(space
);
1239 while (space
&& isl_space_is_wrapping(space
))
1240 space
= isl_space_domain(isl_space_unwrap(space
));
1241 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
1242 isl_space_free(space
);
1247 return isl_multi_pw_aff_get_tuple_id(expr
->acc
.index
, isl_dim_out
);
1250 /* Return the parameter space of "expr".
1252 __isl_give isl_space
*pet_expr_access_get_parameter_space(
1253 __isl_keep pet_expr
*expr
)
1259 if (expr
->type
!= pet_expr_access
)
1260 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1261 "not an access expression", return NULL
);
1263 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1264 space
= isl_space_params(space
);
1269 /* Return the domain space of "expr", including the arguments (if any).
1271 __isl_give isl_space
*pet_expr_access_get_augmented_domain_space(
1272 __isl_keep pet_expr
*expr
)
1278 if (expr
->type
!= pet_expr_access
)
1279 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1280 "not an access expression", return NULL
);
1282 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1283 space
= isl_space_domain(space
);
1288 /* Return the domain space of "expr", without the arguments (if any).
1290 __isl_give isl_space
*pet_expr_access_get_domain_space(
1291 __isl_keep pet_expr
*expr
)
1295 space
= pet_expr_access_get_augmented_domain_space(expr
);
1296 if (isl_space_is_wrapping(space
))
1297 space
= isl_space_domain(isl_space_unwrap(space
));
1302 /* Return the space of the data accessed by "expr".
1304 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
1310 if (expr
->type
!= pet_expr_access
)
1311 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1312 "not an access expression", return NULL
);
1314 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1315 space
= isl_space_range(space
);
1320 /* Modify all subexpressions of "expr" by calling "fn" on them.
1321 * The subexpressions are traversed in depth first preorder.
1323 __isl_give pet_expr
*pet_expr_map_top_down(__isl_take pet_expr
*expr
,
1324 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1332 expr
= fn(expr
, user
);
1334 n
= pet_expr_get_n_arg(expr
);
1335 for (i
= 0; i
< n
; ++i
) {
1336 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1337 arg
= pet_expr_map_top_down(arg
, fn
, user
);
1338 expr
= pet_expr_set_arg(expr
, i
, arg
);
1344 /* Modify all expressions of type "type" in "expr" by calling "fn" on them.
1346 static __isl_give pet_expr
*pet_expr_map_expr_of_type(__isl_take pet_expr
*expr
,
1347 enum pet_expr_type type
,
1348 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1353 n
= pet_expr_get_n_arg(expr
);
1354 for (i
= 0; i
< n
; ++i
) {
1355 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1356 arg
= pet_expr_map_expr_of_type(arg
, type
, fn
, user
);
1357 expr
= pet_expr_set_arg(expr
, i
, arg
);
1363 if (expr
->type
== type
)
1364 expr
= fn(expr
, user
);
1369 /* Modify all expressions of type pet_expr_access in "expr"
1370 * by calling "fn" on them.
1372 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
1373 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1376 return pet_expr_map_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1379 /* Modify all expressions of type pet_expr_call in "expr"
1380 * by calling "fn" on them.
1382 __isl_give pet_expr
*pet_expr_map_call(__isl_take pet_expr
*expr
,
1383 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1386 return pet_expr_map_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1389 /* Modify all expressions of type pet_expr_op in "expr"
1390 * by calling "fn" on them.
1392 __isl_give pet_expr
*pet_expr_map_op(__isl_take pet_expr
*expr
,
1393 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1396 return pet_expr_map_expr_of_type(expr
, pet_expr_op
, fn
, user
);
1399 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1401 * Return -1 on error (where fn returning a negative value is treated as
1403 * Otherwise return 0.
1405 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
1406 enum pet_expr_type type
,
1407 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1414 for (i
= 0; i
< expr
->n_arg
; ++i
)
1415 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
1416 type
, fn
, user
) < 0)
1419 if (expr
->type
== type
)
1420 return fn(expr
, user
);
1425 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1427 * Return -1 on error (where fn returning a negative value is treated as
1429 * Otherwise return 0.
1431 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
1432 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1434 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1437 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1439 * Return -1 on error (where fn returning a negative value is treated as
1441 * Otherwise return 0.
1443 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
1444 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1446 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1449 /* Internal data structure for pet_expr_writes.
1450 * "id" is the identifier that we are looking for.
1451 * "found" is set if we have found the identifier being written to.
1453 struct pet_expr_writes_data
{
1458 /* Given an access expression, check if it writes to data->id.
1459 * If so, set data->found and abort the search.
1461 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1463 struct pet_expr_writes_data
*data
= user
;
1466 if (!expr
->acc
.write
)
1468 if (pet_expr_is_affine(expr
))
1471 write_id
= pet_expr_access_get_id(expr
);
1472 isl_id_free(write_id
);
1477 if (write_id
!= data
->id
)
1484 /* Does expression "expr" write to "id"?
1486 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1488 struct pet_expr_writes_data data
;
1492 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1499 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1500 * index expression and access relations of "expr" (if any)
1501 * to dimensions of "dst_type" at "dst_pos".
1503 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1504 enum isl_dim_type dst_type
, unsigned dst_pos
,
1505 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1507 enum pet_expr_access_type type
;
1509 expr
= pet_expr_cow(expr
);
1512 if (expr
->type
!= pet_expr_access
)
1513 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1514 "not an access pet_expr", return pet_expr_free(expr
));
1516 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1517 if (!expr
->acc
.access
[type
])
1519 expr
->acc
.access
[type
] =
1520 pet_union_map_move_dims(expr
->acc
.access
[type
],
1521 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1522 if (!expr
->acc
.access
[type
])
1525 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1526 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1527 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1528 return pet_expr_free(expr
);
1533 /* Replace the index expression and access relations (if any) of "expr"
1534 * by their preimages under the function represented by "ma".
1536 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1537 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1539 enum pet_expr_access_type type
;
1541 expr
= pet_expr_cow(expr
);
1544 if (expr
->type
!= pet_expr_access
)
1545 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1546 "not an access pet_expr", goto error
);
1548 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1549 if (!expr
->acc
.access
[type
])
1551 expr
->acc
.access
[type
] =
1552 isl_union_map_preimage_domain_multi_aff(
1553 expr
->acc
.access
[type
], isl_multi_aff_copy(ma
));
1554 if (!expr
->acc
.access
[type
])
1557 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1559 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1560 return pet_expr_free(expr
);
1564 isl_multi_aff_free(ma
);
1565 pet_expr_free(expr
);
1569 /* Replace the index expression and access relations (if any) of "expr"
1570 * by their preimages under the function represented by "mpa".
1572 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1573 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1575 enum pet_expr_access_type type
;
1577 expr
= pet_expr_cow(expr
);
1580 if (expr
->type
!= pet_expr_access
)
1581 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1582 "not an access pet_expr", goto error
);
1584 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1585 if (!expr
->acc
.access
[type
])
1587 expr
->acc
.access
[type
] =
1588 isl_union_map_preimage_domain_multi_pw_aff(
1589 expr
->acc
.access
[type
], isl_multi_pw_aff_copy(mpa
));
1590 if (!expr
->acc
.access
[type
])
1593 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1594 expr
->acc
.index
, mpa
);
1595 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1596 return pet_expr_free(expr
);
1600 isl_multi_pw_aff_free(mpa
);
1601 pet_expr_free(expr
);
1605 /* Return the index expression of access expression "expr".
1607 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1608 __isl_keep pet_expr
*expr
)
1612 if (expr
->type
!= pet_expr_access
)
1613 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1614 "not an access expression", return NULL
);
1616 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1619 /* Align the parameters of expr->acc.index and expr->acc.access[*] (if set).
1621 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1624 enum pet_expr_access_type type
;
1626 expr
= pet_expr_cow(expr
);
1629 if (expr
->type
!= pet_expr_access
)
1630 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1631 "not an access expression", return pet_expr_free(expr
));
1633 if (!pet_expr_access_has_any_access_relation(expr
))
1636 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1637 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1638 if (!expr
->acc
.access
[type
])
1640 space
= isl_space_align_params(space
,
1641 isl_union_map_get_space(expr
->acc
.access
[type
]));
1643 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1644 isl_space_copy(space
));
1645 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1646 if (!expr
->acc
.access
[type
])
1648 expr
->acc
.access
[type
] =
1649 isl_union_map_align_params(expr
->acc
.access
[type
],
1650 isl_space_copy(space
));
1651 if (!expr
->acc
.access
[type
])
1654 isl_space_free(space
);
1655 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1656 return pet_expr_free(expr
);
1661 /* Are "expr1" and "expr2" both array accesses such that
1662 * the access relation of "expr1" is a subset of that of "expr2"?
1663 * Only take into account the first "n_arg" arguments.
1665 * This function is tailored for use by mark_self_dependences in nest.c.
1666 * In particular, the input expressions may have more than "n_arg"
1667 * elements in their arguments arrays, while only the first "n_arg"
1668 * elements are referenced from the access relations.
1670 int pet_expr_is_sub_access(__isl_keep pet_expr
*expr1
,
1671 __isl_keep pet_expr
*expr2
, int n_arg
)
1677 if (!expr1
|| !expr2
)
1679 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1681 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1683 if (pet_expr_is_affine(expr1
))
1685 if (pet_expr_is_affine(expr2
))
1687 n1
= pet_expr_get_n_arg(expr1
);
1690 n2
= pet_expr_get_n_arg(expr2
);
1695 for (i
= 0; i
< n1
; ++i
) {
1697 equal
= pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]);
1698 if (equal
< 0 || !equal
)
1701 id1
= pet_expr_access_get_id(expr1
);
1702 id2
= pet_expr_access_get_id(expr2
);
1710 expr1
= pet_expr_copy(expr1
);
1711 expr2
= pet_expr_copy(expr2
);
1712 expr1
= introduce_access_relations(expr1
);
1713 expr2
= introduce_access_relations(expr2
);
1714 if (!expr1
|| !expr2
)
1717 is_subset
= isl_union_map_is_subset(
1718 expr1
->acc
.access
[pet_expr_access_may_read
],
1719 expr2
->acc
.access
[pet_expr_access_may_read
]);
1721 pet_expr_free(expr1
);
1722 pet_expr_free(expr2
);
1726 pet_expr_free(expr1
);
1727 pet_expr_free(expr2
);
1731 /* Given a set in the iteration space "domain", extend it to live in the space
1732 * of the domain of access relations.
1734 * That, is the number of arguments "n" is 0, then simply return domain.
1735 * Otherwise, return [domain -> [a_1,...,a_n]].
1737 static __isl_give isl_set
*add_arguments(__isl_take isl_set
*domain
, int n
)
1744 map
= isl_map_from_domain(domain
);
1745 map
= isl_map_add_dims(map
, isl_dim_out
, n
);
1746 return isl_map_wrap(map
);
1749 /* Add extra conditions to the domains of all access relations in "expr",
1750 * introducing access relations if they are not already present.
1752 * The conditions are not added to the index expression. Instead, they
1753 * are used to try and simplify the index expression.
1755 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1756 __isl_take isl_set
*cond
)
1759 isl_union_set
*uset
;
1760 enum pet_expr_access_type type
;
1762 expr
= pet_expr_cow(expr
);
1766 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1767 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1768 isl_set_copy(cond
));
1773 if (expr
->type
!= pet_expr_access
) {
1778 expr
= introduce_access_relations(expr
);
1782 cond
= add_arguments(cond
, expr
->n_arg
);
1783 uset
= isl_union_set_from_set(isl_set_copy(cond
));
1784 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1785 if (!expr
->acc
.access
[type
])
1787 expr
->acc
.access
[type
] =
1788 isl_union_map_intersect_domain(expr
->acc
.access
[type
],
1789 isl_union_set_copy(uset
));
1790 if (!expr
->acc
.access
[type
])
1793 isl_union_set_free(uset
);
1794 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, cond
);
1795 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1796 return pet_expr_free(expr
);
1801 return pet_expr_free(expr
);
1804 /* Modify the access relations (if any) and index expression
1805 * of the given access expression
1806 * based on the given iteration space transformation.
1807 * In particular, precompose the access relation and index expression
1808 * with the update function.
1810 * If the access has any arguments then the domain of the access relation
1811 * is a wrapped mapping from the iteration space to the space of
1812 * argument values. We only need to change the domain of this wrapped
1813 * mapping, so we extend the input transformation with an identity mapping
1814 * on the space of argument values.
1816 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1817 __isl_keep isl_multi_pw_aff
*update
)
1819 enum pet_expr_access_type type
;
1821 expr
= pet_expr_cow(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
));
1828 update
= isl_multi_pw_aff_copy(update
);
1830 if (expr
->n_arg
> 0) {
1832 isl_multi_pw_aff
*id
;
1834 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1835 space
= isl_space_domain(space
);
1836 space
= isl_space_unwrap(space
);
1837 space
= isl_space_range(space
);
1838 space
= isl_space_map_from_set(space
);
1839 id
= isl_multi_pw_aff_identity(space
);
1840 update
= isl_multi_pw_aff_product(update
, id
);
1843 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1844 if (!expr
->acc
.access
[type
])
1846 expr
->acc
.access
[type
] =
1847 isl_union_map_preimage_domain_multi_pw_aff(
1848 expr
->acc
.access
[type
],
1849 isl_multi_pw_aff_copy(update
));
1850 if (!expr
->acc
.access
[type
])
1853 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1854 expr
->acc
.index
, update
);
1855 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1856 return pet_expr_free(expr
);
1861 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1863 isl_multi_pw_aff
*update
= user
;
1865 return pet_expr_access_update_domain(expr
, update
);
1868 /* Modify all access relations in "expr" by precomposing them with
1869 * the given iteration space transformation.
1871 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1872 __isl_take isl_multi_pw_aff
*update
)
1874 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1875 isl_multi_pw_aff_free(update
);
1879 /* Given an expression with accesses that have a 0D anonymous domain,
1880 * replace those domains by "space".
1882 __isl_give pet_expr
*pet_expr_insert_domain(__isl_take pet_expr
*expr
,
1883 __isl_take isl_space
*space
)
1885 isl_multi_pw_aff
*mpa
;
1887 space
= isl_space_from_domain(space
);
1888 mpa
= isl_multi_pw_aff_zero(space
);
1889 return pet_expr_update_domain(expr
, mpa
);
1892 /* Add all parameters in "space" to the access relations (if any)
1893 * and index expression of "expr".
1895 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1897 isl_space
*space
= user
;
1898 enum pet_expr_access_type type
;
1900 expr
= pet_expr_cow(expr
);
1903 if (expr
->type
!= pet_expr_access
)
1904 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1905 "not an access expression", return pet_expr_free(expr
));
1907 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1908 if (!expr
->acc
.access
[type
])
1910 expr
->acc
.access
[type
] =
1911 isl_union_map_align_params(expr
->acc
.access
[type
],
1912 isl_space_copy(space
));
1913 if (!expr
->acc
.access
[type
])
1916 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1917 isl_space_copy(space
));
1918 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1919 return pet_expr_free(expr
);
1924 /* Add all parameters in "space" to all access relations and index expressions
1927 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1928 __isl_take isl_space
*space
)
1930 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1931 isl_space_free(space
);
1935 /* Insert an argument expression corresponding to "test" in front
1936 * of the list of arguments described by *n_arg and *args.
1938 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1939 __isl_keep isl_multi_pw_aff
*test
)
1942 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1945 return pet_expr_free(expr
);
1946 expr
= pet_expr_cow(expr
);
1951 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1953 return pet_expr_free(expr
);
1956 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1958 return pet_expr_free(expr
);
1959 for (i
= 0; i
< expr
->n_arg
; ++i
)
1960 ext
[1 + i
] = expr
->args
[i
];
1965 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1967 return pet_expr_free(expr
);
1972 /* Make the expression "expr" depend on the value of "test"
1973 * being equal to "satisfied".
1975 * If "test" is an affine expression, we simply add the conditions
1976 * on the expression having the value "satisfied" to all access relations
1977 * (introducing access relations if they are missing) and index expressions.
1979 * Otherwise, we add a filter to "expr" (which is then assumed to be
1980 * an access expression) corresponding to "test" being equal to "satisfied".
1982 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1983 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1988 isl_pw_multi_aff
*pma
;
1989 enum pet_expr_access_type type
;
1991 expr
= pet_expr_cow(expr
);
1995 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1999 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2000 isl_multi_pw_aff_free(test
);
2002 cond
= isl_pw_aff_non_zero_set(pa
);
2004 cond
= isl_pw_aff_zero_set(pa
);
2005 return pet_expr_restrict(expr
, cond
);
2008 ctx
= isl_multi_pw_aff_get_ctx(test
);
2009 if (expr
->type
!= pet_expr_access
)
2010 isl_die(ctx
, isl_error_invalid
,
2011 "can only filter access expressions", goto error
);
2013 expr
= introduce_access_relations(expr
);
2017 space
= isl_space_domain(isl_multi_pw_aff_get_space(expr
->acc
.index
));
2018 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2019 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
2021 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2022 if (!expr
->acc
.access
[type
])
2024 expr
->acc
.access
[type
] =
2025 isl_union_map_preimage_domain_pw_multi_aff(
2026 expr
->acc
.access
[type
],
2027 isl_pw_multi_aff_copy(pma
));
2028 if (!expr
->acc
.access
[type
])
2031 pma
= isl_pw_multi_aff_gist(pma
,
2032 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
)));
2033 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2034 expr
->acc
.index
, pma
);
2035 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2038 expr
= insert_access_arg(expr
, test
);
2040 isl_multi_pw_aff_free(test
);
2043 isl_multi_pw_aff_free(test
);
2044 return pet_expr_free(expr
);
2047 /* Add a reference identifier to access expression "expr".
2048 * "user" points to an integer that contains the sequence number
2049 * of the next reference.
2051 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
2058 expr
= pet_expr_cow(expr
);
2061 if (expr
->type
!= pet_expr_access
)
2062 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2063 "not an access expression", return pet_expr_free(expr
));
2065 ctx
= pet_expr_get_ctx(expr
);
2066 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
2067 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
2068 if (!expr
->acc
.ref_id
)
2069 return pet_expr_free(expr
);
2074 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
2076 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
2079 /* Reset the user pointer on all parameter and tuple ids in
2080 * the access relations (if any) and the index expression
2081 * of the access expression "expr".
2083 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
2086 enum pet_expr_access_type type
;
2088 expr
= pet_expr_cow(expr
);
2091 if (expr
->type
!= pet_expr_access
)
2092 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2093 "not an access expression", return pet_expr_free(expr
));
2095 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2096 if (!expr
->acc
.access
[type
])
2098 expr
->acc
.access
[type
] =
2099 isl_union_map_reset_user(expr
->acc
.access
[type
]);
2100 if (!expr
->acc
.access
[type
])
2103 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
2104 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2105 return pet_expr_free(expr
);
2110 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
2112 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
2115 /* Data used in access_gist() callback.
2117 struct pet_access_gist_data
{
2119 isl_union_map
*value_bounds
;
2122 /* Given an expression "expr" of type pet_expr_access, compute
2123 * the gist of the associated access relations (if any) and index expression
2124 * with respect to data->domain and the bounds on the values of the arguments
2125 * of the expression.
2127 * The arguments of "expr" have been gisted right before "expr" itself
2128 * is gisted. The gisted arguments may have become equal where before
2129 * they may not have been (obviously) equal. We therefore take
2130 * the opportunity to remove duplicate arguments here.
2132 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
2134 struct pet_access_gist_data
*data
= user
;
2136 isl_union_set
*uset
;
2137 enum pet_expr_access_type type
;
2139 expr
= pet_expr_remove_duplicate_args(expr
);
2140 expr
= pet_expr_cow(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 pet_expr_free(expr
));
2147 domain
= isl_set_copy(data
->domain
);
2148 if (expr
->n_arg
> 0)
2149 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
2150 data
->value_bounds
);
2152 uset
= isl_union_set_from_set(isl_set_copy(domain
));
2153 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2154 if (!expr
->acc
.access
[type
])
2156 expr
->acc
.access
[type
] =
2157 isl_union_map_gist_domain(expr
->acc
.access
[type
],
2158 isl_union_set_copy(uset
));
2159 if (!expr
->acc
.access
[type
])
2162 isl_union_set_free(uset
);
2163 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
2164 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2165 return pet_expr_free(expr
);
2170 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
2171 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2173 struct pet_access_gist_data data
= { context
, value_bounds
};
2175 return pet_expr_map_access(expr
, &access_gist
, &data
);
2178 /* Mark "expr" as a read dependening on "read".
2180 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
2184 return pet_expr_free(expr
);
2185 if (expr
->type
!= pet_expr_access
)
2186 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2187 "not an access expression", return pet_expr_free(expr
));
2188 if (expr
->acc
.read
== read
)
2190 expr
= pet_expr_cow(expr
);
2193 expr
->acc
.read
= read
;
2198 /* Mark "expr" as a write dependening on "write".
2200 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
2204 return pet_expr_free(expr
);
2205 if (expr
->type
!= pet_expr_access
)
2206 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2207 "not an access expression", return pet_expr_free(expr
));
2208 if (expr
->acc
.write
== write
)
2210 expr
= pet_expr_cow(expr
);
2213 expr
->acc
.write
= write
;
2218 /* Mark "expr" as a kill dependening on "kill".
2220 __isl_give pet_expr
*pet_expr_access_set_kill(__isl_take pet_expr
*expr
,
2224 return pet_expr_free(expr
);
2225 if (expr
->type
!= pet_expr_access
)
2226 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2227 "not an access expression", return pet_expr_free(expr
));
2228 if (expr
->acc
.kill
== kill
)
2230 expr
= pet_expr_cow(expr
);
2233 expr
->acc
.kill
= kill
;
2238 /* Map the access type "type" to the corresponding location
2239 * in the access array.
2240 * In particular, the access relation of type pet_expr_access_killed is
2241 * stored in the element at position pet_expr_access_fake_killed.
2243 static enum pet_expr_access_type
internalize_type(
2244 enum pet_expr_access_type type
)
2246 if (type
== pet_expr_access_killed
)
2247 return pet_expr_access_fake_killed
;
2251 /* Replace the access relation of the given "type" of "expr" by "access".
2252 * If the access relation is non-empty and the type is a read or a write,
2253 * then also mark the access expression itself as a read or a write.
2255 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
2256 enum pet_expr_access_type type
, __isl_take isl_union_map
*access
)
2260 expr
= pet_expr_cow(expr
);
2261 if (!expr
|| !access
)
2263 if (expr
->type
!= pet_expr_access
)
2264 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2265 "not an access expression", goto error
);
2266 type
= internalize_type(type
);
2267 isl_union_map_free(expr
->acc
.access
[type
]);
2268 expr
->acc
.access
[type
] = access
;
2273 empty
= isl_union_map_is_empty(access
);
2275 return pet_expr_free(expr
);
2279 if (type
== pet_expr_access_may_read
)
2280 expr
= pet_expr_access_set_read(expr
, 1);
2282 expr
= pet_expr_access_set_write(expr
, 1);
2286 isl_union_map_free(access
);
2287 pet_expr_free(expr
);
2291 /* Replace the index expression of "expr" by "index" and
2292 * set the array depth accordingly.
2294 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
2295 __isl_take isl_multi_pw_aff
*index
)
2297 expr
= pet_expr_cow(expr
);
2298 if (!expr
|| !index
)
2300 if (expr
->type
!= pet_expr_access
)
2301 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2302 "not an access expression", goto error
);
2303 isl_multi_pw_aff_free(expr
->acc
.index
);
2304 expr
->acc
.index
= index
;
2305 expr
->acc
.depth
= isl_multi_pw_aff_dim(index
, isl_dim_out
);
2309 isl_multi_pw_aff_free(index
);
2310 pet_expr_free(expr
);
2314 /* Return the reference identifier of access expression "expr".
2316 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
2320 if (expr
->type
!= pet_expr_access
)
2321 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2322 "not an access expression", return NULL
);
2324 return isl_id_copy(expr
->acc
.ref_id
);
2327 /* Replace the reference identifier of access expression "expr" by "ref_id".
2329 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
2330 __isl_take isl_id
*ref_id
)
2332 expr
= pet_expr_cow(expr
);
2333 if (!expr
|| !ref_id
)
2335 if (expr
->type
!= pet_expr_access
)
2336 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2337 "not an access expression", goto error
);
2338 isl_id_free(expr
->acc
.ref_id
);
2339 expr
->acc
.ref_id
= ref_id
;
2343 isl_id_free(ref_id
);
2344 pet_expr_free(expr
);
2348 /* Tag the access relation "access" with "id".
2349 * That is, insert the id as the range of a wrapped relation
2350 * in the domain of "access".
2352 * If "access" is of the form
2356 * then the result is of the form
2358 * [D[i] -> id[]] -> A[a]
2360 __isl_give isl_union_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
2361 __isl_take isl_union_map
*access
)
2364 isl_multi_aff
*add_tag
;
2367 if (expr
->type
!= pet_expr_access
)
2368 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2369 "not an access expression",
2370 return isl_union_map_free(access
));
2372 id
= isl_id_copy(expr
->acc
.ref_id
);
2373 space
= pet_expr_access_get_domain_space(expr
);
2374 space
= isl_space_from_domain(space
);
2375 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
2376 add_tag
= isl_multi_aff_domain_map(space
);
2377 access
= isl_union_map_preimage_domain_multi_aff(access
, add_tag
);
2382 /* Return the access relation of the given "type" associated to "expr"
2383 * that maps pairs of domain iterations and argument values
2384 * to the corresponding accessed data elements.
2386 * If the requested access relation is explicitly available,
2387 * then return a copy. Otherwise, check if it is irrelevant for
2388 * the access expression and return an empty relation if this is the case.
2389 * Otherwise, introduce the requested access relation in "expr" and
2392 __isl_give isl_union_map
*pet_expr_access_get_dependent_access(
2393 __isl_keep pet_expr
*expr
, enum pet_expr_access_type type
)
2395 isl_union_map
*access
;
2400 if (expr
->type
!= pet_expr_access
)
2401 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2402 "not an access expression", return NULL
);
2404 type
= internalize_type(type
);
2405 if (expr
->acc
.access
[type
])
2406 return isl_union_map_copy(expr
->acc
.access
[type
]);
2408 if (type
== pet_expr_access_may_read
)
2409 empty
= !expr
->acc
.read
;
2411 empty
= !expr
->acc
.write
;
2414 expr
= pet_expr_copy(expr
);
2415 expr
= introduce_access_relations(expr
);
2418 access
= isl_union_map_copy(expr
->acc
.access
[type
]);
2419 pet_expr_free(expr
);
2424 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr
));
2427 /* Return the may read access relation associated to "expr"
2428 * that maps pairs of domain iterations and argument values
2429 * to the corresponding accessed data elements.
2431 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_read(
2432 __isl_keep pet_expr
*expr
)
2434 return pet_expr_access_get_dependent_access(expr
,
2435 pet_expr_access_may_read
);
2438 /* Return the may write access relation associated to "expr"
2439 * that maps pairs of domain iterations and argument values
2440 * to the corresponding accessed data elements.
2442 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_write(
2443 __isl_keep pet_expr
*expr
)
2445 return pet_expr_access_get_dependent_access(expr
,
2446 pet_expr_access_may_write
);
2449 /* Return the must write access relation associated to "expr"
2450 * that maps pairs of domain iterations and argument values
2451 * to the corresponding accessed data elements.
2453 __isl_give isl_union_map
*pet_expr_access_get_dependent_must_write(
2454 __isl_keep pet_expr
*expr
)
2456 return pet_expr_access_get_dependent_access(expr
,
2457 pet_expr_access_must_write
);
2460 /* Return the relation of the given "type" mapping domain iterations
2461 * to the accessed data elements.
2462 * In particular, take the access relation and, in case of may_read
2463 * or may_write, project out the values of the arguments, if any.
2464 * In case of must_write, return the empty relation if there are
2467 __isl_give isl_union_map
*pet_expr_access_get_access(__isl_keep pet_expr
*expr
,
2468 enum pet_expr_access_type type
)
2470 isl_union_map
*access
;
2476 if (expr
->type
!= pet_expr_access
)
2477 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2478 "not an access expression", return NULL
);
2480 if (expr
->n_arg
!= 0 && type
== pet_expr_access_must_write
) {
2481 space
= pet_expr_access_get_parameter_space(expr
);
2482 return isl_union_map_empty(space
);
2485 access
= pet_expr_access_get_dependent_access(expr
, type
);
2486 if (expr
->n_arg
== 0)
2489 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
2490 space
= isl_space_domain(space
);
2491 map
= isl_map_universe(isl_space_unwrap(space
));
2492 map
= isl_map_domain_map(map
);
2493 access
= isl_union_map_apply_domain(access
,
2494 isl_union_map_from_map(map
));
2499 /* Return the relation mapping domain iterations to all possibly
2500 * read data elements.
2502 __isl_give isl_union_map
*pet_expr_access_get_may_read(
2503 __isl_keep pet_expr
*expr
)
2505 return pet_expr_access_get_access(expr
, pet_expr_access_may_read
);
2508 /* Return the relation mapping domain iterations to all possibly
2509 * written data elements.
2511 __isl_give isl_union_map
*pet_expr_access_get_may_write(
2512 __isl_keep pet_expr
*expr
)
2514 return pet_expr_access_get_access(expr
, pet_expr_access_may_write
);
2517 /* Return a relation mapping domain iterations to definitely
2518 * written data elements, assuming the statement containing
2519 * the expression is executed.
2521 __isl_give isl_union_map
*pet_expr_access_get_must_write(
2522 __isl_keep pet_expr
*expr
)
2524 return pet_expr_access_get_access(expr
, pet_expr_access_must_write
);
2527 /* Return the relation of the given "type" mapping domain iterations to
2528 * accessed data elements, with its domain tagged with the reference
2531 static __isl_give isl_union_map
*pet_expr_access_get_tagged_access(
2532 __isl_keep pet_expr
*expr
, enum pet_expr_access_type type
)
2534 isl_union_map
*access
;
2539 access
= pet_expr_access_get_access(expr
, type
);
2540 access
= pet_expr_tag_access(expr
, access
);
2545 /* Return the relation mapping domain iterations to all possibly
2546 * read data elements, with its domain tagged with the reference
2549 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_read(
2550 __isl_keep pet_expr
*expr
)
2552 return pet_expr_access_get_tagged_access(expr
,
2553 pet_expr_access_may_read
);
2556 /* Return the relation mapping domain iterations to all possibly
2557 * written data elements, with its domain tagged with the reference
2560 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_write(
2561 __isl_keep pet_expr
*expr
)
2563 return pet_expr_access_get_tagged_access(expr
,
2564 pet_expr_access_may_write
);
2567 /* Return the operation type of operation expression "expr".
2569 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
2573 if (expr
->type
!= pet_expr_op
)
2574 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2575 "not an operation expression", return pet_op_last
);
2580 /* Replace the operation type of operation expression "expr" by "type".
2582 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
2583 enum pet_op_type type
)
2586 return pet_expr_free(expr
);
2587 if (expr
->type
!= pet_expr_op
)
2588 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2589 "not an operation expression",
2590 return pet_expr_free(expr
));
2591 if (expr
->op
== type
)
2593 expr
= pet_expr_cow(expr
);
2601 /* Return the name of the function called by "expr".
2603 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
2607 if (expr
->type
!= pet_expr_call
)
2608 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2609 "not a call expression", return NULL
);
2610 return expr
->c
.name
;
2613 /* Replace the name of the function called by "expr" by "name".
2615 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
2616 __isl_keep
const char *name
)
2618 expr
= pet_expr_cow(expr
);
2620 return pet_expr_free(expr
);
2621 if (expr
->type
!= pet_expr_call
)
2622 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2623 "not a call expression", return pet_expr_free(expr
));
2625 expr
->c
.name
= strdup(name
);
2627 return pet_expr_free(expr
);
2631 /* Does the call expression "expr" have an associated function summary?
2633 int pet_expr_call_has_summary(__isl_keep pet_expr
*expr
)
2637 if (expr
->type
!= pet_expr_call
)
2638 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2639 "not a call expression", return -1);
2641 return expr
->c
.summary
!= NULL
;
2644 /* Return a copy of the function summary associated to
2645 * the call expression "expr".
2647 __isl_give pet_function_summary
*pet_expr_call_get_summary(
2648 __isl_keep pet_expr
*expr
)
2652 if (expr
->type
!= pet_expr_call
)
2653 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2654 "not a call expression", return NULL
);
2656 return pet_function_summary_copy(expr
->c
.summary
);
2659 /* Replace the function summary associated to the call expression "expr"
2662 __isl_give pet_expr
*pet_expr_call_set_summary(__isl_take pet_expr
*expr
,
2663 __isl_take pet_function_summary
*summary
)
2665 expr
= pet_expr_cow(expr
);
2666 if (!expr
|| !summary
)
2668 if (expr
->type
!= pet_expr_call
)
2669 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2670 "not a call expression", goto error
);
2671 pet_function_summary_free(expr
->c
.summary
);
2672 expr
->c
.summary
= summary
;
2675 pet_function_summary_free(summary
);
2676 return pet_expr_free(expr
);
2679 /* Replace the type of the cast performed by "expr" by "name".
2681 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
2682 __isl_keep
const char *name
)
2684 expr
= pet_expr_cow(expr
);
2686 return pet_expr_free(expr
);
2687 if (expr
->type
!= pet_expr_cast
)
2688 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2689 "not a cast expression", return pet_expr_free(expr
));
2690 free(expr
->type_name
);
2691 expr
->type_name
= strdup(name
);
2692 if (!expr
->type_name
)
2693 return pet_expr_free(expr
);
2697 /* Return the value of the integer represented by "expr".
2699 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
2703 if (expr
->type
!= pet_expr_int
)
2704 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2705 "not an int expression", return NULL
);
2707 return isl_val_copy(expr
->i
);
2710 /* Replace the value of the integer represented by "expr" by "v".
2712 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
2713 __isl_take isl_val
*v
)
2715 expr
= pet_expr_cow(expr
);
2718 if (expr
->type
!= pet_expr_int
)
2719 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2720 "not an int expression", goto error
);
2721 isl_val_free(expr
->i
);
2727 pet_expr_free(expr
);
2731 /* Replace the value and string representation of the double
2732 * represented by "expr" by "d" and "s".
2734 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
2735 double d
, __isl_keep
const char *s
)
2737 expr
= pet_expr_cow(expr
);
2739 return pet_expr_free(expr
);
2740 if (expr
->type
!= pet_expr_double
)
2741 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2742 "not a double expression", return pet_expr_free(expr
));
2745 expr
->d
.s
= strdup(s
);
2747 return pet_expr_free(expr
);
2751 /* Return a string representation of the double expression "expr".
2753 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2757 if (expr
->type
!= pet_expr_double
)
2758 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2759 "not a double expression", return NULL
);
2760 return strdup(expr
->d
.s
);
2763 /* Return a piecewise affine expression defined on the specified domain
2764 * that represents NaN.
2766 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2768 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2771 /* This function is called when we come across an access that is
2772 * nested in what is supposed to be an affine expression.
2773 * "pc" is the context in which the affine expression is created.
2774 * If nesting is allowed in "pc", we return an affine expression that is
2775 * equal to a new parameter corresponding to this nested access.
2776 * Otherwise, we return NaN.
2778 * Note that we currently don't allow nested accesses themselves
2779 * to contain any nested accesses, so we check if "expr" itself
2780 * involves any nested accesses (either explicitly as arguments
2781 * or implicitly through parameters) and return NaN if it does.
2783 * The new parameter is resolved in resolve_nested.
2785 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2786 __isl_keep pet_context
*pc
)
2791 isl_local_space
*ls
;
2797 if (!pet_context_allow_nesting(pc
))
2798 return non_affine(pet_context_get_space(pc
));
2800 if (pet_expr_get_type(expr
) != pet_expr_access
)
2801 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2802 "not an access expression", return NULL
);
2804 if (expr
->n_arg
> 0)
2805 return non_affine(pet_context_get_space(pc
));
2807 space
= pet_expr_access_get_parameter_space(expr
);
2808 nested
= pet_nested_any_in_space(space
);
2809 isl_space_free(space
);
2811 return non_affine(pet_context_get_space(pc
));
2813 ctx
= pet_expr_get_ctx(expr
);
2814 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2815 space
= pet_context_get_space(pc
);
2816 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2818 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2819 ls
= isl_local_space_from_space(space
);
2820 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2822 return isl_pw_aff_from_aff(aff
);
2825 /* Extract an affine expression from the access pet_expr "expr".
2826 * "pc" is the context in which the affine expression is created.
2828 * If "expr" is actually an affine expression rather than
2829 * a real access, then we return that expression.
2830 * Otherwise, we require that "expr" is of an integral type.
2831 * If not, we return NaN.
2833 * If the variable has been assigned a known affine expression,
2834 * then we return that expression.
2836 * Otherwise, we return an expression that is equal to a parameter
2837 * representing "expr" (if "allow_nested" is set).
2839 static __isl_give isl_pw_aff
*extract_affine_from_access(
2840 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2844 if (pet_expr_is_affine(expr
))
2845 return pet_expr_get_affine(expr
);
2847 if (pet_expr_get_type_size(expr
) == 0)
2848 return non_affine(pet_context_get_space(pc
));
2850 if (!pet_expr_is_scalar_access(expr
))
2851 return nested_access(expr
, pc
);
2853 id
= pet_expr_access_get_id(expr
);
2854 if (pet_context_is_assigned(pc
, id
))
2855 return pet_context_get_value(pc
, id
);
2858 return nested_access(expr
, pc
);
2861 /* Construct an affine expression from the integer constant "expr".
2862 * "pc" is the context in which the affine expression is created.
2864 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2865 __isl_keep pet_context
*pc
)
2867 isl_local_space
*ls
;
2873 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2874 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2876 return isl_pw_aff_from_aff(aff
);
2879 /* Extract an affine expression from an addition or subtraction operation.
2880 * Return NaN if we are unable to extract an affine expression.
2882 * "pc" is the context in which the affine expression is created.
2884 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2885 __isl_keep pet_context
*pc
)
2892 if (expr
->n_arg
!= 2)
2893 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2894 "expecting two arguments", return NULL
);
2896 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2897 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2899 switch (pet_expr_op_get_type(expr
)) {
2901 return isl_pw_aff_add(lhs
, rhs
);
2903 return isl_pw_aff_sub(lhs
, rhs
);
2905 isl_pw_aff_free(lhs
);
2906 isl_pw_aff_free(rhs
);
2907 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2908 "not an addition or subtraction operation",
2914 /* Extract an affine expression from an integer division or a modulo operation.
2915 * Return NaN if we are unable to extract an affine expression.
2917 * "pc" is the context in which the affine expression is created.
2919 * In particular, if "expr" is lhs/rhs, then return
2921 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2923 * If "expr" is lhs%rhs, then return
2925 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2927 * If the second argument (rhs) is not a (positive) integer constant,
2928 * then we fail to extract an affine expression.
2930 * We simplify the result in the context of the domain of "pc" in case
2931 * this domain implies that lhs >= 0 (or < 0).
2933 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2934 __isl_keep pet_context
*pc
)
2943 if (expr
->n_arg
!= 2)
2944 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2945 "expecting two arguments", return NULL
);
2947 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2949 is_cst
= isl_pw_aff_is_cst(rhs
);
2950 if (is_cst
< 0 || !is_cst
) {
2951 isl_pw_aff_free(rhs
);
2952 return non_affine(pet_context_get_space(pc
));
2955 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2957 switch (pet_expr_op_get_type(expr
)) {
2959 res
= isl_pw_aff_tdiv_q(lhs
, rhs
);
2962 res
= isl_pw_aff_tdiv_r(lhs
, rhs
);
2965 isl_pw_aff_free(lhs
);
2966 isl_pw_aff_free(rhs
);
2967 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2968 "not a div or mod operator", return NULL
);
2971 return isl_pw_aff_gist(res
, pet_context_get_gist_domain(pc
));
2974 /* Extract an affine expression from a multiplication operation.
2975 * Return NaN if we are unable to extract an affine expression.
2976 * In particular, if neither of the arguments is a (piecewise) constant
2977 * then we return NaN.
2979 * "pc" is the context in which the affine expression is created.
2981 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2982 __isl_keep pet_context
*pc
)
2984 int lhs_cst
, rhs_cst
;
2990 if (expr
->n_arg
!= 2)
2991 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2992 "expecting two arguments", return NULL
);
2994 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2995 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2997 lhs_cst
= isl_pw_aff_is_cst(lhs
);
2998 rhs_cst
= isl_pw_aff_is_cst(rhs
);
2999 if (lhs_cst
>= 0 && rhs_cst
>= 0 && (lhs_cst
|| rhs_cst
))
3000 return isl_pw_aff_mul(lhs
, rhs
);
3002 isl_pw_aff_free(lhs
);
3003 isl_pw_aff_free(rhs
);
3005 if (lhs_cst
< 0 || rhs_cst
< 0)
3008 return non_affine(pet_context_get_space(pc
));
3011 /* Extract an affine expression from a negation operation.
3012 * Return NaN if we are unable to extract an affine expression.
3014 * "pc" is the context in which the affine expression is created.
3016 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
3017 __isl_keep pet_context
*pc
)
3023 if (expr
->n_arg
!= 1)
3024 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3025 "expecting one argument", return NULL
);
3027 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
3028 return isl_pw_aff_neg(res
);
3031 /* Extract an affine expression from a conditional operation.
3032 * Return NaN if we are unable to extract an affine expression.
3034 * "pc" is the context in which the affine expression is created.
3036 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
3037 __isl_keep pet_context
*pc
)
3039 isl_pw_aff
*cond
, *lhs
, *rhs
;
3043 if (expr
->n_arg
!= 3)
3044 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3045 "expecting three arguments", return NULL
);
3047 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3048 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
3049 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
3051 return isl_pw_aff_cond(cond
, lhs
, rhs
);
3054 /* Limit the domain of "pwaff" to those elements where the function
3057 * 2^{width-1} <= pwaff < 2^{width-1}
3059 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
3064 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
3065 isl_local_space
*ls
= isl_local_space_from_space(space
);
3070 ctx
= isl_pw_aff_get_ctx(pwaff
);
3071 v
= isl_val_int_from_ui(ctx
, width
- 1);
3072 v
= isl_val_2exp(v
);
3074 bound
= isl_aff_zero_on_domain(ls
);
3075 bound
= isl_aff_add_constant_val(bound
, v
);
3076 b
= isl_pw_aff_from_aff(bound
);
3078 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
3079 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3081 b
= isl_pw_aff_neg(b
);
3082 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
3083 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3088 /* Handle potential overflows on signed computations.
3090 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
3091 * then we adjust the domain of "pa" to avoid overflows.
3093 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
3097 struct pet_options
*options
;
3102 ctx
= isl_pw_aff_get_ctx(pa
);
3103 options
= isl_ctx_peek_pet_options(ctx
);
3104 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
3105 pa
= avoid_overflow(pa
, width
);
3110 /* Extract an affine expression from some an operation.
3111 * Return NaN if we are unable to extract an affine expression.
3112 * If the result of a binary (non boolean) operation is unsigned,
3113 * then we wrap it based on the size of the type. If the result is signed,
3114 * then we ensure that no overflow occurs.
3116 * "pc" is the context in which the affine expression is created.
3118 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
3119 __isl_keep pet_context
*pc
)
3124 switch (pet_expr_op_get_type(expr
)) {
3127 res
= extract_affine_add_sub(expr
, pc
);
3131 res
= extract_affine_div_mod(expr
, pc
);
3134 res
= extract_affine_mul(expr
, pc
);
3137 return extract_affine_neg(expr
, pc
);
3139 return extract_affine_cond(expr
, pc
);
3149 return pet_expr_extract_affine_condition(expr
, pc
);
3151 return non_affine(pet_context_get_space(pc
));
3156 if (isl_pw_aff_involves_nan(res
)) {
3157 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
3158 isl_pw_aff_free(res
);
3159 return non_affine(space
);
3162 type_size
= pet_expr_get_type_size(expr
);
3164 res
= pet_wrap_pw_aff(res
, type_size
);
3166 res
= signed_overflow(res
, -type_size
);
3171 /* Internal data structure for affine builtin function declarations.
3173 * "pencil" is set if the builtin is pencil specific.
3174 * "n_args" is the number of arguments the function takes.
3175 * "name" is the function name.
3177 struct affine_builtin_decl
{
3183 static struct affine_builtin_decl affine_builtins
[] = {
3191 { 0, 2, "intFloor" },
3192 { 0, 2, "intCeil" },
3197 /* List of min and max builtin functions.
3199 static const char *min_max_builtins
[] = {
3200 "min", "imin", "umin",
3201 "max", "imax", "umax"
3204 /* Is a function call to "name" with "n_args" arguments a call to a
3205 * builtin function for which we can construct an affine expression?
3206 * pencil specific builtins are only recognized if "pencil" is set.
3208 static int is_affine_builtin(int pencil
, int n_args
, const char *name
)
3212 for (i
= 0; i
< ARRAY_SIZE(affine_builtins
); ++i
) {
3213 struct affine_builtin_decl
*decl
= &affine_builtins
[i
];
3215 if (decl
->pencil
&& !pencil
)
3217 if (decl
->n_args
== n_args
&& !strcmp(decl
->name
, name
))
3224 /* Is function "name" a known min or max builtin function?
3226 static int is_min_or_max_builtin(const char *name
)
3230 for (i
= 0; i
< ARRAY_SIZE(min_max_builtins
); ++i
)
3231 if (!strcmp(min_max_builtins
[i
], name
))
3237 /* Extract an affine expression from some special function calls.
3238 * Return NaN if we are unable to extract an affine expression.
3239 * In particular, we handle "min", "max", "ceild", "floord",
3240 * "intMod", "intFloor" and "intCeil".
3241 * In case of the latter five, the second argument needs to be
3242 * a (positive) integer constant.
3243 * If the pencil option is set, then we also handle "{i,u}min" and
3246 * "pc" is the context in which the affine expression is created.
3248 static __isl_give isl_pw_aff
*extract_affine_from_call(
3249 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3252 isl_pw_aff
*aff1
, *aff2
;
3255 struct pet_options
*options
;
3259 ctx
= pet_expr_get_ctx(expr
);
3260 options
= isl_ctx_peek_pet_options(ctx
);
3262 n
= pet_expr_get_n_arg(expr
);
3263 name
= pet_expr_call_get_name(expr
);
3264 if (!is_affine_builtin(options
->pencil
, n
, name
))
3265 return non_affine(pet_context_get_space(pc
));
3267 if (is_min_or_max_builtin(name
)) {
3268 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3269 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
3271 if (strstr(name
, "min"))
3272 aff1
= isl_pw_aff_min(aff1
, aff2
);
3274 aff1
= isl_pw_aff_max(aff1
, aff2
);
3275 } else if (!strcmp(name
, "intMod")) {
3278 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
3279 return non_affine(pet_context_get_space(pc
));
3280 v
= pet_expr_int_get_val(expr
->args
[1]);
3281 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3282 aff1
= isl_pw_aff_mod_val(aff1
, v
);
3286 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
3287 return non_affine(pet_context_get_space(pc
));
3288 v
= pet_expr_int_get_val(expr
->args
[1]);
3289 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3290 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
3291 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
3292 aff1
= isl_pw_aff_floor(aff1
);
3294 aff1
= isl_pw_aff_ceil(aff1
);
3300 /* Extract an affine expression from "expr", if possible.
3301 * Otherwise return NaN.
3303 * "pc" is the context in which the affine expression is created.
3305 * Store the result in "pc" such that it can be reused in case
3306 * pet_expr_extract_affine is called again on the same pair of
3309 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
3310 __isl_keep pet_context
*pc
)
3312 isl_maybe_isl_pw_aff m
;
3318 m
= pet_context_get_extracted_affine(pc
, expr
);
3319 if (m
.valid
< 0 || m
.valid
)
3322 switch (pet_expr_get_type(expr
)) {
3323 case pet_expr_access
:
3324 pa
= extract_affine_from_access(expr
, pc
);
3327 pa
= extract_affine_from_int(expr
, pc
);
3330 pa
= extract_affine_from_op(expr
, pc
);
3333 pa
= extract_affine_from_call(expr
, pc
);
3336 case pet_expr_double
:
3337 case pet_expr_error
:
3338 pa
= non_affine(pet_context_get_space(pc
));
3342 if (pet_context_set_extracted_affine(pc
, expr
, pa
) < 0)
3343 return isl_pw_aff_free(pa
);
3348 /* Extract an affine expressions representing the comparison "LHS op RHS"
3349 * Return NaN if we are unable to extract such an affine expression.
3351 * "pc" is the context in which the affine expression is created.
3353 * If the comparison is of the form
3357 * then the expression is constructed as the conjunction of
3362 * A similar optimization is performed for max(a,b) <= c.
3363 * We do this because that will lead to simpler representations
3364 * of the expression.
3365 * If isl is ever enhanced to explicitly deal with min and max expressions,
3366 * this optimization can be removed.
3368 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
3369 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
3370 __isl_keep pet_context
*pc
)
3372 isl_pw_aff
*lhs_pa
, *rhs_pa
;
3374 if (op
== pet_op_gt
)
3375 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
3376 if (op
== pet_op_ge
)
3377 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
3379 if (op
== pet_op_lt
|| op
== pet_op_le
) {
3380 if (pet_expr_is_min(rhs
)) {
3381 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
3383 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
3385 return pet_and(lhs_pa
, rhs_pa
);
3387 if (pet_expr_is_max(lhs
)) {
3388 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
3390 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
3392 return pet_and(lhs_pa
, rhs_pa
);
3396 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
3397 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
3399 return pet_comparison(op
, lhs_pa
, rhs_pa
);
3402 /* Extract an affine expressions from the comparison "expr".
3403 * Return NaN if we are unable to extract such an affine expression.
3405 * "pc" is the context in which the affine expression is created.
3407 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
3408 __isl_keep pet_context
*pc
)
3410 enum pet_op_type type
;
3414 if (expr
->n_arg
!= 2)
3415 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3416 "expecting two arguments", return NULL
);
3418 type
= pet_expr_op_get_type(expr
);
3419 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
3423 /* Extract an affine expression representing the boolean operation
3424 * expressed by "expr".
3425 * Return NaN if we are unable to extract an affine expression.
3427 * "pc" is the context in which the affine expression is created.
3429 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
3430 __isl_keep pet_context
*pc
)
3432 isl_pw_aff
*lhs
, *rhs
;
3438 n
= pet_expr_get_n_arg(expr
);
3439 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3441 return pet_not(lhs
);
3443 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
3444 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
3447 /* Extract the affine expression "expr != 0 ? 1 : 0".
3448 * Return NaN if we are unable to extract an affine expression.
3450 * "pc" is the context in which the affine expression is created.
3452 static __isl_give isl_pw_aff
*extract_implicit_condition(
3453 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3457 res
= pet_expr_extract_affine(expr
, pc
);
3458 return pet_to_bool(res
);
3461 /* Extract a boolean affine expression from "expr".
3462 * Return NaN if we are unable to extract an affine expression.
3464 * "pc" is the context in which the affine expression is created.
3466 * If "expr" is neither a comparison nor a boolean operation,
3467 * then we assume it is an affine expression and return the
3468 * boolean expression "expr != 0 ? 1 : 0".
3470 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
3471 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3476 if (pet_expr_is_comparison(expr
))
3477 return extract_comparison(expr
, pc
);
3478 if (pet_expr_is_boolean(expr
))
3479 return extract_boolean(expr
, pc
);
3481 return extract_implicit_condition(expr
, pc
);
3484 /* Check if "expr" is an assume expression and if its single argument
3485 * can be converted to an affine expression in the context of "pc".
3486 * If so, replace the argument by the affine expression.
3488 __isl_give pet_expr
*pet_expr_resolve_assume(__isl_take pet_expr
*expr
,
3489 __isl_keep pet_context
*pc
)
3492 isl_multi_pw_aff
*index
;
3496 if (!pet_expr_is_assume(expr
))
3498 if (expr
->n_arg
!= 1)
3499 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3500 "expecting one argument", return pet_expr_free(expr
));
3502 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3504 return pet_expr_free(expr
);
3505 if (isl_pw_aff_involves_nan(cond
)) {
3506 isl_pw_aff_free(cond
);
3510 index
= isl_multi_pw_aff_from_pw_aff(cond
);
3511 expr
= pet_expr_set_arg(expr
, 0, pet_expr_from_index(index
));
3516 /* Return the number of bits needed to represent the type of "expr".
3517 * See the description of the type_size field of pet_expr.
3519 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
3521 return expr
? expr
->type_size
: 0;
3524 /* Replace the number of bits needed to represent the type of "expr"
3526 * See the description of the type_size field of pet_expr.
3528 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
3531 expr
= pet_expr_cow(expr
);
3535 expr
->type_size
= type_size
;
3540 /* Extend an access expression "expr" with an additional index "index".
3541 * In particular, add "index" as an extra argument to "expr" and
3542 * adjust the index expression of "expr" to refer to this extra argument.
3543 * The caller is responsible for calling pet_expr_access_set_depth
3544 * to update the corresponding access relation.
3546 * Note that we only collect the individual index expressions as
3547 * arguments of "expr" here.
3548 * An attempt to integrate them into the index expression of "expr"
3549 * is performed in pet_expr_access_plug_in_args.
3551 __isl_give pet_expr
*pet_expr_access_subscript(__isl_take pet_expr
*expr
,
3552 __isl_take pet_expr
*index
)
3556 isl_local_space
*ls
;
3559 expr
= pet_expr_cow(expr
);
3560 if (!expr
|| !index
)
3562 if (expr
->type
!= pet_expr_access
)
3563 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3564 "not an access pet_expr", goto error
);
3566 n
= pet_expr_get_n_arg(expr
);
3567 expr
= pet_expr_insert_arg(expr
, n
, index
);
3571 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3572 ls
= isl_local_space_from_space(space
);
3573 pa
= isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, isl_dim_set
, n
));
3574 expr
->acc
.index
= pet_array_subscript(expr
->acc
.index
, pa
);
3575 if (!expr
->acc
.index
)
3576 return pet_expr_free(expr
);
3580 pet_expr_free(expr
);
3581 pet_expr_free(index
);
3585 /* Extend an access expression "expr" with an additional member acces to "id".
3586 * In particular, extend the index expression of "expr" to include
3587 * the additional member access.
3588 * The caller is responsible for calling pet_expr_access_set_depth
3589 * to update the corresponding access relation.
3591 __isl_give pet_expr
*pet_expr_access_member(__isl_take pet_expr
*expr
,
3592 __isl_take isl_id
*id
)
3595 isl_multi_pw_aff
*field_access
;
3597 expr
= pet_expr_cow(expr
);
3600 if (expr
->type
!= pet_expr_access
)
3601 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3602 "not an access pet_expr", goto error
);
3604 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3605 space
= isl_space_from_domain(space
);
3606 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3607 field_access
= isl_multi_pw_aff_zero(space
);
3608 expr
->acc
.index
= pet_array_member(expr
->acc
.index
, field_access
);
3609 if (!expr
->acc
.index
)
3610 return pet_expr_free(expr
);
3614 pet_expr_free(expr
);
3619 /* Prefix the access expression "expr" with "prefix".
3620 * If "add" is set, then it is not the index expression "prefix" itself
3621 * that was passed to the function, but its address.
3623 __isl_give pet_expr
*pet_expr_access_patch(__isl_take pet_expr
*expr
,
3624 __isl_take isl_multi_pw_aff
*prefix
, int add
)
3626 enum pet_expr_access_type type
;
3628 expr
= pet_expr_cow(expr
);
3629 if (!expr
|| !prefix
)
3631 if (expr
->type
!= pet_expr_access
)
3632 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3633 "not an access pet_expr", goto error
);
3635 expr
->acc
.depth
+= isl_multi_pw_aff_dim(prefix
, isl_dim_out
) - add
;
3636 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
3637 if (!expr
->acc
.access
[type
])
3639 expr
->acc
.access
[type
] = pet_patch_union_map(
3640 isl_multi_pw_aff_copy(prefix
), expr
->acc
.access
[type
],
3642 if (!expr
->acc
.access
[type
])
3645 expr
->acc
.index
= pet_patch_multi_pw_aff(prefix
, expr
->acc
.index
, add
);
3646 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
3647 return pet_expr_free(expr
);
3651 pet_expr_free(expr
);
3652 isl_multi_pw_aff_free(prefix
);
3656 /* Dump the arguments of "expr" to "p" as a YAML sequence keyed
3657 * by "args", if there are any such arguments.
3659 static __isl_give isl_printer
*dump_arguments(__isl_keep pet_expr
*expr
,
3660 __isl_take isl_printer
*p
)
3664 if (expr
->n_arg
== 0)
3667 p
= isl_printer_print_str(p
, "args");
3668 p
= isl_printer_yaml_next(p
);
3669 p
= isl_printer_yaml_start_sequence(p
);
3670 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3671 p
= pet_expr_print(expr
->args
[i
], p
);
3672 p
= isl_printer_yaml_next(p
);
3674 p
= isl_printer_yaml_end_sequence(p
);
3679 /* Print "expr" to "p" in YAML format.
3681 __isl_give isl_printer
*pet_expr_print(__isl_keep pet_expr
*expr
,
3682 __isl_take isl_printer
*p
)
3685 return isl_printer_free(p
);
3687 switch (expr
->type
) {
3688 case pet_expr_double
:
3689 p
= isl_printer_print_str(p
, expr
->d
.s
);
3692 p
= isl_printer_print_val(p
, expr
->i
);
3694 case pet_expr_access
:
3695 p
= isl_printer_yaml_start_mapping(p
);
3696 if (expr
->acc
.ref_id
) {
3697 p
= isl_printer_print_str(p
, "ref_id");
3698 p
= isl_printer_yaml_next(p
);
3699 p
= isl_printer_print_id(p
, expr
->acc
.ref_id
);
3700 p
= isl_printer_yaml_next(p
);
3702 p
= isl_printer_print_str(p
, "index");
3703 p
= isl_printer_yaml_next(p
);
3704 p
= isl_printer_print_multi_pw_aff(p
, expr
->acc
.index
);
3705 p
= isl_printer_yaml_next(p
);
3706 p
= isl_printer_print_str(p
, "depth");
3707 p
= isl_printer_yaml_next(p
);
3708 p
= isl_printer_print_int(p
, expr
->acc
.depth
);
3709 p
= isl_printer_yaml_next(p
);
3710 if (expr
->acc
.kill
) {
3711 p
= isl_printer_print_str(p
, "kill");
3712 p
= isl_printer_yaml_next(p
);
3713 p
= isl_printer_print_int(p
, 1);
3714 p
= isl_printer_yaml_next(p
);
3716 p
= isl_printer_print_str(p
, "read");
3717 p
= isl_printer_yaml_next(p
);
3718 p
= isl_printer_print_int(p
, expr
->acc
.read
);
3719 p
= isl_printer_yaml_next(p
);
3720 p
= isl_printer_print_str(p
, "write");
3721 p
= isl_printer_yaml_next(p
);
3722 p
= isl_printer_print_int(p
, expr
->acc
.write
);
3723 p
= isl_printer_yaml_next(p
);
3725 if (expr
->acc
.access
[pet_expr_access_may_read
]) {
3726 p
= isl_printer_print_str(p
, "may_read");
3727 p
= isl_printer_yaml_next(p
);
3728 p
= isl_printer_print_union_map(p
,
3729 expr
->acc
.access
[pet_expr_access_may_read
]);
3730 p
= isl_printer_yaml_next(p
);
3732 if (expr
->acc
.access
[pet_expr_access_may_write
]) {
3733 p
= isl_printer_print_str(p
, "may_write");
3734 p
= isl_printer_yaml_next(p
);
3735 p
= isl_printer_print_union_map(p
,
3736 expr
->acc
.access
[pet_expr_access_may_write
]);
3737 p
= isl_printer_yaml_next(p
);
3739 if (expr
->acc
.access
[pet_expr_access_must_write
]) {
3740 p
= isl_printer_print_str(p
, "must_write");
3741 p
= isl_printer_yaml_next(p
);
3742 p
= isl_printer_print_union_map(p
,
3743 expr
->acc
.access
[pet_expr_access_must_write
]);
3744 p
= isl_printer_yaml_next(p
);
3746 p
= dump_arguments(expr
, p
);
3747 p
= isl_printer_yaml_end_mapping(p
);
3750 p
= isl_printer_yaml_start_mapping(p
);
3751 p
= isl_printer_print_str(p
, "op");
3752 p
= isl_printer_yaml_next(p
);
3753 p
= isl_printer_print_str(p
, op_str
[expr
->op
]);
3754 p
= isl_printer_yaml_next(p
);
3755 p
= dump_arguments(expr
, p
);
3756 p
= isl_printer_yaml_end_mapping(p
);
3759 p
= isl_printer_yaml_start_mapping(p
);
3760 p
= isl_printer_print_str(p
, "call");
3761 p
= isl_printer_yaml_next(p
);
3762 p
= isl_printer_print_str(p
, expr
->c
.name
);
3763 p
= isl_printer_print_str(p
, "/");
3764 p
= isl_printer_print_int(p
, expr
->n_arg
);
3765 p
= isl_printer_yaml_next(p
);
3766 p
= dump_arguments(expr
, p
);
3767 if (expr
->c
.summary
) {
3768 p
= isl_printer_print_str(p
, "summary");
3769 p
= isl_printer_yaml_next(p
);
3770 p
= pet_function_summary_print(expr
->c
.summary
, p
);
3772 p
= isl_printer_yaml_end_mapping(p
);
3775 p
= isl_printer_yaml_start_mapping(p
);
3776 p
= isl_printer_print_str(p
, "cast");
3777 p
= isl_printer_yaml_next(p
);
3778 p
= isl_printer_print_str(p
, expr
->type_name
);
3779 p
= isl_printer_yaml_next(p
);
3780 p
= dump_arguments(expr
, p
);
3781 p
= isl_printer_yaml_end_mapping(p
);
3783 case pet_expr_error
:
3784 p
= isl_printer_print_str(p
, "ERROR");
3791 /* Dump "expr" to stderr with indentation "indent".
3793 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
3800 p
= isl_printer_to_file(pet_expr_get_ctx(expr
), stderr
);
3801 p
= isl_printer_set_indent(p
, indent
);
3802 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_BLOCK
);
3803 p
= isl_printer_start_line(p
);
3804 p
= pet_expr_print(expr
, p
);
3806 isl_printer_free(p
);
3809 void pet_expr_dump(__isl_keep pet_expr
*expr
)
3811 pet_expr_dump_with_indent(expr
, 0);