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
39 #include "value_bounds.h"
41 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
43 static char *type_str
[] = {
44 [pet_expr_access
] = "access",
45 [pet_expr_call
] = "call",
46 [pet_expr_cast
] = "cast",
47 [pet_expr_double
] = "double",
48 [pet_expr_int
] = "int",
52 static char *op_str
[] = {
53 [pet_op_add_assign
] = "+=",
54 [pet_op_sub_assign
] = "-=",
55 [pet_op_mul_assign
] = "*=",
56 [pet_op_div_assign
] = "/=",
57 [pet_op_assign
] = "=",
72 [pet_op_post_inc
] = "++",
73 [pet_op_post_dec
] = "--",
74 [pet_op_pre_inc
] = "++",
75 [pet_op_pre_dec
] = "--",
76 [pet_op_address_of
] = "&",
85 [pet_op_assume
] = "assume",
86 [pet_op_kill
] = "kill"
89 const char *pet_op_str(enum pet_op_type op
)
94 int pet_op_is_inc_dec(enum pet_op_type op
)
96 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
97 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
100 const char *pet_type_str(enum pet_expr_type type
)
102 return type_str
[type
];
105 enum pet_op_type
pet_str_op(const char *str
)
109 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
110 if (!strcmp(op_str
[i
], str
))
116 enum pet_expr_type
pet_str_type(const char *str
)
120 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
121 if (!strcmp(type_str
[i
], str
))
127 /* Construct an access pet_expr from an access relation and an index expression.
128 * By default, it is considered to be a read access.
130 struct pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
131 __isl_take isl_multi_pw_aff
*index
)
133 isl_ctx
*ctx
= isl_map_get_ctx(access
);
134 struct pet_expr
*expr
;
136 if (!index
|| !access
)
138 expr
= isl_calloc_type(ctx
, struct pet_expr
);
142 expr
->type
= pet_expr_access
;
143 expr
->acc
.access
= access
;
144 expr
->acc
.index
= index
;
150 isl_map_free(access
);
151 isl_multi_pw_aff_free(index
);
155 /* Construct an access pet_expr from an index expression.
156 * By default, the access is considered to be a read access.
158 struct pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
162 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
163 return pet_expr_from_access_and_index(access
, index
);
166 /* Extend the range of "access" with "n" dimensions, retaining
167 * the tuple identifier on this range.
169 * If "access" represents a member access, then extend the range
172 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
176 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
178 if (!isl_map_range_is_wrapping(access
)) {
179 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
183 domain
= isl_map_copy(access
);
184 domain
= isl_map_range_factor_domain(domain
);
185 access
= isl_map_range_factor_range(access
);
186 access
= extend_range(access
, n
);
187 access
= isl_map_range_product(domain
, access
);
190 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
195 /* Construct an access pet_expr from an index expression and
196 * the depth of the accessed array.
197 * By default, the access is considered to be a read access.
199 * If the number of indices is smaller than the depth of the array,
200 * then we assume that all elements of the remaining dimensions
203 struct pet_expr
*pet_expr_from_index_and_depth(
204 __isl_take isl_multi_pw_aff
*index
, int depth
)
209 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
212 dim
= isl_map_dim(access
, isl_dim_out
);
214 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
215 "number of indices greater than depth",
216 access
= isl_map_free(access
));
218 return pet_expr_from_access_and_index(access
, index
);
220 access
= extend_range(access
, depth
- dim
);
222 return pet_expr_from_access_and_index(access
, index
);
224 isl_multi_pw_aff_free(index
);
228 /* Construct a pet_expr that kills the elements specified by
229 * the index expression "index" and the access relation "access".
231 struct pet_expr
*pet_expr_kill_from_access_and_index(__isl_take isl_map
*access
,
232 __isl_take isl_multi_pw_aff
*index
)
235 struct pet_expr
*expr
;
237 if (!access
|| !index
)
240 ctx
= isl_multi_pw_aff_get_ctx(index
);
241 expr
= pet_expr_from_access_and_index(access
, index
);
245 return pet_expr_new_unary(ctx
, pet_op_kill
, expr
);
247 isl_map_free(access
);
248 isl_multi_pw_aff_free(index
);
252 /* Construct a unary pet_expr that performs "op" on "arg".
254 struct pet_expr
*pet_expr_new_unary(isl_ctx
*ctx
, enum pet_op_type op
,
255 struct pet_expr
*arg
)
257 struct pet_expr
*expr
;
261 expr
= isl_alloc_type(ctx
, struct pet_expr
);
265 expr
->type
= pet_expr_op
;
268 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
271 expr
->args
[pet_un_arg
] = arg
;
279 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
281 struct pet_expr
*pet_expr_new_binary(isl_ctx
*ctx
, enum pet_op_type op
,
282 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
284 struct pet_expr
*expr
;
288 expr
= isl_alloc_type(ctx
, struct pet_expr
);
292 expr
->type
= pet_expr_op
;
295 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 2);
298 expr
->args
[pet_bin_lhs
] = lhs
;
299 expr
->args
[pet_bin_rhs
] = rhs
;
308 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
310 struct pet_expr
*pet_expr_new_ternary(isl_ctx
*ctx
, struct pet_expr
*cond
,
311 struct pet_expr
*lhs
, struct pet_expr
*rhs
)
313 struct pet_expr
*expr
;
315 if (!cond
|| !lhs
|| !rhs
)
317 expr
= isl_alloc_type(ctx
, struct pet_expr
);
321 expr
->type
= pet_expr_op
;
322 expr
->op
= pet_op_cond
;
324 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 3);
327 expr
->args
[pet_ter_cond
] = cond
;
328 expr
->args
[pet_ter_true
] = lhs
;
329 expr
->args
[pet_ter_false
] = rhs
;
339 /* Construct a call pet_expr that calls function "name" with "n_arg"
340 * arguments. The caller is responsible for filling in the arguments.
342 struct pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
345 struct pet_expr
*expr
;
347 expr
= isl_alloc_type(ctx
, struct pet_expr
);
351 expr
->type
= pet_expr_call
;
353 expr
->name
= strdup(name
);
354 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, n_arg
);
355 if (!expr
->name
|| !expr
->args
)
356 return pet_expr_free(expr
);
361 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
363 struct pet_expr
*pet_expr_new_cast(isl_ctx
*ctx
, const char *type_name
,
364 struct pet_expr
*arg
)
366 struct pet_expr
*expr
;
371 expr
= isl_alloc_type(ctx
, struct pet_expr
);
375 expr
->type
= pet_expr_cast
;
377 expr
->type_name
= strdup(type_name
);
378 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
379 if (!expr
->type_name
|| !expr
->args
)
391 /* Construct a pet_expr that represents the double "d".
393 struct pet_expr
*pet_expr_new_double(isl_ctx
*ctx
, double val
, const char *s
)
395 struct pet_expr
*expr
;
397 expr
= isl_calloc_type(ctx
, struct pet_expr
);
401 expr
->type
= pet_expr_double
;
403 expr
->d
.s
= strdup(s
);
405 return pet_expr_free(expr
);
410 /* Construct a pet_expr that represents the integer value "v".
412 struct pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
415 struct pet_expr
*expr
;
420 ctx
= isl_val_get_ctx(v
);
421 expr
= isl_calloc_type(ctx
, struct pet_expr
);
425 expr
->type
= pet_expr_int
;
434 struct pet_expr
*pet_expr_free(struct pet_expr
*expr
)
441 for (i
= 0; i
< expr
->n_arg
; ++i
)
442 pet_expr_free(expr
->args
[i
]);
445 switch (expr
->type
) {
446 case pet_expr_access
:
447 isl_id_free(expr
->acc
.ref_id
);
448 isl_map_free(expr
->acc
.access
);
449 isl_multi_pw_aff_free(expr
->acc
.index
);
455 free(expr
->type_name
);
457 case pet_expr_double
:
461 isl_val_free(expr
->i
);
471 /* Does "expr" represent an access to an unnamed space, i.e.,
472 * does it represent an affine expression?
474 int pet_expr_is_affine(struct pet_expr
*expr
)
480 if (expr
->type
!= pet_expr_access
)
483 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
490 /* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
492 int pet_expr_is_scalar_access(struct pet_expr
*expr
)
496 if (expr
->type
!= pet_expr_access
)
499 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
502 /* Return 1 if the two pet_exprs are equivalent.
504 int pet_expr_is_equal(struct pet_expr
*expr1
, struct pet_expr
*expr2
)
508 if (!expr1
|| !expr2
)
511 if (expr1
->type
!= expr2
->type
)
513 if (expr1
->n_arg
!= expr2
->n_arg
)
515 for (i
= 0; i
< expr1
->n_arg
; ++i
)
516 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
518 switch (expr1
->type
) {
519 case pet_expr_double
:
520 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
522 if (expr1
->d
.val
!= expr2
->d
.val
)
526 if (!isl_val_eq(expr1
->i
, expr2
->i
))
529 case pet_expr_access
:
530 if (expr1
->acc
.read
!= expr2
->acc
.read
)
532 if (expr1
->acc
.write
!= expr2
->acc
.write
)
534 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
536 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
538 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
540 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
542 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
547 if (expr1
->op
!= expr2
->op
)
551 if (strcmp(expr1
->name
, expr2
->name
))
555 if (strcmp(expr1
->type_name
, expr2
->type_name
))
563 /* Does the access expression "expr" read the accessed elements?
565 int pet_expr_access_is_read(struct pet_expr
*expr
)
569 if (expr
->type
!= pet_expr_access
)
572 return expr
->acc
.read
;
575 /* Does the access expression "expr" write to the accessed elements?
577 int pet_expr_access_is_write(struct pet_expr
*expr
)
581 if (expr
->type
!= pet_expr_access
)
584 return expr
->acc
.write
;
587 /* Return the identifier of the array accessed by "expr".
589 * If "expr" represents a member access, then return the identifier
590 * of the outer structure array.
592 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
596 if (expr
->type
!= pet_expr_access
)
599 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
603 space
= isl_map_get_space(expr
->acc
.access
);
604 space
= isl_space_range(space
);
605 while (space
&& isl_space_is_wrapping(space
))
606 space
= isl_space_domain(isl_space_unwrap(space
));
607 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
608 isl_space_free(space
);
613 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
616 /* Return the parameter space of "expr".
618 __isl_give isl_space
*pet_expr_access_get_parameter_space(struct pet_expr
*expr
)
624 if (expr
->type
!= pet_expr_access
)
627 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
628 space
= isl_space_params(space
);
633 /* Return the space of the data accessed by "expr".
635 __isl_give isl_space
*pet_expr_access_get_data_space(struct pet_expr
*expr
)
641 if (expr
->type
!= pet_expr_access
)
644 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
645 space
= isl_space_range(space
);
650 /* Modify all expressions of type pet_expr_access in "expr"
651 * by calling "fn" on them.
653 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
654 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
662 for (i
= 0; i
< expr
->n_arg
; ++i
) {
663 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
665 return pet_expr_free(expr
);
668 if (expr
->type
== pet_expr_access
)
669 expr
= fn(expr
, user
);
674 /* Call "fn" on each of the subexpressions of "expr" of type "type".
676 * Return -1 on error (where fn returning a negative value is treated as
678 * Otherwise return 0.
680 int pet_expr_foreach_expr_of_type(struct pet_expr
*expr
,
681 enum pet_expr_type type
, int (*fn
)(struct pet_expr
*expr
, void *user
),
689 for (i
= 0; i
< expr
->n_arg
; ++i
)
690 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
694 if (expr
->type
== type
)
695 return fn(expr
, user
);
700 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
702 * Return -1 on error (where fn returning a negative value is treated as
704 * Otherwise return 0.
706 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
707 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
709 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
712 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
714 * Return -1 on error (where fn returning a negative value is treated as
716 * Otherwise return 0.
718 int pet_expr_foreach_call_expr(struct pet_expr
*expr
,
719 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
721 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
724 /* Internal data structure for pet_expr_writes.
725 * "id" is the identifier that we are looking for.
726 * "found" is set if we have found the identifier being written to.
728 struct pet_expr_writes_data
{
733 /* Given an access expression, check if it writes to data->id.
734 * If so, set data->found and abort the search.
736 static int writes(struct pet_expr
*expr
, void *user
)
738 struct pet_expr_writes_data
*data
= user
;
741 if (!expr
->acc
.write
)
743 if (pet_expr_is_affine(expr
))
746 write_id
= pet_expr_access_get_id(expr
);
747 isl_id_free(write_id
);
752 if (write_id
!= data
->id
)
759 /* Does expression "expr" write to "id"?
761 int pet_expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
763 struct pet_expr_writes_data data
;
767 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
774 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
775 * index expression and access relation of "expr"
776 * to dimensions of "dst_type" at "dst_pos".
778 struct pet_expr
*pet_expr_access_move_dims(struct pet_expr
*expr
,
779 enum isl_dim_type dst_type
, unsigned dst_pos
,
780 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
784 if (expr
->type
!= pet_expr_access
)
785 return pet_expr_free(expr
);
787 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
788 dst_type
, dst_pos
, src_type
, src_pos
, n
);
789 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
790 dst_type
, dst_pos
, src_type
, src_pos
, n
);
791 if (!expr
->acc
.access
|| !expr
->acc
.index
)
792 return pet_expr_free(expr
);
797 /* Replace the index expression and access relation of "expr"
798 * by their preimages under the function represented by "ma".
800 struct pet_expr
*pet_expr_access_pullback_multi_aff(
801 struct pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
805 if (expr
->type
!= pet_expr_access
)
808 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(expr
->acc
.access
,
809 isl_multi_aff_copy(ma
));
810 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
812 if (!expr
->acc
.access
|| !expr
->acc
.index
)
813 return pet_expr_free(expr
);
817 isl_multi_aff_free(ma
);
822 /* Align the parameters of expr->acc.index and expr->acc.access.
824 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
828 if (expr
->type
!= pet_expr_access
)
829 return pet_expr_free(expr
);
831 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
832 isl_multi_pw_aff_get_space(expr
->acc
.index
));
833 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
834 isl_map_get_space(expr
->acc
.access
));
835 if (!expr
->acc
.access
|| !expr
->acc
.index
)
836 return pet_expr_free(expr
);
841 /* Add extra conditions on the parameters to all access relations in "expr".
843 * The conditions are not added to the index expression. Instead, they
844 * are used to try and simplify the index expression.
846 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
847 __isl_take isl_set
*cond
)
854 for (i
= 0; i
< expr
->n_arg
; ++i
) {
855 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
861 if (expr
->type
== pet_expr_access
) {
862 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
864 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
865 expr
->acc
.index
, isl_set_copy(cond
));
866 if (!expr
->acc
.access
|| !expr
->acc
.index
)
874 return pet_expr_free(expr
);
877 /* Modify the access relation and index expression
878 * of the given access expression
879 * based on the given iteration space transformation.
880 * In particular, precompose the access relation and index expression
881 * with the update function.
883 * If the access has any arguments then the domain of the access relation
884 * is a wrapped mapping from the iteration space to the space of
885 * argument values. We only need to change the domain of this wrapped
886 * mapping, so we extend the input transformation with an identity mapping
887 * on the space of argument values.
889 struct pet_expr
*pet_expr_access_update_domain(struct pet_expr
*expr
,
890 __isl_keep isl_multi_pw_aff
*update
)
894 update
= isl_multi_pw_aff_copy(update
);
896 space
= isl_map_get_space(expr
->acc
.access
);
897 space
= isl_space_domain(space
);
898 if (!isl_space_is_wrapping(space
))
899 isl_space_free(space
);
901 isl_multi_pw_aff
*id
;
902 space
= isl_space_unwrap(space
);
903 space
= isl_space_range(space
);
904 space
= isl_space_map_from_set(space
);
905 id
= isl_multi_pw_aff_identity(space
);
906 update
= isl_multi_pw_aff_product(update
, id
);
909 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
911 isl_multi_pw_aff_copy(update
));
912 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
913 expr
->acc
.index
, update
);
914 if (!expr
->acc
.access
|| !expr
->acc
.index
)
915 return pet_expr_free(expr
);
920 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
922 isl_multi_pw_aff
*update
= user
;
924 return pet_expr_access_update_domain(expr
, update
);
927 /* Modify all access relations in "expr" by precomposing them with
928 * the given iteration space transformation.
930 struct pet_expr
*pet_expr_update_domain(struct pet_expr
*expr
,
931 __isl_take isl_multi_pw_aff
*update
)
933 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
934 isl_multi_pw_aff_free(update
);
938 /* Add all parameters in "space" to the access relation and index expression
941 static struct pet_expr
*align_params(struct pet_expr
*expr
, void *user
)
943 isl_space
*space
= user
;
945 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
946 isl_space_copy(space
));
947 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
948 isl_space_copy(space
));
949 if (!expr
->acc
.access
|| !expr
->acc
.index
)
950 return pet_expr_free(expr
);
955 /* Add all parameters in "space" to all access relations and index expressions
958 struct pet_expr
*pet_expr_align_params(struct pet_expr
*expr
,
959 __isl_take isl_space
*space
)
961 expr
= pet_expr_map_access(expr
, &align_params
, space
);
962 isl_space_free(space
);
966 /* Insert an argument expression corresponding to "test" in front
967 * of the list of arguments described by *n_arg and *args.
969 static struct pet_expr
*insert_access_arg(struct pet_expr
*expr
,
970 __isl_keep isl_multi_pw_aff
*test
)
973 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
976 return pet_expr_free(expr
);
979 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
981 return pet_expr_free(expr
);
983 struct pet_expr
**ext
;
984 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + expr
->n_arg
);
986 return pet_expr_free(expr
);
987 for (i
= 0; i
< expr
->n_arg
; ++i
)
988 ext
[1 + i
] = expr
->args
[i
];
993 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
995 return pet_expr_free(expr
);
1000 /* Make the expression "expr" depend on the value of "test"
1001 * being equal to "satisfied".
1003 * If "test" is an affine expression, we simply add the conditions
1004 * on the expression having the value "satisfied" to all access relations
1005 * and index expressions.
1007 * Otherwise, we add a filter to "expr" (which is then assumed to be
1008 * an access expression) corresponding to "test" being equal to "satisfied".
1010 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
1011 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1016 isl_pw_multi_aff
*pma
;
1021 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1025 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
1026 isl_multi_pw_aff_free(test
);
1028 cond
= isl_pw_aff_non_zero_set(pa
);
1030 cond
= isl_pw_aff_zero_set(pa
);
1031 return pet_expr_restrict(expr
, isl_set_params(cond
));
1034 ctx
= isl_multi_pw_aff_get_ctx(test
);
1035 if (expr
->type
!= pet_expr_access
)
1036 isl_die(ctx
, isl_error_invalid
,
1037 "can only filter access expressions", goto error
);
1039 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
1040 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1041 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
1043 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
1045 isl_pw_multi_aff_copy(pma
));
1046 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
1047 expr
->acc
.index
, pma
);
1048 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1051 expr
= insert_access_arg(expr
, test
);
1053 isl_multi_pw_aff_free(test
);
1056 isl_multi_pw_aff_free(test
);
1057 return pet_expr_free(expr
);
1060 /* Check if the given index expression accesses a (0D) array that corresponds
1061 * to one of the parameters in "space". If so, replace the array access
1062 * by an access to the set of integers with as index (and value)
1065 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
1066 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
1068 isl_local_space
*ls
;
1069 isl_id
*array_id
= NULL
;
1073 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
1074 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1075 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1077 isl_space_free(space
);
1080 isl_id_free(array_id
);
1084 space
= isl_multi_pw_aff_get_domain_space(index
);
1085 isl_multi_pw_aff_free(index
);
1087 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1089 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
1090 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
1093 isl_id_free(array_id
);
1095 ls
= isl_local_space_from_space(space
);
1096 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
1097 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1102 /* Check if the given access relation accesses a (0D) array that corresponds
1103 * to one of the parameters in "space". If so, replace the array access
1104 * by an access to the set of integers with as index (and value)
1107 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1108 __isl_take isl_space
*space
)
1110 isl_id
*array_id
= NULL
;
1113 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1114 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1115 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1117 isl_space_free(space
);
1120 isl_id_free(array_id
);
1124 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1126 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1127 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1130 isl_id_free(array_id
);
1132 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1133 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1138 /* If "expr" accesses a (0D) array that corresponds to one of the parameters
1139 * in "space" then replace it by a value equal to the corresponding parameter.
1141 static struct pet_expr
*detect_parameter_accesses(struct pet_expr
*expr
,
1144 isl_space
*space
= user
;
1146 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1147 isl_space_copy(space
));
1148 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
1149 isl_space_copy(space
));
1150 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1151 return pet_expr_free(expr
);
1156 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1157 * in "space" by a value equal to the corresponding parameter.
1159 struct pet_expr
*pet_expr_detect_parameter_accesses(struct pet_expr
*expr
,
1160 __isl_take isl_space
*space
)
1162 expr
= pet_expr_map_access(expr
, &detect_parameter_accesses
, space
);
1163 isl_space_free(space
);
1167 /* Add a reference identifier to access expression "expr".
1168 * "user" points to an integer that contains the sequence number
1169 * of the next reference.
1171 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
1180 ctx
= isl_map_get_ctx(expr
->acc
.access
);
1181 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1182 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1183 if (!expr
->acc
.ref_id
)
1184 return pet_expr_free(expr
);
1189 struct pet_expr
*pet_expr_add_ref_ids(struct pet_expr
*expr
, int *n_ref
)
1191 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1194 /* Reset the user pointer on all parameter and tuple ids in
1195 * the access relation and the index expressions
1196 * of the access expression "expr".
1198 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
1200 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1201 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1202 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1203 return pet_expr_free(expr
);
1208 struct pet_expr
*pet_expr_anonymize(struct pet_expr
*expr
)
1210 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1213 /* Data used in access_gist() callback.
1215 struct pet_access_gist_data
{
1217 isl_union_map
*value_bounds
;
1220 /* Given an expression "expr" of type pet_expr_access, compute
1221 * the gist of the associated access relation and index expression
1222 * with respect to data->domain and the bounds on the values of the arguments
1223 * of the expression.
1225 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
1227 struct pet_access_gist_data
*data
= user
;
1230 domain
= isl_set_copy(data
->domain
);
1231 if (expr
->n_arg
> 0)
1232 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1233 data
->value_bounds
);
1235 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1236 isl_set_copy(domain
));
1237 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1238 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1239 return pet_expr_free(expr
);
1244 struct pet_expr
*pet_expr_gist(struct pet_expr
*expr
,
1245 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1247 struct pet_access_gist_data data
= { context
, value_bounds
};
1249 return pet_expr_map_access(expr
, &access_gist
, &data
);
1252 /* Tag the access relation "access" with "id".
1253 * That is, insert the id as the range of a wrapped relation
1254 * in the domain of "access".
1256 * If "access" is of the form
1260 * then the result is of the form
1262 * [D[i] -> id[]] -> A[a]
1264 __isl_give isl_map
*pet_expr_tag_access(struct pet_expr
*expr
,
1265 __isl_take isl_map
*access
)
1271 id
= isl_id_copy(expr
->acc
.ref_id
);
1272 space
= isl_space_range(isl_map_get_space(access
));
1273 space
= isl_space_from_range(space
);
1274 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
1275 add_tag
= isl_map_universe(space
);
1276 access
= isl_map_domain_product(access
, add_tag
);
1281 /* Return the relation mapping pairs of domain iterations and argument
1282 * values to the corresponding accessed data elements.
1284 __isl_give isl_map
*pet_expr_access_get_dependent_access(struct pet_expr
*expr
)
1288 if (expr
->type
!= pet_expr_access
)
1291 return isl_map_copy(expr
->acc
.access
);
1294 /* Return the relation mapping domain iterations to all possibly
1295 * accessed data elements.
1296 * In particular, take the access relation and project out the values
1297 * of the arguments, if any.
1299 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
1307 if (expr
->type
!= pet_expr_access
)
1310 access
= pet_expr_access_get_dependent_access(expr
);
1311 if (expr
->n_arg
== 0)
1314 space
= isl_space_domain(isl_map_get_space(access
));
1315 map
= isl_map_universe(isl_space_unwrap(space
));
1316 map
= isl_map_domain_map(map
);
1317 access
= isl_map_apply_domain(access
, map
);
1322 /* Return a relation mapping domain iterations to definitely
1323 * accessed data elements, assuming the statement containing
1324 * the expression is executed.
1326 * If there are no arguments, then all elements are accessed.
1327 * Otherwise, we conservatively return an empty relation.
1329 __isl_give isl_map
*pet_expr_access_get_must_access(struct pet_expr
*expr
)
1335 if (expr
->type
!= pet_expr_access
)
1338 if (expr
->n_arg
== 0)
1339 return pet_expr_access_get_dependent_access(expr
);
1341 space
= isl_map_get_space(expr
->acc
.access
);
1342 space
= isl_space_domain_factor_domain(space
);
1344 return isl_map_empty(space
);
1347 /* Return the relation mapping domain iterations to all possibly
1348 * accessed data elements, with its domain tagged with the reference
1351 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
1352 struct pet_expr
*expr
)
1359 access
= pet_expr_access_get_may_access(expr
);
1360 access
= pet_expr_tag_access(expr
, access
);
1365 /* Return a string representation of the double expression "expr".
1367 __isl_give
char *pet_expr_double_get_str(struct pet_expr
*expr
)
1371 if (expr
->type
!= pet_expr_double
)
1373 return strdup(expr
->d
.s
);
1376 void pet_expr_dump_with_indent(struct pet_expr
*expr
, int indent
)
1383 fprintf(stderr
, "%*s", indent
, "");
1385 switch (expr
->type
) {
1386 case pet_expr_double
:
1387 fprintf(stderr
, "%s\n", expr
->d
.s
);
1390 isl_val_dump(expr
->i
);
1392 case pet_expr_access
:
1393 if (expr
->acc
.ref_id
) {
1394 isl_id_dump(expr
->acc
.ref_id
);
1395 fprintf(stderr
, "%*s", indent
, "");
1397 isl_map_dump(expr
->acc
.access
);
1398 fprintf(stderr
, "%*s", indent
, "");
1399 isl_multi_pw_aff_dump(expr
->acc
.index
);
1400 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
1401 "", expr
->acc
.read
);
1402 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
1403 "", expr
->acc
.write
);
1404 for (i
= 0; i
< expr
->n_arg
; ++i
)
1405 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1408 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
1409 for (i
= 0; i
< expr
->n_arg
; ++i
)
1410 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1413 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
1414 for (i
= 0; i
< expr
->n_arg
; ++i
)
1415 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1418 fprintf(stderr
, "(%s)\n", expr
->type_name
);
1419 for (i
= 0; i
< expr
->n_arg
; ++i
)
1420 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1425 void pet_expr_dump(struct pet_expr
*expr
)
1427 pet_expr_dump_with_indent(expr
, 0);