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
)
241 enum pet_expr_access_type type
;
246 if (expr
->acc
.kill
&& !expr
->acc
.access
[pet_expr_access_fake_killed
])
248 if (expr
->acc
.read
&& !expr
->acc
.access
[pet_expr_access_may_read
])
250 if (expr
->acc
.write
&&
251 (!expr
->acc
.access
[pet_expr_access_may_write
] ||
252 !expr
->acc
.access
[pet_expr_access_must_write
]))
258 /* Replace the depth of the access expr "expr" by "depth".
260 * To avoid inconsistencies between the depth and the access relation,
261 * we currently do not allow the depth to change once the access relation
262 * has been set or computed.
264 __isl_give pet_expr
*pet_expr_access_set_depth(__isl_take pet_expr
*expr
,
272 if (expr
->acc
.depth
== depth
)
274 if (pet_expr_access_has_any_access_relation(expr
))
275 isl_die(pet_expr_get_ctx(expr
), isl_error_unsupported
,
276 "depth cannot be changed after access relation "
277 "has been set or computed", return pet_expr_free(expr
));
279 expr
= pet_expr_cow(expr
);
282 expr
->acc
.depth
= depth
;
287 /* Construct a pet_expr that kills the elements specified by
288 * the index expression "index" and the access relation "access".
290 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
291 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
296 if (!access
|| !index
)
299 expr
= pet_expr_from_index(index
);
300 expr
= pet_expr_access_set_read(expr
, 0);
301 expr
= pet_expr_access_set_kill(expr
, 1);
302 depth
= isl_map_dim(access
, isl_dim_out
);
303 expr
= pet_expr_access_set_depth(expr
, depth
);
304 expr
= pet_expr_access_set_access(expr
, pet_expr_access_killed
,
305 isl_union_map_from_map(access
));
306 return pet_expr_new_unary(0, pet_op_kill
, expr
);
308 isl_map_free(access
);
309 isl_multi_pw_aff_free(index
);
313 /* Construct a unary pet_expr that performs "op" on "arg",
314 * where the result is represented using a type of "type_size" bits
315 * (may be zero if unknown or if the type is not an integer).
317 __isl_give pet_expr
*pet_expr_new_unary(int type_size
, enum pet_op_type op
,
318 __isl_take pet_expr
*arg
)
325 ctx
= pet_expr_get_ctx(arg
);
326 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
327 expr
= pet_expr_set_n_arg(expr
, 1);
332 expr
->type_size
= type_size
;
333 expr
->args
[pet_un_arg
] = arg
;
341 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
342 * where the result is represented using a type of "type_size" bits
343 * (may be zero if unknown or if the type is not an integer).
345 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
346 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
353 ctx
= pet_expr_get_ctx(lhs
);
354 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
355 expr
= pet_expr_set_n_arg(expr
, 2);
360 expr
->type_size
= type_size
;
361 expr
->args
[pet_bin_lhs
] = lhs
;
362 expr
->args
[pet_bin_rhs
] = rhs
;
371 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
373 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
374 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
379 if (!cond
|| !lhs
|| !rhs
)
381 ctx
= pet_expr_get_ctx(cond
);
382 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
383 expr
= pet_expr_set_n_arg(expr
, 3);
387 expr
->op
= pet_op_cond
;
388 expr
->args
[pet_ter_cond
] = cond
;
389 expr
->args
[pet_ter_true
] = lhs
;
390 expr
->args
[pet_ter_false
] = rhs
;
400 /* Construct a call pet_expr that calls function "name" with "n_arg"
401 * arguments. The caller is responsible for filling in the arguments.
403 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
408 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
409 expr
= pet_expr_set_n_arg(expr
, n_arg
);
413 expr
->c
.name
= strdup(name
);
415 return pet_expr_free(expr
);
420 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
422 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
423 __isl_take pet_expr
*arg
)
431 ctx
= pet_expr_get_ctx(arg
);
432 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
433 expr
= pet_expr_set_n_arg(expr
, 1);
437 expr
->type_name
= strdup(type_name
);
438 if (!expr
->type_name
)
450 /* Construct a pet_expr that represents the double "d".
452 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
453 double val
, const char *s
)
457 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
462 expr
->d
.s
= strdup(s
);
464 return pet_expr_free(expr
);
469 /* Construct a pet_expr that represents the integer value "v".
471 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
479 ctx
= isl_val_get_ctx(v
);
480 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
492 /* Return an independent duplicate of "expr".
494 * In case of an access expression, make sure the depth of the duplicate is set
495 * before the access relation (if any) is set and after the index expression
498 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
502 enum pet_expr_access_type type
;
507 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
508 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
509 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
510 for (i
= 0; i
< expr
->n_arg
; ++i
)
511 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
513 switch (expr
->type
) {
514 case pet_expr_access
:
515 if (expr
->acc
.ref_id
)
516 dup
= pet_expr_access_set_ref_id(dup
,
517 isl_id_copy(expr
->acc
.ref_id
));
518 dup
= pet_expr_access_set_index(dup
,
519 isl_multi_pw_aff_copy(expr
->acc
.index
));
520 dup
= pet_expr_access_set_depth(dup
, expr
->acc
.depth
);
521 for (type
= pet_expr_access_begin
;
522 type
< pet_expr_access_end
; ++type
) {
523 if (!expr
->acc
.access
[type
])
525 dup
= pet_expr_access_set_access(dup
, type
,
526 isl_union_map_copy(expr
->acc
.access
[type
]));
528 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
529 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
530 dup
= pet_expr_access_set_kill(dup
, expr
->acc
.kill
);
533 dup
= pet_expr_call_set_name(dup
, expr
->c
.name
);
535 dup
= pet_expr_call_set_summary(dup
,
536 pet_function_summary_copy(expr
->c
.summary
));
539 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
541 case pet_expr_double
:
542 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
545 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
548 dup
= pet_expr_op_set_type(dup
, expr
->op
);
551 dup
= pet_expr_free(dup
);
558 /* Return a pet_expr that is equal to "expr" and that has only
559 * a single reference.
561 * If "expr" itself only has one reference, then clear its hash value
562 * since the returned pet_expr will be modified.
564 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
569 if (expr
->ref
== 1) {
574 return pet_expr_dup(expr
);
577 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
579 enum pet_expr_access_type type
;
587 for (i
= 0; i
< expr
->n_arg
; ++i
)
588 pet_expr_free(expr
->args
[i
]);
591 switch (expr
->type
) {
592 case pet_expr_access
:
593 isl_id_free(expr
->acc
.ref_id
);
594 for (type
= pet_expr_access_begin
;
595 type
< pet_expr_access_end
; ++type
)
596 isl_union_map_free(expr
->acc
.access
[type
]);
597 isl_multi_pw_aff_free(expr
->acc
.index
);
601 pet_function_summary_free(expr
->c
.summary
);
604 free(expr
->type_name
);
606 case pet_expr_double
:
610 isl_val_free(expr
->i
);
617 isl_ctx_deref(expr
->ctx
);
622 /* Return an additional reference to "expr".
624 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
633 /* Return the isl_ctx in which "expr" was created.
635 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
637 return expr
? expr
->ctx
: NULL
;
640 /* Return the type of "expr".
642 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
645 return pet_expr_error
;
649 /* Return the number of arguments of "expr".
651 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
659 /* Set the number of arguments of "expr" to "n".
661 * If "expr" originally had more arguments, then remove the extra arguments.
662 * If "expr" originally had fewer arguments, then create space for
663 * the extra arguments ans initialize them to NULL.
665 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
672 if (expr
->n_arg
== n
)
674 expr
= pet_expr_cow(expr
);
678 if (n
< expr
->n_arg
) {
679 for (i
= n
; i
< expr
->n_arg
; ++i
)
680 pet_expr_free(expr
->args
[i
]);
685 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
687 return pet_expr_free(expr
);
689 for (i
= expr
->n_arg
; i
< n
; ++i
)
690 expr
->args
[i
] = NULL
;
696 /* Return the argument of "expr" at position "pos".
698 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
702 if (pos
< 0 || pos
>= expr
->n_arg
)
703 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
704 "position out of bounds", return NULL
);
706 return pet_expr_copy(expr
->args
[pos
]);
709 /* Replace "expr" by its argument at position "pos".
711 __isl_give pet_expr
*pet_expr_arg(__isl_take pet_expr
*expr
, int pos
)
715 arg
= pet_expr_get_arg(expr
, pos
);
721 /* Replace the argument of "expr" at position "pos" by "arg".
723 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
724 __isl_take pet_expr
*arg
)
728 if (pos
< 0 || pos
>= expr
->n_arg
)
729 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
730 "position out of bounds", goto error
);
731 if (expr
->args
[pos
] == arg
) {
736 expr
= pet_expr_cow(expr
);
740 pet_expr_free(expr
->args
[pos
]);
741 expr
->args
[pos
] = arg
;
750 /* Does "expr" perform a comparison operation?
752 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
756 if (expr
->type
!= pet_expr_op
)
771 /* Does "expr" perform a boolean operation?
773 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
777 if (expr
->type
!= pet_expr_op
)
789 /* Is "expr" an address-of operation?
791 int pet_expr_is_address_of(__isl_keep pet_expr
*expr
)
795 if (expr
->type
!= pet_expr_op
)
797 return expr
->op
== pet_op_address_of
;
800 /* Is "expr" an assume statement?
802 int pet_expr_is_assume(__isl_keep pet_expr
*expr
)
806 if (expr
->type
!= pet_expr_op
)
808 return expr
->op
== pet_op_assume
;
811 /* Does "expr" perform a min operation?
813 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
817 if (expr
->type
!= pet_expr_call
)
819 if (expr
->n_arg
!= 2)
821 if (strcmp(expr
->c
.name
, "min") != 0)
826 /* Does "expr" perform a max operation?
828 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
832 if (expr
->type
!= pet_expr_call
)
834 if (expr
->n_arg
!= 2)
836 if (strcmp(expr
->c
.name
, "max") != 0)
841 /* Does "expr" represent an access to an unnamed space, i.e.,
842 * does it represent an affine expression?
844 isl_bool
pet_expr_is_affine(__isl_keep pet_expr
*expr
)
849 return isl_bool_error
;
850 if (expr
->type
!= pet_expr_access
)
851 return isl_bool_false
;
853 has_id
= isl_multi_pw_aff_has_tuple_id(expr
->acc
.index
, isl_dim_out
);
855 return isl_bool_error
;
860 /* Given that "expr" represents an affine expression, i.e., that
861 * it is an access to an unnamed (1D) space, return this affine expression.
863 __isl_give isl_pw_aff
*pet_expr_get_affine(__isl_keep pet_expr
*expr
)
867 isl_multi_pw_aff
*mpa
;
869 is_affine
= pet_expr_is_affine(expr
);
873 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
874 "not an affine expression", return NULL
);
876 mpa
= pet_expr_access_get_index(expr
);
877 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
878 isl_multi_pw_aff_free(mpa
);
882 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
883 * not part of any struct?
885 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
889 if (expr
->type
!= pet_expr_access
)
891 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
))
894 return expr
->acc
.depth
== 0;
897 /* Are "mpa1" and "mpa2" obviously equal to each other, up to reordering
900 static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
901 __isl_keep isl_multi_pw_aff
*mpa2
)
905 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
906 if (equal
< 0 || equal
)
908 mpa2
= isl_multi_pw_aff_copy(mpa2
);
909 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
910 isl_multi_pw_aff_get_space(mpa1
));
911 equal
= isl_multi_pw_aff_plain_is_equal(mpa1
, mpa2
);
912 isl_multi_pw_aff_free(mpa2
);
917 /* Construct an access relation from the index expression and
918 * the array depth of the access expression "expr".
920 * If the number of indices is smaller than the depth of the array,
921 * then we assume that all elements of the remaining dimensions
924 static __isl_give isl_union_map
*construct_access_relation(
925 __isl_keep pet_expr
*expr
)
934 access
= isl_map_from_multi_pw_aff(pet_expr_access_get_index(expr
));
938 dim
= isl_map_dim(access
, isl_dim_out
);
939 if (dim
> expr
->acc
.depth
)
940 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
941 "number of indices greater than depth",
942 access
= isl_map_free(access
));
944 if (dim
!= expr
->acc
.depth
)
945 access
= extend_range(access
, expr
->acc
.depth
- dim
);
947 return isl_union_map_from_map(access
);
950 /* Ensure that all relevant access relations are explicitly
951 * available in "expr".
953 * If "expr" does not already have the relevant access relations, then create
954 * them based on the index expression and the array depth.
956 * We do not cow since adding an explicit access relation
957 * does not change the meaning of the expression.
958 * However, the explicit access relations may modify the hash value,
959 * so the cached value is reset.
961 static __isl_give pet_expr
*introduce_access_relations(
962 __isl_take pet_expr
*expr
)
964 enum pet_expr_access_type type
;
965 isl_union_map
*access
;
967 int kill
, read
, write
;
971 if (has_relevant_access_relations(expr
))
974 access
= construct_access_relation(expr
);
976 return pet_expr_free(expr
);
979 kill
= expr
->acc
.kill
;
980 read
= expr
->acc
.read
;
981 write
= expr
->acc
.write
;
982 if (kill
&& !expr
->acc
.access
[pet_expr_access_fake_killed
])
983 expr
->acc
.access
[pet_expr_access_fake_killed
] =
984 isl_union_map_copy(access
);
985 if (read
&& !expr
->acc
.access
[pet_expr_access_may_read
])
986 expr
->acc
.access
[pet_expr_access_may_read
] =
987 isl_union_map_copy(access
);
988 if (write
&& !expr
->acc
.access
[pet_expr_access_may_write
])
989 expr
->acc
.access
[pet_expr_access_may_write
] =
990 isl_union_map_copy(access
);
991 if (write
&& !expr
->acc
.access
[pet_expr_access_must_write
])
992 expr
->acc
.access
[pet_expr_access_must_write
] =
993 isl_union_map_copy(access
);
995 isl_union_map_free(access
);
997 if (!has_relevant_access_relations(expr
))
998 return pet_expr_free(expr
);
1003 /* Return a hash value that digests "expr".
1004 * If a hash value was computed already, then return that value.
1005 * Otherwise, compute the hash value and store a copy in expr->hash.
1007 uint32_t pet_expr_get_hash(__isl_keep pet_expr
*expr
)
1010 enum pet_expr_access_type type
;
1011 uint32_t hash
, hash_f
;
1018 hash
= isl_hash_init();
1019 isl_hash_byte(hash
, expr
->type
& 0xFF);
1020 isl_hash_byte(hash
, expr
->n_arg
& 0xFF);
1021 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1023 hash_i
= pet_expr_get_hash(expr
->args
[i
]);
1024 isl_hash_hash(hash
, hash_i
);
1026 switch (expr
->type
) {
1027 case pet_expr_error
:
1029 case pet_expr_double
:
1030 hash
= isl_hash_string(hash
, expr
->d
.s
);
1033 hash_f
= isl_val_get_hash(expr
->i
);
1034 isl_hash_hash(hash
, hash_f
);
1036 case pet_expr_access
:
1037 isl_hash_byte(hash
, expr
->acc
.read
& 0xFF);
1038 isl_hash_byte(hash
, expr
->acc
.write
& 0xFF);
1039 isl_hash_byte(hash
, expr
->acc
.kill
& 0xFF);
1040 hash_f
= isl_id_get_hash(expr
->acc
.ref_id
);
1041 isl_hash_hash(hash
, hash_f
);
1042 hash_f
= isl_multi_pw_aff_get_hash(expr
->acc
.index
);
1043 isl_hash_hash(hash
, hash_f
);
1044 isl_hash_byte(hash
, expr
->acc
.depth
& 0xFF);
1045 for (type
= pet_expr_access_begin
;
1046 type
< pet_expr_access_end
; ++type
) {
1047 hash_f
= isl_union_map_get_hash(expr
->acc
.access
[type
]);
1048 isl_hash_hash(hash
, hash_f
);
1052 isl_hash_byte(hash
, expr
->op
& 0xFF);
1055 hash
= isl_hash_string(hash
, expr
->c
.name
);
1058 hash
= isl_hash_string(hash
, expr
->type_name
);
1065 /* Return 1 if the two pet_exprs are equivalent.
1067 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
1070 enum pet_expr_access_type type
;
1072 if (!expr1
|| !expr2
)
1075 if (expr1
->type
!= expr2
->type
)
1077 if (expr1
->n_arg
!= expr2
->n_arg
)
1079 for (i
= 0; i
< expr1
->n_arg
; ++i
)
1080 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
1082 switch (expr1
->type
) {
1083 case pet_expr_error
:
1085 case pet_expr_double
:
1086 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
1088 if (expr1
->d
.val
!= expr2
->d
.val
)
1092 if (!isl_val_eq(expr1
->i
, expr2
->i
))
1095 case pet_expr_access
:
1096 if (expr1
->acc
.read
!= expr2
->acc
.read
)
1098 if (expr1
->acc
.write
!= expr2
->acc
.write
)
1100 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
1102 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
1104 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
1106 if (!multi_pw_aff_is_equal(expr1
->acc
.index
, expr2
->acc
.index
))
1108 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
1110 if (has_relevant_access_relations(expr1
) !=
1111 has_relevant_access_relations(expr2
)) {
1113 expr1
= pet_expr_copy(expr1
);
1114 expr2
= pet_expr_copy(expr2
);
1115 expr1
= introduce_access_relations(expr1
);
1116 expr2
= introduce_access_relations(expr2
);
1117 equal
= pet_expr_is_equal(expr1
, expr2
);
1118 pet_expr_free(expr1
);
1119 pet_expr_free(expr2
);
1122 for (type
= pet_expr_access_begin
;
1123 type
< pet_expr_access_end
; ++type
) {
1124 if (!expr1
->acc
.access
[type
] !=
1125 !expr2
->acc
.access
[type
])
1127 if (!expr1
->acc
.access
[type
])
1129 if (!isl_union_map_is_equal(expr1
->acc
.access
[type
],
1130 expr2
->acc
.access
[type
]))
1135 if (expr1
->op
!= expr2
->op
)
1139 if (strcmp(expr1
->c
.name
, expr2
->c
.name
))
1143 if (strcmp(expr1
->type_name
, expr2
->type_name
))
1151 /* Do "expr1" and "expr2" represent two accesses to the same array
1152 * that are also of the same type? That is, can these two accesses
1153 * be replaced by a single access?
1155 isl_bool
pet_expr_is_same_access(__isl_keep pet_expr
*expr1
,
1156 __isl_keep pet_expr
*expr2
)
1158 isl_space
*space1
, *space2
;
1161 if (!expr1
|| !expr2
)
1162 return isl_bool_error
;
1163 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1164 return isl_bool_false
;
1165 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1166 return isl_bool_false
;
1167 if (expr1
->acc
.read
!= expr2
->acc
.read
)
1168 return isl_bool_false
;
1169 if (expr1
->acc
.write
!= expr2
->acc
.write
)
1170 return isl_bool_false
;
1171 if (expr1
->acc
.kill
!= expr2
->acc
.kill
)
1172 return isl_bool_false
;
1173 if (expr1
->acc
.depth
!= expr2
->acc
.depth
)
1174 return isl_bool_false
;
1176 space1
= isl_multi_pw_aff_get_space(expr1
->acc
.index
);
1177 space2
= isl_multi_pw_aff_get_space(expr2
->acc
.index
);
1178 same
= isl_space_tuple_is_equal(space1
, isl_dim_out
,
1179 space2
, isl_dim_out
);
1180 if (same
>= 0 && same
)
1181 same
= isl_space_tuple_is_equal(space1
, isl_dim_in
,
1182 space2
, isl_dim_in
);
1183 isl_space_free(space1
);
1184 isl_space_free(space2
);
1189 /* Does the access expression "expr" read the accessed elements?
1191 isl_bool
pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
1194 return isl_bool_error
;
1195 if (expr
->type
!= pet_expr_access
)
1196 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1197 "not an access expression", return isl_bool_error
);
1199 return expr
->acc
.read
;
1202 /* Does the access expression "expr" write to the accessed elements?
1204 isl_bool
pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
1207 return isl_bool_error
;
1208 if (expr
->type
!= pet_expr_access
)
1209 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1210 "not an access expression", return isl_bool_error
);
1212 return expr
->acc
.write
;
1215 /* Does the access expression "expr" kill the accessed elements?
1217 isl_bool
pet_expr_access_is_kill(__isl_keep pet_expr
*expr
)
1220 return isl_bool_error
;
1221 if (expr
->type
!= pet_expr_access
)
1222 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1223 "not an access expression", return isl_bool_error
);
1225 return expr
->acc
.kill
;
1228 /* Return the identifier of the array accessed by "expr".
1230 * If "expr" represents a member access, then return the identifier
1231 * of the outer structure array.
1233 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
1237 if (expr
->type
!= pet_expr_access
)
1238 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1239 "not an access expression", return NULL
);
1241 if (isl_multi_pw_aff_range_is_wrapping(expr
->acc
.index
)) {
1245 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1246 space
= isl_space_range(space
);
1247 while (space
&& isl_space_is_wrapping(space
))
1248 space
= isl_space_domain(isl_space_unwrap(space
));
1249 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
1250 isl_space_free(space
);
1255 return isl_multi_pw_aff_get_tuple_id(expr
->acc
.index
, isl_dim_out
);
1258 /* Return the parameter space of "expr".
1260 __isl_give isl_space
*pet_expr_access_get_parameter_space(
1261 __isl_keep pet_expr
*expr
)
1267 if (expr
->type
!= pet_expr_access
)
1268 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1269 "not an access expression", return NULL
);
1271 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1272 space
= isl_space_params(space
);
1277 /* Return the domain space of "expr", including the arguments (if any).
1279 __isl_give isl_space
*pet_expr_access_get_augmented_domain_space(
1280 __isl_keep pet_expr
*expr
)
1286 if (expr
->type
!= pet_expr_access
)
1287 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1288 "not an access expression", return NULL
);
1290 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1291 space
= isl_space_domain(space
);
1296 /* Return the domain space of "expr", without the arguments (if any).
1298 __isl_give isl_space
*pet_expr_access_get_domain_space(
1299 __isl_keep pet_expr
*expr
)
1303 space
= pet_expr_access_get_augmented_domain_space(expr
);
1304 if (isl_space_is_wrapping(space
))
1305 space
= isl_space_domain(isl_space_unwrap(space
));
1310 /* Return the space of the data accessed by "expr".
1312 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
1318 if (expr
->type
!= pet_expr_access
)
1319 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1320 "not an access expression", return NULL
);
1322 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1323 space
= isl_space_range(space
);
1328 /* Modify all subexpressions of "expr" by calling "fn" on them.
1329 * The subexpressions are traversed in depth first preorder.
1331 __isl_give pet_expr
*pet_expr_map_top_down(__isl_take pet_expr
*expr
,
1332 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1340 expr
= fn(expr
, user
);
1342 n
= pet_expr_get_n_arg(expr
);
1343 for (i
= 0; i
< n
; ++i
) {
1344 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1345 arg
= pet_expr_map_top_down(arg
, fn
, user
);
1346 expr
= pet_expr_set_arg(expr
, i
, arg
);
1352 /* Modify all expressions of type "type" in "expr" by calling "fn" on them.
1354 static __isl_give pet_expr
*pet_expr_map_expr_of_type(__isl_take pet_expr
*expr
,
1355 enum pet_expr_type type
,
1356 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1361 n
= pet_expr_get_n_arg(expr
);
1362 for (i
= 0; i
< n
; ++i
) {
1363 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
1364 arg
= pet_expr_map_expr_of_type(arg
, type
, fn
, user
);
1365 expr
= pet_expr_set_arg(expr
, i
, arg
);
1371 if (expr
->type
== type
)
1372 expr
= fn(expr
, user
);
1377 /* Modify all expressions of type pet_expr_access in "expr"
1378 * by calling "fn" on them.
1380 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
1381 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1384 return pet_expr_map_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1387 /* Modify all expressions of type pet_expr_call in "expr"
1388 * by calling "fn" on them.
1390 __isl_give pet_expr
*pet_expr_map_call(__isl_take pet_expr
*expr
,
1391 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1394 return pet_expr_map_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1397 /* Modify all expressions of type pet_expr_op in "expr"
1398 * by calling "fn" on them.
1400 __isl_give pet_expr
*pet_expr_map_op(__isl_take pet_expr
*expr
,
1401 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
1404 return pet_expr_map_expr_of_type(expr
, pet_expr_op
, fn
, user
);
1407 /* Call "fn" on each of the subexpressions of "expr" of type "type".
1409 * Return -1 on error (where fn returning a negative value is treated as
1411 * Otherwise return 0.
1413 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
1414 enum pet_expr_type type
,
1415 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1422 for (i
= 0; i
< expr
->n_arg
; ++i
)
1423 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
1424 type
, fn
, user
) < 0)
1427 if (expr
->type
== type
)
1428 return fn(expr
, user
);
1433 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
1435 * Return -1 on error (where fn returning a negative value is treated as
1437 * Otherwise return 0.
1439 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
1440 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1442 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
1445 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
1447 * Return -1 on error (where fn returning a negative value is treated as
1449 * Otherwise return 0.
1451 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
1452 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1454 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1457 /* Internal data structure for pet_expr_writes.
1458 * "id" is the identifier that we are looking for.
1459 * "found" is set if we have found the identifier being written to.
1461 struct pet_expr_writes_data
{
1466 /* Given an access expression, check if it writes to data->id.
1467 * If so, set data->found and abort the search.
1469 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1471 struct pet_expr_writes_data
*data
= user
;
1474 if (!expr
->acc
.write
)
1476 if (pet_expr_is_affine(expr
))
1479 write_id
= pet_expr_access_get_id(expr
);
1480 isl_id_free(write_id
);
1485 if (write_id
!= data
->id
)
1492 /* Does expression "expr" write to "id"?
1494 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1496 struct pet_expr_writes_data data
;
1500 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1507 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1508 * index expression and access relations of "expr" (if any)
1509 * to dimensions of "dst_type" at "dst_pos".
1511 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1512 enum isl_dim_type dst_type
, unsigned dst_pos
,
1513 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1515 enum pet_expr_access_type type
;
1517 expr
= pet_expr_cow(expr
);
1520 if (expr
->type
!= pet_expr_access
)
1521 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1522 "not an access pet_expr", return pet_expr_free(expr
));
1524 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1525 if (!expr
->acc
.access
[type
])
1527 expr
->acc
.access
[type
] =
1528 pet_union_map_move_dims(expr
->acc
.access
[type
],
1529 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1530 if (!expr
->acc
.access
[type
])
1533 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1534 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1535 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1536 return pet_expr_free(expr
);
1541 /* Replace the index expression and access relations (if any) of "expr"
1542 * by their preimages under the function represented by "ma".
1544 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1545 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1547 enum pet_expr_access_type type
;
1549 expr
= pet_expr_cow(expr
);
1552 if (expr
->type
!= pet_expr_access
)
1553 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1554 "not an access pet_expr", goto error
);
1556 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1557 if (!expr
->acc
.access
[type
])
1559 expr
->acc
.access
[type
] =
1560 isl_union_map_preimage_domain_multi_aff(
1561 expr
->acc
.access
[type
], isl_multi_aff_copy(ma
));
1562 if (!expr
->acc
.access
[type
])
1565 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1567 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1568 return pet_expr_free(expr
);
1572 isl_multi_aff_free(ma
);
1573 pet_expr_free(expr
);
1577 /* Replace the index expression and access relations (if any) of "expr"
1578 * by their preimages under the function represented by "mpa".
1580 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1581 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1583 enum pet_expr_access_type type
;
1585 expr
= pet_expr_cow(expr
);
1588 if (expr
->type
!= pet_expr_access
)
1589 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1590 "not an access pet_expr", goto error
);
1592 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1593 if (!expr
->acc
.access
[type
])
1595 expr
->acc
.access
[type
] =
1596 isl_union_map_preimage_domain_multi_pw_aff(
1597 expr
->acc
.access
[type
], isl_multi_pw_aff_copy(mpa
));
1598 if (!expr
->acc
.access
[type
])
1601 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1602 expr
->acc
.index
, mpa
);
1603 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1604 return pet_expr_free(expr
);
1608 isl_multi_pw_aff_free(mpa
);
1609 pet_expr_free(expr
);
1613 /* Return the index expression of access expression "expr".
1615 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1616 __isl_keep pet_expr
*expr
)
1620 if (expr
->type
!= pet_expr_access
)
1621 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1622 "not an access expression", return NULL
);
1624 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1627 /* Align the parameters of expr->acc.index and expr->acc.access[*] (if set).
1629 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1632 enum pet_expr_access_type type
;
1634 expr
= pet_expr_cow(expr
);
1637 if (expr
->type
!= pet_expr_access
)
1638 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1639 "not an access expression", return pet_expr_free(expr
));
1641 if (!pet_expr_access_has_any_access_relation(expr
))
1644 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1645 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1646 if (!expr
->acc
.access
[type
])
1648 space
= isl_space_align_params(space
,
1649 isl_union_map_get_space(expr
->acc
.access
[type
]));
1651 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1652 isl_space_copy(space
));
1653 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1654 if (!expr
->acc
.access
[type
])
1656 expr
->acc
.access
[type
] =
1657 isl_union_map_align_params(expr
->acc
.access
[type
],
1658 isl_space_copy(space
));
1659 if (!expr
->acc
.access
[type
])
1662 isl_space_free(space
);
1663 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
1664 return pet_expr_free(expr
);
1669 /* Are "expr1" and "expr2" both array accesses such that
1670 * the access relation of "expr1" is a subset of that of "expr2"?
1671 * Only take into account the first "n_arg" arguments.
1673 * This function is tailored for use by mark_self_dependences in nest.c.
1674 * In particular, the input expressions may have more than "n_arg"
1675 * elements in their arguments arrays, while only the first "n_arg"
1676 * elements are referenced from the access relations.
1678 int pet_expr_is_sub_access(__isl_keep pet_expr
*expr1
,
1679 __isl_keep pet_expr
*expr2
, int n_arg
)
1685 if (!expr1
|| !expr2
)
1687 if (pet_expr_get_type(expr1
) != pet_expr_access
)
1689 if (pet_expr_get_type(expr2
) != pet_expr_access
)
1691 if (pet_expr_is_affine(expr1
))
1693 if (pet_expr_is_affine(expr2
))
1695 n1
= pet_expr_get_n_arg(expr1
);
1698 n2
= pet_expr_get_n_arg(expr2
);
1703 for (i
= 0; i
< n1
; ++i
) {
1705 equal
= pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]);
1706 if (equal
< 0 || !equal
)
1709 id1
= pet_expr_access_get_id(expr1
);
1710 id2
= pet_expr_access_get_id(expr2
);
1718 expr1
= pet_expr_copy(expr1
);
1719 expr2
= pet_expr_copy(expr2
);
1720 expr1
= introduce_access_relations(expr1
);
1721 expr2
= introduce_access_relations(expr2
);
1722 if (!expr1
|| !expr2
)
1725 is_subset
= isl_union_map_is_subset(
1726 expr1
->acc
.access
[pet_expr_access_may_read
],
1727 expr2
->acc
.access
[pet_expr_access_may_read
]);
1729 pet_expr_free(expr1
);
1730 pet_expr_free(expr2
);
1734 pet_expr_free(expr1
);
1735 pet_expr_free(expr2
);
1739 /* Given a set in the iteration space "domain", extend it to live in the space
1740 * of the domain of access relations.
1742 * That, is the number of arguments "n" is 0, then simply return domain.
1743 * Otherwise, return [domain -> [a_1,...,a_n]].
1745 static __isl_give isl_set
*add_arguments(__isl_take isl_set
*domain
, int n
)
1752 map
= isl_map_from_domain(domain
);
1753 map
= isl_map_add_dims(map
, isl_dim_out
, n
);
1754 return isl_map_wrap(map
);
1757 /* Add extra conditions to the domains of all access relations in "expr",
1758 * introducing access relations if they are not already present.
1760 * The conditions are not added to the index expression. Instead, they
1761 * are used to try and simplify the index expression.
1763 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1764 __isl_take isl_set
*cond
)
1767 isl_union_set
*uset
;
1768 enum pet_expr_access_type type
;
1770 expr
= pet_expr_cow(expr
);
1774 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1775 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1776 isl_set_copy(cond
));
1781 if (expr
->type
!= pet_expr_access
) {
1786 expr
= introduce_access_relations(expr
);
1790 cond
= add_arguments(cond
, expr
->n_arg
);
1791 uset
= isl_union_set_from_set(isl_set_copy(cond
));
1792 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1793 if (!expr
->acc
.access
[type
])
1795 expr
->acc
.access
[type
] =
1796 isl_union_map_intersect_domain(expr
->acc
.access
[type
],
1797 isl_union_set_copy(uset
));
1798 if (!expr
->acc
.access
[type
])
1801 isl_union_set_free(uset
);
1802 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, cond
);
1803 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1804 return pet_expr_free(expr
);
1809 return pet_expr_free(expr
);
1812 /* Modify the access relations (if any) and index expression
1813 * of the given access expression
1814 * based on the given iteration space transformation.
1815 * In particular, precompose the access relation and index expression
1816 * with the update function.
1818 * If the access has any arguments then the domain of the access relation
1819 * is a wrapped mapping from the iteration space to the space of
1820 * argument values. We only need to change the domain of this wrapped
1821 * mapping, so we extend the input transformation with an identity mapping
1822 * on the space of argument values.
1824 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1825 __isl_keep isl_multi_pw_aff
*update
)
1827 enum pet_expr_access_type type
;
1829 expr
= pet_expr_cow(expr
);
1832 if (expr
->type
!= pet_expr_access
)
1833 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1834 "not an access expression", return pet_expr_free(expr
));
1836 update
= isl_multi_pw_aff_copy(update
);
1838 if (expr
->n_arg
> 0) {
1840 isl_multi_pw_aff
*id
;
1842 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
1843 space
= isl_space_domain(space
);
1844 space
= isl_space_unwrap(space
);
1845 space
= isl_space_range(space
);
1846 space
= isl_space_map_from_set(space
);
1847 id
= isl_multi_pw_aff_identity(space
);
1848 update
= isl_multi_pw_aff_product(update
, id
);
1851 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1852 if (!expr
->acc
.access
[type
])
1854 expr
->acc
.access
[type
] =
1855 isl_union_map_preimage_domain_multi_pw_aff(
1856 expr
->acc
.access
[type
],
1857 isl_multi_pw_aff_copy(update
));
1858 if (!expr
->acc
.access
[type
])
1861 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1862 expr
->acc
.index
, update
);
1863 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1864 return pet_expr_free(expr
);
1869 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1871 isl_multi_pw_aff
*update
= user
;
1873 return pet_expr_access_update_domain(expr
, update
);
1876 /* Modify all access relations in "expr" by precomposing them with
1877 * the given iteration space transformation.
1879 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1880 __isl_take isl_multi_pw_aff
*update
)
1882 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1883 isl_multi_pw_aff_free(update
);
1887 /* Given an expression with accesses that have a 0D anonymous domain,
1888 * replace those domains by "space".
1890 __isl_give pet_expr
*pet_expr_insert_domain(__isl_take pet_expr
*expr
,
1891 __isl_take isl_space
*space
)
1893 isl_multi_pw_aff
*mpa
;
1895 space
= isl_space_from_domain(space
);
1896 mpa
= isl_multi_pw_aff_zero(space
);
1897 return pet_expr_update_domain(expr
, mpa
);
1900 /* Add all parameters in "space" to the access relations (if any)
1901 * and index expression of "expr".
1903 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1905 isl_space
*space
= user
;
1906 enum pet_expr_access_type type
;
1908 expr
= pet_expr_cow(expr
);
1911 if (expr
->type
!= pet_expr_access
)
1912 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1913 "not an access expression", return pet_expr_free(expr
));
1915 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
1916 if (!expr
->acc
.access
[type
])
1918 expr
->acc
.access
[type
] =
1919 isl_union_map_align_params(expr
->acc
.access
[type
],
1920 isl_space_copy(space
));
1921 if (!expr
->acc
.access
[type
])
1924 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1925 isl_space_copy(space
));
1926 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
1927 return pet_expr_free(expr
);
1932 /* Add all parameters in "space" to all access relations and index expressions
1935 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1936 __isl_take isl_space
*space
)
1938 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1939 isl_space_free(space
);
1943 /* Insert an argument expression corresponding to "test" in front
1944 * of the list of arguments described by *n_arg and *args.
1946 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1947 __isl_keep isl_multi_pw_aff
*test
)
1950 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1953 return pet_expr_free(expr
);
1954 expr
= pet_expr_cow(expr
);
1959 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1961 return pet_expr_free(expr
);
1964 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1966 return pet_expr_free(expr
);
1967 for (i
= 0; i
< expr
->n_arg
; ++i
)
1968 ext
[1 + i
] = expr
->args
[i
];
1973 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1975 return pet_expr_free(expr
);
1980 /* Make the expression "expr" depend on the value of "test"
1981 * being equal to "satisfied".
1983 * If "test" is an affine expression, we simply add the conditions
1984 * on the expression having the value "satisfied" to all access relations
1985 * (introducing access relations if they are missing) and index expressions.
1987 * Otherwise, we add a filter to "expr" (which is then assumed to be
1988 * an access expression) corresponding to "test" being equal to "satisfied".
1990 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1991 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1996 isl_pw_multi_aff
*pma
;
1997 enum pet_expr_access_type type
;
1999 expr
= pet_expr_cow(expr
);
2003 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
2007 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
2008 isl_multi_pw_aff_free(test
);
2010 cond
= isl_pw_aff_non_zero_set(pa
);
2012 cond
= isl_pw_aff_zero_set(pa
);
2013 return pet_expr_restrict(expr
, cond
);
2016 ctx
= isl_multi_pw_aff_get_ctx(test
);
2017 if (expr
->type
!= pet_expr_access
)
2018 isl_die(ctx
, isl_error_invalid
,
2019 "can only filter access expressions", goto error
);
2021 expr
= introduce_access_relations(expr
);
2025 space
= isl_space_domain(isl_multi_pw_aff_get_space(expr
->acc
.index
));
2026 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
2027 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
2029 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2030 if (!expr
->acc
.access
[type
])
2032 expr
->acc
.access
[type
] =
2033 isl_union_map_preimage_domain_pw_multi_aff(
2034 expr
->acc
.access
[type
],
2035 isl_pw_multi_aff_copy(pma
));
2036 if (!expr
->acc
.access
[type
])
2039 pma
= isl_pw_multi_aff_gist(pma
,
2040 isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma
)));
2041 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
2042 expr
->acc
.index
, pma
);
2043 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2046 expr
= insert_access_arg(expr
, test
);
2048 isl_multi_pw_aff_free(test
);
2051 isl_multi_pw_aff_free(test
);
2052 return pet_expr_free(expr
);
2055 /* Add a reference identifier to access expression "expr".
2056 * "user" points to an integer that contains the sequence number
2057 * of the next reference.
2059 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
2066 expr
= pet_expr_cow(expr
);
2069 if (expr
->type
!= pet_expr_access
)
2070 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2071 "not an access expression", return pet_expr_free(expr
));
2073 ctx
= pet_expr_get_ctx(expr
);
2074 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
2075 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
2076 if (!expr
->acc
.ref_id
)
2077 return pet_expr_free(expr
);
2082 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
2084 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
2087 /* Reset the user pointer on all parameter and tuple ids in
2088 * the access relations (if any) and the index expression
2089 * of the access expression "expr".
2091 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
2094 enum pet_expr_access_type type
;
2096 expr
= pet_expr_cow(expr
);
2099 if (expr
->type
!= pet_expr_access
)
2100 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2101 "not an access expression", return pet_expr_free(expr
));
2103 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2104 if (!expr
->acc
.access
[type
])
2106 expr
->acc
.access
[type
] =
2107 isl_union_map_reset_user(expr
->acc
.access
[type
]);
2108 if (!expr
->acc
.access
[type
])
2111 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
2112 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2113 return pet_expr_free(expr
);
2118 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
2120 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
2123 /* Data used in access_gist() callback.
2125 struct pet_access_gist_data
{
2127 isl_union_map
*value_bounds
;
2130 /* Given an expression "expr" of type pet_expr_access, compute
2131 * the gist of the associated access relations (if any) and index expression
2132 * with respect to data->domain and the bounds on the values of the arguments
2133 * of the expression.
2135 * The arguments of "expr" have been gisted right before "expr" itself
2136 * is gisted. The gisted arguments may have become equal where before
2137 * they may not have been (obviously) equal. We therefore take
2138 * the opportunity to remove duplicate arguments here.
2140 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
2142 struct pet_access_gist_data
*data
= user
;
2144 isl_union_set
*uset
;
2145 enum pet_expr_access_type type
;
2147 expr
= pet_expr_remove_duplicate_args(expr
);
2148 expr
= pet_expr_cow(expr
);
2151 if (expr
->type
!= pet_expr_access
)
2152 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2153 "not an access expression", return pet_expr_free(expr
));
2155 domain
= isl_set_copy(data
->domain
);
2156 if (expr
->n_arg
> 0)
2157 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
2158 data
->value_bounds
);
2160 uset
= isl_union_set_from_set(isl_set_copy(domain
));
2161 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
2162 if (!expr
->acc
.access
[type
])
2164 expr
->acc
.access
[type
] =
2165 isl_union_map_gist_domain(expr
->acc
.access
[type
],
2166 isl_union_set_copy(uset
));
2167 if (!expr
->acc
.access
[type
])
2170 isl_union_set_free(uset
);
2171 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
2172 if (type
< pet_expr_access_end
|| !expr
->acc
.index
)
2173 return pet_expr_free(expr
);
2178 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
2179 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
2181 struct pet_access_gist_data data
= { context
, value_bounds
};
2183 return pet_expr_map_access(expr
, &access_gist
, &data
);
2186 /* Mark "expr" as a read dependening on "read".
2188 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
2192 return pet_expr_free(expr
);
2193 if (expr
->type
!= pet_expr_access
)
2194 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2195 "not an access expression", return pet_expr_free(expr
));
2196 if (expr
->acc
.read
== read
)
2198 expr
= pet_expr_cow(expr
);
2201 expr
->acc
.read
= read
;
2206 /* Mark "expr" as a write dependening on "write".
2208 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
2212 return pet_expr_free(expr
);
2213 if (expr
->type
!= pet_expr_access
)
2214 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2215 "not an access expression", return pet_expr_free(expr
));
2216 if (expr
->acc
.write
== write
)
2218 expr
= pet_expr_cow(expr
);
2221 expr
->acc
.write
= write
;
2226 /* Mark "expr" as a kill dependening on "kill".
2228 __isl_give pet_expr
*pet_expr_access_set_kill(__isl_take pet_expr
*expr
,
2232 return pet_expr_free(expr
);
2233 if (expr
->type
!= pet_expr_access
)
2234 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2235 "not an access expression", return pet_expr_free(expr
));
2236 if (expr
->acc
.kill
== kill
)
2238 expr
= pet_expr_cow(expr
);
2241 expr
->acc
.kill
= kill
;
2246 /* Map the access type "type" to the corresponding location
2247 * in the access array.
2248 * In particular, the access relation of type pet_expr_access_killed is
2249 * stored in the element at position pet_expr_access_fake_killed.
2251 static enum pet_expr_access_type
internalize_type(
2252 enum pet_expr_access_type type
)
2254 if (type
== pet_expr_access_killed
)
2255 return pet_expr_access_fake_killed
;
2259 /* Replace the access relation of the given "type" of "expr" by "access".
2260 * If the access relation is non-empty and the type is a read or a write,
2261 * then also mark the access expression itself as a read or a write.
2263 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
2264 enum pet_expr_access_type type
, __isl_take isl_union_map
*access
)
2268 expr
= pet_expr_cow(expr
);
2269 if (!expr
|| !access
)
2271 if (expr
->type
!= pet_expr_access
)
2272 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2273 "not an access expression", goto error
);
2274 type
= internalize_type(type
);
2275 isl_union_map_free(expr
->acc
.access
[type
]);
2276 expr
->acc
.access
[type
] = access
;
2281 empty
= isl_union_map_is_empty(access
);
2283 return pet_expr_free(expr
);
2287 if (type
== pet_expr_access_may_read
)
2288 expr
= pet_expr_access_set_read(expr
, 1);
2290 expr
= pet_expr_access_set_write(expr
, 1);
2294 isl_union_map_free(access
);
2295 pet_expr_free(expr
);
2299 /* Replace the index expression of "expr" by "index" and
2300 * set the array depth accordingly.
2302 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
2303 __isl_take isl_multi_pw_aff
*index
)
2305 expr
= pet_expr_cow(expr
);
2306 if (!expr
|| !index
)
2308 if (expr
->type
!= pet_expr_access
)
2309 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2310 "not an access expression", goto error
);
2311 isl_multi_pw_aff_free(expr
->acc
.index
);
2312 expr
->acc
.index
= index
;
2313 expr
->acc
.depth
= isl_multi_pw_aff_dim(index
, isl_dim_out
);
2317 isl_multi_pw_aff_free(index
);
2318 pet_expr_free(expr
);
2322 /* Return the reference identifier of access expression "expr".
2324 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
2328 if (expr
->type
!= pet_expr_access
)
2329 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2330 "not an access expression", return NULL
);
2332 return isl_id_copy(expr
->acc
.ref_id
);
2335 /* Replace the reference identifier of access expression "expr" by "ref_id".
2337 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
2338 __isl_take isl_id
*ref_id
)
2340 expr
= pet_expr_cow(expr
);
2341 if (!expr
|| !ref_id
)
2343 if (expr
->type
!= pet_expr_access
)
2344 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2345 "not an access expression", goto error
);
2346 isl_id_free(expr
->acc
.ref_id
);
2347 expr
->acc
.ref_id
= ref_id
;
2351 isl_id_free(ref_id
);
2352 pet_expr_free(expr
);
2356 /* Tag the access relation "access" with "id".
2357 * That is, insert the id as the range of a wrapped relation
2358 * in the domain of "access".
2360 * If "access" is of the form
2364 * then the result is of the form
2366 * [D[i] -> id[]] -> A[a]
2368 __isl_give isl_union_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
2369 __isl_take isl_union_map
*access
)
2372 isl_multi_aff
*add_tag
;
2375 if (expr
->type
!= pet_expr_access
)
2376 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2377 "not an access expression",
2378 return isl_union_map_free(access
));
2380 id
= isl_id_copy(expr
->acc
.ref_id
);
2381 space
= pet_expr_access_get_domain_space(expr
);
2382 space
= isl_space_from_domain(space
);
2383 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
2384 add_tag
= isl_multi_aff_domain_map(space
);
2385 access
= isl_union_map_preimage_domain_multi_aff(access
, add_tag
);
2390 /* Return the access relation of the given "type" associated to "expr"
2391 * that maps pairs of domain iterations and argument values
2392 * to the corresponding accessed data elements.
2394 * If the requested access relation is explicitly available,
2395 * then return a copy. Otherwise, check if it is irrelevant for
2396 * the access expression and return an empty relation if this is the case.
2397 * Otherwise, introduce the requested access relation in "expr" and
2400 __isl_give isl_union_map
*pet_expr_access_get_dependent_access(
2401 __isl_keep pet_expr
*expr
, enum pet_expr_access_type type
)
2403 isl_union_map
*access
;
2408 if (expr
->type
!= pet_expr_access
)
2409 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2410 "not an access expression", return NULL
);
2412 type
= internalize_type(type
);
2413 if (expr
->acc
.access
[type
])
2414 return isl_union_map_copy(expr
->acc
.access
[type
]);
2416 if (type
== pet_expr_access_may_read
)
2417 empty
= !expr
->acc
.read
;
2419 empty
= !expr
->acc
.write
;
2422 expr
= pet_expr_copy(expr
);
2423 expr
= introduce_access_relations(expr
);
2426 access
= isl_union_map_copy(expr
->acc
.access
[type
]);
2427 pet_expr_free(expr
);
2432 return isl_union_map_empty(pet_expr_access_get_parameter_space(expr
));
2435 /* Return the may read access relation associated to "expr"
2436 * that maps pairs of domain iterations and argument values
2437 * to the corresponding accessed data elements.
2439 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_read(
2440 __isl_keep pet_expr
*expr
)
2442 return pet_expr_access_get_dependent_access(expr
,
2443 pet_expr_access_may_read
);
2446 /* Return the may write access relation associated to "expr"
2447 * that maps pairs of domain iterations and argument values
2448 * to the corresponding accessed data elements.
2450 __isl_give isl_union_map
*pet_expr_access_get_dependent_may_write(
2451 __isl_keep pet_expr
*expr
)
2453 return pet_expr_access_get_dependent_access(expr
,
2454 pet_expr_access_may_write
);
2457 /* Return the must write access relation associated to "expr"
2458 * that maps pairs of domain iterations and argument values
2459 * to the corresponding accessed data elements.
2461 __isl_give isl_union_map
*pet_expr_access_get_dependent_must_write(
2462 __isl_keep pet_expr
*expr
)
2464 return pet_expr_access_get_dependent_access(expr
,
2465 pet_expr_access_must_write
);
2468 /* Return the relation of the given "type" mapping domain iterations
2469 * to the accessed data elements.
2470 * In particular, take the access relation and, in case of may_read
2471 * or may_write, project out the values of the arguments, if any.
2472 * In case of must_write, return the empty relation if there are
2475 __isl_give isl_union_map
*pet_expr_access_get_access(__isl_keep pet_expr
*expr
,
2476 enum pet_expr_access_type type
)
2478 isl_union_map
*access
;
2484 if (expr
->type
!= pet_expr_access
)
2485 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2486 "not an access expression", return NULL
);
2488 if (expr
->n_arg
!= 0 && type
== pet_expr_access_must_write
) {
2489 space
= pet_expr_access_get_parameter_space(expr
);
2490 return isl_union_map_empty(space
);
2493 access
= pet_expr_access_get_dependent_access(expr
, type
);
2494 if (expr
->n_arg
== 0)
2497 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
2498 space
= isl_space_domain(space
);
2499 map
= isl_map_universe(isl_space_unwrap(space
));
2500 map
= isl_map_domain_map(map
);
2501 access
= isl_union_map_apply_domain(access
,
2502 isl_union_map_from_map(map
));
2507 /* Return the relation mapping domain iterations to all possibly
2508 * read data elements.
2510 __isl_give isl_union_map
*pet_expr_access_get_may_read(
2511 __isl_keep pet_expr
*expr
)
2513 return pet_expr_access_get_access(expr
, pet_expr_access_may_read
);
2516 /* Return the relation mapping domain iterations to all possibly
2517 * written data elements.
2519 __isl_give isl_union_map
*pet_expr_access_get_may_write(
2520 __isl_keep pet_expr
*expr
)
2522 return pet_expr_access_get_access(expr
, pet_expr_access_may_write
);
2525 /* Return a relation mapping domain iterations to definitely
2526 * written data elements, assuming the statement containing
2527 * the expression is executed.
2529 __isl_give isl_union_map
*pet_expr_access_get_must_write(
2530 __isl_keep pet_expr
*expr
)
2532 return pet_expr_access_get_access(expr
, pet_expr_access_must_write
);
2535 /* Return the relation of the given "type" mapping domain iterations to
2536 * accessed data elements, with its domain tagged with the reference
2539 static __isl_give isl_union_map
*pet_expr_access_get_tagged_access(
2540 __isl_keep pet_expr
*expr
, enum pet_expr_access_type type
)
2542 isl_union_map
*access
;
2547 access
= pet_expr_access_get_access(expr
, type
);
2548 access
= pet_expr_tag_access(expr
, access
);
2553 /* Return the relation mapping domain iterations to all possibly
2554 * read data elements, with its domain tagged with the reference
2557 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_read(
2558 __isl_keep pet_expr
*expr
)
2560 return pet_expr_access_get_tagged_access(expr
,
2561 pet_expr_access_may_read
);
2564 /* Return the relation mapping domain iterations to all possibly
2565 * written data elements, with its domain tagged with the reference
2568 __isl_give isl_union_map
*pet_expr_access_get_tagged_may_write(
2569 __isl_keep pet_expr
*expr
)
2571 return pet_expr_access_get_tagged_access(expr
,
2572 pet_expr_access_may_write
);
2575 /* Return the operation type of operation expression "expr".
2577 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
2581 if (expr
->type
!= pet_expr_op
)
2582 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2583 "not an operation expression", return pet_op_last
);
2588 /* Replace the operation type of operation expression "expr" by "type".
2590 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
2591 enum pet_op_type type
)
2594 return pet_expr_free(expr
);
2595 if (expr
->type
!= pet_expr_op
)
2596 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2597 "not an operation expression",
2598 return pet_expr_free(expr
));
2599 if (expr
->op
== type
)
2601 expr
= pet_expr_cow(expr
);
2609 /* Return the name of the function called by "expr".
2611 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
2615 if (expr
->type
!= pet_expr_call
)
2616 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2617 "not a call expression", return NULL
);
2618 return expr
->c
.name
;
2621 /* Replace the name of the function called by "expr" by "name".
2623 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
2624 __isl_keep
const char *name
)
2626 expr
= pet_expr_cow(expr
);
2628 return pet_expr_free(expr
);
2629 if (expr
->type
!= pet_expr_call
)
2630 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2631 "not a call expression", return pet_expr_free(expr
));
2633 expr
->c
.name
= strdup(name
);
2635 return pet_expr_free(expr
);
2639 /* Does the call expression "expr" have an associated function summary?
2641 int pet_expr_call_has_summary(__isl_keep pet_expr
*expr
)
2645 if (expr
->type
!= pet_expr_call
)
2646 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2647 "not a call expression", return -1);
2649 return expr
->c
.summary
!= NULL
;
2652 /* Return a copy of the function summary associated to
2653 * the call expression "expr".
2655 __isl_give pet_function_summary
*pet_expr_call_get_summary(
2656 __isl_keep pet_expr
*expr
)
2660 if (expr
->type
!= pet_expr_call
)
2661 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2662 "not a call expression", return NULL
);
2664 return pet_function_summary_copy(expr
->c
.summary
);
2667 /* Replace the function summary associated to the call expression "expr"
2670 __isl_give pet_expr
*pet_expr_call_set_summary(__isl_take pet_expr
*expr
,
2671 __isl_take pet_function_summary
*summary
)
2673 expr
= pet_expr_cow(expr
);
2674 if (!expr
|| !summary
)
2676 if (expr
->type
!= pet_expr_call
)
2677 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2678 "not a call expression", goto error
);
2679 pet_function_summary_free(expr
->c
.summary
);
2680 expr
->c
.summary
= summary
;
2683 pet_function_summary_free(summary
);
2684 return pet_expr_free(expr
);
2687 /* Replace the type of the cast performed by "expr" by "name".
2689 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
2690 __isl_keep
const char *name
)
2692 expr
= pet_expr_cow(expr
);
2694 return pet_expr_free(expr
);
2695 if (expr
->type
!= pet_expr_cast
)
2696 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2697 "not a cast expression", return pet_expr_free(expr
));
2698 free(expr
->type_name
);
2699 expr
->type_name
= strdup(name
);
2700 if (!expr
->type_name
)
2701 return pet_expr_free(expr
);
2705 /* Return the value of the integer represented by "expr".
2707 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
2711 if (expr
->type
!= pet_expr_int
)
2712 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2713 "not an int expression", return NULL
);
2715 return isl_val_copy(expr
->i
);
2718 /* Replace the value of the integer represented by "expr" by "v".
2720 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
2721 __isl_take isl_val
*v
)
2723 expr
= pet_expr_cow(expr
);
2726 if (expr
->type
!= pet_expr_int
)
2727 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2728 "not an int expression", goto error
);
2729 isl_val_free(expr
->i
);
2735 pet_expr_free(expr
);
2739 /* Replace the value and string representation of the double
2740 * represented by "expr" by "d" and "s".
2742 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
2743 double d
, __isl_keep
const char *s
)
2745 expr
= pet_expr_cow(expr
);
2747 return pet_expr_free(expr
);
2748 if (expr
->type
!= pet_expr_double
)
2749 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2750 "not a double expression", return pet_expr_free(expr
));
2753 expr
->d
.s
= strdup(s
);
2755 return pet_expr_free(expr
);
2759 /* Return a string representation of the double expression "expr".
2761 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2765 if (expr
->type
!= pet_expr_double
)
2766 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2767 "not a double expression", return NULL
);
2768 return strdup(expr
->d
.s
);
2771 /* Return a piecewise affine expression defined on the specified domain
2772 * that represents NaN.
2774 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2776 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2779 /* This function is called when we come across an access that is
2780 * nested in what is supposed to be an affine expression.
2781 * "pc" is the context in which the affine expression is created.
2782 * If nesting is allowed in "pc", we return an affine expression that is
2783 * equal to a new parameter corresponding to this nested access.
2784 * Otherwise, we return NaN.
2786 * Note that we currently don't allow nested accesses themselves
2787 * to contain any nested accesses, so we check if "expr" itself
2788 * involves any nested accesses (either explicitly as arguments
2789 * or implicitly through parameters) and return NaN if it does.
2791 * The new parameter is resolved in resolve_nested.
2793 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2794 __isl_keep pet_context
*pc
)
2799 isl_local_space
*ls
;
2805 if (!pet_context_allow_nesting(pc
))
2806 return non_affine(pet_context_get_space(pc
));
2808 if (pet_expr_get_type(expr
) != pet_expr_access
)
2809 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2810 "not an access expression", return NULL
);
2812 if (expr
->n_arg
> 0)
2813 return non_affine(pet_context_get_space(pc
));
2815 space
= pet_expr_access_get_parameter_space(expr
);
2816 nested
= pet_nested_any_in_space(space
);
2817 isl_space_free(space
);
2819 return non_affine(pet_context_get_space(pc
));
2821 ctx
= pet_expr_get_ctx(expr
);
2822 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2823 space
= pet_context_get_space(pc
);
2824 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2826 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2827 ls
= isl_local_space_from_space(space
);
2828 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2830 return isl_pw_aff_from_aff(aff
);
2833 /* Extract an affine expression from the access pet_expr "expr".
2834 * "pc" is the context in which the affine expression is created.
2836 * If "expr" is actually an affine expression rather than
2837 * a real access, then we return that expression.
2838 * Otherwise, we require that "expr" is of an integral type.
2839 * If not, we return NaN.
2841 * If the variable has been assigned a known affine expression,
2842 * then we return that expression.
2844 * Otherwise, we return an expression that is equal to a parameter
2845 * representing "expr" (if "allow_nested" is set).
2847 static __isl_give isl_pw_aff
*extract_affine_from_access(
2848 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2853 if (pet_expr_is_affine(expr
))
2854 return pet_expr_get_affine(expr
);
2856 if (pet_expr_get_type_size(expr
) == 0)
2857 return non_affine(pet_context_get_space(pc
));
2859 if (!pet_expr_is_scalar_access(expr
))
2860 return nested_access(expr
, pc
);
2862 id
= pet_expr_access_get_id(expr
);
2863 if (pet_context_is_assigned(pc
, id
))
2864 return pet_context_get_value(pc
, id
);
2867 return nested_access(expr
, pc
);
2870 /* Construct an affine expression from the integer constant "expr".
2871 * "pc" is the context in which the affine expression is created.
2873 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2874 __isl_keep pet_context
*pc
)
2876 isl_local_space
*ls
;
2882 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2883 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2885 return isl_pw_aff_from_aff(aff
);
2888 /* Extract an affine expression from an addition or subtraction operation.
2889 * Return NaN if we are unable to extract an affine expression.
2891 * "pc" is the context in which the affine expression is created.
2893 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2894 __isl_keep pet_context
*pc
)
2901 if (expr
->n_arg
!= 2)
2902 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2903 "expecting two arguments", return NULL
);
2905 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2906 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2908 switch (pet_expr_op_get_type(expr
)) {
2910 return isl_pw_aff_add(lhs
, rhs
);
2912 return isl_pw_aff_sub(lhs
, rhs
);
2914 isl_pw_aff_free(lhs
);
2915 isl_pw_aff_free(rhs
);
2916 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2917 "not an addition or subtraction operation",
2923 /* Extract an affine expression from an integer division or a modulo operation.
2924 * Return NaN if we are unable to extract an affine expression.
2926 * "pc" is the context in which the affine expression is created.
2928 * In particular, if "expr" is lhs/rhs, then return
2930 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2932 * If "expr" is lhs%rhs, then return
2934 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2936 * If the second argument (rhs) is not a (positive) integer constant,
2937 * then we fail to extract an affine expression.
2939 * We simplify the result in the context of the domain of "pc" in case
2940 * this domain implies that lhs >= 0 (or < 0).
2942 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2943 __isl_keep pet_context
*pc
)
2952 if (expr
->n_arg
!= 2)
2953 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2954 "expecting two arguments", return NULL
);
2956 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2958 is_cst
= isl_pw_aff_is_cst(rhs
);
2959 if (is_cst
< 0 || !is_cst
) {
2960 isl_pw_aff_free(rhs
);
2961 return non_affine(pet_context_get_space(pc
));
2964 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2966 switch (pet_expr_op_get_type(expr
)) {
2968 res
= isl_pw_aff_tdiv_q(lhs
, rhs
);
2971 res
= isl_pw_aff_tdiv_r(lhs
, rhs
);
2974 isl_pw_aff_free(lhs
);
2975 isl_pw_aff_free(rhs
);
2976 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2977 "not a div or mod operator", return NULL
);
2980 return isl_pw_aff_gist(res
, pet_context_get_gist_domain(pc
));
2983 /* Extract an affine expression from a multiplication operation.
2984 * Return NaN if we are unable to extract an affine expression.
2985 * In particular, if neither of the arguments is a (piecewise) constant
2986 * then we return NaN.
2988 * "pc" is the context in which the affine expression is created.
2990 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2991 __isl_keep pet_context
*pc
)
2993 int lhs_cst
, rhs_cst
;
2999 if (expr
->n_arg
!= 2)
3000 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3001 "expecting two arguments", return NULL
);
3003 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
3004 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
3006 lhs_cst
= isl_pw_aff_is_cst(lhs
);
3007 rhs_cst
= isl_pw_aff_is_cst(rhs
);
3008 if (lhs_cst
>= 0 && rhs_cst
>= 0 && (lhs_cst
|| rhs_cst
))
3009 return isl_pw_aff_mul(lhs
, rhs
);
3011 isl_pw_aff_free(lhs
);
3012 isl_pw_aff_free(rhs
);
3014 if (lhs_cst
< 0 || rhs_cst
< 0)
3017 return non_affine(pet_context_get_space(pc
));
3020 /* Extract an affine expression from a negation operation.
3021 * Return NaN if we are unable to extract an affine expression.
3023 * "pc" is the context in which the affine expression is created.
3025 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
3026 __isl_keep pet_context
*pc
)
3032 if (expr
->n_arg
!= 1)
3033 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3034 "expecting one argument", return NULL
);
3036 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
3037 return isl_pw_aff_neg(res
);
3040 /* Extract an affine expression from a conditional operation.
3041 * Return NaN if we are unable to extract an affine expression.
3043 * "pc" is the context in which the affine expression is created.
3045 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
3046 __isl_keep pet_context
*pc
)
3048 isl_pw_aff
*cond
, *lhs
, *rhs
;
3052 if (expr
->n_arg
!= 3)
3053 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3054 "expecting three arguments", return NULL
);
3056 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3057 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
3058 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
3060 return isl_pw_aff_cond(cond
, lhs
, rhs
);
3063 /* Limit the domain of "pwaff" to those elements where the function
3066 * 2^{width-1} <= pwaff < 2^{width-1}
3068 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
3073 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
3074 isl_local_space
*ls
= isl_local_space_from_space(space
);
3079 ctx
= isl_pw_aff_get_ctx(pwaff
);
3080 v
= isl_val_int_from_ui(ctx
, width
- 1);
3081 v
= isl_val_2exp(v
);
3083 bound
= isl_aff_zero_on_domain(ls
);
3084 bound
= isl_aff_add_constant_val(bound
, v
);
3085 b
= isl_pw_aff_from_aff(bound
);
3087 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
3088 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3090 b
= isl_pw_aff_neg(b
);
3091 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
3092 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
3097 /* Handle potential overflows on signed computations.
3099 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
3100 * then we adjust the domain of "pa" to avoid overflows.
3102 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
3106 struct pet_options
*options
;
3111 ctx
= isl_pw_aff_get_ctx(pa
);
3112 options
= isl_ctx_peek_pet_options(ctx
);
3113 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
3114 pa
= avoid_overflow(pa
, width
);
3119 /* Extract an affine expression from some an operation.
3120 * Return NaN if we are unable to extract an affine expression.
3121 * If the result of a binary (non boolean) operation is unsigned,
3122 * then we wrap it based on the size of the type. If the result is signed,
3123 * then we ensure that no overflow occurs.
3125 * "pc" is the context in which the affine expression is created.
3127 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
3128 __isl_keep pet_context
*pc
)
3133 switch (pet_expr_op_get_type(expr
)) {
3136 res
= extract_affine_add_sub(expr
, pc
);
3140 res
= extract_affine_div_mod(expr
, pc
);
3143 res
= extract_affine_mul(expr
, pc
);
3146 return extract_affine_neg(expr
, pc
);
3148 return extract_affine_cond(expr
, pc
);
3158 return pet_expr_extract_affine_condition(expr
, pc
);
3160 return non_affine(pet_context_get_space(pc
));
3165 if (isl_pw_aff_involves_nan(res
)) {
3166 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
3167 isl_pw_aff_free(res
);
3168 return non_affine(space
);
3171 type_size
= pet_expr_get_type_size(expr
);
3173 res
= pet_wrap_pw_aff(res
, type_size
);
3175 res
= signed_overflow(res
, -type_size
);
3180 /* Internal data structure for affine builtin function declarations.
3182 * "pencil" is set if the builtin is pencil specific.
3183 * "n_args" is the number of arguments the function takes.
3184 * "name" is the function name.
3186 struct affine_builtin_decl
{
3192 static struct affine_builtin_decl affine_builtins
[] = {
3200 { 0, 2, "intFloor" },
3201 { 0, 2, "intCeil" },
3206 /* List of min and max builtin functions.
3208 static const char *min_max_builtins
[] = {
3209 "min", "imin", "umin",
3210 "max", "imax", "umax"
3213 /* Is a function call to "name" with "n_args" arguments a call to a
3214 * builtin function for which we can construct an affine expression?
3215 * pencil specific builtins are only recognized if "pencil" is set.
3217 static int is_affine_builtin(int pencil
, int n_args
, const char *name
)
3221 for (i
= 0; i
< ARRAY_SIZE(affine_builtins
); ++i
) {
3222 struct affine_builtin_decl
*decl
= &affine_builtins
[i
];
3224 if (decl
->pencil
&& !pencil
)
3226 if (decl
->n_args
== n_args
&& !strcmp(decl
->name
, name
))
3233 /* Is function "name" a known min or max builtin function?
3235 static int is_min_or_max_builtin(const char *name
)
3239 for (i
= 0; i
< ARRAY_SIZE(min_max_builtins
); ++i
)
3240 if (!strcmp(min_max_builtins
[i
], name
))
3246 /* Extract an affine expression from some special function calls.
3247 * Return NaN if we are unable to extract an affine expression.
3248 * In particular, we handle "min", "max", "ceild", "floord",
3249 * "intMod", "intFloor" and "intCeil".
3250 * In case of the latter five, the second argument needs to be
3251 * a (positive) integer constant.
3252 * If the pencil option is set, then we also handle "{i,u}min" and
3255 * "pc" is the context in which the affine expression is created.
3257 static __isl_give isl_pw_aff
*extract_affine_from_call(
3258 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3261 isl_pw_aff
*aff1
, *aff2
;
3264 struct pet_options
*options
;
3268 ctx
= pet_expr_get_ctx(expr
);
3269 options
= isl_ctx_peek_pet_options(ctx
);
3271 n
= pet_expr_get_n_arg(expr
);
3272 name
= pet_expr_call_get_name(expr
);
3273 if (!is_affine_builtin(options
->pencil
, n
, name
))
3274 return non_affine(pet_context_get_space(pc
));
3276 if (is_min_or_max_builtin(name
)) {
3277 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3278 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
3280 if (strstr(name
, "min"))
3281 aff1
= isl_pw_aff_min(aff1
, aff2
);
3283 aff1
= isl_pw_aff_max(aff1
, aff2
);
3284 } else if (!strcmp(name
, "intMod")) {
3287 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
3288 return non_affine(pet_context_get_space(pc
));
3289 v
= pet_expr_int_get_val(expr
->args
[1]);
3290 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3291 aff1
= isl_pw_aff_mod_val(aff1
, v
);
3295 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
3296 return non_affine(pet_context_get_space(pc
));
3297 v
= pet_expr_int_get_val(expr
->args
[1]);
3298 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
3299 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
3300 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
3301 aff1
= isl_pw_aff_floor(aff1
);
3303 aff1
= isl_pw_aff_ceil(aff1
);
3309 /* Extract an affine expression from "expr", if possible.
3310 * Otherwise return NaN.
3312 * "pc" is the context in which the affine expression is created.
3314 * Store the result in "pc" such that it can be reused in case
3315 * pet_expr_extract_affine is called again on the same pair of
3318 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
3319 __isl_keep pet_context
*pc
)
3321 isl_maybe_isl_pw_aff m
;
3327 m
= pet_context_get_extracted_affine(pc
, expr
);
3328 if (m
.valid
< 0 || m
.valid
)
3331 switch (pet_expr_get_type(expr
)) {
3332 case pet_expr_access
:
3333 pa
= extract_affine_from_access(expr
, pc
);
3336 pa
= extract_affine_from_int(expr
, pc
);
3339 pa
= extract_affine_from_op(expr
, pc
);
3342 pa
= extract_affine_from_call(expr
, pc
);
3345 case pet_expr_double
:
3346 case pet_expr_error
:
3347 pa
= non_affine(pet_context_get_space(pc
));
3351 if (pet_context_set_extracted_affine(pc
, expr
, pa
) < 0)
3352 return isl_pw_aff_free(pa
);
3357 /* Extract an affine expressions representing the comparison "LHS op RHS"
3358 * Return NaN if we are unable to extract such an affine expression.
3360 * "pc" is the context in which the affine expression is created.
3362 * If the comparison is of the form
3366 * then the expression is constructed as the conjunction of
3371 * A similar optimization is performed for max(a,b) <= c.
3372 * We do this because that will lead to simpler representations
3373 * of the expression.
3374 * If isl is ever enhanced to explicitly deal with min and max expressions,
3375 * this optimization can be removed.
3377 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
3378 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
3379 __isl_keep pet_context
*pc
)
3381 isl_pw_aff
*lhs_pa
, *rhs_pa
;
3383 if (op
== pet_op_gt
)
3384 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
3385 if (op
== pet_op_ge
)
3386 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
3388 if (op
== pet_op_lt
|| op
== pet_op_le
) {
3389 if (pet_expr_is_min(rhs
)) {
3390 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
3392 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
3394 return pet_and(lhs_pa
, rhs_pa
);
3396 if (pet_expr_is_max(lhs
)) {
3397 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
3399 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
3401 return pet_and(lhs_pa
, rhs_pa
);
3405 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
3406 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
3408 return pet_comparison(op
, lhs_pa
, rhs_pa
);
3411 /* Extract an affine expressions from the comparison "expr".
3412 * Return NaN if we are unable to extract such an affine expression.
3414 * "pc" is the context in which the affine expression is created.
3416 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
3417 __isl_keep pet_context
*pc
)
3419 enum pet_op_type type
;
3423 if (expr
->n_arg
!= 2)
3424 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3425 "expecting two arguments", return NULL
);
3427 type
= pet_expr_op_get_type(expr
);
3428 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
3432 /* Extract an affine expression representing the boolean operation
3433 * expressed by "expr".
3434 * Return NaN if we are unable to extract an affine expression.
3436 * "pc" is the context in which the affine expression is created.
3438 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
3439 __isl_keep pet_context
*pc
)
3441 isl_pw_aff
*lhs
, *rhs
;
3447 n
= pet_expr_get_n_arg(expr
);
3448 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3450 return pet_not(lhs
);
3452 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
3453 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
3456 /* Extract the affine expression "expr != 0 ? 1 : 0".
3457 * Return NaN if we are unable to extract an affine expression.
3459 * "pc" is the context in which the affine expression is created.
3461 static __isl_give isl_pw_aff
*extract_implicit_condition(
3462 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3466 res
= pet_expr_extract_affine(expr
, pc
);
3467 return pet_to_bool(res
);
3470 /* Extract a boolean affine expression from "expr".
3471 * Return NaN if we are unable to extract an affine expression.
3473 * "pc" is the context in which the affine expression is created.
3475 * If "expr" is neither a comparison nor a boolean operation,
3476 * then we assume it is an affine expression and return the
3477 * boolean expression "expr != 0 ? 1 : 0".
3479 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
3480 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
3485 if (pet_expr_is_comparison(expr
))
3486 return extract_comparison(expr
, pc
);
3487 if (pet_expr_is_boolean(expr
))
3488 return extract_boolean(expr
, pc
);
3490 return extract_implicit_condition(expr
, pc
);
3493 /* Check if "expr" is an assume expression and if its single argument
3494 * can be converted to an affine expression in the context of "pc".
3495 * If so, replace the argument by the affine expression.
3497 __isl_give pet_expr
*pet_expr_resolve_assume(__isl_take pet_expr
*expr
,
3498 __isl_keep pet_context
*pc
)
3501 isl_multi_pw_aff
*index
;
3505 if (!pet_expr_is_assume(expr
))
3507 if (expr
->n_arg
!= 1)
3508 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3509 "expecting one argument", return pet_expr_free(expr
));
3511 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
3513 return pet_expr_free(expr
);
3514 if (isl_pw_aff_involves_nan(cond
)) {
3515 isl_pw_aff_free(cond
);
3519 index
= isl_multi_pw_aff_from_pw_aff(cond
);
3520 expr
= pet_expr_set_arg(expr
, 0, pet_expr_from_index(index
));
3525 /* Return the number of bits needed to represent the type of "expr".
3526 * See the description of the type_size field of pet_expr.
3528 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
3530 return expr
? expr
->type_size
: 0;
3533 /* Replace the number of bits needed to represent the type of "expr"
3535 * See the description of the type_size field of pet_expr.
3537 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
3540 expr
= pet_expr_cow(expr
);
3544 expr
->type_size
= type_size
;
3549 /* Extend an access expression "expr" with an additional index "index".
3550 * In particular, add "index" as an extra argument to "expr" and
3551 * adjust the index expression of "expr" to refer to this extra argument.
3552 * The caller is responsible for calling pet_expr_access_set_depth
3553 * to update the corresponding access relation.
3555 * Note that we only collect the individual index expressions as
3556 * arguments of "expr" here.
3557 * An attempt to integrate them into the index expression of "expr"
3558 * is performed in pet_expr_access_plug_in_args.
3560 __isl_give pet_expr
*pet_expr_access_subscript(__isl_take pet_expr
*expr
,
3561 __isl_take pet_expr
*index
)
3565 isl_local_space
*ls
;
3568 expr
= pet_expr_cow(expr
);
3569 if (!expr
|| !index
)
3571 if (expr
->type
!= pet_expr_access
)
3572 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3573 "not an access pet_expr", goto error
);
3575 n
= pet_expr_get_n_arg(expr
);
3576 expr
= pet_expr_insert_arg(expr
, n
, index
);
3580 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3581 ls
= isl_local_space_from_space(space
);
3582 pa
= isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, isl_dim_set
, n
));
3583 expr
->acc
.index
= pet_array_subscript(expr
->acc
.index
, pa
);
3584 if (!expr
->acc
.index
)
3585 return pet_expr_free(expr
);
3589 pet_expr_free(expr
);
3590 pet_expr_free(index
);
3594 /* Extend an access expression "expr" with an additional member acces to "id".
3595 * In particular, extend the index expression of "expr" to include
3596 * the additional member access.
3597 * The caller is responsible for calling pet_expr_access_set_depth
3598 * to update the corresponding access relation.
3600 __isl_give pet_expr
*pet_expr_access_member(__isl_take pet_expr
*expr
,
3601 __isl_take isl_id
*id
)
3604 isl_multi_pw_aff
*field_access
;
3606 expr
= pet_expr_cow(expr
);
3609 if (expr
->type
!= pet_expr_access
)
3610 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3611 "not an access pet_expr", goto error
);
3613 space
= isl_multi_pw_aff_get_domain_space(expr
->acc
.index
);
3614 space
= isl_space_from_domain(space
);
3615 space
= isl_space_set_tuple_id(space
, isl_dim_out
, id
);
3616 field_access
= isl_multi_pw_aff_zero(space
);
3617 expr
->acc
.index
= pet_array_member(expr
->acc
.index
, field_access
);
3618 if (!expr
->acc
.index
)
3619 return pet_expr_free(expr
);
3623 pet_expr_free(expr
);
3628 /* Prefix the access expression "expr" with "prefix".
3629 * If "add" is set, then it is not the index expression "prefix" itself
3630 * that was passed to the function, but its address.
3632 __isl_give pet_expr
*pet_expr_access_patch(__isl_take pet_expr
*expr
,
3633 __isl_take isl_multi_pw_aff
*prefix
, int add
)
3635 enum pet_expr_access_type type
;
3637 expr
= pet_expr_cow(expr
);
3638 if (!expr
|| !prefix
)
3640 if (expr
->type
!= pet_expr_access
)
3641 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
3642 "not an access pet_expr", goto error
);
3644 expr
->acc
.depth
+= isl_multi_pw_aff_dim(prefix
, isl_dim_out
) - add
;
3645 for (type
= pet_expr_access_begin
; type
< pet_expr_access_end
; ++type
) {
3646 if (!expr
->acc
.access
[type
])
3648 expr
->acc
.access
[type
] = pet_patch_union_map(
3649 isl_multi_pw_aff_copy(prefix
), expr
->acc
.access
[type
],
3651 if (!expr
->acc
.access
[type
])
3654 expr
->acc
.index
= pet_patch_multi_pw_aff(prefix
, expr
->acc
.index
, add
);
3655 if (!expr
->acc
.index
|| type
< pet_expr_access_end
)
3656 return pet_expr_free(expr
);
3660 pet_expr_free(expr
);
3661 isl_multi_pw_aff_free(prefix
);
3665 /* Dump the arguments of "expr" to "p" as a YAML sequence keyed
3666 * by "args", if there are any such arguments.
3668 static __isl_give isl_printer
*dump_arguments(__isl_keep pet_expr
*expr
,
3669 __isl_take isl_printer
*p
)
3673 if (expr
->n_arg
== 0)
3676 p
= isl_printer_print_str(p
, "args");
3677 p
= isl_printer_yaml_next(p
);
3678 p
= isl_printer_yaml_start_sequence(p
);
3679 for (i
= 0; i
< expr
->n_arg
; ++i
) {
3680 p
= pet_expr_print(expr
->args
[i
], p
);
3681 p
= isl_printer_yaml_next(p
);
3683 p
= isl_printer_yaml_end_sequence(p
);
3688 /* Print "expr" to "p" in YAML format.
3690 __isl_give isl_printer
*pet_expr_print(__isl_keep pet_expr
*expr
,
3691 __isl_take isl_printer
*p
)
3694 return isl_printer_free(p
);
3696 switch (expr
->type
) {
3697 case pet_expr_double
:
3698 p
= isl_printer_print_str(p
, expr
->d
.s
);
3701 p
= isl_printer_print_val(p
, expr
->i
);
3703 case pet_expr_access
:
3704 p
= isl_printer_yaml_start_mapping(p
);
3705 if (expr
->acc
.ref_id
) {
3706 p
= isl_printer_print_str(p
, "ref_id");
3707 p
= isl_printer_yaml_next(p
);
3708 p
= isl_printer_print_id(p
, expr
->acc
.ref_id
);
3709 p
= isl_printer_yaml_next(p
);
3711 p
= isl_printer_print_str(p
, "index");
3712 p
= isl_printer_yaml_next(p
);
3713 p
= isl_printer_print_multi_pw_aff(p
, expr
->acc
.index
);
3714 p
= isl_printer_yaml_next(p
);
3715 p
= isl_printer_print_str(p
, "depth");
3716 p
= isl_printer_yaml_next(p
);
3717 p
= isl_printer_print_int(p
, expr
->acc
.depth
);
3718 p
= isl_printer_yaml_next(p
);
3719 if (expr
->acc
.kill
) {
3720 p
= isl_printer_print_str(p
, "kill");
3721 p
= isl_printer_yaml_next(p
);
3722 p
= isl_printer_print_int(p
, 1);
3723 p
= isl_printer_yaml_next(p
);
3725 p
= isl_printer_print_str(p
, "read");
3726 p
= isl_printer_yaml_next(p
);
3727 p
= isl_printer_print_int(p
, expr
->acc
.read
);
3728 p
= isl_printer_yaml_next(p
);
3729 p
= isl_printer_print_str(p
, "write");
3730 p
= isl_printer_yaml_next(p
);
3731 p
= isl_printer_print_int(p
, expr
->acc
.write
);
3732 p
= isl_printer_yaml_next(p
);
3734 if (expr
->acc
.access
[pet_expr_access_may_read
]) {
3735 p
= isl_printer_print_str(p
, "may_read");
3736 p
= isl_printer_yaml_next(p
);
3737 p
= isl_printer_print_union_map(p
,
3738 expr
->acc
.access
[pet_expr_access_may_read
]);
3739 p
= isl_printer_yaml_next(p
);
3741 if (expr
->acc
.access
[pet_expr_access_may_write
]) {
3742 p
= isl_printer_print_str(p
, "may_write");
3743 p
= isl_printer_yaml_next(p
);
3744 p
= isl_printer_print_union_map(p
,
3745 expr
->acc
.access
[pet_expr_access_may_write
]);
3746 p
= isl_printer_yaml_next(p
);
3748 if (expr
->acc
.access
[pet_expr_access_must_write
]) {
3749 p
= isl_printer_print_str(p
, "must_write");
3750 p
= isl_printer_yaml_next(p
);
3751 p
= isl_printer_print_union_map(p
,
3752 expr
->acc
.access
[pet_expr_access_must_write
]);
3753 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
, "op");
3761 p
= isl_printer_yaml_next(p
);
3762 p
= isl_printer_print_str(p
, op_str
[expr
->op
]);
3763 p
= isl_printer_yaml_next(p
);
3764 p
= dump_arguments(expr
, p
);
3765 p
= isl_printer_yaml_end_mapping(p
);
3768 p
= isl_printer_yaml_start_mapping(p
);
3769 p
= isl_printer_print_str(p
, "call");
3770 p
= isl_printer_yaml_next(p
);
3771 p
= isl_printer_print_str(p
, expr
->c
.name
);
3772 p
= isl_printer_print_str(p
, "/");
3773 p
= isl_printer_print_int(p
, expr
->n_arg
);
3774 p
= isl_printer_yaml_next(p
);
3775 p
= dump_arguments(expr
, p
);
3776 if (expr
->c
.summary
) {
3777 p
= isl_printer_print_str(p
, "summary");
3778 p
= isl_printer_yaml_next(p
);
3779 p
= pet_function_summary_print(expr
->c
.summary
, p
);
3781 p
= isl_printer_yaml_end_mapping(p
);
3784 p
= isl_printer_yaml_start_mapping(p
);
3785 p
= isl_printer_print_str(p
, "cast");
3786 p
= isl_printer_yaml_next(p
);
3787 p
= isl_printer_print_str(p
, expr
->type_name
);
3788 p
= isl_printer_yaml_next(p
);
3789 p
= dump_arguments(expr
, p
);
3790 p
= isl_printer_yaml_end_mapping(p
);
3792 case pet_expr_error
:
3793 p
= isl_printer_print_str(p
, "ERROR");
3800 /* Dump "expr" to stderr with indentation "indent".
3802 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
3809 p
= isl_printer_to_file(pet_expr_get_ctx(expr
), stderr
);
3810 p
= isl_printer_set_indent(p
, indent
);
3811 p
= isl_printer_set_yaml_style(p
, ISL_YAML_STYLE_BLOCK
);
3812 p
= isl_printer_start_line(p
);
3813 p
= pet_expr_print(expr
, p
);
3815 isl_printer_free(p
);
3818 void pet_expr_dump(__isl_keep pet_expr
*expr
)
3820 pet_expr_dump_with_indent(expr
, 0);