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
42 #include "value_bounds.h"
44 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
46 static char *type_str
[] = {
47 [pet_expr_access
] = "access",
48 [pet_expr_call
] = "call",
49 [pet_expr_cast
] = "cast",
50 [pet_expr_double
] = "double",
51 [pet_expr_int
] = "int",
55 static char *op_str
[] = {
56 [pet_op_add_assign
] = "+=",
57 [pet_op_sub_assign
] = "-=",
58 [pet_op_mul_assign
] = "*=",
59 [pet_op_div_assign
] = "/=",
60 [pet_op_assign
] = "=",
75 [pet_op_post_inc
] = "++",
76 [pet_op_post_dec
] = "--",
77 [pet_op_pre_inc
] = "++",
78 [pet_op_pre_dec
] = "--",
79 [pet_op_address_of
] = "&",
88 [pet_op_assume
] = "assume",
89 [pet_op_kill
] = "kill"
92 const char *pet_op_str(enum pet_op_type op
)
97 int pet_op_is_inc_dec(enum pet_op_type op
)
99 return op
== pet_op_post_inc
|| op
== pet_op_post_dec
||
100 op
== pet_op_pre_inc
|| op
== pet_op_pre_dec
;
103 const char *pet_type_str(enum pet_expr_type type
)
105 return type_str
[type
];
108 enum pet_op_type
pet_str_op(const char *str
)
112 for (i
= 0; i
< ARRAY_SIZE(op_str
); ++i
)
113 if (!strcmp(op_str
[i
], str
))
119 enum pet_expr_type
pet_str_type(const char *str
)
123 for (i
= 0; i
< ARRAY_SIZE(type_str
); ++i
)
124 if (!strcmp(type_str
[i
], str
))
130 /* Construct a pet_expr of the given type.
132 __isl_give pet_expr
*pet_expr_alloc(isl_ctx
*ctx
, enum pet_expr_type type
)
136 expr
= isl_calloc_type(ctx
, struct pet_expr
);
148 /* Construct an access pet_expr from an access relation and an index expression.
149 * By default, it is considered to be a read access.
151 __isl_give pet_expr
*pet_expr_from_access_and_index( __isl_take isl_map
*access
,
152 __isl_take isl_multi_pw_aff
*index
)
154 isl_ctx
*ctx
= isl_map_get_ctx(access
);
157 if (!index
|| !access
)
159 expr
= pet_expr_alloc(ctx
, pet_expr_access
);
163 expr
->acc
.access
= access
;
164 expr
->acc
.index
= index
;
170 isl_map_free(access
);
171 isl_multi_pw_aff_free(index
);
175 /* Construct an access pet_expr from an index expression.
176 * By default, the access is considered to be a read access.
178 __isl_give pet_expr
*pet_expr_from_index(__isl_take isl_multi_pw_aff
*index
)
182 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
183 return pet_expr_from_access_and_index(access
, index
);
186 /* Extend the range of "access" with "n" dimensions, retaining
187 * the tuple identifier on this range.
189 * If "access" represents a member access, then extend the range
192 static __isl_give isl_map
*extend_range(__isl_take isl_map
*access
, int n
)
196 id
= isl_map_get_tuple_id(access
, isl_dim_out
);
198 if (!isl_map_range_is_wrapping(access
)) {
199 access
= isl_map_add_dims(access
, isl_dim_out
, n
);
203 domain
= isl_map_copy(access
);
204 domain
= isl_map_range_factor_domain(domain
);
205 access
= isl_map_range_factor_range(access
);
206 access
= extend_range(access
, n
);
207 access
= isl_map_range_product(domain
, access
);
210 access
= isl_map_set_tuple_id(access
, isl_dim_out
, id
);
215 /* Construct an access pet_expr from the number of bits needed to
216 * represent the type of the expression (may be zero if unknown or
217 * if the type is not an integer) an index expression and
218 * the depth of the accessed array.
219 * By default, the access is considered to be a read access.
221 * If the number of indices is smaller than the depth of the array,
222 * then we assume that all elements of the remaining dimensions
225 __isl_give pet_expr
*pet_expr_from_index_and_depth(int type_size
,
226 __isl_take isl_multi_pw_aff
*index
, int depth
)
232 access
= isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index
));
235 dim
= isl_map_dim(access
, isl_dim_out
);
237 isl_die(isl_map_get_ctx(access
), isl_error_internal
,
238 "number of indices greater than depth",
239 access
= isl_map_free(access
));
242 access
= extend_range(access
, depth
- dim
);
244 expr
= pet_expr_from_access_and_index(access
, index
);
248 expr
->type_size
= type_size
;
252 isl_multi_pw_aff_free(index
);
256 /* Construct a pet_expr that kills the elements specified by
257 * the index expression "index" and the access relation "access".
259 __isl_give pet_expr
*pet_expr_kill_from_access_and_index(
260 __isl_take isl_map
*access
, __isl_take isl_multi_pw_aff
*index
)
264 if (!access
|| !index
)
267 expr
= pet_expr_from_access_and_index(access
, index
);
268 expr
= pet_expr_access_set_read(expr
, 0);
269 return pet_expr_new_unary(pet_op_kill
, expr
);
271 isl_map_free(access
);
272 isl_multi_pw_aff_free(index
);
276 /* Construct a unary pet_expr that performs "op" on "arg".
278 __isl_give pet_expr
*pet_expr_new_unary(enum pet_op_type op
,
279 __isl_take pet_expr
*arg
)
286 ctx
= pet_expr_get_ctx(arg
);
287 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
288 expr
= pet_expr_set_n_arg(expr
, 1);
293 expr
->args
[pet_un_arg
] = arg
;
301 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs",
302 * where the result is represented using a type of "type_size" bits
303 * (may be zero if unknown or if the type is not an integer).
305 __isl_give pet_expr
*pet_expr_new_binary(int type_size
, enum pet_op_type op
,
306 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
313 ctx
= pet_expr_get_ctx(lhs
);
314 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
315 expr
= pet_expr_set_n_arg(expr
, 2);
320 expr
->type_size
= type_size
;
321 expr
->args
[pet_bin_lhs
] = lhs
;
322 expr
->args
[pet_bin_rhs
] = rhs
;
331 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
333 __isl_give pet_expr
*pet_expr_new_ternary(__isl_take pet_expr
*cond
,
334 __isl_take pet_expr
*lhs
, __isl_take pet_expr
*rhs
)
339 if (!cond
|| !lhs
|| !rhs
)
341 ctx
= pet_expr_get_ctx(cond
);
342 expr
= pet_expr_alloc(ctx
, pet_expr_op
);
343 expr
= pet_expr_set_n_arg(expr
, 3);
347 expr
->op
= pet_op_cond
;
348 expr
->args
[pet_ter_cond
] = cond
;
349 expr
->args
[pet_ter_true
] = lhs
;
350 expr
->args
[pet_ter_false
] = rhs
;
360 /* Construct a call pet_expr that calls function "name" with "n_arg"
361 * arguments. The caller is responsible for filling in the arguments.
363 __isl_give pet_expr
*pet_expr_new_call(isl_ctx
*ctx
, const char *name
,
368 expr
= pet_expr_alloc(ctx
, pet_expr_call
);
369 expr
= pet_expr_set_n_arg(expr
, n_arg
);
373 expr
->name
= strdup(name
);
375 return pet_expr_free(expr
);
380 /* Construct a pet_expr that represents the cast of "arg" to "type_name".
382 __isl_give pet_expr
*pet_expr_new_cast(const char *type_name
,
383 __isl_take pet_expr
*arg
)
391 ctx
= pet_expr_get_ctx(arg
);
392 expr
= pet_expr_alloc(ctx
, pet_expr_cast
);
393 expr
= pet_expr_set_n_arg(expr
, 1);
397 expr
->type_name
= strdup(type_name
);
398 if (!expr
->type_name
)
410 /* Construct a pet_expr that represents the double "d".
412 __isl_give pet_expr
*pet_expr_new_double(isl_ctx
*ctx
,
413 double val
, const char *s
)
417 expr
= pet_expr_alloc(ctx
, pet_expr_double
);
422 expr
->d
.s
= strdup(s
);
424 return pet_expr_free(expr
);
429 /* Construct a pet_expr that represents the integer value "v".
431 __isl_give pet_expr
*pet_expr_new_int(__isl_take isl_val
*v
)
439 ctx
= isl_val_get_ctx(v
);
440 expr
= pet_expr_alloc(ctx
, pet_expr_int
);
452 static __isl_give pet_expr
*pet_expr_dup(__isl_keep pet_expr
*expr
)
460 dup
= pet_expr_alloc(expr
->ctx
, expr
->type
);
461 dup
= pet_expr_set_type_size(dup
, expr
->type_size
);
462 dup
= pet_expr_set_n_arg(dup
, expr
->n_arg
);
463 for (i
= 0; i
< expr
->n_arg
; ++i
)
464 dup
= pet_expr_set_arg(dup
, i
, pet_expr_copy(expr
->args
[i
]));
466 switch (expr
->type
) {
467 case pet_expr_access
:
468 if (expr
->acc
.ref_id
)
469 dup
= pet_expr_access_set_ref_id(dup
,
470 isl_id_copy(expr
->acc
.ref_id
));
471 dup
= pet_expr_access_set_access(dup
,
472 isl_map_copy(expr
->acc
.access
));
473 dup
= pet_expr_access_set_index(dup
,
474 isl_multi_pw_aff_copy(expr
->acc
.index
));
475 dup
= pet_expr_access_set_read(dup
, expr
->acc
.read
);
476 dup
= pet_expr_access_set_write(dup
, expr
->acc
.write
);
479 dup
= pet_expr_call_set_name(dup
, expr
->name
);
482 dup
= pet_expr_cast_set_type_name(dup
, expr
->type_name
);
484 case pet_expr_double
:
485 dup
= pet_expr_double_set(dup
, expr
->d
.val
, expr
->d
.s
);
488 dup
= pet_expr_int_set_val(dup
, isl_val_copy(expr
->i
));
491 dup
= pet_expr_op_set_type(dup
, expr
->op
);
494 dup
= pet_expr_free(dup
);
501 __isl_give pet_expr
*pet_expr_cow(__isl_take pet_expr
*expr
)
509 return pet_expr_dup(expr
);
512 __isl_null pet_expr
*pet_expr_free(__isl_take pet_expr
*expr
)
521 for (i
= 0; i
< expr
->n_arg
; ++i
)
522 pet_expr_free(expr
->args
[i
]);
525 switch (expr
->type
) {
526 case pet_expr_access
:
527 isl_id_free(expr
->acc
.ref_id
);
528 isl_map_free(expr
->acc
.access
);
529 isl_multi_pw_aff_free(expr
->acc
.index
);
535 free(expr
->type_name
);
537 case pet_expr_double
:
541 isl_val_free(expr
->i
);
548 isl_ctx_deref(expr
->ctx
);
553 /* Return an additional reference to "expr".
555 __isl_give pet_expr
*pet_expr_copy(__isl_keep pet_expr
*expr
)
564 /* Return the isl_ctx in which "expr" was created.
566 isl_ctx
*pet_expr_get_ctx(__isl_keep pet_expr
*expr
)
568 return expr
? expr
->ctx
: NULL
;
571 /* Return the type of "expr".
573 enum pet_expr_type
pet_expr_get_type(__isl_keep pet_expr
*expr
)
576 return pet_expr_error
;
580 /* Return the number of arguments of "expr".
582 int pet_expr_get_n_arg(__isl_keep pet_expr
*expr
)
590 /* Set the number of arguments of "expr" to "n".
592 * If "expr" originally had more arguments, then remove the extra arguments.
593 * If "expr" originally had fewer arguments, then create space for
594 * the extra arguments ans initialize them to NULL.
596 __isl_give pet_expr
*pet_expr_set_n_arg(__isl_take pet_expr
*expr
, int n
)
603 if (expr
->n_arg
== n
)
605 expr
= pet_expr_cow(expr
);
609 if (n
< expr
->n_arg
) {
610 for (i
= n
; i
< expr
->n_arg
; ++i
)
611 pet_expr_free(expr
->args
[i
]);
616 args
= isl_realloc_array(expr
->ctx
, expr
->args
, pet_expr
*, n
);
618 return pet_expr_free(expr
);
620 for (i
= expr
->n_arg
; i
< n
; ++i
)
621 expr
->args
[i
] = NULL
;
627 /* Return the argument of "expr" at position "pos".
629 __isl_give pet_expr
*pet_expr_get_arg(__isl_keep pet_expr
*expr
, int pos
)
633 if (pos
< 0 || pos
>= expr
->n_arg
)
634 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
635 "position out of bounds", return NULL
);
637 return pet_expr_copy(expr
->args
[pos
]);
640 /* Replace the argument of "expr" at position "pos" by "arg".
642 __isl_give pet_expr
*pet_expr_set_arg(__isl_take pet_expr
*expr
, int pos
,
643 __isl_take pet_expr
*arg
)
647 if (pos
< 0 || pos
>= expr
->n_arg
)
648 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
649 "position out of bounds", goto error
);
650 if (expr
->args
[pos
] == arg
) {
655 expr
= pet_expr_cow(expr
);
659 pet_expr_free(expr
->args
[pos
]);
660 expr
->args
[pos
] = arg
;
669 /* Does "expr" perform a comparison operation?
671 int pet_expr_is_comparison(__isl_keep pet_expr
*expr
)
675 if (expr
->type
!= pet_expr_op
)
690 /* Does "expr" perform a boolean operation?
692 int pet_expr_is_boolean(__isl_keep pet_expr
*expr
)
696 if (expr
->type
!= pet_expr_op
)
708 /* Does "expr" perform a min operation?
710 int pet_expr_is_min(__isl_keep pet_expr
*expr
)
714 if (expr
->type
!= pet_expr_call
)
716 if (expr
->n_arg
!= 2)
718 if (strcmp(expr
->name
, "min") != 0)
723 /* Does "expr" perform a max operation?
725 int pet_expr_is_max(__isl_keep pet_expr
*expr
)
729 if (expr
->type
!= pet_expr_call
)
731 if (expr
->n_arg
!= 2)
733 if (strcmp(expr
->name
, "max") != 0)
738 /* Does "expr" represent an access to an unnamed space, i.e.,
739 * does it represent an affine expression?
741 int pet_expr_is_affine(__isl_keep pet_expr
*expr
)
747 if (expr
->type
!= pet_expr_access
)
750 has_id
= isl_map_has_tuple_id(expr
->acc
.access
, isl_dim_out
);
757 /* Does "expr" represent an access to a scalar, i.e., a zero-dimensional array,
758 * not part of any struct?
760 int pet_expr_is_scalar_access(__isl_keep pet_expr
*expr
)
764 if (expr
->type
!= pet_expr_access
)
766 if (isl_map_range_is_wrapping(expr
->acc
.access
))
769 return isl_map_dim(expr
->acc
.access
, isl_dim_out
) == 0;
772 /* Return 1 if the two pet_exprs are equivalent.
774 int pet_expr_is_equal(__isl_keep pet_expr
*expr1
, __isl_keep pet_expr
*expr2
)
778 if (!expr1
|| !expr2
)
781 if (expr1
->type
!= expr2
->type
)
783 if (expr1
->n_arg
!= expr2
->n_arg
)
785 for (i
= 0; i
< expr1
->n_arg
; ++i
)
786 if (!pet_expr_is_equal(expr1
->args
[i
], expr2
->args
[i
]))
788 switch (expr1
->type
) {
791 case pet_expr_double
:
792 if (strcmp(expr1
->d
.s
, expr2
->d
.s
))
794 if (expr1
->d
.val
!= expr2
->d
.val
)
798 if (!isl_val_eq(expr1
->i
, expr2
->i
))
801 case pet_expr_access
:
802 if (expr1
->acc
.read
!= expr2
->acc
.read
)
804 if (expr1
->acc
.write
!= expr2
->acc
.write
)
806 if (expr1
->acc
.ref_id
!= expr2
->acc
.ref_id
)
808 if (!expr1
->acc
.access
|| !expr2
->acc
.access
)
810 if (!isl_map_is_equal(expr1
->acc
.access
, expr2
->acc
.access
))
812 if (!expr1
->acc
.index
|| !expr2
->acc
.index
)
814 if (!isl_multi_pw_aff_plain_is_equal(expr1
->acc
.index
,
819 if (expr1
->op
!= expr2
->op
)
823 if (strcmp(expr1
->name
, expr2
->name
))
827 if (strcmp(expr1
->type_name
, expr2
->type_name
))
835 /* Does the access expression "expr" read the accessed elements?
837 int pet_expr_access_is_read(__isl_keep pet_expr
*expr
)
841 if (expr
->type
!= pet_expr_access
)
842 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
843 "not an access expression", return -1);
845 return expr
->acc
.read
;
848 /* Does the access expression "expr" write to the accessed elements?
850 int pet_expr_access_is_write(__isl_keep pet_expr
*expr
)
854 if (expr
->type
!= pet_expr_access
)
855 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
856 "not an access expression", return -1);
858 return expr
->acc
.write
;
861 /* Return the identifier of the array accessed by "expr".
863 * If "expr" represents a member access, then return the identifier
864 * of the outer structure array.
866 __isl_give isl_id
*pet_expr_access_get_id(__isl_keep pet_expr
*expr
)
870 if (expr
->type
!= pet_expr_access
)
871 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
872 "not an access expression", return NULL
);
874 if (isl_map_range_is_wrapping(expr
->acc
.access
)) {
878 space
= isl_map_get_space(expr
->acc
.access
);
879 space
= isl_space_range(space
);
880 while (space
&& isl_space_is_wrapping(space
))
881 space
= isl_space_domain(isl_space_unwrap(space
));
882 id
= isl_space_get_tuple_id(space
, isl_dim_set
);
883 isl_space_free(space
);
888 return isl_map_get_tuple_id(expr
->acc
.access
, isl_dim_out
);
891 /* Return the parameter space of "expr".
893 __isl_give isl_space
*pet_expr_access_get_parameter_space(
894 __isl_keep pet_expr
*expr
)
900 if (expr
->type
!= pet_expr_access
)
901 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
902 "not an access expression", return NULL
);
904 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
905 space
= isl_space_params(space
);
910 /* Return the space of the data accessed by "expr".
912 __isl_give isl_space
*pet_expr_access_get_data_space(__isl_keep pet_expr
*expr
)
918 if (expr
->type
!= pet_expr_access
)
919 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
920 "not an access expression", return NULL
);
922 space
= isl_multi_pw_aff_get_space(expr
->acc
.index
);
923 space
= isl_space_range(space
);
928 /* Modify all expressions of type pet_expr_access in "expr"
929 * by calling "fn" on them.
931 __isl_give pet_expr
*pet_expr_map_access(__isl_take pet_expr
*expr
,
932 __isl_give pet_expr
*(*fn
)(__isl_take pet_expr
*expr
, void *user
),
937 n
= pet_expr_get_n_arg(expr
);
938 for (i
= 0; i
< n
; ++i
) {
939 pet_expr
*arg
= pet_expr_get_arg(expr
, i
);
940 arg
= pet_expr_map_access(arg
, fn
, user
);
941 expr
= pet_expr_set_arg(expr
, i
, arg
);
947 if (expr
->type
== pet_expr_access
)
948 expr
= fn(expr
, user
);
953 /* Call "fn" on each of the subexpressions of "expr" of type "type".
955 * Return -1 on error (where fn returning a negative value is treated as
957 * Otherwise return 0.
959 int pet_expr_foreach_expr_of_type(__isl_keep pet_expr
*expr
,
960 enum pet_expr_type type
,
961 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
968 for (i
= 0; i
< expr
->n_arg
; ++i
)
969 if (pet_expr_foreach_expr_of_type(expr
->args
[i
],
973 if (expr
->type
== type
)
974 return fn(expr
, user
);
979 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
981 * Return -1 on error (where fn returning a negative value is treated as
983 * Otherwise return 0.
985 int pet_expr_foreach_access_expr(__isl_keep pet_expr
*expr
,
986 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
988 return pet_expr_foreach_expr_of_type(expr
, pet_expr_access
, fn
, user
);
991 /* Call "fn" on each of the subexpressions of "expr" of type pet_expr_call.
993 * Return -1 on error (where fn returning a negative value is treated as
995 * Otherwise return 0.
997 int pet_expr_foreach_call_expr(__isl_keep pet_expr
*expr
,
998 int (*fn
)(__isl_keep pet_expr
*expr
, void *user
), void *user
)
1000 return pet_expr_foreach_expr_of_type(expr
, pet_expr_call
, fn
, user
);
1003 /* Internal data structure for pet_expr_writes.
1004 * "id" is the identifier that we are looking for.
1005 * "found" is set if we have found the identifier being written to.
1007 struct pet_expr_writes_data
{
1012 /* Given an access expression, check if it writes to data->id.
1013 * If so, set data->found and abort the search.
1015 static int writes(__isl_keep pet_expr
*expr
, void *user
)
1017 struct pet_expr_writes_data
*data
= user
;
1020 if (!expr
->acc
.write
)
1022 if (pet_expr_is_affine(expr
))
1025 write_id
= pet_expr_access_get_id(expr
);
1026 isl_id_free(write_id
);
1031 if (write_id
!= data
->id
)
1038 /* Does expression "expr" write to "id"?
1040 int pet_expr_writes(__isl_keep pet_expr
*expr
, __isl_keep isl_id
*id
)
1042 struct pet_expr_writes_data data
;
1046 if (pet_expr_foreach_access_expr(expr
, &writes
, &data
) < 0 &&
1053 /* Move the "n" dimensions of "src_type" starting at "src_pos" of
1054 * index expression and access relation of "expr"
1055 * to dimensions of "dst_type" at "dst_pos".
1057 __isl_give pet_expr
*pet_expr_access_move_dims(__isl_take pet_expr
*expr
,
1058 enum isl_dim_type dst_type
, unsigned dst_pos
,
1059 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1061 expr
= pet_expr_cow(expr
);
1064 if (expr
->type
!= pet_expr_access
)
1065 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1066 "not an access pet_expr", return pet_expr_free(expr
));
1068 expr
->acc
.access
= isl_map_move_dims(expr
->acc
.access
,
1069 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1070 expr
->acc
.index
= isl_multi_pw_aff_move_dims(expr
->acc
.index
,
1071 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1072 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1073 return pet_expr_free(expr
);
1078 /* Replace the index expression and access relation of "expr"
1079 * by their preimages under the function represented by "ma".
1081 __isl_give pet_expr
*pet_expr_access_pullback_multi_aff(
1082 __isl_take pet_expr
*expr
, __isl_take isl_multi_aff
*ma
)
1084 expr
= pet_expr_cow(expr
);
1087 if (expr
->type
!= pet_expr_access
)
1088 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1089 "not an access pet_expr", goto error
);
1091 expr
->acc
.access
= isl_map_preimage_domain_multi_aff(expr
->acc
.access
,
1092 isl_multi_aff_copy(ma
));
1093 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_aff(expr
->acc
.index
,
1095 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1096 return pet_expr_free(expr
);
1100 isl_multi_aff_free(ma
);
1101 pet_expr_free(expr
);
1105 /* Replace the index expression and access relation of "expr"
1106 * by their preimages under the function represented by "mpa".
1108 __isl_give pet_expr
*pet_expr_access_pullback_multi_pw_aff(
1109 __isl_take pet_expr
*expr
, __isl_take isl_multi_pw_aff
*mpa
)
1111 expr
= pet_expr_cow(expr
);
1114 if (expr
->type
!= pet_expr_access
)
1115 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1116 "not an access pet_expr", goto error
);
1118 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1119 expr
->acc
.access
, isl_multi_pw_aff_copy(mpa
));
1120 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1121 expr
->acc
.index
, mpa
);
1122 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1123 return pet_expr_free(expr
);
1127 isl_multi_pw_aff_free(mpa
);
1128 pet_expr_free(expr
);
1132 /* Return the access relation of access expression "expr".
1134 __isl_give isl_map
*pet_expr_access_get_access(__isl_keep pet_expr
*expr
)
1138 if (expr
->type
!= pet_expr_access
)
1139 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1140 "not an access expression", return NULL
);
1142 return isl_map_copy(expr
->acc
.access
);
1145 /* Return the index expression of access expression "expr".
1147 __isl_give isl_multi_pw_aff
*pet_expr_access_get_index(
1148 __isl_keep pet_expr
*expr
)
1152 if (expr
->type
!= pet_expr_access
)
1153 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1154 "not an access expression", return NULL
);
1156 return isl_multi_pw_aff_copy(expr
->acc
.index
);
1159 /* Align the parameters of expr->acc.index and expr->acc.access.
1161 __isl_give pet_expr
*pet_expr_access_align_params(__isl_take pet_expr
*expr
)
1163 expr
= pet_expr_cow(expr
);
1166 if (expr
->type
!= pet_expr_access
)
1167 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1168 "not an access expression", return pet_expr_free(expr
));
1170 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1171 isl_multi_pw_aff_get_space(expr
->acc
.index
));
1172 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1173 isl_map_get_space(expr
->acc
.access
));
1174 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1175 return pet_expr_free(expr
);
1180 /* Add extra conditions on the parameters to all access relations in "expr".
1182 * The conditions are not added to the index expression. Instead, they
1183 * are used to try and simplify the index expression.
1185 __isl_give pet_expr
*pet_expr_restrict(__isl_take pet_expr
*expr
,
1186 __isl_take isl_set
*cond
)
1190 expr
= pet_expr_cow(expr
);
1194 for (i
= 0; i
< expr
->n_arg
; ++i
) {
1195 expr
->args
[i
] = pet_expr_restrict(expr
->args
[i
],
1196 isl_set_copy(cond
));
1201 if (expr
->type
== pet_expr_access
) {
1202 expr
->acc
.access
= isl_map_intersect_params(expr
->acc
.access
,
1203 isl_set_copy(cond
));
1204 expr
->acc
.index
= isl_multi_pw_aff_gist_params(
1205 expr
->acc
.index
, isl_set_copy(cond
));
1206 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1214 return pet_expr_free(expr
);
1217 /* Modify the access relation and index expression
1218 * of the given access expression
1219 * based on the given iteration space transformation.
1220 * In particular, precompose the access relation and index expression
1221 * with the update function.
1223 * If the access has any arguments then the domain of the access relation
1224 * is a wrapped mapping from the iteration space to the space of
1225 * argument values. We only need to change the domain of this wrapped
1226 * mapping, so we extend the input transformation with an identity mapping
1227 * on the space of argument values.
1229 __isl_give pet_expr
*pet_expr_access_update_domain(__isl_take pet_expr
*expr
,
1230 __isl_keep isl_multi_pw_aff
*update
)
1234 expr
= pet_expr_cow(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 pet_expr_free(expr
));
1241 update
= isl_multi_pw_aff_copy(update
);
1243 space
= isl_map_get_space(expr
->acc
.access
);
1244 space
= isl_space_domain(space
);
1245 if (!isl_space_is_wrapping(space
))
1246 isl_space_free(space
);
1248 isl_multi_pw_aff
*id
;
1249 space
= isl_space_unwrap(space
);
1250 space
= isl_space_range(space
);
1251 space
= isl_space_map_from_set(space
);
1252 id
= isl_multi_pw_aff_identity(space
);
1253 update
= isl_multi_pw_aff_product(update
, id
);
1256 expr
->acc
.access
= isl_map_preimage_domain_multi_pw_aff(
1258 isl_multi_pw_aff_copy(update
));
1259 expr
->acc
.index
= isl_multi_pw_aff_pullback_multi_pw_aff(
1260 expr
->acc
.index
, update
);
1261 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1262 return pet_expr_free(expr
);
1267 static __isl_give pet_expr
*update_domain(__isl_take pet_expr
*expr
, void *user
)
1269 isl_multi_pw_aff
*update
= user
;
1271 return pet_expr_access_update_domain(expr
, update
);
1274 /* Modify all access relations in "expr" by precomposing them with
1275 * the given iteration space transformation.
1277 __isl_give pet_expr
*pet_expr_update_domain(__isl_take pet_expr
*expr
,
1278 __isl_take isl_multi_pw_aff
*update
)
1280 expr
= pet_expr_map_access(expr
, &update_domain
, update
);
1281 isl_multi_pw_aff_free(update
);
1285 /* Add all parameters in "space" to the access relation and index expression
1288 static __isl_give pet_expr
*align_params(__isl_take pet_expr
*expr
, void *user
)
1290 isl_space
*space
= user
;
1292 expr
= pet_expr_cow(expr
);
1295 if (expr
->type
!= pet_expr_access
)
1296 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1297 "not an access expression", return pet_expr_free(expr
));
1299 expr
->acc
.access
= isl_map_align_params(expr
->acc
.access
,
1300 isl_space_copy(space
));
1301 expr
->acc
.index
= isl_multi_pw_aff_align_params(expr
->acc
.index
,
1302 isl_space_copy(space
));
1303 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1304 return pet_expr_free(expr
);
1309 /* Add all parameters in "space" to all access relations and index expressions
1312 __isl_give pet_expr
*pet_expr_align_params(__isl_take pet_expr
*expr
,
1313 __isl_take isl_space
*space
)
1315 expr
= pet_expr_map_access(expr
, &align_params
, space
);
1316 isl_space_free(space
);
1320 /* Insert an argument expression corresponding to "test" in front
1321 * of the list of arguments described by *n_arg and *args.
1323 static __isl_give pet_expr
*insert_access_arg(__isl_take pet_expr
*expr
,
1324 __isl_keep isl_multi_pw_aff
*test
)
1327 isl_ctx
*ctx
= isl_multi_pw_aff_get_ctx(test
);
1330 return pet_expr_free(expr
);
1331 expr
= pet_expr_cow(expr
);
1336 expr
->args
= isl_calloc_array(ctx
, pet_expr
*, 1);
1338 return pet_expr_free(expr
);
1341 ext
= isl_calloc_array(ctx
, pet_expr
*, 1 + expr
->n_arg
);
1343 return pet_expr_free(expr
);
1344 for (i
= 0; i
< expr
->n_arg
; ++i
)
1345 ext
[1 + i
] = expr
->args
[i
];
1350 expr
->args
[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test
));
1352 return pet_expr_free(expr
);
1357 /* Make the expression "expr" depend on the value of "test"
1358 * being equal to "satisfied".
1360 * If "test" is an affine expression, we simply add the conditions
1361 * on the expression having the value "satisfied" to all access relations
1362 * and index expressions.
1364 * Otherwise, we add a filter to "expr" (which is then assumed to be
1365 * an access expression) corresponding to "test" being equal to "satisfied".
1367 __isl_give pet_expr
*pet_expr_filter(__isl_take pet_expr
*expr
,
1368 __isl_take isl_multi_pw_aff
*test
, int satisfied
)
1373 isl_pw_multi_aff
*pma
;
1375 expr
= pet_expr_cow(expr
);
1379 if (!isl_multi_pw_aff_has_tuple_id(test
, isl_dim_out
)) {
1383 pa
= isl_multi_pw_aff_get_pw_aff(test
, 0);
1384 isl_multi_pw_aff_free(test
);
1386 cond
= isl_pw_aff_non_zero_set(pa
);
1388 cond
= isl_pw_aff_zero_set(pa
);
1389 return pet_expr_restrict(expr
, isl_set_params(cond
));
1392 ctx
= isl_multi_pw_aff_get_ctx(test
);
1393 if (expr
->type
!= pet_expr_access
)
1394 isl_die(ctx
, isl_error_invalid
,
1395 "can only filter access expressions", goto error
);
1397 space
= isl_space_domain(isl_map_get_space(expr
->acc
.access
));
1398 id
= isl_multi_pw_aff_get_tuple_id(test
, isl_dim_out
);
1399 pma
= pet_filter_insert_pma(space
, id
, satisfied
);
1401 expr
->acc
.access
= isl_map_preimage_domain_pw_multi_aff(
1403 isl_pw_multi_aff_copy(pma
));
1404 expr
->acc
.index
= isl_multi_pw_aff_pullback_pw_multi_aff(
1405 expr
->acc
.index
, pma
);
1406 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1409 expr
= insert_access_arg(expr
, test
);
1411 isl_multi_pw_aff_free(test
);
1414 isl_multi_pw_aff_free(test
);
1415 return pet_expr_free(expr
);
1418 /* Check if the given index expression accesses a (0D) array that corresponds
1419 * to one of the parameters in "space". If so, replace the array access
1420 * by an access to the set of integers with as index (and value)
1423 static __isl_give isl_multi_pw_aff
*index_detect_parameter(
1424 __isl_take isl_multi_pw_aff
*index
, __isl_take isl_space
*space
)
1426 isl_local_space
*ls
;
1427 isl_id
*array_id
= NULL
;
1431 if (isl_multi_pw_aff_has_tuple_id(index
, isl_dim_out
)) {
1432 array_id
= isl_multi_pw_aff_get_tuple_id(index
, isl_dim_out
);
1433 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1435 isl_space_free(space
);
1438 isl_id_free(array_id
);
1442 space
= isl_multi_pw_aff_get_domain_space(index
);
1443 isl_multi_pw_aff_free(index
);
1445 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1447 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
1448 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, array_id
);
1451 isl_id_free(array_id
);
1453 ls
= isl_local_space_from_space(space
);
1454 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
1455 index
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
1460 /* Check if the given access relation accesses a (0D) array that corresponds
1461 * to one of the parameters in "space". If so, replace the array access
1462 * by an access to the set of integers with as index (and value)
1465 static __isl_give isl_map
*access_detect_parameter(__isl_take isl_map
*access
,
1466 __isl_take isl_space
*space
)
1468 isl_id
*array_id
= NULL
;
1471 if (isl_map_has_tuple_id(access
, isl_dim_out
)) {
1472 array_id
= isl_map_get_tuple_id(access
, isl_dim_out
);
1473 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, array_id
);
1475 isl_space_free(space
);
1478 isl_id_free(array_id
);
1482 pos
= isl_map_find_dim_by_id(access
, isl_dim_param
, array_id
);
1484 access
= isl_map_insert_dims(access
, isl_dim_param
, 0, 1);
1485 access
= isl_map_set_dim_id(access
, isl_dim_param
, 0, array_id
);
1488 isl_id_free(array_id
);
1490 access
= isl_map_insert_dims(access
, isl_dim_out
, 0, 1);
1491 access
= isl_map_equate(access
, isl_dim_param
, pos
, isl_dim_out
, 0);
1496 /* If "expr" accesses a (0D) array that corresponds to one of the parameters
1497 * in "space" then replace it by a value equal to the corresponding parameter.
1499 static __isl_give pet_expr
*detect_parameter_accesses(__isl_take pet_expr
*expr
,
1502 isl_space
*space
= user
;
1504 expr
= pet_expr_cow(expr
);
1507 if (expr
->type
!= pet_expr_access
)
1508 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1509 "not an access expression", return pet_expr_free(expr
));
1511 expr
->acc
.access
= access_detect_parameter(expr
->acc
.access
,
1512 isl_space_copy(space
));
1513 expr
->acc
.index
= index_detect_parameter(expr
->acc
.index
,
1514 isl_space_copy(space
));
1515 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1516 return pet_expr_free(expr
);
1521 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1522 * in "space" by a value equal to the corresponding parameter.
1524 __isl_give pet_expr
*pet_expr_detect_parameter_accesses(
1525 __isl_take pet_expr
*expr
, __isl_take isl_space
*space
)
1527 expr
= pet_expr_map_access(expr
, &detect_parameter_accesses
, space
);
1528 isl_space_free(space
);
1532 /* Add a reference identifier to access expression "expr".
1533 * "user" points to an integer that contains the sequence number
1534 * of the next reference.
1536 static __isl_give pet_expr
*access_add_ref_id(__isl_take pet_expr
*expr
,
1543 expr
= pet_expr_cow(expr
);
1546 if (expr
->type
!= pet_expr_access
)
1547 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1548 "not an access expression", return pet_expr_free(expr
));
1550 ctx
= isl_map_get_ctx(expr
->acc
.access
);
1551 snprintf(name
, sizeof(name
), "__pet_ref_%d", (*n_ref
)++);
1552 expr
->acc
.ref_id
= isl_id_alloc(ctx
, name
, NULL
);
1553 if (!expr
->acc
.ref_id
)
1554 return pet_expr_free(expr
);
1559 __isl_give pet_expr
*pet_expr_add_ref_ids(__isl_take pet_expr
*expr
, int *n_ref
)
1561 return pet_expr_map_access(expr
, &access_add_ref_id
, n_ref
);
1564 /* Reset the user pointer on all parameter and tuple ids in
1565 * the access relation and the index expressions
1566 * of the access expression "expr".
1568 static __isl_give pet_expr
*access_anonymize(__isl_take pet_expr
*expr
,
1571 expr
= pet_expr_cow(expr
);
1574 if (expr
->type
!= pet_expr_access
)
1575 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1576 "not an access expression", return pet_expr_free(expr
));
1578 expr
->acc
.access
= isl_map_reset_user(expr
->acc
.access
);
1579 expr
->acc
.index
= isl_multi_pw_aff_reset_user(expr
->acc
.index
);
1580 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1581 return pet_expr_free(expr
);
1586 __isl_give pet_expr
*pet_expr_anonymize(__isl_take pet_expr
*expr
)
1588 return pet_expr_map_access(expr
, &access_anonymize
, NULL
);
1591 /* Data used in access_gist() callback.
1593 struct pet_access_gist_data
{
1595 isl_union_map
*value_bounds
;
1598 /* Given an expression "expr" of type pet_expr_access, compute
1599 * the gist of the associated access relation and index expression
1600 * with respect to data->domain and the bounds on the values of the arguments
1601 * of the expression.
1603 static __isl_give pet_expr
*access_gist(__isl_take pet_expr
*expr
, void *user
)
1605 struct pet_access_gist_data
*data
= user
;
1608 expr
= pet_expr_cow(expr
);
1611 if (expr
->type
!= pet_expr_access
)
1612 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1613 "not an access expression", return pet_expr_free(expr
));
1615 domain
= isl_set_copy(data
->domain
);
1616 if (expr
->n_arg
> 0)
1617 domain
= pet_value_bounds_apply(domain
, expr
->n_arg
, expr
->args
,
1618 data
->value_bounds
);
1620 expr
->acc
.access
= isl_map_gist_domain(expr
->acc
.access
,
1621 isl_set_copy(domain
));
1622 expr
->acc
.index
= isl_multi_pw_aff_gist(expr
->acc
.index
, domain
);
1623 if (!expr
->acc
.access
|| !expr
->acc
.index
)
1624 return pet_expr_free(expr
);
1629 __isl_give pet_expr
*pet_expr_gist(__isl_take pet_expr
*expr
,
1630 __isl_keep isl_set
*context
, __isl_keep isl_union_map
*value_bounds
)
1632 struct pet_access_gist_data data
= { context
, value_bounds
};
1634 return pet_expr_map_access(expr
, &access_gist
, &data
);
1637 /* Mark "expr" as a read dependening on "read".
1639 __isl_give pet_expr
*pet_expr_access_set_read(__isl_take pet_expr
*expr
,
1643 return pet_expr_free(expr
);
1644 if (expr
->type
!= pet_expr_access
)
1645 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1646 "not an access expression", return pet_expr_free(expr
));
1647 if (expr
->acc
.read
== read
)
1649 expr
= pet_expr_cow(expr
);
1652 expr
->acc
.read
= read
;
1657 /* Mark "expr" as a write dependening on "write".
1659 __isl_give pet_expr
*pet_expr_access_set_write(__isl_take pet_expr
*expr
,
1663 return pet_expr_free(expr
);
1664 if (expr
->type
!= pet_expr_access
)
1665 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1666 "not an access expression", return pet_expr_free(expr
));
1667 if (expr
->acc
.write
== write
)
1669 expr
= pet_expr_cow(expr
);
1672 expr
->acc
.write
= write
;
1677 /* Replace the access relation of "expr" by "access".
1679 __isl_give pet_expr
*pet_expr_access_set_access(__isl_take pet_expr
*expr
,
1680 __isl_take isl_map
*access
)
1682 expr
= pet_expr_cow(expr
);
1683 if (!expr
|| !access
)
1685 if (expr
->type
!= pet_expr_access
)
1686 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1687 "not an access expression", goto error
);
1688 isl_map_free(expr
->acc
.access
);
1689 expr
->acc
.access
= access
;
1693 isl_map_free(access
);
1694 pet_expr_free(expr
);
1698 /* Replace the index expression of "expr" by "index".
1700 __isl_give pet_expr
*pet_expr_access_set_index(__isl_take pet_expr
*expr
,
1701 __isl_take isl_multi_pw_aff
*index
)
1703 expr
= pet_expr_cow(expr
);
1704 if (!expr
|| !index
)
1706 if (expr
->type
!= pet_expr_access
)
1707 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1708 "not an access expression", goto error
);
1709 isl_multi_pw_aff_free(expr
->acc
.index
);
1710 expr
->acc
.index
= index
;
1714 isl_multi_pw_aff_free(index
);
1715 pet_expr_free(expr
);
1719 /* Return the reference identifier of access expression "expr".
1721 __isl_give isl_id
*pet_expr_access_get_ref_id(__isl_keep pet_expr
*expr
)
1725 if (expr
->type
!= pet_expr_access
)
1726 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1727 "not an access expression", return NULL
);
1729 return isl_id_copy(expr
->acc
.ref_id
);
1732 /* Replace the reference identifier of access expression "expr" by "ref_id".
1734 __isl_give pet_expr
*pet_expr_access_set_ref_id(__isl_take pet_expr
*expr
,
1735 __isl_take isl_id
*ref_id
)
1737 expr
= pet_expr_cow(expr
);
1738 if (!expr
|| !ref_id
)
1740 if (expr
->type
!= pet_expr_access
)
1741 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1742 "not an access expression", goto error
);
1743 isl_id_free(expr
->acc
.ref_id
);
1744 expr
->acc
.ref_id
= ref_id
;
1748 isl_id_free(ref_id
);
1749 pet_expr_free(expr
);
1753 /* Tag the access relation "access" with "id".
1754 * That is, insert the id as the range of a wrapped relation
1755 * in the domain of "access".
1757 * If "access" is of the form
1761 * then the result is of the form
1763 * [D[i] -> id[]] -> A[a]
1765 __isl_give isl_map
*pet_expr_tag_access(__isl_keep pet_expr
*expr
,
1766 __isl_take isl_map
*access
)
1772 if (expr
->type
!= pet_expr_access
)
1773 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1774 "not an access expression",
1775 return isl_map_free(access
));
1777 id
= isl_id_copy(expr
->acc
.ref_id
);
1778 space
= isl_space_range(isl_map_get_space(access
));
1779 space
= isl_space_from_range(space
);
1780 space
= isl_space_set_tuple_id(space
, isl_dim_in
, id
);
1781 add_tag
= isl_map_universe(space
);
1782 access
= isl_map_domain_product(access
, add_tag
);
1787 /* Return the relation mapping pairs of domain iterations and argument
1788 * values to the corresponding accessed data elements.
1790 __isl_give isl_map
*pet_expr_access_get_dependent_access(
1791 __isl_keep pet_expr
*expr
)
1795 if (expr
->type
!= pet_expr_access
)
1796 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1797 "not an access expression", return NULL
);
1799 return isl_map_copy(expr
->acc
.access
);
1802 /* Return the relation mapping domain iterations to all possibly
1803 * accessed data elements.
1804 * In particular, take the access relation and project out the values
1805 * of the arguments, if any.
1807 __isl_give isl_map
*pet_expr_access_get_may_access(__isl_keep pet_expr
*expr
)
1815 if (expr
->type
!= pet_expr_access
)
1816 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1817 "not an access expression", return NULL
);
1819 access
= pet_expr_access_get_dependent_access(expr
);
1820 if (expr
->n_arg
== 0)
1823 space
= isl_space_domain(isl_map_get_space(access
));
1824 map
= isl_map_universe(isl_space_unwrap(space
));
1825 map
= isl_map_domain_map(map
);
1826 access
= isl_map_apply_domain(access
, map
);
1831 /* Return a relation mapping domain iterations to definitely
1832 * accessed data elements, assuming the statement containing
1833 * the expression is executed.
1835 * If there are no arguments, then all elements are accessed.
1836 * Otherwise, we conservatively return an empty relation.
1838 __isl_give isl_map
*pet_expr_access_get_must_access(__isl_keep pet_expr
*expr
)
1844 if (expr
->type
!= pet_expr_access
)
1845 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1846 "not an access expression", return NULL
);
1848 if (expr
->n_arg
== 0)
1849 return pet_expr_access_get_dependent_access(expr
);
1851 space
= isl_map_get_space(expr
->acc
.access
);
1852 space
= isl_space_domain_factor_domain(space
);
1854 return isl_map_empty(space
);
1857 /* Return the relation mapping domain iterations to all possibly
1858 * accessed data elements, with its domain tagged with the reference
1861 __isl_give isl_map
*pet_expr_access_get_tagged_may_access(
1862 __isl_keep pet_expr
*expr
)
1869 access
= pet_expr_access_get_may_access(expr
);
1870 access
= pet_expr_tag_access(expr
, access
);
1875 /* Return the operation type of operation expression "expr".
1877 enum pet_op_type
pet_expr_op_get_type(__isl_keep pet_expr
*expr
)
1881 if (expr
->type
!= pet_expr_op
)
1882 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1883 "not an operation expression", return pet_op_last
);
1888 /* Replace the operation type of operation expression "expr" by "type".
1890 __isl_give pet_expr
*pet_expr_op_set_type(__isl_take pet_expr
*expr
,
1891 enum pet_op_type type
)
1894 return pet_expr_free(expr
);
1895 if (expr
->type
!= pet_expr_op
)
1896 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1897 "not an operation expression",
1898 return pet_expr_free(expr
));
1899 if (expr
->op
== type
)
1901 expr
= pet_expr_cow(expr
);
1909 /* Return the name of the function called by "expr".
1911 __isl_keep
const char *pet_expr_call_get_name(__isl_keep pet_expr
*expr
)
1915 if (expr
->type
!= pet_expr_call
)
1916 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1917 "not a call expression", return NULL
);
1921 /* Replace the name of the function called by "expr" by "name".
1923 __isl_give pet_expr
*pet_expr_call_set_name(__isl_take pet_expr
*expr
,
1924 __isl_keep
const char *name
)
1926 expr
= pet_expr_cow(expr
);
1928 return pet_expr_free(expr
);
1929 if (expr
->type
!= pet_expr_call
)
1930 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1931 "not a call expression", return pet_expr_free(expr
));
1933 expr
->name
= strdup(name
);
1935 return pet_expr_free(expr
);
1939 /* Replace the type of the cast performed by "expr" by "name".
1941 __isl_give pet_expr
*pet_expr_cast_set_type_name(__isl_take pet_expr
*expr
,
1942 __isl_keep
const char *name
)
1944 expr
= pet_expr_cow(expr
);
1946 return pet_expr_free(expr
);
1947 if (expr
->type
!= pet_expr_cast
)
1948 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1949 "not a cast expression", return pet_expr_free(expr
));
1950 free(expr
->type_name
);
1951 expr
->type_name
= strdup(name
);
1952 if (!expr
->type_name
)
1953 return pet_expr_free(expr
);
1957 /* Return the value of the integer represented by "expr".
1959 __isl_give isl_val
*pet_expr_int_get_val(__isl_keep pet_expr
*expr
)
1963 if (expr
->type
!= pet_expr_int
)
1964 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1965 "not an int expression", return NULL
);
1967 return isl_val_copy(expr
->i
);
1970 /* Replace the value of the integer represented by "expr" by "v".
1972 __isl_give pet_expr
*pet_expr_int_set_val(__isl_take pet_expr
*expr
,
1973 __isl_take isl_val
*v
)
1975 expr
= pet_expr_cow(expr
);
1978 if (expr
->type
!= pet_expr_int
)
1979 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
1980 "not an int expression", goto error
);
1981 isl_val_free(expr
->i
);
1987 pet_expr_free(expr
);
1991 /* Replace the value and string representation of the double
1992 * represented by "expr" by "d" and "s".
1994 __isl_give pet_expr
*pet_expr_double_set(__isl_take pet_expr
*expr
,
1995 double d
, __isl_keep
const char *s
)
1997 expr
= pet_expr_cow(expr
);
1999 return pet_expr_free(expr
);
2000 if (expr
->type
!= pet_expr_double
)
2001 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2002 "not a double expression", return pet_expr_free(expr
));
2005 expr
->d
.s
= strdup(s
);
2007 return pet_expr_free(expr
);
2011 /* Return a string representation of the double expression "expr".
2013 __isl_give
char *pet_expr_double_get_str(__isl_keep pet_expr
*expr
)
2017 if (expr
->type
!= pet_expr_double
)
2018 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2019 "not a double expression", return NULL
);
2020 return strdup(expr
->d
.s
);
2023 /* Return a piecewise affine expression defined on the specified domain
2024 * that represents NaN.
2026 static __isl_give isl_pw_aff
*non_affine(__isl_take isl_space
*space
)
2028 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
2031 /* This function is called when we come across an access that is
2032 * nested in what is supposed to be an affine expression.
2033 * "pc" is the context in which the affine expression is created.
2034 * If nesting is allowed in "pc", we return an affine expression that is
2035 * equal to a new parameter corresponding to this nested access.
2036 * Otherwise, we return NaN.
2038 * Note that we currently don't allow nested accesses themselves
2039 * to contain any nested accesses, so we check if "expr" itself
2040 * involves any nested accesses and return NaN if it does.
2042 * The new parameter is resolved in resolve_nested.
2044 static __isl_give isl_pw_aff
*nested_access(__isl_keep pet_expr
*expr
,
2045 __isl_keep pet_context
*pc
)
2050 isl_local_space
*ls
;
2056 if (!pet_context_allow_nesting(pc
))
2057 return non_affine(pet_context_get_space(pc
));
2059 if (pet_expr_get_type(expr
) != pet_expr_access
)
2060 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2061 "not an access expression", return NULL
);
2063 space
= pet_expr_access_get_parameter_space(expr
);
2064 nested
= pet_nested_any_in_space(space
);
2065 isl_space_free(space
);
2067 return non_affine(pet_context_get_space(pc
));
2069 ctx
= pet_expr_get_ctx(expr
);
2070 id
= pet_nested_pet_expr(pet_expr_copy(expr
));
2071 space
= pet_context_get_space(pc
);
2072 space
= isl_space_insert_dims(space
, isl_dim_param
, 0, 1);
2074 space
= isl_space_set_dim_id(space
, isl_dim_param
, 0, id
);
2075 ls
= isl_local_space_from_space(space
);
2076 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, 0);
2078 return isl_pw_aff_from_aff(aff
);
2081 /* Extract an affine expression from the access pet_expr "expr".
2082 * "pc" is the context in which the affine expression is created.
2084 * If "expr" is actually an affine expression rather than
2085 * a real access, then we return that expression.
2086 * Otherwise, we require that "expr" is of an integral type.
2087 * If not, we return NaN.
2089 * If we are accessing a scalar (i.e., not an array and not a member)
2090 * and if that scalar can be treated as a parameter (because it is
2091 * not assigned a known or unknown value in the relevant part of the AST),
2092 * then we return an affine expression equal to that parameter.
2094 * If the variable has been assigned a known affine expression,
2095 * then we return that expression.
2097 * Otherwise, we return an expression that is equal to a parameter
2098 * representing "expr" (if "allow_nested" is set).
2100 static __isl_give isl_pw_aff
*extract_affine_from_access(
2101 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2106 isl_local_space
*ls
;
2109 if (pet_expr_is_affine(expr
)) {
2111 isl_multi_pw_aff
*mpa
;
2113 mpa
= pet_expr_access_get_index(expr
);
2114 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
2115 isl_multi_pw_aff_free(mpa
);
2119 if (pet_expr_get_type_size(expr
) == 0)
2120 return non_affine(pet_context_get_space(pc
));
2122 if (!pet_expr_is_scalar_access(expr
))
2123 return nested_access(expr
, pc
);
2125 id
= pet_expr_access_get_id(expr
);
2126 if (pet_context_is_assigned(pc
, id
)) {
2129 pa
= pet_context_get_value(pc
, id
);
2132 if (!isl_pw_aff_involves_nan(pa
))
2134 isl_pw_aff_free(pa
);
2135 return nested_access(expr
, pc
);
2138 space
= pet_context_get_space(pc
);
2140 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2144 pos
= isl_space_dim(space
, isl_dim_param
);
2145 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
2146 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
, id
);
2149 ls
= isl_local_space_from_space(space
);
2150 aff
= isl_aff_var_on_domain(ls
, isl_dim_param
, pos
);
2152 return isl_pw_aff_from_aff(aff
);
2155 /* Construct an affine expression from the integer constant "expr".
2156 * "pc" is the context in which the affine expression is created.
2158 static __isl_give isl_pw_aff
*extract_affine_from_int(__isl_keep pet_expr
*expr
,
2159 __isl_keep pet_context
*pc
)
2161 isl_local_space
*ls
;
2167 ls
= isl_local_space_from_space(pet_context_get_space(pc
));
2168 aff
= isl_aff_val_on_domain(ls
, pet_expr_int_get_val(expr
));
2170 return isl_pw_aff_from_aff(aff
);
2173 /* Extract an affine expression from an addition or subtraction operation.
2174 * Return NaN if we are unable to extract an affine expression.
2176 * "pc" is the context in which the affine expression is created.
2178 static __isl_give isl_pw_aff
*extract_affine_add_sub(__isl_keep pet_expr
*expr
,
2179 __isl_keep pet_context
*pc
)
2186 if (expr
->n_arg
!= 2)
2187 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2188 "expecting two arguments", return NULL
);
2190 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2191 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2193 switch (pet_expr_op_get_type(expr
)) {
2195 return isl_pw_aff_add(lhs
, rhs
);
2197 return isl_pw_aff_sub(lhs
, rhs
);
2199 isl_pw_aff_free(lhs
);
2200 isl_pw_aff_free(rhs
);
2201 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2202 "not an addition or subtraction operation",
2208 /* Extract an affine expression from an integer division or a modulo operation.
2209 * Return NaN if we are unable to extract an affine expression.
2211 * "pc" is the context in which the affine expression is created.
2213 * In particular, if "expr" is lhs/rhs, then return
2215 * lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs)
2217 * If "expr" is lhs%rhs, then return
2219 * lhs - rhs * (lhs >= 0 ? floor(lhs/rhs) : ceil(lhs/rhs))
2221 * If the second argument (rhs) is not a (positive) integer constant,
2222 * then we fail to extract an affine expression.
2224 static __isl_give isl_pw_aff
*extract_affine_div_mod(__isl_keep pet_expr
*expr
,
2225 __isl_keep pet_context
*pc
)
2233 if (expr
->n_arg
!= 2)
2234 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2235 "expecting two arguments", return NULL
);
2237 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2239 is_cst
= isl_pw_aff_is_cst(rhs
);
2240 if (is_cst
< 0 || !is_cst
) {
2241 isl_pw_aff_free(rhs
);
2242 return non_affine(pet_context_get_space(pc
));
2245 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2247 switch (pet_expr_op_get_type(expr
)) {
2249 return isl_pw_aff_tdiv_q(lhs
, rhs
);
2251 return isl_pw_aff_tdiv_r(lhs
, rhs
);
2253 isl_pw_aff_free(lhs
);
2254 isl_pw_aff_free(rhs
);
2255 isl_die(pet_expr_get_ctx(expr
), isl_error_internal
,
2256 "not a div or mod operator", return NULL
);
2261 /* Extract an affine expression from a multiplication operation.
2262 * Return NaN if we are unable to extract an affine expression.
2263 * In particular, if neither of the arguments is a (piecewise) constant
2264 * then we return NaN.
2266 * "pc" is the context in which the affine expression is created.
2268 static __isl_give isl_pw_aff
*extract_affine_mul(__isl_keep pet_expr
*expr
,
2269 __isl_keep pet_context
*pc
)
2271 int lhs_cst
, rhs_cst
;
2277 if (expr
->n_arg
!= 2)
2278 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2279 "expecting two arguments", return NULL
);
2281 lhs
= pet_expr_extract_affine(expr
->args
[0], pc
);
2282 rhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2284 lhs_cst
= isl_pw_aff_is_cst(lhs
);
2285 rhs_cst
= isl_pw_aff_is_cst(rhs
);
2286 if (lhs_cst
< 0 || rhs_cst
< 0 || (!lhs_cst
&& !rhs_cst
)) {
2287 isl_pw_aff_free(lhs
);
2288 isl_pw_aff_free(rhs
);
2289 return non_affine(pet_context_get_space(pc
));
2292 return isl_pw_aff_mul(lhs
, rhs
);
2295 /* Extract an affine expression from a negation operation.
2296 * Return NaN if we are unable to extract an affine expression.
2298 * "pc" is the context in which the affine expression is created.
2300 static __isl_give isl_pw_aff
*extract_affine_neg(__isl_keep pet_expr
*expr
,
2301 __isl_keep pet_context
*pc
)
2307 if (expr
->n_arg
!= 1)
2308 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2309 "expecting one argument", return NULL
);
2311 res
= pet_expr_extract_affine(expr
->args
[0], pc
);
2312 return isl_pw_aff_neg(res
);
2315 /* Extract an affine expression from a conditional operation.
2316 * Return NaN if we are unable to extract an affine expression.
2318 * "pc" is the context in which the affine expression is created.
2320 static __isl_give isl_pw_aff
*extract_affine_cond(__isl_keep pet_expr
*expr
,
2321 __isl_keep pet_context
*pc
)
2323 isl_pw_aff
*cond
, *lhs
, *rhs
;
2327 if (expr
->n_arg
!= 3)
2328 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2329 "expecting three arguments", return NULL
);
2331 cond
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2332 lhs
= pet_expr_extract_affine(expr
->args
[1], pc
);
2333 rhs
= pet_expr_extract_affine(expr
->args
[2], pc
);
2335 return isl_pw_aff_cond(cond
, lhs
, rhs
);
2342 static __isl_give isl_pw_aff
*wrap(__isl_take isl_pw_aff
*pwaff
, unsigned width
)
2347 ctx
= isl_pw_aff_get_ctx(pwaff
);
2348 mod
= isl_val_int_from_ui(ctx
, width
);
2349 mod
= isl_val_2exp(mod
);
2351 pwaff
= isl_pw_aff_mod_val(pwaff
, mod
);
2356 /* Limit the domain of "pwaff" to those elements where the function
2359 * 2^{width-1} <= pwaff < 2^{width-1}
2361 static __isl_give isl_pw_aff
*avoid_overflow(__isl_take isl_pw_aff
*pwaff
,
2366 isl_space
*space
= isl_pw_aff_get_domain_space(pwaff
);
2367 isl_local_space
*ls
= isl_local_space_from_space(space
);
2372 ctx
= isl_pw_aff_get_ctx(pwaff
);
2373 v
= isl_val_int_from_ui(ctx
, width
- 1);
2374 v
= isl_val_2exp(v
);
2376 bound
= isl_aff_zero_on_domain(ls
);
2377 bound
= isl_aff_add_constant_val(bound
, v
);
2378 b
= isl_pw_aff_from_aff(bound
);
2380 dom
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff
), isl_pw_aff_copy(b
));
2381 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2383 b
= isl_pw_aff_neg(b
);
2384 dom
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff
), b
);
2385 pwaff
= isl_pw_aff_intersect_domain(pwaff
, dom
);
2390 /* Handle potential overflows on signed computations.
2392 * If options->signed_overflow is set to PET_OVERFLOW_AVOID,
2393 * then we adjust the domain of "pa" to avoid overflows.
2395 static __isl_give isl_pw_aff
*signed_overflow(__isl_take isl_pw_aff
*pa
,
2399 struct pet_options
*options
;
2404 ctx
= isl_pw_aff_get_ctx(pa
);
2405 options
= isl_ctx_peek_pet_options(ctx
);
2406 if (!options
|| options
->signed_overflow
== PET_OVERFLOW_AVOID
)
2407 pa
= avoid_overflow(pa
, width
);
2412 /* Extract an affine expression from some an operation.
2413 * Return NaN if we are unable to extract an affine expression.
2414 * If the result of a binary (non boolean) operation is unsigned,
2415 * then we wrap it based on the size of the type. If the result is signed,
2416 * then we ensure that no overflow occurs.
2418 * "pc" is the context in which the affine expression is created.
2420 static __isl_give isl_pw_aff
*extract_affine_from_op(__isl_keep pet_expr
*expr
,
2421 __isl_keep pet_context
*pc
)
2426 switch (pet_expr_op_get_type(expr
)) {
2429 res
= extract_affine_add_sub(expr
, pc
);
2433 res
= extract_affine_div_mod(expr
, pc
);
2436 res
= extract_affine_mul(expr
, pc
);
2439 return extract_affine_neg(expr
, pc
);
2441 return extract_affine_cond(expr
, pc
);
2451 return pet_expr_extract_affine_condition(expr
, pc
);
2453 return non_affine(pet_context_get_space(pc
));
2458 if (isl_pw_aff_involves_nan(res
)) {
2459 isl_space
*space
= isl_pw_aff_get_domain_space(res
);
2460 isl_pw_aff_free(res
);
2461 return non_affine(space
);
2464 type_size
= pet_expr_get_type_size(expr
);
2466 res
= wrap(res
, type_size
);
2468 res
= signed_overflow(res
, -type_size
);
2473 /* Extract an affine expression from some special function calls.
2474 * Return NaN if we are unable to extract an affine expression.
2475 * In particular, we handle "min", "max", "ceild", "floord",
2476 * "intMod", "intFloor" and "intCeil".
2477 * In case of the latter five, the second argument needs to be
2478 * a (positive) integer constant.
2480 * "pc" is the context in which the affine expression is created.
2482 static __isl_give isl_pw_aff
*extract_affine_from_call(
2483 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2485 isl_pw_aff
*aff1
, *aff2
;
2489 n
= pet_expr_get_n_arg(expr
);
2490 name
= pet_expr_call_get_name(expr
);
2491 if (!(n
== 2 && !strcmp(name
, "min")) &&
2492 !(n
== 2 && !strcmp(name
, "max")) &&
2493 !(n
== 2 && !strcmp(name
, "intMod")) &&
2494 !(n
== 2 && !strcmp(name
, "intFloor")) &&
2495 !(n
== 2 && !strcmp(name
, "intCeil")) &&
2496 !(n
== 2 && !strcmp(name
, "floord")) &&
2497 !(n
== 2 && !strcmp(name
, "ceild")))
2498 return non_affine(pet_context_get_space(pc
));
2500 if (!strcmp(name
, "min") || !strcmp(name
, "max")) {
2501 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2502 aff2
= pet_expr_extract_affine(expr
->args
[1], pc
);
2504 if (!strcmp(name
, "min"))
2505 aff1
= isl_pw_aff_min(aff1
, aff2
);
2507 aff1
= isl_pw_aff_max(aff1
, aff2
);
2508 } else if (!strcmp(name
, "intMod")) {
2511 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2512 return non_affine(pet_context_get_space(pc
));
2513 v
= pet_expr_int_get_val(expr
->args
[1]);
2514 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2515 aff1
= isl_pw_aff_mod_val(aff1
, v
);
2519 if (pet_expr_get_type(expr
->args
[1]) != pet_expr_int
)
2520 return non_affine(pet_context_get_space(pc
));
2521 v
= pet_expr_int_get_val(expr
->args
[1]);
2522 aff1
= pet_expr_extract_affine(expr
->args
[0], pc
);
2523 aff1
= isl_pw_aff_scale_down_val(aff1
, v
);
2524 if (!strcmp(name
, "floord") || !strcmp(name
, "intFloor"))
2525 aff1
= isl_pw_aff_floor(aff1
);
2527 aff1
= isl_pw_aff_ceil(aff1
);
2533 /* Extract an affine expression from "expr", if possible.
2534 * Otherwise return NaN.
2536 * "pc" is the context in which the affine expression is created.
2538 __isl_give isl_pw_aff
*pet_expr_extract_affine(__isl_keep pet_expr
*expr
,
2539 __isl_keep pet_context
*pc
)
2544 switch (pet_expr_get_type(expr
)) {
2545 case pet_expr_access
:
2546 return extract_affine_from_access(expr
, pc
);
2548 return extract_affine_from_int(expr
, pc
);
2550 return extract_affine_from_op(expr
, pc
);
2552 return extract_affine_from_call(expr
, pc
);
2554 case pet_expr_double
:
2555 case pet_expr_error
:
2556 return non_affine(pet_context_get_space(pc
));
2560 /* Extract an affine expressions representing the comparison "LHS op RHS"
2561 * Return NaN if we are unable to extract such an affine expression.
2563 * "pc" is the context in which the affine expression is created.
2565 * If the comparison is of the form
2569 * then the expression is constructed as the conjunction of
2574 * A similar optimization is performed for max(a,b) <= c.
2575 * We do this because that will lead to simpler representations
2576 * of the expression.
2577 * If isl is ever enhanced to explicitly deal with min and max expressions,
2578 * this optimization can be removed.
2580 __isl_give isl_pw_aff
*pet_expr_extract_comparison(enum pet_op_type op
,
2581 __isl_keep pet_expr
*lhs
, __isl_keep pet_expr
*rhs
,
2582 __isl_keep pet_context
*pc
)
2584 isl_pw_aff
*lhs_pa
, *rhs_pa
;
2586 if (op
== pet_op_gt
)
2587 return pet_expr_extract_comparison(pet_op_lt
, rhs
, lhs
, pc
);
2588 if (op
== pet_op_ge
)
2589 return pet_expr_extract_comparison(pet_op_le
, rhs
, lhs
, pc
);
2591 if (op
== pet_op_lt
|| op
== pet_op_le
) {
2592 if (pet_expr_is_min(rhs
)) {
2593 lhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2595 rhs_pa
= pet_expr_extract_comparison(op
, lhs
,
2597 return pet_and(lhs_pa
, rhs_pa
);
2599 if (pet_expr_is_max(lhs
)) {
2600 lhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[0],
2602 rhs_pa
= pet_expr_extract_comparison(op
, lhs
->args
[1],
2604 return pet_and(lhs_pa
, rhs_pa
);
2608 lhs_pa
= pet_expr_extract_affine(lhs
, pc
);
2609 rhs_pa
= pet_expr_extract_affine(rhs
, pc
);
2611 return pet_comparison(op
, lhs_pa
, rhs_pa
);
2614 /* Extract an affine expressions from the comparison "expr".
2615 * Return NaN if we are unable to extract such an affine expression.
2617 * "pc" is the context in which the affine expression is created.
2619 static __isl_give isl_pw_aff
*extract_comparison(__isl_keep pet_expr
*expr
,
2620 __isl_keep pet_context
*pc
)
2622 enum pet_op_type type
;
2626 if (expr
->n_arg
!= 2)
2627 isl_die(pet_expr_get_ctx(expr
), isl_error_invalid
,
2628 "expecting two arguments", return NULL
);
2630 type
= pet_expr_op_get_type(expr
);
2631 return pet_expr_extract_comparison(type
, expr
->args
[0], expr
->args
[1],
2635 /* Extract an affine expression representing the boolean operation
2636 * expressed by "expr".
2637 * Return NaN if we are unable to extract an affine expression.
2639 * "pc" is the context in which the affine expression is created.
2641 static __isl_give isl_pw_aff
*extract_boolean(__isl_keep pet_expr
*expr
,
2642 __isl_keep pet_context
*pc
)
2644 isl_pw_aff
*lhs
, *rhs
;
2650 n
= pet_expr_get_n_arg(expr
);
2651 lhs
= pet_expr_extract_affine_condition(expr
->args
[0], pc
);
2653 return pet_not(lhs
);
2655 rhs
= pet_expr_extract_affine_condition(expr
->args
[1], pc
);
2656 return pet_boolean(pet_expr_op_get_type(expr
), lhs
, rhs
);
2659 /* Extract the affine expression "expr != 0 ? 1 : 0".
2660 * Return NaN if we are unable to extract an affine expression.
2662 * "pc" is the context in which the affine expression is created.
2664 static __isl_give isl_pw_aff
*extract_implicit_condition(
2665 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2669 res
= pet_expr_extract_affine(expr
, pc
);
2670 return pet_to_bool(res
);
2673 /* Extract a boolean affine expression from "expr".
2674 * Return NaN if we are unable to extract an affine expression.
2676 * "pc" is the context in which the affine expression is created.
2678 * If "expr" is neither a comparison nor a boolean operation,
2679 * then we assume it is an affine expression and return the
2680 * boolean expression "expr != 0 ? 1 : 0".
2682 __isl_give isl_pw_aff
*pet_expr_extract_affine_condition(
2683 __isl_keep pet_expr
*expr
, __isl_keep pet_context
*pc
)
2688 if (pet_expr_is_comparison(expr
))
2689 return extract_comparison(expr
, pc
);
2690 if (pet_expr_is_boolean(expr
))
2691 return extract_boolean(expr
, pc
);
2693 return extract_implicit_condition(expr
, pc
);
2696 /* Return the number of bits needed to represent the type of "expr".
2697 * See the description of the type_size field of pet_expr.
2699 int pet_expr_get_type_size(__isl_keep pet_expr
*expr
)
2701 return expr
? expr
->type_size
: 0;
2704 /* Replace the number of bits needed to represent the type of "expr"
2706 * See the description of the type_size field of pet_expr.
2708 __isl_give pet_expr
*pet_expr_set_type_size(__isl_take pet_expr
*expr
,
2711 expr
= pet_expr_cow(expr
);
2715 expr
->type_size
= type_size
;
2720 void pet_expr_dump_with_indent(__isl_keep pet_expr
*expr
, int indent
)
2727 fprintf(stderr
, "%*s", indent
, "");
2729 switch (expr
->type
) {
2730 case pet_expr_double
:
2731 fprintf(stderr
, "%s\n", expr
->d
.s
);
2734 isl_val_dump(expr
->i
);
2736 case pet_expr_access
:
2737 if (expr
->acc
.ref_id
) {
2738 isl_id_dump(expr
->acc
.ref_id
);
2739 fprintf(stderr
, "%*s", indent
, "");
2741 isl_map_dump(expr
->acc
.access
);
2742 fprintf(stderr
, "%*s", indent
, "");
2743 isl_multi_pw_aff_dump(expr
->acc
.index
);
2744 fprintf(stderr
, "%*sread: %d\n", indent
+ 2,
2745 "", expr
->acc
.read
);
2746 fprintf(stderr
, "%*swrite: %d\n", indent
+ 2,
2747 "", expr
->acc
.write
);
2748 for (i
= 0; i
< expr
->n_arg
; ++i
)
2749 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2752 fprintf(stderr
, "%s\n", op_str
[expr
->op
]);
2753 for (i
= 0; i
< expr
->n_arg
; ++i
)
2754 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2757 fprintf(stderr
, "%s/%d\n", expr
->name
, expr
->n_arg
);
2758 for (i
= 0; i
< expr
->n_arg
; ++i
)
2759 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2762 fprintf(stderr
, "(%s)\n", expr
->type_name
);
2763 for (i
= 0; i
< expr
->n_arg
; ++i
)
2764 pet_expr_dump_with_indent(expr
->args
[i
], indent
+ 2);
2766 case pet_expr_error
:
2767 fprintf(stderr
, "ERROR\n");
2772 void pet_expr_dump(__isl_keep pet_expr
*expr
)
2774 pet_expr_dump_with_indent(expr
, 0);