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 /* Return the identifier of the array accessed by "expr".
565 * If "expr" represents a member access, then return the identifier
566 * of the outer structure array.
568 __isl_give isl_id
*pet_expr_access_get_id(struct pet_expr
*expr
)
572 if (expr
->type
!= pet_expr_access
)
575 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
579 space
= isl_map_get_space(expr
->acc
.access
);
580 space
= isl_space_range(space
);
581 while (space
&& isl_space_is_wrapping(space
))
582 space
= isl_space_domain(isl_space_unwrap(space
));
583 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
584 isl_space_free(space
);
589 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
592 /* Return the parameter space of "expr".
594 __isl_give isl_space
*pet_expr_access_get_parameter_space(struct pet_expr
*expr
)
600 if (expr
->type
!= pet_expr_access
)
603 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
604 space
= isl_space_params(space
);
609 /* Return the space of the data accessed by "expr".
611 __isl_give isl_space
*pet_expr_access_get_data_space(struct pet_expr
*expr
)
617 if (expr
->type
!= pet_expr_access
)
620 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
621 space
= isl_space_range(space
);
626 /* Modify all expressions of type pet_expr_access in "expr"
627 * by calling "fn" on them.
629 struct pet_expr
*pet_expr_map_access(struct pet_expr
*expr
,
630 struct pet_expr
*(*fn
)(struct pet_expr
*expr
, void *user
),
638 for (i
= 0; i
< expr
->n_arg
; ++i
) {
639 expr
->args
[i
] = pet_expr_map_access(expr
->args
[i
], fn
, user
);
641 return pet_expr_free(expr
);
644 if (expr
->type
== pet_expr_access
)
645 expr
= fn(expr
, user
);
650 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
652 * Return -1 on error (where fn return a negative value is treated as an error).
653 * Otherwise return 0.
655 int pet_expr_foreach_access_expr(struct pet_expr
*expr
,
656 int (*fn
)(struct pet_expr
*expr
, void *user
), void *user
)
663 for (i
= 0; i
< expr
->n_arg
; ++i
)
664 if (pet_expr_foreach_access_expr(expr
->args
[i
], fn
, user
) < 0)
667 if (expr
->type
== pet_expr_access
)
668 return fn(expr
, user
);
673 /* Internal data structure for pet_expr_writes.
674 * "id" is the identifier that we are looking for.
675 * "found" is set if we have found the identifier being written to.
677 struct pet_expr_writes_data
{
682 /* Given an access expression, check if it writes to data->id.
683 * If so, set data->found and abort the search.
685 static int writes(struct pet_expr
*expr
, void *user
)
687 struct pet_expr_writes_data
*data
= user
;
690 if (!expr
->acc
.write
)
692 if (pet_expr_is_affine(expr
))
695 write_id
= pet_expr_access_get_id(expr
);
696 isl_id_free(write_id
);
701 if (write_id
!= data
->id
)
708 /* Does expression "expr" write to "id"?
710 int pet_expr_writes(struct pet_expr
*expr
, __isl_keep isl_id
*id
)
712 struct pet_expr_writes_data data
;
716 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
723 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
724 * index expression and access relation of "expr"
725 * to dimensions of "dst_type" at "dst_pos".
727 struct pet_expr
*pet_expr_access_move_dims(struct pet_expr
*expr
,
728 enum isl_dim_type dst_type
, unsigned dst_pos
,
729 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
733 if (expr
->type
!= pet_expr_access
)
734 return pet_expr_free(expr
);
736 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
737 dst_type
, dst_pos
, src_type
, src_pos
, n
);
738 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
739 dst_type
, dst_pos
, src_type
, src_pos
, n
);
740 if (!expr
->acc
.access
|| !expr
->acc
.index
)
741 return pet_expr_free(expr
);
746 /* Replace the index expression and access relation of "expr"
747 * by their preimages under the function represented by "ma".
749 struct pet_expr
*pet_expr_access_pullback_multi_aff(
750 struct pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
754 if (expr
->type
!= pet_expr_access
)
757 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(expr
->acc
.access
,
758 isl_multi_aff_copy(ma
));
759 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
761 if (!expr
->acc
.access
|| !expr
->acc
.index
)
762 return pet_expr_free(expr
);
766 isl_multi_aff_free(ma
);
771 /* Align the parameters of expr->acc.index and expr->acc.access.
773 struct pet_expr
*pet_expr_access_align_params(struct pet_expr
*expr
)
777 if (expr
->type
!= pet_expr_access
)
778 return pet_expr_free(expr
);
780 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
781 isl_multi_pw_aff_get_space(expr
->acc
.index
));
782 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
783 isl_map_get_space(expr
->acc
.access
));
784 if (!expr
->acc
.access
|| !expr
->acc
.index
)
785 return pet_expr_free(expr
);
790 /* Add extra conditions on the parameters to all access relations in "expr".
792 * The conditions are not added to the index expression. Instead, they
793 * are used to try and simplify the index expression.
795 struct pet_expr
*pet_expr_restrict(struct pet_expr
*expr
,
796 __isl_take isl_set
*cond
)
803 for (i
= 0; i
< expr
->n_arg
; ++i
) {
804 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
810 if (expr
->type
== pet_expr_access
) {
811 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
813 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
814 expr
->acc
.index
, isl_set_copy(cond
));
815 if (!expr
->acc
.access
|| !expr
->acc
.index
)
823 return pet_expr_free(expr
);
826 /* Modify the access relation and index expression
827 * of the given access expression
828 * based on the given iteration space transformation.
829 * In particular, precompose the access relation and index expression
830 * with the update function.
832 * If the access has any arguments then the domain of the access relation
833 * is a wrapped mapping from the iteration space to the space of
834 * argument values. We only need to change the domain of this wrapped
835 * mapping, so we extend the input transformation with an identity mapping
836 * on the space of argument values.
838 struct pet_expr
*pet_expr_access_update_domain(struct pet_expr
*expr
,
839 __isl_keep isl_multi_pw_aff
*update
)
843 update
= isl_multi_pw_aff_copy(update
);
845 space
= isl_map_get_space(expr
->acc
.access
);
846 space
= isl_space_domain(space
);
847 if (!isl_space_is_wrapping(space
))
848 isl_space_free(space
);
850 isl_multi_pw_aff
*id
;
851 space
= isl_space_unwrap(space
);
852 space
= isl_space_range(space
);
853 space
= isl_space_map_from_set(space
);
854 id
= isl_multi_pw_aff_identity(space
);
855 update
= isl_multi_pw_aff_product(update
, id
);
858 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
860 isl_multi_pw_aff_copy(update
));
861 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
862 expr
->acc
.index
, update
);
863 if (!expr
->acc
.access
|| !expr
->acc
.index
)
864 return pet_expr_free(expr
);
869 static struct pet_expr
*update_domain(struct pet_expr
*expr
, void *user
)
871 isl_multi_pw_aff
*update
= user
;
873 return pet_expr_access_update_domain(expr
, update
);
876 /* Modify all access relations in "expr" by precomposing them with
877 * the given iteration space transformation.
879 struct pet_expr
*pet_expr_update_domain(struct pet_expr
*expr
,
880 __isl_take isl_multi_pw_aff
*update
)
882 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
883 isl_multi_pw_aff_free(update
);
887 /* Add all parameters in "space" to the access relation and index expression
890 static struct pet_expr
*align_params(struct pet_expr
*expr
, void *user
)
892 isl_space
*space
= user
;
894 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
895 isl_space_copy(space
));
896 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
897 isl_space_copy(space
));
898 if (!expr
->acc
.access
|| !expr
->acc
.index
)
899 return pet_expr_free(expr
);
904 /* Add all parameters in "space" to all access relations and index expressions
907 struct pet_expr
*pet_expr_align_params(struct pet_expr
*expr
,
908 __isl_take isl_space
*space
)
910 expr
= pet_expr_map_access(expr
, &align_params
, space
);
911 isl_space_free(space
);
915 /* Insert an argument expression corresponding to "test" in front
916 * of the list of arguments described by *n_arg and *args.
918 static struct pet_expr
*insert_access_arg(struct pet_expr
*expr
,
919 __isl_keep isl_multi_pw_aff
*test
)
922 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
925 return pet_expr_free(expr
);
928 expr
->args
= isl_calloc_array(ctx
, struct pet_expr
*, 1);
930 return pet_expr_free(expr
);
932 struct pet_expr
**ext
;
933 ext
= isl_calloc_array(ctx
, struct pet_expr
*, 1 + expr
->n_arg
);
935 return pet_expr_free(expr
);
936 for (i
= 0; i
< expr
->n_arg
; ++i
)
937 ext
[1 + i
] = expr
->args
[i
];
942 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
944 return pet_expr_free(expr
);
949 /* Make the expression "expr" depend on the value of "test"
950 * being equal to "satisfied".
952 * If "test" is an affine expression, we simply add the conditions
953 * on the expression having the value "satisfied" to all access relations
954 * and index expressions.
956 * Otherwise, we add a filter to "expr" (which is then assumed to be
957 * an access expression) corresponding to "test" being equal to "satisfied".
959 struct pet_expr
*pet_expr_filter(struct pet_expr
*expr
,
960 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
965 isl_pw_multi_aff
*pma
;
970 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
974 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
975 isl_multi_pw_aff_free(test
);
977 cond
= isl_pw_aff_non_zero_set(pa
);
979 cond
= isl_pw_aff_zero_set(pa
);
980 return pet_expr_restrict(expr
, isl_set_params(cond
));
983 ctx
= isl_multi_pw_aff_get_ctx(test
);
984 if (expr
->type
!= pet_expr_access
)
985 isl_die(ctx
, isl_error_invalid
,
986 "can only filter access expressions", goto error
);
988 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
989 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
990 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
992 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
994 isl_pw_multi_aff_copy(pma
));
995 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
996 expr
->acc
.index
, pma
);
997 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1000 expr
= insert_access_arg(expr
, test
);
1002 isl_multi_pw_aff_free(test
);
1005 isl_multi_pw_aff_free(test
);
1006 return pet_expr_free(expr
);
1009 /* Check if the given index expression accesses a (0D) array that corresponds
1010 * to one of the parameters in "space". If so, replace the array access
1011 * by an access to the set of integers with as index (and value)
1014 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
1015 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
1017 isl_local_space
*ls
;
1018 isl_id
*array_id
= NULL
;
1022 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
1023 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1024 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1026 isl_space_free(space
);
1029 isl_id_free(array_id
);
1033 space
= isl_multi_pw_aff_get_domain_space(index
);
1034 isl_multi_pw_aff_free(index
);
1036 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1038 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
1039 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
1042 isl_id_free(array_id
);
1044 ls
= isl_local_space_from_space(space
);
1045 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
1046 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1051 /* Check if the given access relation accesses a (0D) array that corresponds
1052 * to one of the parameters in "space". If so, replace the array access
1053 * by an access to the set of integers with as index (and value)
1056 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1057 __isl_take isl_space
*space
)
1059 isl_id
*array_id
= NULL
;
1062 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1063 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1064 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1066 isl_space_free(space
);
1069 isl_id_free(array_id
);
1073 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1075 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1076 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1079 isl_id_free(array_id
);
1081 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1082 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1087 /* If "expr" accesses a (0D) array that corresponds to one of the parameters
1088 * in "space" then replace it by a value equal to the corresponding parameter.
1090 static struct pet_expr
*detect_parameter_accesses(struct pet_expr
*expr
,
1093 isl_space
*space
= user
;
1095 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1096 isl_space_copy(space
));
1097 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
1098 isl_space_copy(space
));
1099 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1100 return pet_expr_free(expr
);
1105 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1106 * in "space" by a value equal to the corresponding parameter.
1108 struct pet_expr
*pet_expr_detect_parameter_accesses(struct pet_expr
*expr
,
1109 __isl_take isl_space
*space
)
1111 expr
= pet_expr_map_access(expr
, &detect_parameter_accesses
, space
);
1112 isl_space_free(space
);
1116 /* Add a reference identifier to access expression "expr".
1117 * "user" points to an integer that contains the sequence number
1118 * of the next reference.
1120 static struct pet_expr
*access_add_ref_id(struct pet_expr
*expr
, void *user
)
1129 ctx
= isl_map_get_ctx(expr
->acc
.access
);
1130 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1131 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1132 if (!expr
->acc
.ref_id
)
1133 return pet_expr_free(expr
);
1138 struct pet_expr
*pet_expr_add_ref_ids(struct pet_expr
*expr
, int *n_ref
)
1140 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1143 /* Reset the user pointer on all parameter and tuple ids in
1144 * the access relation and the index expressions
1145 * of the access expression "expr".
1147 static struct pet_expr
*access_anonymize(struct pet_expr
*expr
, void *user
)
1149 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1150 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1151 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1152 return pet_expr_free(expr
);
1157 struct pet_expr
*pet_expr_anonymize(struct pet_expr
*expr
)
1159 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1162 /* Data used in access_gist() callback.
1164 struct pet_access_gist_data
{
1166 isl_union_map
*value_bounds
;
1169 /* Given an expression "expr" of type pet_expr_access, compute
1170 * the gist of the associated access relation and index expression
1171 * with respect to data->domain and the bounds on the values of the arguments
1172 * of the expression.
1174 static struct pet_expr
*access_gist(struct pet_expr
*expr
, void *user
)
1176 struct pet_access_gist_data
*data
= user
;
1179 domain
= isl_set_copy(data
->domain
);
1180 if (expr
->n_arg
> 0)
1181 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1182 data
->value_bounds
);
1184 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1185 isl_set_copy(domain
));
1186 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1187 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1188 return pet_expr_free(expr
);
1193 struct pet_expr
*pet_expr_gist(struct pet_expr
*expr
,
1194 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1196 struct pet_access_gist_data data
= { context
, value_bounds
};
1198 return pet_expr_map_access(expr
, &access_gist
, &data
);
1201 /* Tag the access relation "access" with "id".
1202 * That is, insert the id as the range of a wrapped relation
1203 * in the domain of "access".
1205 * If "access" is of the form
1209 * then the result is of the form
1211 * [D[i] -> id[]] -> A[a]
1213 __isl_give isl_map
*pet_expr_tag_access(struct pet_expr
*expr
,
1214 __isl_take isl_map
*access
)
1220 id
= isl_id_copy(expr
->acc
.ref_id
);
1221 space
= isl_space_range(isl_map_get_space(access
));
1222 space
= isl_space_from_range(space
);
1223 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
1224 add_tag
= isl_map_universe(space
);
1225 access
= isl_map_domain_product(access
, add_tag
);
1230 /* Return the relation mapping domain iterations to all possibly
1231 * accessed data elements.
1232 * In particular, take the access relation and project out the values
1233 * of the arguments, if any.
1235 __isl_give isl_map
*pet_expr_access_get_may_access(struct pet_expr
*expr
)
1243 if (expr
->type
!= pet_expr_access
)
1246 access
= isl_map_copy(expr
->acc
.access
);
1247 if (expr
->n_arg
== 0)
1250 space
= isl_space_domain(isl_map_get_space(access
));
1251 map
= isl_map_universe(isl_space_unwrap(space
));
1252 map
= isl_map_domain_map(map
);
1253 access
= isl_map_apply_domain(access
, map
);
1258 /* Return the relation mapping domain iterations to all possibly
1259 * accessed data elements, with its domain tagged with the reference
1262 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
1263 struct pet_expr
*expr
)
1270 access
= pet_expr_access_get_may_access(expr
);
1271 access
= pet_expr_tag_access(expr
, access
);
1276 void pet_expr_dump_with_indent(struct pet_expr
*expr
, int indent
)
1283 fprintf(stderr
, "%*s", indent
, "");
1285 switch (expr
->type
) {
1286 case pet_expr_double
:
1287 fprintf(stderr
, "%s\n", expr
->d
.s
);
1290 isl_val_dump(expr
->i
);
1292 case pet_expr_access
:
1293 if (expr
->acc
.ref_id
) {
1294 isl_id_dump(expr
->acc
.ref_id
);
1295 fprintf(stderr
, "%*s", indent
, "");
1297 isl_map_dump(expr
->acc
.access
);
1298 fprintf(stderr
, "%*s", indent
, "");
1299 isl_multi_pw_aff_dump(expr
->acc
.index
);
1300 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
1301 "", expr
->acc
.read
);
1302 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
1303 "", expr
->acc
.write
);
1304 for (i
= 0; i
< expr
->n_arg
; ++i
)
1305 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1308 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
1309 for (i
= 0; i
< expr
->n_arg
; ++i
)
1310 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1313 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
1314 for (i
= 0; i
< expr
->n_arg
; ++i
)
1315 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1318 fprintf(stderr
, "(%s)\n", expr
->type_name
);
1319 for (i
= 0; i
< expr
->n_arg
; ++i
)
1320 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
1325 void pet_expr_dump(struct pet_expr
*expr
)
1327 pet_expr_dump_with_indent(expr
, 0);